algorithm - 行列指数の高速な方法はありますか？

Question

^{単純な分割統治アルゴリズムよりも、M n}（Mは行列、nは整数）を計算するための行列指数関数の高速な方法はありますか？

Answer 1

行列を固有値と固有ベクトルに因数分解できます。次に、

M = V^-1 * D * V

ここで、Vは固有ベクトル行列、Dは対角行列です。これをN乗すると、次のようになります。

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

すべてのVおよびV^-1項がキャンセルされるためです。

Dは対角線であるため、完全な行列ではなく、一連の（実）数をn乗する必要があります。nの対数時間でそれを行うことができます。

固有値と固有ベクトルの計算はr^3です（ここで、rはMの行/列の数です）。rとnの相対的なサイズによっては、これが速い場合とそうでない場合があります。

Answer 2

オイラー高速パワーアルゴリズムを使用するのは非常に簡単です。次のアルゴリズムを使用します。

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

Answer 3

二乗による指数は、行列の高乗を得るために頻繁に使用されます。

Answer 4

行列形式でFibbonacciシーケンスを計算するために使用されるアプローチをお勧めします。AFAIK、その効率はO（log（n））です。