高速行列累乗

Question

単純な除算および征服アルゴリズムよりもM^n（Mは行列、nは整数）を計算するための行列累乗の方法はありません。

Answer 1

行列を固有値と固有ベクトルに分解できます。そして、あなたは得る。

M = V^-1 * D * V 

ここで、Vは固有ベクトル行列であり、Dは対角行列である。すべてのVおよびV^-1項はキャンセルので

M^n = (V^-1 * D * V) * (V^-1 * D * V) * ... * (V^-1 * D * V) 
    = V^-1 * D^n * V 

：N乗にこれを上げるために、あなたのような何かを得ます。

Dは対角線であるため、完全な行列ではなく、n乗の（実際の）数を増やすだけです。あなたはnの対数時間でそれを行うことができます。

固有値と固有ベクトルの計算はr^3（rはMの行数/列数）です。 rとnの相対的な大きさに応じて、これは速くてもいいかもしれません。

Answer 2

Exponentiation by squaringは、高出力のマトリックスを得るためによく使用されます。

Answer 3

matrix formでFibbonacciシーケンスを計算するために使用する方法をお勧めします。 AFAIKの効率はO（log（n））です。

Answer 4

オイラー高速パワーアルゴリズムを使うのは簡単です。次のアルゴリズムを使用してください。以下は

#define SIZE 10 

//It's simple E matrix 
// 1 0 ... 0 
// 0 1 ... 0 
// .... 
// 0 0 ... 1 
void one(long a[SIZE][SIZE]) 
{ 
    for (int i = 0; i < SIZE; i++) 
     for (int j = 0; j < SIZE; j++) 
      a[i][j] = (i == j); 
} 

//Multiply matrix a to matrix b and print result into a 
void mul(long a[SIZE][SIZE], long b[SIZE][SIZE]) 
{ 
    long res[SIZE][SIZE] = {{0}}; 

    for (int i = 0; i < SIZE; i++) 
     for (int j = 0; j < SIZE; j++) 
      for (int k = 0; k < SIZE; k++) 
      { 
       res[i][j] += a[i][k] * b[k][j]; 
      } 

    for (int i = 0; i < SIZE; i++) 
     for (int j = 0; j < SIZE; j++) 
      a[i][j] = res[i][j]; 
} 

//Caluclate a^n and print result into matrix res 
void pow(long a[SIZE][SIZE], long n, long res[SIZE][SIZE]) 
{ 
    one(res); 

    while (n > 0) { 
     if (n % 2 == 0) 
     { 
      mul(a, a); 
      n /= 2; 
     } 
     else { 
      mul(res, a); 
      n--; 
     } 
    } 
} 

番号の等価見つけてください：

long power(long num, long pow) 
{ 
    if (pow == 0) return 1; 
    if (pow % 2 == 0) 
     return power(num*num, pow/2); 
    else 
     return power(num, pow - 1) * num; 
}