Re: Strange performance of matdet

[Charles Greathouse <charles.greathouse@case.edu>]

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

where the heuristic could be "check entries until a non-integer,
non-real is found, using flag 2 in that case and flag 1 otherwise".
Slowdown would be very small for matrices over (multivariate)
polynomials as long as a polynomial entry occurs relatively early on.
Slowdown for integer matrices should be offset by savings.

In general I like to use 0 for "default" rather than one of the
algorithms so there's a future-proof way to refer to a particular
algorithm even if others are added later.

Charles Greathouse
Analyst/Programmer
Case Western Reserve University

On Fri, Sep 7, 2012 at 8:21 AM, Bill Allombert
<Bill.Allombert@math.u-bordeaux1.fr> wrote:
> On Fri, Sep 07, 2012 at 01:56:32PM +0200, Jernej Azarija wrote:
>> Hello!
>>
>> 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.
>
> Cheers,
> Bill.