Charles Greathouse on Fri, 07 Sep 2012 15:26:29 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: Strange performance of matdet |
> 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.