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

Is there any faster method of matrix exponentiation to calculate Mⁿ (where M is a matrix and n is an integer) than the simple divide and conquer algorithm?

您可以将矩阵分解为特征值和特征向量。然后你得到

M = V * D * V^-1

其中 V 是特征向量矩阵，D 是对角矩阵。将此值提高到 N 次方，您会得到如下结果：

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

因为所有 V 和 V^-1 项都取消了。

由于 D 是对角线，因此您只需计算一堆（实数）数字的 n 次方，而不是完整的矩阵。您可以在 n 的对数时间内完成此操作。

计算特征值和特征向量为r^3（其中r是M的行/列数）。根据 r 和 n 的相对大小，这可能会更快，也可能不会。