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