#13925: Tune rational echelon form code
------------------------------+---------------------------------------------
Reporter: nbruin | Owner: jason, was
Type: defect | Status: new
Priority: major | Milestone: sage-5.6
Component: linear algebra | Keywords:
Work issues: | Report Upstream: N/A
Reviewers: | Authors:
Merged in: | Dependencies:
Stopgaps: |
------------------------------+---------------------------------------------
Presently, there are whole ranges of matrix sizes and ranks where the
default heuristic for choosing an `echelon_form` algorithm for matrices
over `QQ` chooses the slowest choice possible:
{{{
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.
See [http://trac.sagemath.org/sage_trac/ticket/13400#comment:29 #13400,
comment 29] for the context of some of the remarks about the conditions
under which these timings were made. The essential problem reported in
this ticket is quite independent of memory issues, though!
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13925>
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.
