faer calculates the eigenvalues of a nontrivial adjacency matrix as `0` and `+/- inf`

[sarah-ek]

faer calculates the eigenvalues of a nontrivial adjacency matrix as `0` and `+/- inf`

[sarah-ek]

it's not a user error. i forgot i should be detecting zeros at the head/tail of the matrix during the eigenvalue computation xP

[ariasanovsky]

Smaller bug witness ($N = 15$)

let edges = [[2, 0], [6, 4], [7, 0], [8, 4], [9, 8], [10, 0], [11, 0], [12, 4], [13, 5], [13, 11], [13, 3], [14, 1], [14, 3], [14, 4]]
// ...
let correct_lambda_1 = 2.2950716903444595;

[ariasanovsky]

Smaller bug witness ($N = 8$)

let edges = [[1, 0], [3, 0], [5, 2], [5, 0], [6, 0], [6, 4], [7, 6]]
// ...
let correct_lambda_1 = 2.2215832939527633;

[ariasanovsky]

Smaller bug witness ($N = 4$)

let edges = [[1, 0], [2, 0], [3, 0]];
// [0.0 + 0.0 * I, -inf + 0.0 * I, 0.0 + 0.0 * I, 0.0 + 0.0 * I]
// [0.0, -inf, 0.0, 0.0]

[ariasanovsky]

Smaller bug witness ($N = 3$)

let edges = [[1, 0], [0, 2]];
/*
[
[0.0, 1.0, 1.0],
[1.0, 0.0, 0.0],
[1.0, 0.0, 0.0],
]
[0.0 + 0.0 * I, -inf + 0.0 * I, 0.0 + 0.0 * I]
[0.0, -inf, 0.0]
*/

However, after permutation, the values are correct

let edges = [[1, 0], [2, 1]];
/*
[
[0.0, 1.0, 0.0],
[1.0, 0.0, 1.0],
[0.0, 1.0, 0.0],
]
[-1.414213562373094 + 0.0 * I, 5.160802341031001e-17 + 0.0 * I, 1.414213562373095 + 0.0 * I]
[-1.414213562373094, 5.160802341031001e-17, 1.414213562373095]
*/

[ariasanovsky]

Unit test

#[test]
fn path_on_three_vertices_has_correct_eigenvalues_regardless_of_permutation() {
    let all_edges = [
        [(1, 0), (2, 0)],
        [(2, 1), (1, 0)],
        [(2, 1), (2, 0)],
    ];
    let correct_eigenvalues = [2.0f64.sqrt(), 0., -2.0f64.sqrt()];
    for edges in all_edges {
        let mut a = faer::Mat::zeros(3, 3);
        for (v, u) in edges.iter() {
            a[(*v, *u)] = 1.0;
            a[(*u, *v)] = 1.0;
        }
        let eigs_complex: Vec<faer::complex_native::c64> = a.eigenvalues();
        let mut eigs_real = eigs_complex
            .iter()
            .map(|e| e.re)
            .collect::<Vec<_>>();
        eigs_real.sort_by(|a, b| b.partial_cmp(a).unwrap());
        let error = correct_eigenvalues.iter().zip(eigs_real.iter()).map(|(a, b)| (a - b).powi(2)).sum::<f64>();
        assert!(
            error < 1e-10,
            "error = {error}\nedges = {edges:?}\na = {a:?}\neigs = {eigs_complex:?}\neigs = {eigs_real:?}",
        );
    }
}

[ariasanovsky]

Patching with

const ZERO: f64 = 0.0000001;
let mut a = Mat::from_fn(N, N, |_, _| ZERO);

solve my problem.

If this is user error, feel free to close.

[sarah-ek]

fixed in 0.15.0
thanks a bunch!