use super::{ql, reduce};
use crate::application::linalg::scaling::{self, GateBound};
use crate::application::linalg::SymmetricEigenDecomposition;
use crate::domain::real::RealScalar;
use leto::{Array2, ArrayView2, LetoError, Result};
#[derive(Debug, Clone)]
pub struct SymmetricEigenWorkspace<T> {
order: usize,
reduced: Vec<T>,
vectors: Vec<T>,
values: Vec<T>,
off_diagonal: Vec<T>,
reflector_scales: Vec<T>,
scratch: Vec<T>,
}
impl<T> Default for SymmetricEigenWorkspace<T> {
fn default() -> Self {
Self::new()
}
}
impl<T> SymmetricEigenWorkspace<T> {
#[must_use]
pub const fn new() -> Self {
Self {
order: 0,
reduced: Vec::new(),
vectors: Vec::new(),
values: Vec::new(),
off_diagonal: Vec::new(),
reflector_scales: Vec::new(),
scratch: Vec::new(),
}
}
#[must_use]
pub fn order(&self) -> usize {
self.order
}
#[must_use]
pub fn eigenvalues(&self) -> &[T] {
&self.values[..self.order]
}
pub fn eigenvectors(&self) -> std::slice::ChunksExact<'_, T> {
let n = self.order;
self.vectors[..n * n].chunks_exact(n.max(1))
}
}
impl<T: RealScalar> SymmetricEigenWorkspace<T> {
pub fn decompose(&mut self, matrix: &ArrayView2<'_, T>) -> Result<()> {
let [rows, _] = matrix.shape();
self.decompose_within(matrix, ql::sweep_budget(rows))
}
fn decompose_within(&mut self, matrix: &ArrayView2<'_, T>, budget: usize) -> Result<()> {
self.order = 0;
let [rows, cols] = matrix.shape();
if rows != cols {
return Err(LetoError::ShapeMismatch {
lhs: vec![rows, cols],
rhs: vec![rows, rows],
});
}
let n = rows;
self.load_lower_triangle(matrix, n)?;
let exponent = scaling::gate_exponent(&self.reduced, 2, |values, largest| {
GateBound::factor(2 * scaling::norm_ratio_log2(values, largest))
})?
.unwrap_or(0);
scaling::scale_by_power_of_two(&mut self.reduced, -exponent);
self.values.resize(n, T::ZERO);
self.off_diagonal.resize(n, T::ZERO);
self.reflector_scales.resize(n, T::ZERO);
self.vectors.resize(n * n, T::ZERO);
reduce::tridiagonalize(
&mut self.reduced,
n,
&mut self.values,
&mut self.off_diagonal,
&mut self.reflector_scales,
&mut self.scratch,
);
reduce::accumulate_transposed_factor(
&self.reduced,
n,
&self.reflector_scales,
&mut self.vectors,
);
ql::diagonalize(
&mut self.values,
&mut self.off_diagonal,
&mut self.vectors,
n,
budget,
)?;
scaling::restore(
&mut self.values,
exponent,
"symmetric eigensolver: an eigenvalue exceeds the scalar range",
)?;
self.order = n;
Ok(())
}
fn load_lower_triangle(&mut self, matrix: &ArrayView2<'_, T>, n: usize) -> Result<()> {
self.reduced.clear();
if let Some(slice) = matrix.as_slice() {
self.reduced.extend_from_slice(slice);
} else {
self.reduced.extend(matrix.iter().copied());
}
for i in 0..n {
for j in 0..=i {
let value = self.reduced[i * n + j];
if !value.is_finite() {
return Err(LetoError::InvalidInput(format!(
"symmetric eigensolver input has a non-finite entry at ({i}, {j})"
)));
}
self.reduced[j * n + i] = value;
}
}
Ok(())
}
}
pub fn symmetric_eigen_qr<T: RealScalar>(
matrix: &ArrayView2<'_, T>,
) -> Result<SymmetricEigenDecomposition<T>> {
let mut workspace = SymmetricEigenWorkspace::new();
workspace.decompose(matrix)?;
let n = workspace.order();
let mut columns = vec![T::ZERO; n * n];
for (k, vector) in workspace.eigenvectors().enumerate() {
for (row, &value) in vector.iter().enumerate() {
columns[row * n + k] = value;
}
}
Ok(SymmetricEigenDecomposition {
eigenvalues: workspace.values,
eigenvectors: Array2::from_shape_vec([n, n], columns)?,
})
}
#[cfg(test)]
mod tests {
use super::SymmetricEigenWorkspace;
use leto::{Array2, LetoError};
#[test]
fn exhausted_sweep_budget_is_a_typed_convergence_error() {
let matrix = Array2::from_shape_vec(
[3, 3],
vec![2.0_f64, 1.0, 1.0, 1.0, 2.0, 1.0, 1.0, 1.0, 2.0],
)
.expect("invariant: nine entries");
let mut workspace = SymmetricEigenWorkspace::new();
let result = workspace.decompose_within(&matrix.view(), 0);
let Err(LetoError::ConvergenceError {
max_iters,
residual,
tol,
}) = result
else {
panic!("expected ConvergenceError, got {result:?}");
};
assert_eq!(max_iters, 0);
assert_eq!(tol, f64::EPSILON / 2.0);
let off_diagonal_0 = 2.0_f64.sqrt();
let norm_estimate = 2.0_f64.abs() + off_diagonal_0.abs();
let expected_residual = off_diagonal_0.abs() / norm_estimate;
assert_eq!(residual, expected_residual);
assert!(residual > tol && residual <= 1.0, "{residual}");
assert_eq!(workspace.order(), 0);
assert!(workspace.eigenvalues().is_empty());
}
}