I have some large (n~100) square matrices with entries two variable polynomials of bounded degree (roughly <20, but many entries are smaller) and integer coefficients, and I'd like to be able to compute their determinants (exactly, as two variable polynomials with integer coefficients).
What method should I use? Is there an efficient software implementation already?
In smaller instances of the problem, I've just been using Mathematica
's builtin Det
function and hoping for the best, but I suspect it's just doing row reduction with two variable rational functions, which quickly becomes inefficient.
I've also tried (thanks Emily!) substituting integer values, calculating the determinant using row reduction with (much faster) arbitrary precision rational arithmetic, and then Newton interpolation. Sadly my implementation seems even slower than Mathematica
.
At this point I'm happy with 'good guesses', where if I check a few new values and consistently get the right answers I'm satisfied --- if proving the answer is really correct is much slower that's okay.
Finally, in case this suggests a good trick, there appears to some structure to the answers for my problem instances: the determinant factors, with a large fraction of the total degree coming from high powers of a few low degree polynomials, and then a handful of large factors without multiplicity. I can even predict some of the small factors and (approximately) their multiplicity.