#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):
OOPS! Turns out the default algorithm for these matrices is "padic", which
is a bad choice as these examples show. It's particularly bad for low rank
examples such as this one. If we take a vandermonde matrix, it's a little
better
{{{
def test1(N,t):
L=[[i^j for i in [1..N]] for j in [1..N]]
for i in range(t):
m=matrix(QQ,N,N,L).echelon_form()
}}}
but multimodular is a clear winner. There the fields DO get generated in a
deterministic order:
{{{
sage.matrix.matrix_modn_dense.MAX_MODULUS
p=previous_prime(sage.matrix.matrix_modn_dense.MAX_MODULUS)
while ...:
...
p = previous_prime(p)
}}}
so if it were an issue we should store finite fields for some of those p
(and also for `sage.matrix.matrix_modn_sparse.MAX_MODULUS` for good
measure).
Indeed:
{{{
sage: import gc
sage: def test1(N,t):
....: L=[[i^j for i in [1..N]] for j in [1..N]]
....: for i in range(t):
....:
m=matrix(QQ,N,N,srange(N*N)).echelon_form(algorithm="multimodular")
....:
sage: %time test1(20,10^3)
CPU times: user 1.43 s, sys: 0.02 s, total: 1.46 s
Wall time: 1.47 s
sage: gc.collect()
523
sage: %time test1(20,10^3)
CPU times: user 1.40 s, sys: 0.02 s, total: 1.42 s
Wall time: 1.43 s
sage: gc.collect()
523
sage: %time test1(20,10^3)
CPU times: user 1.41 s, sys: 0.02 s, total: 1.43 s
Wall time: 1.43 s
sage: gc.collect()
523
sage: FieldCache=[]
sage: N=sage.matrix.matrix_modn_dense.MAX_MODULUS
sage: p=previous_prime(N+1)
sage: for i in range(20):
....: FieldCache.append(Integers(p))
....: p=previous_prime(p)
....:
sage: %time test1(20,10^3)
CPU times: user 1.41 s, sys: 0.01 s, total: 1.43 s
Wall time: 1.44 s
sage: gc.collect()
523
sage: %time test1(20,10^3)
CPU times: user 1.41 s, sys: 0.01 s, total: 1.42 s
Wall time: 1.43 s
sage: gc.collect()
523
sage: MatrixCache=[MatrixSpace(F,20,20) for F in FieldCache]
sage:
sage:
sage: %time test1(20,10^3)
CPU times: user 1.25 s, sys: 0.01 s, total: 1.26 s
Wall time: 1.27 s
sage: gc.collect()
0
sage: %time test1(20,10^3)
CPU times: user 1.25 s, sys: 0.01 s, total: 1.26 s
Wall time: 1.26 s
sage: gc.collect()
0
}}}
so it seems that with Thierry's code fixed, constructing the matrix rings
is the only measurable overhead in this. And I don't think we can
intelligently
cache those.
The REAL surprise is that in the padic variant the primes get selected via
this
little pearl:
{{{
p = previous_prime(rstate.c_random() % (MAX_MODULUS-15000) + 10000)
}}}
Random numbers are very expensive! So just changing that (in two places)
to a
simple `p = previous_prime(p)` reduces the time SIGNIFICANTLY and in
practice of
course behaves just as well, unless you have a particularly nasty
adversary
(perhaps draw from a pool a bit larger than just the primes in sequence?).
In short, after picking off the `is_subcategory` problem, I don't think
this
example is telling us much more than that the choice of algorithm in
`echelon_form` can use some tuning. Its preference for `padic` over
`multimodular` might be premature and was probably induced by William's
euphoria
about discovering a really neat trick. As he documents, it should be used
on
matrices with large entries.
Futhermore, perhaps the implementation of
`padic` is placing a little too much emphasis on properly emulating
randomness.
That's probably a little less of an issue for matrices for which the
algorithm
is suited, but I don't think one gets real benefit out of using such high
quality randomization.
I suspect there are some places we can benefit from more tuned/intelligent
coding and caching, this piece of code is not giving huge pointers where
...
Perhaps one should profile some examples in elliptic curves and see how
much
time is spent in coercion/creation of parents.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13400#comment:18>
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.
