#13400: Use strong caches diligently
-------------------------------+--------------------------------------------
Reporter: nbruin | Owner: robertwb
Type: enhancement | Status: new
Priority: major | Milestone: sage-wishlist
Component: coercion | Resolution:
Keywords: | Work issues:
Report Upstream: N/A | Reviewers:
Authors: | Merged in:
Dependencies: | Stopgaps:
-------------------------------+--------------------------------------------
Comment (by nbruin):
OK, this is more about tuning rational echelon form code, but since the
issue came up here, I'll post some preliminary timings here:
{{{
from sage.misc.sage_timeit import sage_timeit
def timemat(n,m,r,B):
"""
does some matrix timings on a single random matrix described by the
parameters given:
n : Number of distinct rows
m : Number of colums
r : Number of times the rows should be repeated
B : Height bound on rational numbers put in the matrix
The matrix is essentially generated by constructing an n x m matrix
with random entries and then stacking r copies. This is meant as a
cheap
way of making non-maximal rank matrices.
"""
M = MatrixSpace(QQ,n*r,m)
L = r*list(randint(-B,B)/randint(1,B) for j in range(n*m))
D = globals().copy()
D['M'] = M
D['L'] = L
t1=min(sage_timeit('M(L).echelon_form("classical")',D).series)
t2=min(sage_timeit('M(L).echelon_form("multimodular")',D).series)/t1
t3=min(sage_timeit('M(L).echelon_form("padic")',D).series)/t1
return (1,t2,t3)
}}}
Timings are reported as `(classical,multimodular,padic)` with `classical`
scaled to 1. These tests are all in the range where currently `padic` is
chosen as a default. These timings are all done on 5.3b2 + #12313 + fix of
Thierry's code + un-randomization of prime choice in `padic`. Without
#12313 one would run out of memory on `padic` and without the other ones,
the timings of padic would be much worse:
{{{
sage: timemat(10,10,1,10^3)
(1, 1.4593604789072667, 2.25968735560318)
sage: timemat(10,10,1,10^800)
(1, 1.4550198262904093, 2.2320730206016584)
sage: timemat(20,20,1,10^800)
(1, 0.26421709436394647, 0.39672901423049933)
sage: timemat(50,50,1,10^20)
(1, 0.028462514595311343, 0.04085242952549667)
sage: timemat(20,30,2,10^20)
(1, 1.311503148833886, 1.0495737479473444)
sage: timemat(20,30,1,10^20)
(1, 1.1408739793541882, 0.8243377328388548)
sage: timemat(20,30,2,10^800)
(1, 1.0566089264644132, 1.2234341427870548)
sage: timemat(50,60,2,10^800)
(1, 0.5444370157383747, 0.18547612309046932)
}}}
so it seems that the cross-overs could use some tuning. In particular, for
non-maximal rank matrices it seems to take a while longer to overtake
classical. It would be great if someone would be able to tune this code
properly. It is very useful if sage would echelonize small matrices
quickly over arbitrary base fields quickly in most most cases (and not
make silly choices), because it allows linear algebra intensive algorithms
in a base-field agnostic way.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13400#comment:29>
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.
