#15104: Special case modn_dense matrix operations to improve performance
-------------------------------------+-------------------------------------
Reporter: nbruin | Owner:
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-6.2
Component: linear algebra | Resolution:
Keywords: | Merged in:
Authors: Nils Bruin, Simon | Reviewers:
King | Work issues: regression in
Report Upstream: N/A | right_kernel_matrix
Branch: | Commit:
u/SimonKing/ticket/15104 | 0f008f9266e3ed6fbd67e7f3d357474825bdb160
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by SimonKing):
__Good news first__
The proposed `__init__` method for the category of algebras seems not to
result in a severe regression in the benchmark examples from #11900. Or
perhaps there is a regression in `prove_BSD`, but this would be due to the
current commits, not due to the new init method.
First, with the added `__init__` method for the category of algebras:
{{{
sage: %time D = J0(46).endomorphism_ring().discriminant()
CPU times: user 10.23 s, sys: 0.17 s, total: 10.40 s
Wall time: 10.42 s
sage: %time TestSuite(CrystalOfTableaux(['B',4],shape=[2,1,1,0])).run()
CPU times: user 3.24 s, sys: 0.02 s, total: 3.26 s
Wall time: 3.27 s
sage: W.<z> = CyclotomicField(13)
sage: %time M = Matrix(W, 2, 3, [10^30*(1-z)^13, 1, 2, 3, 4,
z]).echelon_form()
CPU times: user 2.01 s, sys: 0.02 s, total: 2.03 s
Wall time: 2.05 s
sage: %time L = EllipticCurve('960d1').prove_BSD()
CPU times: user 4.62 s, sys: 0.07 s, total: 4.69 s
Wall time: 4.71 s
sage: def test(E):
....: for p in prime_range(10000):
....: if p != 389:
....: G = E.change_ring(GF(p)).abelian_group()
....:
sage: E = EllipticCurve('389a')
sage: %time test(E)
CPU times: user 26.80 s, sys: 0.09 s, total: 26.89 s
Wall time: 26.94 s
sage: E = J0(46).endomorphism_ring()
sage: %time g = E.gens()
CPU times: user 9.39 s, sys: 0.15 s, total: 9.54 s
Wall time: 9.56 s
}}}
Next, with the current commits:
{{{
sage: %time D = J0(46).endomorphism_ring().discriminant()
CPU times: user 9.98 s, sys: 0.19 s, total: 10.17 s
Wall time: 10.21 s
sage: %time TestSuite(CrystalOfTableaux(['B',4],shape=[2,1,1,0])).run()
CPU times: user 3.30 s, sys: 0.06 s, total: 3.36 s
Wall time: 3.23 s
sage: W.<z> = CyclotomicField(13)
sage: %time M = Matrix(W, 2, 3, [10^30*(1-z)^13, 1, 2, 3, 4,
z]).echelon_form()
CPU times: user 2.02 s, sys: 0.01 s, total: 2.03 s
Wall time: 2.04 s
sage: %time L = EllipticCurve('960d1').prove_BSD()
CPU times: user 4.70 s, sys: 0.06 s, total: 4.77 s
Wall time: 4.79 s
sage: def test(E):
....: for p in prime_range(10000):
....: if p != 389:
....: G = E.change_ring(GF(p)).abelian_group()
....:
sage: E = EllipticCurve('389a')
sage: %time test(E)
CPU times: user 27.44 s, sys: 0.11 s, total: 27.55 s
Wall time: 27.60 s
sage: E = J0(46).endomorphism_ring()
sage: %time g = E.gens()
CPU times: user 9.17 s, sys: 0.19 s, total: 9.37 s
Wall time: 9.39 s
}}}
And finally, as baseline, the master branch:
{{{
sage: %time D = J0(46).endomorphism_ring().discriminant()
CPU times: user 10.07 s, sys: 0.20 s, total: 10.27 s
Wall time: 10.29 s
sage: %time TestSuite(CrystalOfTableaux(['B',4],shape=[2,1,1,0])).run()
CPU times: user 3.18 s, sys: 0.00 s, total: 3.18 s
Wall time: 3.19 s
sage: W.<z> = CyclotomicField(13)
sage: %time M = Matrix(W, 2, 3, [10^30*(1-z)^13, 1, 2, 3, 4,
z]).echelon_form()
CPU times: user 1.96 s, sys: 0.02 s, total: 1.98 s
Wall time: 1.99 s
sage: %time L = EllipticCurve('960d1').prove_BSD()
CPU times: user 4.68 s, sys: 0.08 s, total: 4.76 s
Wall time: 4.78 s
sage: def test(E):
....: for p in prime_range(10000):
....: if p != 389:
....: G = E.change_ring(GF(p)).abelian_group()
....:
sage: E = EllipticCurve('389a')
sage: %time test(E)
CPU times: user 27.20 s, sys: 0.08 s, total: 27.28 s
Wall time: 27.33 s
sage: E = J0(46).endomorphism_ring()
sage: %time g = E.gens()
CPU times: user 9.25 s, sys: 0.16 s, total: 9.41 s
Wall time: 9.43 s
}}}
Hence, in these tests, that have previously been the reason to have an
incomplete category initialisation of matrix spaces, there would be no
regression when letting the category of algebras create and store their
super categories upon initialisation.
What is your opinion on that idea?
__Worries__
Did some regression creep in without being noticed? The first example,
{{{
%time D = J0(46).endomorphism_ring().discriminant()
}}}
used to be faster, pre-#9138 and post-#11900.
I'd say this particular example should go on a separate ticket.
--
Ticket URL: <http://trac.sagemath.org/ticket/15104#comment:32>
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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/groups/opt_out.
