Fast Exponentiation Matrix

Question

Esiste un metodo più veloce di esponenziazione matriciale per calcolare M^n (dove M è una matrice en è un intero) rispetto al semplice algoritmo di divisione e conquista.

Answer 1

È possibile calcolare la matrice in autovalori e autovettori. Quindi ottieni

M = V^-1 * D * V 

Dove V è la matrice autovettore e D è una matrice diagonale. Per sollevare questo all'ennesima potenza, si ottiene qualcosa di simile:

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

Perché tutto il V e^-1 termini V si annullano.

Dato che D è diagonale, è sufficiente generare un numero di numeri (reali) all'ennesima potenza, anziché a matrici complete. Puoi farlo in tempo logaritmico in n.

Calcolo di autovalori e autovettori è r^3 (dove r è il numero di righe/colonne di M). A seconda delle dimensioni relative di r e n, questo potrebbe essere più veloce o meno.

Answer 2

Exponentiation by squaring viene spesso utilizzato per ottenere alte potenze di matrici.

Answer 3

Vorrei raccomandare l'approccio utilizzato per calcolare la sequenza di Fibbonacci in matrix form. AFAIK, la sua efficienza è O (log (n)).

Answer 4

È molto semplice utilizzare l'algoritmo di Euler a potenza elevata. Usa l'algoritmo successivo.

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

Qui di seguito potete trovare equivalente per i numeri:

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