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/ -~----------~----~----~----~------~----~------~--~---
