#7730: hessenberg_form hangs (or is *very* slow)
-------------------------+--------------------------------------------------
Reporter: spancratz | Owner: AlexGhitza
Type: defect | Status: new
Priority: minor | Milestone:
Component: algebra | Keywords: matrices, hessenberg form
Work_issues: | Author:
Upstream: N/A | Reviewer:
Merged: |
-------------------------+--------------------------------------------------
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.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7730>
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.
