On Dec 17, 2009, at 5:58 PM, Christian Szegedy wrote: > It is impossible to come up with any reasonable explanation for this > kind of slowdown. Even if you do extremely stupid things like > summing all permutations and simplifying the expression at the end, > you > can't get that slow.
No, but if someone tried to be clever, and messed up, you can. > Additionally, you cansee that the inverse is computed readily. If you > look at the > entries of the inverse, you can see the determinant in almost every > nonzero entry as denominator (naturally...) It is completely > implausible > that the inverse() function which essentially computes the determinant > (and a lot more) is magnitudes faster than computing the determinant > alone. > > I have not seen a ticket opened for this issue, but I would strongly > suggest > to open one (I don't have any account for the Trac, but would be > happy to > get one.) That would be great. This intrigued me, so I hunted down where it's hanging. It is trying to take a gcd in fraction field reduction. See http://sage.math.washington.edu/home/robertwb/det.sage for the hanging example. > On 12/17/09, Robert Bradshaw <rober...@math.washington.edu> wrote: >> The speed could be do to the inefficiency of fraction field >> arithmetic >> over the polynomial ring. Ideally, we should have fraction-free >> gaussian elimination. Also, easily invertable/small determinant may >> actually be worse--as it could be creating a lot of large >> intermediate >> values with non-trivial gcds that are all canceling out. >> >> It would be interesting to profile and see what exactly is taking all >> the time. >> >> >> - Robert >> >> >> On Dec 17, 2009, at 11:39 AM, Christian Szegedy wrote: >> >>> You evaluate it over ZZ[x1,...,xn] rather than GF(2)[x1,...,x4]. >>> >>> Anyways, it simply can't be *that* slow in any case: even: the >>> (theoretically ) maximum number of monoms that can be in any >>> expansion is less than a few thousands, so the upper limit >>> for a naively implemented Gaussian elimination is in the >>> order of seconds. However the matrix is even much simpler than >>> that and even the inverse is computed immediately. >>> >>> On 12/17/09, ma...@mendelu.cz <ma...@mendelu.cz> wrote: >>>> And another observation: >>>> >>>> maxima returns answer immediatelly (with a lag necessary to start >>>> maxima) >>>> m is the original matrix from x.py >>>> >>>> sage: m._maxima_().determinant().expand().sage() >>>> x0^2*x2^2*x3^2*x7^2 - 2*x0*x1*x2*x3*x4*x5*x6*x7 + >>>> x1^2*x4^2*x5^2*x6^2 >>>> >>>> >>>> Anyway, the answer is different from expected one. I do not konw >>>> which >>>> one is correct. >>>> >>>> Robert >>>> >>>> >>>> >>>> On 17 pro, 11:40, "ma...@mendelu.cz" <ma...@mendelu.cz> wrote: >>>>> perhaps problems expanding polynomials? even determinant of >>>>> submatrix >>>>> (0,0,5,5) is suprisingly slow. >>>>> >>>>> workaroud is to replace polynomials in your matrix by variables. >>>>> >>>>> var('x0 x1 x2 x3 x4 x5 x6 x7 a1 a2 a3 a4 a5 a6 a7 b1 b2 b3 b4 b5 >>>>> b6 >>>>> b7') >>>>> m=matrix([[ 0, a1, a2, a3, a4, a5, a6, a7], >>>>> [b1, 0, x0, 0, 0, 0, 0, >>>>> 0], >>>>> [b2, x0, 0, x6, 0, 0, 0, >>>>> 0], >>>>> [b3, 0, x6, 0, x3, 0, 0, >>>>> 0], >>>>> [b4, 0, 0, x3, 0, x4, 0, >>>>> 0], >>>>> [b5, 0, 0, 0, x4, 0, x2, >>>>> 0], >>>>> [b6, 0, 0, 0, 0, x2, 0, >>>>> x1], >>>>> [b7, 0, 0, 0, 0, 0, x1, >>>>> 0]]) >>>>> m >>>>> >>>>> m.det() gives answer immediatelly and you can substitute back for >>>>> a's >>>>> and b's. >>>>> >>>> >>>> >>>> -- >>>> To post to this group, send email to sage-support@googlegroups.com >>>> To unsubscribe from this group, send email to >>>> sage-support+unsubscr...@googlegroups.com >>>> For more options, visit this group at >>>> http://groups.google.com/group/sage-support >>>> URL: http://www.sagemath.org >>>> >>> >> >>> -- >> >>> To post to this group, send email to sage-support@googlegroups.com >>> To unsubscribe from this group, send email to >>> sage-support+unsubscr...@googlegroups.com >>> For more options, visit this group at >>> http://groups.google.com/group/sage-support >>> URL: http://www.sagemath.org >> >> >> -- >> >> To post to this group, send email to sage-support@googlegroups.com >> To unsubscribe from this group, send email to >> sage-support+unsubscr...@googlegroups.com >> For more options, visit this group at >> http://groups.google.com/group/sage-support >> URL: http://www.sagemath.org >> > > -- > To post to this group, send email to sage-support@googlegroups.com > To unsubscribe from this group, send email to > sage-support+unsubscr...@googlegroups.com > For more options, visit this group at > http://groups.google.com/group/sage-support > URL: http://www.sagemath.org -- To post to this group, send email to sage-support@googlegroups.com To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org
