smith-test.js

function display_homology(dimension_face_names, boundary) {
    let result = homology_from_names(dimension_face_names, boundary);
    result.forEach(([dim, {free_generators, torsion_generators}]) => {
        let head = `H_${dim}:`;
        function print(s) {
            console.log(head + " ".repeat(8 - head.length) + s);
            head = "";
        }
        if (free_generators.length == 0 && torsion_generators.length == 0) {
            print("trivial");
        }
        free_generators.forEach((freegen) => {
            print(`a copy of Z generated by ${coeffs_to_string(freegen)}`);
        });
        torsion_generators.forEach(([torgen, order]) => {
            print(`a copy of Z/${order.toString()}Z generated by ${coeffs_to_string(torgen)}`);
        });
    });
}

function randrange(a, b) {
    return BigInt(a + Math.floor(Math.random() * (b - a)));
}

for (let i = 0; i < 20; i++) {
    let a = randrange(-1000, 1000);
    let b = randrange(-1000, 1000);
    let [x, y, g] = xgcd(a, b);
    console.assert(x*a + y*b == g, [[a, b], [x, y, g]]);
    {
        // compute in the standard way.
        let a1 = Math.abs(Number(a));
        let b1 = Math.abs(Number(b));
        while (b1) {
            let t = b1;
            b1 = a1 % b1;
            a1 = t;
        }
        console.assert(a1 == g, [[a, b], [x, y, g], a1]);
    }
}

function matrix_multiply(A, A_num_cols, B, B_num_cols) {
    A.forEach((row) => {
        console.assert(row.length == A_num_cols);
    })
    B.forEach((row) => {
        console.assert(row.length == B_num_cols);
    })
    console.assert(A_num_cols == B.length);
    let result = [];
    A.forEach((row) => {result.push([])});
    for (let i = 0; i < A.length; i++) {
        for (let j = 0; j < B_num_cols; j++) {
            let s = 0n;
            for (let k=0; k < A_num_cols; k++) {
                s += A[i][k]*B[k][j];
            }
            result[i][j] = s;
        }
    }
    return result;
}

function assert_equal(a, b, num_cols, data) {
    console.assert(a.length == b.length, a, b);
    for (let i = 0; i < a.length; i++) {
        console.assert(a[i].length == num_cols);
        console.assert(b[i].length == num_cols);
        for (let j = 0; j < num_cols; j++) {
            console.assert(a[i][j] == b[i][j], [a, b], data);
        }
    }
}

for (let loop = 0; loop < 5; loop++) {
    for (let m = 0; m < 6; m++) {
        for (let n = 0; n < 6; n++) {
            let A = [];
            for (let i = 0; i < m; i++) {
                A[i] = [];
                for (let j = 0; j < n; j++) {
                    // A[i][j] = randrange(-1e50, 1e50);
                    A[i][j] = randrange(-5, 5);
                }
            }
            let result = smithify(A, n);
            let {D, S, Sinv, T, Tinv} = result;
            let info = {A:A, result:result};

            // Assert the D is diagonal
            for (let i = 0; i < D.length; i++) {
                for (let j = 0; j < D[i].length; j++) {
                    if (i != j) {
                        console.assert(D[i][j] == 0n, info);
                    }
                }
            }

            // Assert that D has the right divisibility
            for (let i = 1; i < m && i < n; i++) {
                let d1 = D[i-1][i-1];
                let d2 = D[i][i];
                if (d1 == 0) {
                    console.assert(d2 == 0);
                }
                else {
                    console.assert(d2 % d1 == 0, info);
                }
            }

            // Assert that SAT == D
            result.S.length
            let SA = matrix_multiply(S, m, A, n);
            let SA_T = matrix_multiply(SA, n, T, n);
            assert_equal(SA_T, D, n, info);
            let AT = matrix_multiply(A, n, T, n);
            let S_AT = matrix_multiply(S, m, AT, n);
            assert_equal(S_AT, D, n, info);

            // Assert that (Sinv)*D*(Tinv) == A
            let SinvD = matrix_multiply(Sinv, m, D, n);
            let SinvD_Tinv = matrix_multiply(SinvD, n, Tinv, n);
            assert_equal(SinvD_Tinv, A, n, info);
            let DTinv = matrix_multiply(D, n, Tinv, n);
            let Sinv_DTinv = matrix_multiply(Sinv, m, DTinv, n);
            assert_equal(Sinv_DTinv, A, n);

            // Assert that inverses are computed correctly
            let id_m = [];
            for (let i = 0; i < m; i++) {
                id_m[i] = [];
                for (let j = 0; j < m; j++) {
                    id_m[i][j] = (i == j) ? 1n : 0n;
                }
            }
            let SinvS = matrix_multiply(Sinv, m, S, m)
            assert_equal(SinvS, id_m, m)
            let SSinv = matrix_multiply(Sinv, m, S, m)
            assert_equal(SSinv, id_m, m)

            let id_n = [];
            for (let i = 0; i < n; i++) {
                id_n[i] = [];
                for (let j = 0; j < n; j++) {
                    id_n[i][j] = (i == j) ? 1n : 0n;
                }
            }
            let TinvT = matrix_multiply(Tinv, n, T, n)
            assert_equal(TinvT, id_n, n);
            let TTinv = matrix_multiply(T, n, Tinv, n)
            assert_equal(TTinv, id_n, n);
        }
    }
}


