#![cfg_attr(test, allow(clippy::unwrap_used, reason = "test scope"))]
use super::{validate_input, SvdDecomposition};
use crate::application::linalg::scaling::{self, GateBound};
use crate::application::linalg::thresholds;
use crate::domain::real::RealScalar;
use leto::{Array2, ArrayView2, Result, Storage};
use rotation::TransposedFactors;
use sweep::qr_iterate;
mod chase;
mod deflation;
#[cfg(test)]
mod graded;
mod rotation;
mod sweep;
#[cfg(test)]
mod tests;
mod zero_shift;
fn svd_bound<T: RealScalar>(rows: usize, cols: usize) -> impl FnOnce(&[T], T) -> GateBound {
move |values, largest| {
let half_log2_m = (thresholds::ceil_log2_count(rows.max(cols)) + 1) / 2;
GateBound {
factor_log2: 2 + half_log2_m + scaling::norm_ratio_log2(values, largest),
floor_log2: thresholds::deflation_count_log2(rows.min(cols))
- scaling::norm_ratio_floor_log2(values, largest),
}
}
}
pub fn singular_values<T: RealScalar>(matrix: &ArrayView2<'_, T>) -> Result<Vec<T>> {
validate_input(matrix)?;
let [rows, cols] = matrix.shape();
if let Some((scaled, exponent)) = scaling::balanced(matrix, 2, svd_bound(rows, cols))? {
let mut sigmas = singular_values_of_balanced(&scaled.view())?;
scaling::restore(
&mut sigmas,
exponent,
"singular value exceeds the scalar range",
)?;
return Ok(sigmas);
}
singular_values_of_balanced(matrix)
}
fn singular_values_of_balanced<T: RealScalar>(matrix: &ArrayView2<'_, T>) -> Result<Vec<T>> {
let [rows, cols] = matrix.shape();
let (mut d, mut e) = if rows >= cols {
crate::application::linalg::bidiagonal::bidiagonal_diag_colmajor(matrix)?
} else {
let transposed = transpose_to_owned(matrix)?;
crate::application::linalg::bidiagonal::bidiagonal_diag_colmajor(&transposed.view())?
};
let k = rows.min(cols);
let counts = qr_iterate::<T, false>(&mut d, &mut e, k, &mut TransposedFactors::none())?;
crate::application::linalg::transformation_counts::record_dbdsqr_counts(
counts.sweeps,
counts.chases,
);
let mut sigmas: Vec<T> = d.into_iter().map(|x| x.abs()).collect();
sigmas.sort_by(|a, b| {
b.partial_cmp(a)
.expect("singular values are finite (not NaN)")
});
Ok(sigmas)
}
fn transpose_to_owned<T: RealScalar>(matrix: &ArrayView2<'_, T>) -> Result<Array2<T>> {
let [rows, cols] = matrix.shape();
let mut values = vec![T::ZERO; rows * cols];
if let Some(slice) = matrix.as_slice() {
for i in 0..rows {
let row = &slice[i * cols..i * cols + cols];
for (j, &val) in row.iter().enumerate() {
values[j * rows + i] = val;
}
}
} else {
for i in 0..rows {
for j in 0..cols {
values[j * rows + i] = *matrix.get([i, j])?;
}
}
}
Array2::from_shape_vec([cols, rows], values)
}
fn transpose_square<T: RealScalar>(src: &[T], n: usize) -> Vec<T> {
let mut out = vec![T::ZERO; n * n];
for i in 0..n {
for j in 0..n {
out[j * n + i] = src[i * n + j];
}
}
out
}
fn svd_tall<T: RealScalar>(matrix: &ArrayView2<'_, T>) -> Result<(Array2<T>, Vec<T>, Array2<T>)> {
let [m, n] = matrix.shape();
debug_assert!(m >= n, "svd_tall requires m >= n");
let bidiag = crate::bidiagonalize(matrix)?;
let mut ut = transpose_square(bidiag.u().storage().as_slice(), m);
let mut vt = transpose_square(bidiag.v().storage().as_slice(), n);
let b = bidiag.b();
let b_slice = b.storage().as_slice();
let cols = b.shape()[1];
let mut d = vec![T::ZERO; n];
let mut e = vec![T::ZERO; n];
for i in 0..n {
d[i] = b_slice[i * cols + i];
if i + 1 < n {
e[i] = b_slice[i * cols + i + 1];
}
}
let counts = qr_iterate::<T, true>(
&mut d,
&mut e,
n,
&mut TransposedFactors::new(&mut ut, m, &mut vt, n),
)?;
crate::application::linalg::transformation_counts::record_dbdsqr_counts(
counts.sweeps,
counts.chases,
);
for i in 0..n {
if d[i] < T::ZERO {
d[i] = d[i].neg();
for slot in &mut ut[i * m..i * m + m] {
*slot = slot.neg();
}
}
}
let mut perm: Vec<usize> = (0..n).collect();
perm.sort_by(|&a, &b| d[b].partial_cmp(&d[a]).expect("singular values are finite"));
let mut sigma = vec![T::ZERO; n];
let mut u_thin = vec![T::ZERO; m * n]; let mut v_thin = vec![T::ZERO; n * n]; for (new_col, &old) in perm.iter().enumerate() {
sigma[new_col] = d[old];
for r in 0..m {
u_thin[r * n + new_col] = ut[old * m + r];
}
for r in 0..n {
v_thin[r * n + new_col] = vt[old * n + r];
}
}
Ok((
Array2::from_shape_vec([m, n], u_thin).expect("U shape matches storage"),
sigma,
Array2::from_shape_vec([n, n], v_thin).expect("V shape matches storage"),
))
}
pub fn svd_decompose<T: RealScalar>(matrix: &ArrayView2<'_, T>) -> Result<SvdDecomposition<T>> {
validate_input(matrix)?;
let [rows, cols] = matrix.shape();
if let Some((scaled, exponent)) = scaling::balanced(matrix, 2, svd_bound(rows, cols))? {
let mut decomposition = svd_of_balanced(&scaled.view())?;
scaling::restore(
&mut decomposition.singular_values,
exponent,
"singular value exceeds the scalar range",
)?;
return Ok(decomposition);
}
svd_of_balanced(matrix)
}
fn svd_of_balanced<T: RealScalar>(matrix: &ArrayView2<'_, T>) -> Result<SvdDecomposition<T>> {
let [m, n] = matrix.shape();
if m >= n {
let (u, sigma, v) = svd_tall(matrix)?;
Ok(SvdDecomposition {
singular_values: sigma,
left_singular_vectors: u,
right_singular_vectors: v,
})
} else {
let transposed = transpose_to_owned(matrix)?;
let (u_t, sigma, v_t) = svd_tall(&transposed.view())?;
Ok(SvdDecomposition {
singular_values: sigma,
left_singular_vectors: v_t,
right_singular_vectors: u_t,
})
}
}