有什么快速的矩阵求幂方法? [英] Is there any fast method of matrix exponentiation?

问题描述

有没有比简单的分而治之算法更快的矩阵求幂方法来计算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.

这篇关于有什么快速的矩阵求幂方法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！