use crate::application::linalg::scaling::{self, GateBound};
use crate::application::linalg::symmetric_qr::symmetric_eigen_qr;
use crate::application::linalg::thresholds::{machine_epsilon, scaled_frobenius};
use crate::domain::real::RealScalar;
use crate::domain::scalar::Scalar;
use leto::{Array2, ArrayView2, LetoError, Result};
use rotation::{diagonalize, EigenvectorWorkspace, NoEigenvectors};
mod rotation;
#[cfg(test)]
mod tests;
#[derive(Debug, Clone)]
pub struct SymmetricEigenDecomposition<T> {
pub eigenvalues: Vec<T>,
pub eigenvectors: Array2<T>,
}
#[inline]
fn default_tolerance<T: RealScalar>() -> T {
machine_epsilon::<T>()
}
fn symmetry_bound<T: RealScalar>(norm: T, n: usize) -> T {
T::from_count(n + 2).mul(machine_epsilon::<T>()).mul(norm)
}
pub fn symmetric_eigen_jacobi<T: RealScalar>(
matrix: &ArrayView2<'_, T>,
) -> Result<SymmetricEigenDecomposition<T>> {
symmetric_eigen_jacobi_with_tolerance(matrix, default_tolerance::<T>())
}
pub fn symmetric_eigenvalues_jacobi<T: RealScalar>(matrix: &ArrayView2<'_, T>) -> Result<Vec<T>> {
symmetric_eigenvalues_jacobi_with_tolerance(matrix, default_tolerance::<T>())
}
pub fn symmetric_eigenvalues_jacobi_with_tolerance<T: RealScalar>(
matrix: &ArrayView2<'_, T>,
tolerance: T,
) -> Result<Vec<T>> {
let (mut a, n) = validated_upper_mirror(matrix, tolerance)?;
let exponent = jacobi_gate_exponent(&a)?;
scaling::scale_by_power_of_two(&mut a, -exponent);
let mut target = NoEigenvectors;
diagonalize(&mut a, n, tolerance, &mut target)?;
let mut diagonal: Vec<T> = (0..n).map(|i| a[i * n + i]).collect();
scaling::restore(
&mut diagonal,
exponent,
"Jacobi eigensolver: an eigenvalue exceeds the scalar range",
)?;
for (i, value) in diagonal.into_iter().enumerate() {
a[i * n + i] = value;
}
Ok(sort_diagonal(&a, n))
}
pub(crate) fn validated_upper_mirror<T: RealScalar>(
matrix: &ArrayView2<'_, T>,
tolerance: T,
) -> Result<(Vec<T>, usize)> {
let [rows, cols] = matrix.shape();
if rows != cols {
return Err(LetoError::ShapeMismatch {
lhs: vec![rows, cols],
rhs: vec![rows, rows],
});
}
let n = rows;
let mut a = copy_row_major(matrix);
validate_symmetric_input(&a, n, tolerance)?;
mirror_upper_triangle(&mut a, n);
Ok((a, n))
}
pub(crate) fn symmetric_eigen_via_ql<T: RealScalar>(
matrix: &ArrayView2<'_, T>,
) -> Result<SymmetricEigenDecomposition<T>> {
let (storage, n) = validated_upper_mirror(matrix, default_tolerance::<T>())?;
let mirror = Array2::from_shape_vec([n, n], storage)?;
symmetric_eigen_qr(&mirror.view())
}
pub fn symmetric_eigen_jacobi_with_tolerance<T: RealScalar>(
matrix: &ArrayView2<'_, T>,
tolerance: T,
) -> Result<SymmetricEigenDecomposition<T>> {
let (mut a, n) = validated_upper_mirror(matrix, tolerance)?;
let exponent = jacobi_gate_exponent(&a)?;
scaling::scale_by_power_of_two(&mut a, -exponent);
let mut v = identity::<T>(n);
let mut target = EigenvectorWorkspace { values: &mut v };
diagonalize(&mut a, n, tolerance, &mut target)?;
let mut diagonal: Vec<T> = (0..n).map(|i| a[i * n + i]).collect();
scaling::restore(
&mut diagonal,
exponent,
"Jacobi eigensolver: an eigenvalue exceeds the scalar range",
)?;
for (i, value) in diagonal.into_iter().enumerate() {
a[i * n + i] = value;
}
let mut order: Vec<usize> = (0..n).collect();
order.sort_by(|&lhs, &rhs| {
a[lhs * n + lhs]
.partial_cmp(&a[rhs * n + rhs])
.unwrap_or(std::cmp::Ordering::Equal)
});
let mut eigenvalues = Vec::with_capacity(n);
let mut eigenvectors = vec![T::ZERO; n * n];
for (new_col, old_col) in order.into_iter().enumerate() {
eigenvalues.push(a[old_col * n + old_col]);
for row in 0..n {
eigenvectors[row * n + new_col] = v[row * n + old_col];
}
}
Ok(SymmetricEigenDecomposition {
eigenvalues,
eigenvectors: Array2::from_shape_vec([n, n], eigenvectors)
.expect("eigenvector shape matches storage"),
})
}
fn validate_symmetric_input<T: RealScalar>(a: &[T], n: usize, tolerance: T) -> Result<()> {
if !tolerance.is_finite() || tolerance < T::ZERO {
return Err(LetoError::InvalidInput(
"eigensolver tolerance must be finite and non-negative".to_string(),
));
}
if let Some(index) = a.iter().position(|value| !value.is_finite()) {
return Err(LetoError::InvalidInput(format!(
"symmetric eigensolver input has a non-finite entry at ({}, {})",
index / n,
index % n
)));
}
let bound = symmetry_bound(scaled_frobenius(a), n);
for row in 0..n {
for col in (row + 1)..n {
if a[row * n + col].sub(a[col * n + row]).abs() > bound {
return Err(LetoError::InvalidInput(format!(
"symmetric eigensolver input is not symmetric at ({row}, {col})"
)));
}
}
}
Ok(())
}
fn jacobi_gate_exponent<T: RealScalar>(a: &[T]) -> Result<i32> {
Ok(scaling::gate_exponent(a, 1, |values, largest| {
GateBound::factor(1 + scaling::norm_ratio_log2(values, largest))
})?
.unwrap_or(0))
}
fn mirror_upper_triangle<T: Scalar>(a: &mut [T], n: usize) {
for row in 0..n {
for col in (row + 1)..n {
a[col * n + row] = a[row * n + col];
}
}
}
fn copy_row_major<T: Scalar>(matrix: &ArrayView2<'_, T>) -> Vec<T> {
if let Some(slice) = matrix.as_slice() {
slice.to_vec()
} else {
matrix.to_contiguous().into_storage().into_inner()
}
}
fn identity<T: Scalar>(n: usize) -> Vec<T> {
let mut values = vec![T::ZERO; n * n];
for index in 0..n {
values[index * n + index] = T::ONE;
}
values
}
fn sort_diagonal<T: RealScalar>(a: &[T], n: usize) -> Vec<T> {
let mut eigenvalues = Vec::with_capacity(n);
for index in 0..n {
eigenvalues.push(a[index * n + index]);
}
eigenvalues.sort_by(|lhs, rhs| {
lhs.partial_cmp(rhs)
.expect("invariant: finite symmetric input yields finite diagonal")
});
eigenvalues
}