Better determinant? det looks horrible

Specific Domains
,
9

Yes, but that’s not the same thing as division-free.

For example, here is an implementation of the Bird algorithm, which is truly division-free (only uses ± and ×), at the cost of worse complexity than Bareiss:

using LinearAlgebra
function birddet(A::AbstractMatrix)
    n = LinearAlgebra.checksquare(A)
    
    function μ!(M, X)
        for j = 2:n, i = 1:j-1
            M[i,j] = X[i,j]
        end
        for j = 1:n-1, i = j+1:n
            M[i,j] = zero(eltype(X))
        end
        M[n,n] = zero(eltype(X))
        for k = n-1:-1:1
            M[k,k] = M[k+1,k+1] - X[k+1,k+1]
        end
        return M
    end
    
    M = similar(A)
    X = copy(A)
    for i = 1:n-1
        mul!(X, μ!(M, X), A)
    end
    return isodd(n) ? X[1,1] : -X[1,1]
end
6 Likes