Slug #675
Matrix determinant over multivariate poly ring
Description
CoCoA can be too slow and require too much RAM for computing determinant of a matrix of multivariate polynomials.
In my case M := MakeMatByRows(8,8, [x[i] | i in 1..64]);
Related issues
History
#1 Updated by John Abbott over 9 years ago
In my specific instance the direct algorithm (as alternating sum of products) would be best.
The problem with multivariate polynomials is the GCDs (needed when computing in the fraction field) which are currently computed slowly using G-bases.
#2 Updated by Anna Maria Bigatti about 9 years ago
in the cocoa manual there is this example
/**/ discriminant((x+1)^20+2);
which is far too slow with the direct algorithm.
So I removed "|| (IsPolyRing(myR) && NumIndets(myR) > 1))" in
void DenseMatImpl::myDet(RingElem& d) const
and it goes very fast. What should we do?
#3 Updated by John Abbott about 9 years ago
- Status changed from New to In Progress
- % Done changed from 0 to 10
I have changed myDet
in DenseMatrix.C
so that it calls DetDirect
only if there are at least 3 indets and the matrix is small (max 9x9) and the entries are all monomials.
This means it runs "fast" for the cases I need for Bettina, and should still be fast in other cases.
Not an ideal solution, but a tolerable hack for the time being.
#4 Updated by John Abbott about 9 years ago
A Google search for "division free algorithm for determinant" produces several hits. Possibly something there may be useful for computing determinants of multivariate polynomials. I vaguely recall having seen the abstract of a paper which claimed to have a clever way of computing determinants using the n! summation by coalescing products (but recall no details now).