Re: Strange performance of matdet

[LoÃc Grenià <loic.grenie@gmail.com>]

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