#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: |
-------------------------+--------------------------------------------------
Comment(by spancratz):
This is mostly just to confirm that the problem is indeed the multivariate
polynomial GCD. I don't know much about this at the moment, but I am
writing an email to Martin Albrecht, who I think wrote the libSINGULAR
interface, to ask whether he has any suggestions.
However, there is another possible improvement that here would push the
problem a little further away (to instances of about twice the size, I
guess), but I think it should also be done in general:
In the generic fraction field implementation, in order to compute the
product a/b * c/d, we first compute a*c and b*d, then form their GCD and
finally divide both the numerator and the denominator by this. This could
be computed much faster if we assumed (or even checked and ensured, if
necessary!) that a/b and c/d are in lowest terms and then compute GCD(a,d)
and GCD(b,c) instead.
I think this might affect the fraction field implementation a lot though,
since it affects the assumptions about when elements are in lowest terms
and when not. I guess that this is something that ought to be discussed
on sage-devel, right?
Sebastian
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7730#comment:6>
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.
