I did try to check that Mathematica was getting the right answer, but I had no luck. I don't know how to convert a mathematica matrix into ordinary matrix form in SAGE, so when I do the comparison it always just says false.
Bill. On 3 Dec, 15:21, Clement Pernet <[EMAIL PROTECTED]> wrote: > Hi there, > > The method using x^k mod charpoly (or minpoly) is clearly the only > method I know about for that problem. > If n is smallish, this is the good way to do it. > > For larger n (say n=O(k)), the computation of the n power of A in step 3 > is the bottleneck (n^4 or n^(w+1) ops in Q, so roughly O(n^5) bit ops). > In this case, a good approach is to replace M by its Frobenius form F = > U^-1AU in step 3 and apply the similarity transformation at last. > > Clément > > David Harvey a écrit : > > >On Dec 3, 2007, at 8:40 AM, Bill Hart wrote: > > >>I've just been looking at SAGE ticket number 173: > > >>http://www.sagemath.org:9002/sage_trac/ticket/173 > > >>The idea is that Mathematica raises a 3 dimensional matrix M over QQ > >>to the power 20,000 much faster than either SAGE or Magma. > > >>I don't know any algorithm for doing this efficiently. I only know one > >>algorithm: > > >>1) Compute the characteristic polynomial p(x) of M (time 0.00s) > >>2) Compute x^20000 mod p (time 0.22s) > >>3) Substitute M into the result (time 0.00s) > > >>It's pretty obvious where the time is going here - polynomial > >>arithmetic. I guess this is the algorithm being used. Is Pari or NTL > >>being used for the polynomial expmod? > > >>I reckon we can speed this up. What do people think? > > >I would have guessed the algorithm was just "compute M^20000 using > >repeated squaring". But your suggestion is quite interesting. > > >Maybe first check that mathematica is getting the right answer, and > >not some stupid floating point approximation or something. > > >david --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~----------~----~----~----~------~----~------~--~---
