Jernej Azarija on Sat, 08 Sep 2012 09:52:25 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: Strange performance of matdet |
As a final question - given that sometimes one knows in advance that a given matrix consist only of integer/real entries, is it advisable to pass the flag=1 or is still preferable to let the heuristic decide for itself? Best, Jernej On Fri, Sep 7, 2012 at 5:41 PM, Loïc Grenié <loic.grenie@gmail.com> wrote: > 2012/9/7 Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr>: >> * Charles Greathouse [2012-09-07 15:26]: >>> > Well, ??matdet states that using the flag 1 is preferable for such matrices. >>> > (but ?matdet states the opposite). >>> >>> If nothing else it would be good to fix ?matdet to match ??matdet. But >>> it seems like better detection would not be expensive relative to the >>> total cost. Maybe >>> >>> matdet(x,{flag}): determinant of the matrix x. If (optional) flag is >>> 2, use Gauss-Bareiss. If flag is set to 1, use classical Gaussian >>> elimination (good for real or integer entries). If the flag is 0 or >>> omitted, use a heuristic to select an appropriate algorithm. >> >> This is the current behaviour :-). I have rewritten the documentation to >> follow current code: >> >> (16:14) gp > ??matdet >> matdet(x,{flag = 0}): >> >> Determinant of the square matrix x. >> >> If flag = 0, uses an appropriate algorithm depending on the coefficients: >> >> * integer entries: method due to Dixon, Pernet and Stein. >> >> * real or p-adic entries: classical Gaussian elimination using maximal >> pivot. >> >> * intmod entries: classical Gaussian elimination using first non-zero >> pivot. >> >> * other cases: Gauss-Bareiss. >> >> If flag = 1, uses classical Gaussian elimination with appropriate pivoting >> strategy (maximal pivot for real or p-adic coefficients). This is usually worse >> than the default. >> >> >>>> This question is motivated by the following discussion on sage >>>> https://groups.google.com/forum/?hl=en-GB&fromgroups=#!topic/sage-devel/uneXpZnRs-U >>>> in which it was noted that there exist a symmetric integer 34x34 >>>> matrix such that it takes matdet ~8minutes to compute the answer >>>> while it takes less than a second to compute the determinant using the >>>> classical Gaussian elimination. >>>> >>>> The matrix in question is the following: >>> >>> Well, ??matdet states that using the flag 1 is preferable for such matrices. >>> (but ?matdet states the opposite). >>> >>> Anyway, the slowdown in Gauss-Bareiss was introduced in the commit below >>> which purpose was to handle better matrices over multivariate polynomials. >>> >>> commit 2155b84a43a0977b19c5740cb281c2baec8ed4bc >>> Author: Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr> >>> Date: Thu Apr 14 09:34:42 2011 +0000 >>> >>> develop wrt to "sparse" row/column in det >>> >>> In the 2.6 branch, we use a modular algorithm instead but only for matrices >>> at least 40x40. >> >> There was a two-pronged bug: >> >> 1) the heuristic used to evaluate the cost of det_develop() was wrong >> [ we ended up computing *a lot* of 20x20 determinants instead of a single 34x34 >> one... ] >> >> 2) matrices with integer entries should never have used this code... >> >> Both problems should be fixed in 'master'. > > Why not checking for DIXON_THRESHOLD inside ZM_det_i (*) and > adding a purely modular + CRT determinant for matrix below said > threshold (see branch loic-ZM_det) ? > > Loïc > > (*) I know: because I wrote it that way... >