是否有任何更快的矩阵求幂方法来计算M^n(其中M是一个矩阵,n是一个整数)比简单的除法和征服算法。快速矩阵求幂
快速矩阵求幂
回答
您可以将矩阵分解为特征值和特征向量。那么你得到
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的相对大小,这可能会更快或者不更快。
据我所知,这种方法与Squaring的Exponentiation具有相同的复杂度。那么有没有更快的方法? –
@AkashdeepSaluja:这比通过平方幂取幂更快。这是O(r^3)时间,平方的指数是O(r^3 logn)时间。 –
为更好地解释上述方法http://www.google.co.in/url?sa=t&rct=j&q=pdf%20nth%20power%20of%20matrix&source=web&cd=1&cad=rja&ved=0CCAQFjAA&url=http% 3A%2F%2Fwww.qc.edu.hk%2Fmath%2FTeaching_Learning%2FNth%2520power%2520of%2520a%2520square%2520matrix.pdf&ei = Jf9JULrwFsi8rAejh4C4DQ&usg = AFQjCNE7yqQce5jdtyyVLFpSZmYUnoWyVA –
Exponentiation by squaring经常用来获得矩阵的高次幂。
我会推荐用于计算matrix form中Fibbonacci序列的方法。 AFAIK,其效率是O(log(n))。
您必须乘以矩阵相乘的成本。整体运行时间为O(n^3 log n)。 – saadtaame
使用欧拉快速幂算法很简单。使用下一个算法。
#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;
}
- 1. horner算法 - 快速求幂
- 2. 快速求幂的实现
- 3. Python中的矩阵求幂
- 4. Numpy矩阵求幂给出负值
- 5. 线性递归使用矩阵求幂
- 6. 矩阵幂方法
- 7. 快速大矩阵生成
- 8. 快速访问矩阵
- 9. 快速矩阵乘法
- 10. 快速矩阵查找
- 11. 快速高效上对角矩阵求逆
- 12. 在另一个矩阵中快速找到矩阵
- 13. 大型稀疏矩阵上的快速非负矩阵分解
- 14. 指数万用行快速访问矩阵矩阵
- 15. 复对称三对角矩阵的快速矩阵指数
- 16. 快速计算图像(或矩阵)
- 17. 快速加载矩阵[numpy的/爪哇]
- 18. 大量小矩阵的快速反演
- 19. 快速(稀疏)矩阵在MATLAB
- 20. 快速核心矩阵计算python
- 21. R - 矩阵产品的快速排序
- 22. 高效,快速的方式padarray矩阵
- 23. 在Numpy/Python中快速稀疏矩阵
- 24. 使稀疏矩阵快速地相乘
- 25. 快速读取整数的大矩阵
- 26. 矩阵RcppGSL的快速子集
- 27. 快速旋转/变换矩阵乘法
- 28. 快速访问的稀疏矩阵
- 29. 当值随时间变化时求幂矩阵
- 30. 萨姆我的总和^说明使用矩阵求幂
嘿,我发现了一个计算器只链接检查出来 http://stackoverflow.com/questions/12268516/matrix-exponentiation -using-fermats-theorem – 2012-09-07 04:57:52
Expokit是一个众所周知的用于执行矩阵求幂的包。 http://fortranwiki.org/fortran/show/Expokit – Sayan