mod francis;
mod standard_block;
mod standardize;
#[cfg(test)]
mod tests;
use crate::application::linalg::scaling::{self, GateBound};
use crate::application::linalg::thresholds;
use crate::domain::real::RealScalar;
use leto::Complex;
use leto::{Array2, ArrayView2, LetoError, Result, Storage};
fn francis_bound<T: RealScalar>(n: usize) -> impl FnOnce(&[T], T) -> GateBound {
move |values, largest| GateBound {
factor_log2: 2 * scaling::norm_ratio_log2(values, largest),
floor_log2: thresholds::deflation_count_log2(n)
- scaling::norm_ratio_floor_log2(values, largest),
}
}
#[derive(Debug, Clone)]
pub struct RealSchur<T> {
q: Vec<T>,
t: Vec<T>,
n: usize,
}
pub fn schur<T: RealScalar>(matrix: &ArrayView2<'_, T>) -> Result<RealSchur<T>> {
let [rows, cols] = matrix.shape();
if rows != cols {
return Err(LetoError::ShapeMismatch {
lhs: vec![rows, cols],
rhs: vec![rows, rows],
});
}
let n = rows;
if n == 0 {
return Ok(RealSchur {
q: vec![],
t: vec![],
n: 0,
});
}
let balanced = scaling::balanced(matrix, 2, francis_bound(n))?;
let (view, exponent) = match &balanced {
Some((scaled, exponent)) => (scaled.view(), *exponent),
None => (*matrix, 0),
};
let hess = crate::hessenberg(&view)?;
let mut t: Vec<T> = hess.h().storage().as_slice().to_vec();
let mut q: Vec<T> = hess.q().storage().as_slice().to_vec();
francis::run::<T, true>(&mut t, &mut q, n)?;
standardize::standardize(&mut t, &mut q, n);
scaling::restore(
&mut t,
exponent,
"Schur form entry exceeds the scalar range",
)?;
Ok(RealSchur { q, t, n })
}
pub(crate) fn real_eigenvalues<T: RealScalar>(
matrix: &ArrayView2<'_, T>,
) -> Result<Vec<Complex<T>>> {
let [rows, cols] = matrix.shape();
if rows != cols {
return Err(LetoError::ShapeMismatch {
lhs: vec![rows, cols],
rhs: vec![rows, rows],
});
}
let n = rows;
if n == 0 {
return Ok(Vec::new());
}
let balanced = scaling::balanced(matrix, 2, francis_bound(n))?;
let (view, exponent) = match &balanced {
Some((scaled, exponent)) => (scaled.view(), *exponent),
None => (*matrix, 0),
};
let (mut h, hn) = crate::application::linalg::hessenberg::hessenberg_values(&view)?;
debug_assert_eq!(hn, n);
let mut unused: [T; 0] = [];
francis::run::<T, false>(&mut h, &mut unused, n)?;
let mut eigenvalues = eigenvalues_from_quasi_triangular(&h, n);
if exponent != 0 {
let mut parts: Vec<T> = eigenvalues.iter().flat_map(|z| [z.re, z.im]).collect();
scaling::restore(&mut parts, exponent, "eigenvalue exceeds the scalar range")?;
for (z, pair) in eigenvalues.iter_mut().zip(parts.chunks_exact(2)) {
*z = Complex::new(pair[0], pair[1]);
}
}
Ok(eigenvalues)
}
pub(crate) fn eigenvalues_from_quasi_triangular<T: RealScalar>(
t: &[T],
n: usize,
) -> Vec<Complex<T>> {
let mut eigs = Vec::with_capacity(n);
let mut i = 0usize;
while i < n {
let is_block = i + 1 < n && t[(i + 1) * n + i] != T::ZERO;
if is_block {
let (re1, im1, re2, im2) = standard_block::standardize_block(
t[i * n + i],
t[i * n + i + 1],
t[(i + 1) * n + i],
t[(i + 1) * n + i + 1],
)
.eigenvalues();
eigs.push(Complex::new(re1, im1));
eigs.push(Complex::new(re2, im2));
i += 2;
} else {
eigs.push(Complex::new(t[i * n + i], T::ZERO));
i += 1;
}
}
eigs
}
impl<T: RealScalar> RealSchur<T> {
#[must_use]
pub fn q(&self) -> Array2<T> {
Array2::from_shape_vec([self.n, self.n], self.q.clone()).expect("Q shape matches storage")
}
#[must_use]
pub fn t(&self) -> Array2<T> {
Array2::from_shape_vec([self.n, self.n], self.t.clone()).expect("T shape matches storage")
}
#[must_use]
pub fn eigenvalues(&self) -> Vec<Complex<T>> {
eigenvalues_from_quasi_triangular(&self.t, self.n)
}
}