#5876: [with patch, needs review] Vast speedup in P1List construction
---------------------------+------------------------------------------------
Reporter: cremona | Owner: craigcitro
Type: enhancement | Status: new
Priority: major | Milestone: sage-3.4.2
Component: modular forms | Keywords: modular manin symbols
---------------------------+------------------------------------------------
The P1List() constructor for Manin symbols (elements of {{{P^1(ZZ/NZZ)}}}
was rather inefficient. It constructed vastly too many symbols,
normalised them all and then deleted duplicates.
This is quite unnecessary since it is easy to generate the list with no
duplicates (and with simpler code).
As reported on sage-nt:
Before (3.4.1):
{{{
sage: time P1List(100000)
CPU times: user 3.52 s, sys: 0.03 s, total: 3.55 s
Wall time: 3.55 s
The projective line over the integers modulo 100000
sage: time P1List(1000000)
CPU times: user 129.11 s, sys: 0.64 s, total: 129.75 s
Wall time: 131.96 s
The projective line over the integers modulo 1000000
}}}
After:
{{{
sage: time P1List(100000)
CPU times: user 0.41 s, sys: 0.01 s, total: 0.42 s
Wall time: 0.42 s
The projective line over the integers modulo 100000
sage: time P1List(1000000)
CPU times: user 8.33 s, sys: 0.12 s, total: 8.45 s
Wall time: 8.80 s
The projective line over the integers modulo 1000000
}}}
The patch does this for both versions {{{p1list_int()}}} and
{{{p1list_llong()}}}.
I think similar speedups are possible in the p1_normalise functions which
would be significant in practice, and will try to get to that tomorrow.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/5876>
Sage <http://sagemath.org/>
Sage - Open Source Mathematical Software: Building the Car Instead of
Reinventing the Wheel
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
