Fwd: sage bug report
William Stein
From: Christian Szegedy <christia...@gmail.com>
Date: Thu, Dec 17, 2009 at 12:26 AM
Subject: sage bug report
To: William Stein <wst...@gmail.com>
Simple 8X8 matrix determinant computation makes sage hang:
load x.py
test()
On the other hand if m.det() is replaced m.inverse(), it runs through
in no time.
The determinant of the matrix is a sum of two monomials:
x1*x4*x5*x6 + x0*x2*x3*x7, but even the most primitive implementation
(summing all 8! permutations,most of them zero) should run through in
much less than minute.
--
William Stein
Associate Professor of Mathematics
University of Washington
http://wstein.org
ma...@mendelu.cz
(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.
Do not know where the bug is, but hope that this helps.
Robert
> x.py
> < 1KZobrazitStáhnout
ma...@mendelu.cz
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
luisfe
On 17 dic, 11:48, "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
If you perform the computations over the polynomial ring, sage gives
an answer
sage: R=FractionField(PolynomialRing(GF(2),",".join(map(genVar,range
(0,10)))))
sage: n=matrix(R.base(),m)
sage: n-m
[0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0]
sage: det(n)
x1^2*x4^2*x5^2*x6^2 + x0^2*x2^2*x3^2*x7^2
However, the result differs from the one in maxima and maple
About the result, the matrix is mod 2, so the expected anwer in maxima
equals the one computed above
sage: factor(det(n))
(x1*x4*x5*x6 + x0*x2*x3*x7)^2
Christian Szegedy
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.
> --
> To post to this group, send email to sage-s...@googlegroups.com
> To unsubscribe from this group, send email to sage-support...@googlegroups.com
> For more options, visit this group at http://groups.google.com/group/sage-support
> URL: http://www.sagemath.org
>
Robert Bradshaw
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
Christian Szegedy
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.)
William Stein
<christia...@gmail.com> 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.
>
> 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.)
Wonderful. Please read http://wiki.sagemath.org/TracGuidelines and
email me offlist for your account. Thanks again for improving the
quality of Sage through your very valuable bug reports.
William
Robert Bradshaw
> 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.
William Stein
<sebastian...@hertford.ox.ac.uk> wrote:
> Dear William,
>
> This is just a very brief reply (before going to bed, it's past 3am here). I've added the bug report as ticket #7730.
http://trac.sagemath.org/sage_trac/ticket/7730
> After I've had a quick look at the problem, it seems it's caused by the computation of the Hessenberg form. In fact, supplying the choice "algorithm='df'" would allow the person who submitted the bug report to carry out the computation quickly. Just in case that person is interested (I am not quite sure what the arrangement for replying to him is, in any case, I think for me it's more appropriate to reply to you):
>
> Computation of det by minors: 2.15s
> Computation of det using the division-free algorithm: 3.87microseconds
> Computation of inverse: 71.6ms
>
> Oh, and the output in either case for the determinant is x1^2*x4^2*x5^2*x6^2 + x0^2*x2^2*x3^2*x7^2, which is different from the bug report. (It looks like the powers of two were omitted in the bug report.)
>
> While I am not all that familiar with the Hessenberg form computation, I am happy to look at it in the next few days --- it seems something that is used that often shouldn't be broken.
>
Thanks! I think I implemented Hessenberg form long, long ago
following H. Cohen's book.... The generic algorithm is fine, so
something must go wrong/weird in the special case under consideration.
William