#5520: [with patch; needs review] implement Pizer's algorithm for computing
Brandt
Modules and Brandt Matrices
---------------------------+------------------------------------------------
Reporter: was | Owner: craigcitro
Type: enhancement | Status: new
Priority: major | Milestone: sage-3.4.1
Component: modular forms | Keywords:
---------------------------+------------------------------------------------
Comment(by tornaria):
Performance of {{{BrandtModule.right_ideals()}}}: equivalence testing is
done using is_equivalent with B=2*dim+10. This is not optimal, and it
seems to lead to a O(n^2^) algorithm:
{{{
sage: time len(BrandtModule(1009,use_cache=False).right_ideals())
CPU times: user 9.72 s, sys: 0.02 s, total: 9.74 s
Wall time: 9.74 s
84
sage: time len(BrandtModule(2003,use_cache=False).right_ideals())
CPU times: user 38.44 s, sys: 0.00 s, total: 38.44 s
Wall time: 38.44 s
168
}}}
OTOH, I hacked {{{right_ideals}}} to take an extra parameter to set B
(bound passed to is_equivalent). The timing is now:
{{{
sage: time len(BrandtModule(1009,use_cache=False).right_ideals(20))
CPU times: user 4.75 s, sys: 0.00 s, total: 4.75 s
Wall time: 4.75 s
84
sage: time len(BrandtModule(2003,use_cache=False).right_ideals(30))
CPU times: user 11.02 s, sys: 0.04 s, total: 11.06 s
Wall time: 11.05 s
168
}}}
The optimal bound is unclear. I'd guess something around O(sqrt(n)) may
work... I discovered those by trial and error.
Now, it is worth precomputing (short) theta series for the ideals, but if
these are hashed as keys of a dictionary --- then the inner loop
{{{
for K in ideals:
if J.is_equivalent(K, B):
is_new = False
break
}}}
can be handled more efficiently as in (pseudo-code):
{{{
theta = J.theta_vector()
if theta in ideals_theta:
for K in ideals_theta[theta]:
if J.is_equivalent(K, B):
is_new = False
break
}}}
IOW, only call is_equivalent for ideals that match in the theta series...
Otherwise, this algorithm is indeed O(n^2^), because each new ideal
requires testing equivalence to false for each of the previously found
ideals.
The same is true for the hecke_matrix_directly() computation...
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/5520#comment:12>
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
-~----------~----~----~----~------~----~------~--~---
