On Mon, Feb 6, 2012 at 6:49 AM, John Cremona <john.crem...@gmail.com> wrote:
> I was trying to find eigenspaces of a 26x26 matrix over Q(zeta_11)
> (for a modular forms application) and ran into:
>
> RuntimeError: we ran out of primes in multimodular charpoly algorithm
>
> which on investigation led me to the following lines in
> sage/ext/multi_modular.pyx:
>
> # We use both integer and double operations, hence the min.
> # MAX_MODULUS = min(int(sqrt(int(MOD_INT_OVERFLOW))-1), int(2)**int(20))
>
> # Hard coded because currently matrix_modn_dense is implemented using C
> ints
> # which are always 32-bit. Once this gets fixed, i.e., there is a better
> # matrix_modn class, then this can change.
> MAX_MODULUS = 46341
>
> so I am just wondering if anyone out there has this on their to-do
> list. Meanwhile using algorithm='pari' will have to do, though it is
> slow....
>
> This is a small trial run. We'll be doing a 50x50 over Q(zeta_13) for
> real....
The way the algorithm works is:
(1) clear denominators to get a matrix A,
(2) compute a bound B such that if we find charpoly(A) mod primes p_i with
the product of the p_i >= B, then we are guaranteed to be done by simply
lifting that charpoly.
(3) adjust fro denominators.
The bound B in your problem is enormous:
sage: a = load('http://sage.math.washington.edu/home/cremona/M26.sobj')
sage: b = a.denominator() * a
sage: RR(b._charpoly_bound())
9.15110810448877e9185
i.e., it's about 10^9186 (!).
The product of the available primes with the current implementation is
"only":
sage: RR(prod([p for p in primes(46000) if p%11==1]))
1.47251631030824e1961
So this algorithm to compute charpoly is doomed unless the implementation
is rewritten to allow for more primes. If that were done, the computation
would work and take about 5 times as long as it takes to complete right
now, i.e., a fixed implementation should take about 5 minutes (so much
better than Pari).
You can also try with proof=False, which will simply try until it looks
likely that the CRT stabilized. But even then it fails in this example.
-- William
--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
