Calculate nth power of a matrix

Question

I'm trying to optimize my code to calculate the nth power of a matrix.

Before I would just call multiplySquare n times but that was way too slow. The problem is, it builds just fine but when I run it, I get a failure with exit value 1. I believe my algorithm is right so what's causing this?

[EDIT] Added recursion termination condition but still, I get the same error.

[EDIT AGAIN] I re-wrote the recursion part again and now it seems to work but only for certain inputs of n. I'll have to play around with it more. Any help would be appreciated.

void multiplySquare(long long A[2][2], long long B[2][2]){

    long long result[2][2];
    for (int i = 0; i < 2; i++){
        for (int j = 0; j < 2; j++){
            result[i][j] = 0;
            for (int k = 0; k < 2; k++){
                result[i][j] += A[i][k] * B[k][j];
            }
        }
    }

    for (int i=0; i<2; i++){
        for (int j=0; j<2; j++){
            A[i][j] = result[i][j]; 
        }
    }
}

void power(long long A[2][2], long long B[2][2], long long n){
    if(n/2 != 0){   
        power(A, B, n/2);
    }
    if(n%2 != 0){
        multiplySquare(A, B);
    }
}

Answer 1

The algorithm to compute the N-th power of a number x efficiently is:

If N is zero, return 1.
If N is 1, return x.
Compute (N/2)-th power. y = x^(N/2)
If N is even, return y*y
If N is odd, return x*y*y

If you translate that logic to your case, you will need something along the lines of:

// Assuming that the result is returned in B.
void power(long long A[2][2], long long B[2][2], long long n)
{
   if ( n == 0 )
   {
      makeIdentity(B);
      return;
   }

   if ( n == 1 )
   {
      assign(A, B);  // Make B same as A.
      return;
   }

   power(A, B, n/2);

   multiplySquare(B, B);
   if(n % 2 != 0)
   {
      multiplySquare(B, A);
   }
}

Answer 2

I'm trying to optimize my code to calculate the nth power of a matrix.

Since your goal is an optimization, it might be a good thing to consider that diagonal matrices have trivial n-th power, i.e. the n-th power on the elements of the main diagonal.

So, firstly you should diagonalise your matrix. One way to do it is to find the eigenvectors and eigenvalues of your initial matrix, A, and utilize the following relationship:

A = P D P^-1

where P is a matrix containing the (column) eigenvectors of A, P^-1 is its inverse and D is a diagonal matrix containing the eigenvalues.

Then: Aⁿ = P Dⁿ P^-1

---

The above equation:

1. Takes A to a place where rising to the n-th power is trivial.
2. Calculates the n-th power.
3. Returns A back to the original place.