algorithm - 有没有快速的矩阵求幂方法？

Question

有没有比简单的分治算法更快的矩阵求幂方法来计算 M ⁿ（其中 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

我会推荐用于以矩阵形式计算斐波那契数列的方法。AFAIK，它的效率是 O(log(n))。