Re: Strange performance of matdet

[Jernej Azarija <stdazi@gmail.com>]

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