console.log("===== Homology of a circle: =====");
display_homology(
    new Map([
        [0, ["v"]],
        [1, ["e"]],
    ]),
    new Map([
        ["v", []],
        ["e", []],
    ])
);

console.log("===== Homology of RP^2: =====");
display_homology(
    new Map([
        [0, ["v"]],
        [1, ["e"]],
        [2, ["f"]],
    ]),
    new Map([
        ["v", []],
        ["e", []],
        ["f", [[2, "e"],]],
    ])
);


console.log("===== Reduced homology of a circle: =====");
display_homology(
    new Map([
        [-1, ["."]],
        [0, ["v"]],
        [1, ["e"]],
    ]),
    new Map([
        ["v", [[+1, "."],]],
    ]),
);


console.log("===== Reduced Nerve of Z/3Z =====");
display_homology(
    new Map([
        [-1, ["."]],
        [0, ["*"]],
        [1, ["a", "b"]],
        [2, ["aa", "ab", "ba", "bb"]],
        [3, ["aaa", "aab", "aba", "abb", "baa", "bab", "bba", "bbb"]],
        [4, ["aaaa", "aaab", "aaba", "aabb", "abaa", "abab", "abba", "abbb",
             "baaa", "baab", "baba", "babb", "bbaa", "bbab", "bbba", "bbbb",]],
    ]),
    new Map([
        ["*", [[1, "."]]],
        ["a", []],
        ["b", []],
        ["aa", [[1,"a"], [-1, "b"], [1, "a"]]],
        ["ab", [[1,"b"], [1, "a"]]],
        ["ba", [[1,"a"], [1, "b"]]],
        ["bb", [[1,"b"], [-1, "a"], [1, "b"]]],
        ["aaa", [[1,"aa"],[-1,"ba"],[1,"ab"],[-1,"aa"]]],
        ["aab", [[1,"ab"],[-1,"bb"],[-1,"aa"]]],
        ["aba", [[1,"ba"],[-1,"ab"]]],
        ["abb", [[1,"bb"],[1,"aa"],[-1,"ab"]]],
        ["baa", [[1,"aa"],[1,"bb"],[-1,"ba"]]],
        ["bab", [[1,"ab"],[-1,"ba"]]],
        ["bba", [[1,"ba"],[-1,"aa"],[-1,"bb"]]],
        ["bbb", [[1,"bb"],[-1,"ab"],[1,"ba"],[-1,"bb"]]],
        ["aaaa", [[1,"aaa"],[-1,"baa"],[1,"aba"],[-1,"aab"],[1,"aaa"]]],
        ["aaab", [[1,"aab"],[-1,"bab"],[1,"abb"],[1,"aaa"]]],
        ["aaba", [[1,"aba"],[-1,"bba"],[1,"aab"]]],
        ["aabb", [[1,"abb"],[-1,"bbb"],[-1,"aaa"],[1,"aab"]]],
        ["abaa", [[1,"baa"],[-1,"abb"],[1,"aba"]]],
        ["abab", [[1,"bab"],[1,"aba"]]],
        ["abba", [[1,"bba"],[1,"aaa"],[1,"abb"]]],
        ["abbb", [[1,"bbb"],[1,"aab"],[-1,"aba"],[1,"abb"]]],
        ["baaa", [[1,"aaa"],[1,"bba"],[-1,"bab"],[1,"baa"]]],
        ["baab", [[1,"aab"],[1,"bbb"],[1,"baa"]]],
        ["baba", [[1,"aba"],[1,"bab"]]],
        ["babb", [[1,"abb"],[-1,"baa"],[1,"bab"]]],
        ["bbaa", [[1,"baa"],[-1,"aaa"],[-1,"bbb"],[1,"bba"]]],
        ["bbab", [[1,"bab"],[-1,"aab"],[1,"bba"]]],
        ["bbba", [[1,"bba"],[-1,"aba"],[1,"baa"],[1,"bbb"]]],
        ["bbbb", [[1,"bbb"],[-1,"abb"],[1,"bab"],[-1,"bba"],[1,"bbb"]]],
    ]),
);

console.log("done with tests.");