#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):
Here's an implementation of the suggestion above:
{{{
diff -r e8e97f260027 sage/modular/quatalg/brandt.py
--- a/sage/modular/quatalg/brandt.py Thu Mar 26 12:34:13 2009 -0700
+++ b/sage/modular/quatalg/brandt.py Thu Mar 26 20:06:25 2009 -0700
@@ -936,7 +936,7 @@
K = self.base_ring()
return matrix(K, [[K(B[i][j][n]) for i in range(m)] for j in
range(m)], sparse=sparse)
- def right_ideals(self):
+ def right_ideals(self, B=None):
"""
Return sorted tuple of representatives for the equivalence
classes of right ideals in self.
@@ -962,9 +962,11 @@
I = R.unit_ideal()
I = R.right_ideal([4*x for x in I.basis()])
- B = 2*self.dimension()+10
+ if B is None:
+ B = 2*self.dimension()+10
ideals = [I]
+ ideals_theta = { tuple(I.theta_series_vector(B)) : [I] }
new_ideals = [I]
newly_computed_ideals = []
@@ -976,13 +978,19 @@
L = self.cyclic_supermodules(I, p)
for J in L:
is_new = True
- for K in ideals:
- if J.is_equivalent(K, B):
- is_new = False
- break
+ J_theta = tuple(J.theta_series_vector(B))
+ if J_theta in ideals_theta:
+ for K in ideals_theta[J_theta]:
+ if J.is_equivalent(K, B):
+ is_new = False
+ break
if is_new:
newly_computed_ideals.append(J)
ideals.append(J)
+ if J_theta in ideals_theta:
+ ideals_theta[J_theta].append(J)
+ else:
+ ideals_theta[J_theta] = [J]
verbose("found %s of %s ideals"%(len(ideals),
self.dimension()), level=2)
if len(ideals) >= self.dimension():
ideals = tuple(sorted(ideals))
}}}
----
With the patch above I get:
{{{
sage: time len(BrandtModule(1009,use_cache=False).right_ideals(42))
CPU times: user 2.48 s, sys: 0.02 s, total: 2.50 s
Wall time: 2.50 s
84
sage: time len(BrandtModule(2003,use_cache=False).right_ideals(84))
CPU times: user 3.98 s, sys: 0.02 s, total: 4.00 s
Wall time: 4.00 s
168
sage: time len(BrandtModule(3001,use_cache=False).right_ideals(125))
CPU times: user 10.32 s, sys: 0.08 s, total: 10.40 s
Wall time: 10.40 s
250
}}}
The optimal bound now seems to be around half the dimension of the space
(experimental, just for those three levels). Take into account that the
faster the function {{{is_equivalent()}}} is, the smallest the optimal
bound (because we can afford to test more false positives).
With this patch, it makes sense to call an is_equivalent function which
doesn't test the theta series, just computes I*Jbar, etc. I don't know if
it would make much difference (I'm currently trying to decipher output of
%prun).
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/5520#comment:13>
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
-~----------~----~----~----~------~----~------~--~---
