问题描述
有没有比简单的分而治之算法更快的矩阵求幂方法来计算M (其中M是矩阵，n是整数)?
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?
推荐答案
您可以将矩阵分解为特征值和特征向量.然后你得到
You could factor the matrix into eigenvalues and eigenvectors. Then you get
M = V^-1 * D * V
其中V是特征向量矩阵，D是对角矩阵.要将其提升到第N次方，您将得到类似的东西:
Where V is the eigenvector matrix and D is a diagonal matrix. To raise this to the Nth power, you get something like:
M^n = (V^-1 * D * V) * (V^-1 * D * V) * ... * (V^-1 * D * V)
= V^-1 * D^n * V
因为所有V和V ^ -1项都抵消了.
Because all the V and V^-1 terms cancel.
由于D是对角线，因此只需要将一堆(实数)数字提高到n次幂即可，而不是完整矩阵.您可以在n的对数时间内完成该操作.
Since D is diagonal, you just have to raise a bunch of (real) numbers to the nth power, rather than full matrices. You can do that in logarithmic time in n.
计算特征值和特征向量为r ^ 3(其中r是M的行数/列数).取决于r和n的相对大小，这可能更快，也可能更快.
Calculating eigenvalues and eigenvectors is r^3 (where r is the number of rows/columns of M). Depending on the relative sizes of r and n, this might be faster or not.
这篇关于有什么快速的矩阵求幂方法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！