#7730: hessenberg_form hangs (or is *very* slow)
-------------------------+--------------------------------------------------
Reporter: spancratz | Owner: spancratz
Type: defect | Status: new
Priority: minor | Milestone:
Component: algebra | Keywords: matrices, hessenberg form
Work_issues: | Author:
Upstream: N/A | Reviewer:
Merged: |
-------------------------+--------------------------------------------------
Changes (by spancratz):
* owner: AlexGhitza => spancratz
Old description:
> I heard of the following bug report through William.
>
> Bug report
> ----------
>
> Simple 8X8 matrix determinant computation makes sage hang:
>
> {{{
> def genVar(i):
> return "x%i"%i
>
> def matrix_from_hash(h):
> R=FractionField(PolynomialRing(GF(2),",".join(map(genVar,range(0,10)))))
> h2 = {}
> for p in h:
> x=R.zero_element()
> for v in h[p]:
> x=x+R.gens()[v]
> h2[p] = x
> h2[p[1],p[0]] = x
> return matrix(h2,sparse=False)
>
> def test():
> m = matrix_from_hash({(0, 1): [0, 5], (1, 2): [0], (5, 6): [2], (6,
> 7): [1], (4, 5): [4], (0, 7): [1, 7], (0, 6): [2, 1], (0, 5): [4, 2], (0,
> 4): [3, 4], (2, 3): [6], (0, 3): [6, 3], (3, 4): [3], (0, 2): [0, 6]})
> print m
> m.charpoly()
> }}}
>
> 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.
>
> Notes
> -----
>
> I could only look at this briefly so far. The problem is --- this is
> perhaps unexpected --- not with the more recent implementation of
> "_charpoly_df". In fact, in the method "charpoly", the method selected
> is "_charpoly_hessenberg". Both methods "hessenberg" and "hessenbergize"
> reveal this problem.
New description:
I heard of the following bug report through William.
[Bug report]
Simple 8X8 matrix determinant computation makes sage hang:
{{{
def genVar(i):
return "x%i"%i
def matrix_from_hash(h):
R=FractionField(PolynomialRing(GF(2),",".join(map(genVar,range(0,10)))))
h2 = {}
for p in h:
x=R.zero_element()
for v in h[p]:
x=x+R.gens()[v]
h2[p] = x
h2[p[1],p[0]] = x
return matrix(h2,sparse=False)
def test():
m = matrix_from_hash({(0, 1): [0, 5], (1, 2): [0], (5, 6): [2], (6,
7): [1], (4, 5): [4], (0, 7): [1, 7], (0, 6): [2, 1], (0, 5): [4, 2], (0,
4): [3, 4], (2, 3): [6], (0, 3): [6, 3], (3, 4): [3], (0, 2): [0, 6]})
print m
m.det()
}}}
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.
[Notes]
I could only look at this briefly so far. The problem is --- this is
perhaps unexpected --- not with the more recent implementation of
"_charpoly_df". In fact, in the method "charpoly", the method selected is
"_charpoly_hessenberg". Both methods "hessenberg" and "hessenbergize"
reveal this problem.
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7730#comment:1>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
