Szybka macierzowa potęgacja

Question

Czy istnieje jakakolwiek szybsza metoda potęgowania macierzy do obliczania M^n (gdzie M jest macierzą, a n jest liczbą całkowitą) niż prosty algorytm dzielenia i podbijania.

Answer 1

Można dokonać analizy macierzy na wartości własne i wektory własne. Otrzymasz wtedy:

M = V^-1 * D * V 

Gdzie V jest macierzą wektorów własnych, a D jest macierzą diagonalną. Aby podnieść tę wartość do N-tej potęgi, otrzymujesz coś takiego:

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

Ponieważ wszystkie warunki V i V^-1 znoszą się.

Ponieważ D jest przekątną, wystarczy podnieść kilka (rzeczywistych) liczb do n-tej mocy, zamiast pełnych macierzy. Możesz to zrobić w logarytmicznym czasie w n.

Obliczanie wartości własnych i wektorów własnych to r^3 (gdzie r jest liczbą rzędów/kolumn M). W zależności od względnych rozmiarów r i n, może to być szybsze lub nie.

Answer 2

Exponentiation by squaring jest często używany do uzyskania wysokiej mocy matryc.

Answer 3

Polecam podejście stosowane do obliczenia sekwencji Fibbonacci w matrix form. AFAIK, jego wydajność to O (log (n)).

Answer 4

To dość prosty w obsłudze algorytm szybkiej mocy Eulera. Użyj następnego algorytmu.

#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--; 
     } 
    } 
} 

Poniżej znaleźć odpowiednik dla liczb:

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; 
}