0

How to implement a fast nxn integer matrix exponentiation algorithm M^n
The matrices are not diagonalizable and not symetric.
I have implemented the algo Exponentiation by Squaring but I know there are faster algos.
I don't want to use a numerical library.

The eigenvectors/values answer is usable for all symetric matrices but not for all matrices, I need a general algo. So my question need other answers than the previous one you pointed out and mark my question as duplicate.

Here is my code for Expo by Squaring but I need a faster algo: ww is the size if the matrix

void expo(int ww, ll n)
{
   int i,j,k;
   memset(ret,0,SZ);
   for(i=0;i<ww;i++)ret[i][i]=1;
   while(n){
     if(n&1){
       memset(tmp,0,SZ);
       for(i=0;i<ww;i++)
         for(j=0;j<ww;j++)
           for(k=0;k<ww;k++)
             tmp[i][j]+=ret[i][k]*mat[k][j];
       memcpy(ret,tmp,SZ);
     }
     memset(tmp,0,SZ);
     for(i=0;i<ww;i++) 
       for(j=0;j<ww;j++)
         for(k=0;k<ww;k++)
           tmp[i][j]+=mat[i][k]*mat[k][j];
     memcpy(mat,tmp,SZ);
     n>>=1;
   }
 }
JeanClaudeDaudin
  • 424
  • 6
  • 15
  • 1
    It's time to post a minimal code example demonstrating what you've got so far. – DavidO Feb 17 '14 at 07:34
  • I've edited and added my code for Expo by Squaring. – JeanClaudeDaudin Feb 17 '14 at 07:48
  • I suspect if you want to make this efficient for large exponents, you're going to want to first put the matrix in [rational canonical form](http://en.wikipedia.org/wiki/Frobenius_normal_form) or similar. – R.. GitHub STOP HELPING ICE Feb 17 '14 at 07:55
  • There are other threads in SO; for non-integer matrices there's the eigenvalue method. For matrix multiplication, the Strassen method doesn't give any advantage for N<20. – Aki Suihkonen Feb 17 '14 at 07:56
  • Do you want C or C++? The posted code might be accepted by a C++ compiler, but it's a long way from being canonical C++. – Potatoswatter Feb 17 '14 at 07:56
  • Also you should mention why it needs to be fast and what kind of matrices these are (so far you only describe what they're *not*). Large integer matrices are a bit unusual. Perhaps you actually only want Boolean matrices? Also you should clarify that you want a power of a matrix, not *e*^M. – Potatoswatter Feb 17 '14 at 07:57
  • I want it efficient for large exponents and n<20. I post C code, but nevermind if it's C++ code. I think pointers on rational canonical form implementation may be of good use – JeanClaudeDaudin Feb 17 '14 at 08:03
  • They are any integer matrices, and I have to compute the power of the matrix. – JeanClaudeDaudin Feb 17 '14 at 08:18
  • Don't you need "bignums" if you deal with large exponent? – nodakai Feb 17 '14 at 10:13
  • 1
    See http://en.wikipedia.org/wiki/Addition-chain_exponentiation. And note that almost certainly you will hit integer overflow. So integers won't do what you want. – btilly Feb 17 '14 at 10:13
  • @nodakai: In my complete code I use long long and modulo 1e9 for benchmarks, I'll use bigint after. – JeanClaudeDaudin Feb 17 '14 at 12:08
  • @DavidO: In the comments here there are two new algos pointers:one by R and one by btilly. The answer in the other question: eigenvectors/values is not usable for any matrix: Not every matrix has an eigenbasis, symetric ones have but not all matrices. So it's not usable. – JeanClaudeDaudin Feb 17 '14 at 17:50
  • Alright, voted to reopen. Thanks for providing code samples. At SO, presenting a complete question, including code samples, right from the start is key to getting a good answer. If time passes before the question is completed with code samples, it gets forgotten, or sometimes closed, and quality follow-up answers become unusual. – DavidO Feb 17 '14 at 18:23
  • I would do algebraic equation for matrix power to see if there are not any things to anihilate ... if not and N is big enough then use more advanced approach: http://www.google.sk/url?sa=t&rct=j&q=&esrc=s&source=web&cd=3&cad=rja&uact=8&ved=0CEAQFjAC&url=http%3A%2F%2Fwww.eecs.berkeley.edu%2F~oholtz%2FTalks%2Fmit.pdf&ei=NLgdU7GGMPOlyAPTn4GQCw&usg=AFQjCNFGFRotly5RS3ME9jMcwK0DFDWO-Q&bvm=bv.62578216,d.bGQ – Spektre Mar 10 '14 at 13:08

0 Answers0