Re: Strange performance of matdet

[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'.

    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]
`