#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 a similar patch for
{{{BrandtModule._compute_hecke_matrix_directly()}}}:
{{{
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 22:09:42 2009 -0700
@@ -822,7 +822,7 @@
"""
return self._compute_hecke_matrix_brandt(n, sparse=sparse)
- def _compute_hecke_matrix_directly(self, n, sparse=False):
+ def _compute_hecke_matrix_directly(self, n, B=None, sparse=False):
"""
Given an integer n coprime to the level, return the matrix of
the n-th Hecke operator on self, computed on our fixed basis
@@ -881,17 +881,27 @@
# of ideals modulo equivalence -- we always provably check
# equivalence if the theta series are the same up to this
# bound.
- B = self.hecke_bound() + 5
+ if B is None:
+ B = self.hecke_bound() + 5
T = matrix(self.base_ring(), self.dimension(), sparse=sparse)
C = self.right_ideals()
- r = 0
- for I in C:
- for J in self.cyclic_supermodules(I, n):
- for i in range(len(C)):
- if C[i].is_equivalent(J, B):
+ theta_dict = {}
+ for i in range(len(C)):
+ I_theta = tuple(C[i].theta_series_vector(B))
+ if I_theta in theta_dict:
+ theta_dict[I_theta].append(i)
+ else:
+ theta_dict[I_theta] = [i]
+ for r in range(len(C)):
+ for J in self.cyclic_supermodules(C[r], n):
+ J_theta = tuple(J.theta_series_vector(B))
+ for i in theta_dict[J_theta]:
+ CiJbar = C[i].multiply_by_conjugate(J)
+ c = CiJbar.theta_series_vector(2)[1]
+ if c != 0:
T[r,i] += 1
- r += 1
+ break
return T
def _compute_hecke_matrix_brandt(self, n, sparse=False):
}}}
Again, I'm exposing the bound {{{B}}} for tuning; we need to figure out
how to pick a sensible default.
Note that, for a fixed value of {{{B}}}, the dictionary {{{theta_dict}}}
is fixed (independent of {{{n}}}, that is) so it could be cached to
improve running time. Indeed, that information could be cached in
{{{right_ideals()}}} as it was already computed in there. However, I don't
expect more than 10-20% speedup for p=2, less for higher primes, since we
are only saving the computation of {{{n}}} theta series out of a total of
{{{(p+2)}}} theta series which need to be computed.
Here's some benchmarks, BEFORE the patch:
{{{
sage: B=BrandtModule(1009,use_cache=False)
sage: time Is=B.right_ideals(40)
CPU times: user 0.73 s, sys: 0.00 s, total: 0.73 s
Wall time: 0.73 s
sage: time T2=B._compute_hecke_matrix_directly(2)
CPU times: user 8.88 s, sys: 0.06 s, total: 8.94 s
Wall time: 8.94 s
}}}
AFTER the patch:
{{{
sage: B=BrandtModule(1009,use_cache=False)
sage: time Is=B.right_ideals(40)
CPU times: user 0.75 s, sys: 0.00 s, total: 0.75 s
Wall time: 0.78 s
sage: time T2=B._compute_hecke_matrix_directly(2,40)
CPU times: user 1.08 s, sys: 0.00 s, total: 1.08 s
Wall time: 1.08 s
sage: time T3=B._compute_hecke_matrix_directly(3)
CPU times: user 1.35 s, sys: 0.01 s, total: 1.36 s
Wall time: 1.35 s
}}}
For comparision:
{{{
sage: time B2=B._compute_hecke_matrix_brandt(2)
CPU times: user 3.97 s, sys: 0.03 s, total: 4.00 s
Wall time: 4.00 s
}}}
Bear in mind that after using the brandt method for p=2, computing
hecke_matrix_brandt for other p's is instantaneous or at least much
faster, but computing with the _directly method will take time
proportional to p+1.
IOW, for this dimension, the direct method is better if we only want to
compute 3 hecke ops, but the brandt method is better for 4 or more hecke
ops.
For larger dimensions, the advantage should be much larger for the direct
method:
{{{
sage: B=BrandtModule(20011,use_cache=False)
sage: time Is=B.right_ideals(120)
prof = [1665, 4994, 4394, 17625, 3327, 1667]
CPU times: user 27.80 s, sys: 0.10 s, total: 27.90 s
Wall time: 27.91 s
sage: time T2=B._compute_hecke_matrix_directly(2,120)
CPU times: user 29.80 s, sys: 0.30 s, total: 30.10 s
Wall time: 30.10 s
sage: time T2=B._compute_hecke_matrix_directly(3,120)
CPU times: user 37.45 s, sys: 0.32 s, total: 37.77 s
Wall time: 37.77 s
}}}
Since the dimension of the space is 1668, in order to compute brandt
matrices we would need 1391946 multiplications of quaternion ideals, same
number of theta series computation. That's about 400 times more
multiplications than the example for p=1009, hence it could take at least
1600 seconds.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/5520#comment:15>
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
-~----------~----~----~----~------~----~------~--~---
