const MAX_QL_ITERATIONS: u32 = 200;
const UNDERFLOW_GUARD: f64 = 1e-300;
#[must_use]
pub fn tridiagonal_ql(diagonal: &[f64], sub_diagonal: &[f64]) -> (Vec<f64>, Vec<f64>) {
let n = diagonal.len();
if n == 0 {
return (vec![], vec![]);
}
if n == 1 {
return (diagonal.to_vec(), vec![1.0]);
}
let mut d = diagonal.to_vec();
let mut e = vec![0.0_f64; n];
for (i, &val) in sub_diagonal.iter().enumerate().take(n - 1) {
e[i + 1] = val;
}
let mut z = vec![0.0_f64; n * n];
for i in 0..n {
z[i * n + i] = 1.0;
}
ql_implicit_shifts(&mut d, &mut e, &mut z, n);
(d, z)
}
#[must_use]
pub fn anderson_diagonalize(disorder: &[f64], t_hop: f64) -> (Vec<f64>, Vec<f64>) {
let n = disorder.len();
if n == 0 {
return (vec![], vec![]);
}
let sub_diag = vec![t_hop; n.saturating_sub(1)];
tridiagonal_ql(disorder, &sub_diag)
}
fn ql_implicit_shifts(d: &mut [f64], e: &mut [f64], z: &mut [f64], n: usize) {
for i in 1..n {
e[i - 1] = e[i];
}
e[n - 1] = 0.0;
for l in 0..n {
let mut iter_count = 0_u32;
loop {
let mut m = l;
while m < n - 1 {
let dd = d[m].abs() + d[m + 1].abs();
#[expect(
clippy::float_cmp,
reason = "standard QL convergence: e[m] is negligible when adding it to dd doesn't change dd at f64 precision"
)]
if (e[m].abs() + dd) == dd {
break;
}
m += 1;
}
if m == l {
break;
}
iter_count += 1;
if iter_count > MAX_QL_ITERATIONS {
break;
}
let mut g = (d[l + 1] - d[l]) / (2.0 * e[l]);
let mut r = g.hypot(1.0);
g = d[m] - d[l] + e[l] / (g + r.copysign(g));
let mut s = 1.0;
let mut c = 1.0;
let mut p = 0.0;
for i in (l..m).rev() {
let mut f = s * e[i];
let b = c * e[i];
r = f.hypot(g);
e[i + 1] = r;
if r.abs() < UNDERFLOW_GUARD {
d[i + 1] -= p;
e[m] = 0.0;
break;
}
s = f / r;
c = g / r;
g = d[i + 1] - p;
r = (d[i] - g).mul_add(s, 2.0 * c * b);
p = s * r;
d[i + 1] = g + p;
g = c.mul_add(r, -b);
for k in 0..n {
f = z[(i + 1) * n + k];
z[(i + 1) * n + k] = s.mul_add(z[i * n + k], c * f);
z[i * n + k] = c.mul_add(z[i * n + k], -(s * f));
}
}
d[l] -= p;
e[l] = g;
e[m] = 0.0;
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn empty_input() {
let (vals, vecs) = tridiagonal_ql(&[], &[]);
assert!(vals.is_empty());
assert!(vecs.is_empty());
}
#[test]
fn single_element() {
let (vals, vecs) = tridiagonal_ql(&[3.0], &[]);
assert_eq!(vals.len(), 1);
assert!((vals[0] - 3.0).abs() < 1e-14);
assert!((vecs[0] - 1.0).abs() < 1e-14);
}
#[test]
fn two_by_two() {
let (vals, vecs) = tridiagonal_ql(&[2.0, 2.0], &[1.0]);
let mut sorted = vals;
sorted.sort_by(|a, b| a.partial_cmp(b).unwrap());
assert!((sorted[0] - 1.0).abs() < 1e-12, "got {}", sorted[0]);
assert!((sorted[1] - 3.0).abs() < 1e-12, "got {}", sorted[1]);
let n = 2;
for i in 0..n {
let norm_sq: f64 = (0..n).map(|k| vecs[i * n + k].powi(2)).sum();
assert!(
(norm_sq - 1.0).abs() < 1e-12,
"eigenvector {i} not normalized: {norm_sq}"
);
}
}
#[test]
fn anderson_3_site() {
let disorder = [0.5, -0.3, 0.1];
let t_hop = 1.0;
let (vals, vecs) = anderson_diagonalize(&disorder, t_hop);
assert_eq!(vals.len(), 3);
assert_eq!(vecs.len(), 9);
let trace: f64 = vals.iter().sum();
assert!(
(trace - 0.3).abs() < 1e-10,
"trace mismatch: {trace} vs 0.3"
);
for i in 0..3 {
let norm_sq: f64 = (0..3).map(|k| vecs[i * 3 + k].powi(2)).sum();
assert!(
(norm_sq - 1.0).abs() < 1e-10,
"eigenvector {i} not normalized: {norm_sq}"
);
}
}
#[test]
fn diagonal_matrix() {
let diag = [5.0, 2.0, 8.0, 1.0];
let sub_diag = [0.0, 0.0, 0.0];
let (vals, _) = tridiagonal_ql(&diag, &sub_diag);
let mut sorted = vals;
sorted.sort_by(|a, b| a.partial_cmp(b).unwrap());
let mut expected = diag.to_vec();
expected.sort_by(|a, b| a.partial_cmp(b).unwrap());
for (v, e) in sorted.iter().zip(expected.iter()) {
assert!((v - e).abs() < 1e-12, "eigenvalue {v} != {e}");
}
}
#[test]
fn eigenvectors_orthogonal() {
let disorder: Vec<f64> = (0..10).map(|i| (i as f64 * 0.7).sin()).collect();
let (_, vecs) = anderson_diagonalize(&disorder, 1.0);
let n = 10;
for i in 0..n {
for j in (i + 1)..n {
let dot: f64 = (0..n).map(|k| vecs[i * n + k] * vecs[j * n + k]).sum();
assert!(
dot.abs() < 1e-10,
"eigenvectors {i} and {j} not orthogonal: dot={dot}"
);
}
}
}
}