On Mon, Feb 6, 2012 at 12:21 PM, John Cremona <john.crem...@gmail.com> wrote: > Thanks! > > Barinder has genuine matrices A, B which give a representation of A_4 > in 26 dimensions over Q(zeta_11), i.e. A^2=I and B^3 = I and some > commutator relation holds. I was surprised when he told me that > A.eigenspaces_right() had beeen running for 2 days (though it turned > out that that A was wrong, it did satisfy A^2=I). > > My example was random: I took J=diag(1,1,...,1,-1,-1,...,-1) with 13 > +1's and 13 -1's and conjugated by a random M (which was > unsurprisingly invertible) to get an Q whose char poly was (X-1)^13 * > (X+1)^13. Using algorithm='pari' gave that correctly, but took > quite a while (the time has scrolled off my screen, it was > 2000s I > think). But in our computation we know that A and B both have +1 as > an eigenvalue and we only want their +1-eigenspaces, which (for my > random A) only takes 87s.
I was just looking at this again, since I've done a lot of work lately on improving multimodular linear algebra, since I need that for modular symbols computations right now. I tried your matrix M: > The matrix is in sagemath:/home/cremona/M26.sobj if you want to play > with it; but remember that this is a random M with M^2=I, not one we > actually want for real. ... and found that one can compute the charpoly using the Hessenberg normal form algorithm very quickly (about 6 seconds): sage: m._clear_cache() sage: m.charpoly(algorithm='hessenberg') verbose 1 (<module>) Computing Hessenberg Normal Form of 26x26 matrix verbose 1 (<module>) Finished Hessenberg Normal Form of 26x26 matrix (time = 5.872043) x^26 - 13*x^24 + 78*x^22 - 286*x^20 + 715*x^18 - 1287*x^16 + 1716*x^14 - 1716*x^12 + 1287*x^10 - 715*x^8 + 286*x^6 - 78*x^4 + 13*x^2 - 1 So maybe you can use that. This is a matrix for which the multimodular approach is *terrible*, but Hessenberg is pretty good. -- William > > John > > On 6 February 2012 17:01, William Stein <wst...@gmail.com> wrote: >> 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: >> >> Can you make your matrix available, e.g., as an sobj on sage.math (or >> somewhere) that I can download. >> It's possible that the real problem is a bug in the echelon routine, >> not the size of the modulus. >> If the multimodular echelon fails to stabilize -- due to a bug -- then >> the consequence is that eventually >> the primes would run out. However, this is highly unlikely to happen >> in practice unless the entries of >> the answer are truly gigantic. >> >> -- William >> >>> >>> 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.... >>> >>> John >>> >>> -- >>> 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 >> >> >> >> -- >> William Stein >> Professor of Mathematics >> University of Washington >> http://wstein.org >> >> -- >> 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 > > -- > 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 -- William Stein Professor of Mathematics University of Washington http://wstein.org -- 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
