#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:
----------------------------------+-----------------------------------------
Changes (by Bouillaguet):
* status: needs_work => needs_review
Comment:
Replying to [comment:5 kcrisman]:
> {{{
> sage: %timeit matrix(100,dd).det()
> 5 loops, best of 3: 228 ms per loop
> sage: %timeit matrix(100,dd,sparse = False).det()
> 25 loops, best of 3: 15.2 ms per loop
> }}}
> 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.
So, there was clearly some improvement.
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.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/5402#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.
