#5402: Sparse determinants are slow
----------------------------------+-----------------------------------------
Reporter: jbandlow | Owner: was
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-5.6
Component: linear algebra | Resolution:
Keywords: determinant | Work issues:
Report Upstream: N/A | Reviewers:
Authors: | Merged in:
Dependencies: | Stopgaps:
----------------------------------+-----------------------------------------
Comment (by kcrisman):
> > It's just that everything is faster now. How much faster would
Moore's law say these should be after four years?
>
> In comment 2, someone complains about this test running for 15 minutes.
On your machine, it runs in 228ms (sparse case). This is about 4000x times
faster. Moore's law tell you that the number of transistor on a chip
doubles every 18 months, so that in 4 years we would have at the very
maximum a 10x speedup.
Interestingly, other than that one, the rest indeed show a 4-10x speedup.
> However, if you look into it a bit deeper, then you'll see that in the
sparse case, computing the determinant triggers the computation of the
charpoly(), and the computation of the charpoly creates a dense version of
the matrix, then runs the dense charpoly algorithm. I thus agree that this
is suboptimal (in particular because linbox has fancy iterative methods
for this kind of computation on sparse matrices).
>
> Anyway, why don't we : a) close this ticket, considering that it is
outdated and that the situation has changed, and b) open a "feature
request" ticket related to sparse matrices over exact rings? I would be
happy to look into this.
Well, given that we ''already'' create the dense matrix, then William's
fix seems like it would speed things up at least a little, or be no worse?
I don't see why we (by which I mean you and other people who compute such
determinants!) couldn't try it out, ''as well as'' of course creating a
new ticket to use fancy methods. Seem reasonable?
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/5402#comment:7>
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.
