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