Fast Matrix Exponentiation

Question

간단한 나누기 및 정복 알고리즘보다 M^n (M은 행렬이고 n은 정수)을 계산하는 더 빠른 행렬 지수 방법이 있습니까?

Answer 1

행렬을 고유 값과 고유 벡터로 분해 할 수 있습니다. 그러면 얻을 수 있습니다.

여기서 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; 
}