Matrix determinant calculation is too aggressive with simplification

[asmeurer]

You can see here that the bareis determinant method calls cancel in order to cancel out fractions. But if the matrix in question has large expressions, this does too much, and can slow things down.

See for instance https://stackoverflow.com/questions/37026935/speeding-up-computation-of-symbolic-determinant-in-sympy, where it was faster to compute the general formula for the determinant and substitute values in than to compute M.det() directly.

[krishnacharya]

@asmeurer I was thinking of implementing the change in the det_bareis, by always calculating the general formula for the n*n Matrix for n>=4 then substituting the specific values of A00 A01 A02 A03.. , should i proceed in this direction

[baoqchau]

Hello @asmeurer. I want to fix this. Do you have any suggestion how to do it?

[asmeurer]

It would need to do that conditionally. For a large sparse matrix, for instance, that would be much slower.

[siefkenj]

For matrices with numbers, it seems that up to 4x4, it's faster to use the general formula, and after that, Bareiss is faster.

[asmeurer]

Same issue occurs for computing inverses of general symbolic matrices.

[oscarbenjamin]

Are you sure it's the same issue or is it perhaps a newer issue (#19920)?

[asmeurer]

Ah, I was trying to find an issue for inverses specifically. I suspect they both have similar causes, since in each case computing the general formula without trying to simplify it is better for a fully symbolic matrix.

[oscarbenjamin]

Yes, but #19920 is a newer issue caused by the changes in 1.6. Many of those changes were reverted but that one remains (I'll push the milestone to 1.7 but it's a release blocker)

[oscarbenjamin]

Also note that there is a new (not public yet) matrix implementation in sympy/polys/domainmatrix which is much faster for many things e.g.:

In [130]: M = Matrix([symbols('x:9')]).reshape(3, 3)                                                                                           

In [131]: %time ok=M.inv()                                                                                                                     
CPU times: user 1.21 s, sys: 7.04 ms, total: 1.22 s
Wall time: 1.23 s

In [132]: from sympy.polys.domainmatrix import DomainMatrix                                                                                    

In [133]: M2 = DomainMatrix.from_list_sympy(3, 3, M.tolist()).to_field()                                                                       

In [134]: %time ok=M2.inv()                                                                                                                    
CPU times: user 78.1 ms, sys: 569 µs, total: 78.7 ms
Wall time: 79.3 ms

[asmeurer]

I don't know how practical this is, but there has been some recent work on representing the general determinant formula with fewer than n! terms https://cp4space.hatsya.com/2022/07/02/a-combinatorial-proof-of-houstons-identity/