快速矩阵幂 [英] Fast Matrix Exponentiation

问题描述

是否有矩阵幂的任何快速的方法来计算立方公尺n（其中，M是一个矩阵，n是一个整数）比简单分而治之算法

Is there any faster method of matrix exponentiation to calculate M^n ( 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屋！