Karim Belabas on Fri, 07 Sep 2012 16:22:50 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: Strange performance of matdet |
* 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'. K.B. -- Karim Belabas, IMB (UMR 5251) Tel: (+33) (0)5 40 00 26 17 Universite Bordeaux 1 Fax: (+33) (0)5 40 00 69 50 351, cours de la Liberation http://www.math.u-bordeaux1.fr/~belabas/ F-33405 Talence (France) http://pari.math.u-bordeaux1.fr/ [PARI/GP] `