最近写了个C程序来计算矩阵的幂,代码如下:
/* 矩阵幂运算,例如
1 2 1 0
3 4 ^ 0 => 0 1
1 2 1 2
3 4 ^ 1 => 3 4
1 2 199 290
3 4 ^ 4 => 435 634
*/
uint32_t* matrix_pow(const uint32_t* matrix, uint32_t exponent) {
uint32_t* result = new_matrix();
if (exponent == 0){
result = identity_matrix();
} else{
result = cloned(matrix);
for (int c = 1; c < exponent; c++){
result = matrix_mul(result, matrix);
}
}
return result;
}
其中, exponent是幂次,cloned()方法是复制矩阵,identity_matrix()返回一个单位矩阵,matrix_mul()用来计算两个计算的乘积。
不知有哪些优化的方法(可以完全改写上面的程序),可以使上面的函数效率更高,可以使用多线程,分治等。
主要还是优化时间复杂度吧,主要是使用快速幂
uint32_t matrix_pow(const uint32_t matrix, uint32_t exponent) {
uint32_t* result = identity_matrix();
while(exponent)
{
if(exponent&1) result=matrix_mul(result, matrix);
matrix=matrix_mul(matrix , matrix);
exponent>>=1;
}
return result;
}
这样只要进行log(exponent)次矩阵乘法即可;
另外不知道你的matrix_mul是怎么实现的,如果一般方法是O(n^3)的,改用Strassen算法则仅需O(n^2.81)复杂度即可;
进行如上改进之后,再考虑通用的优化方法,对于矩阵乘法常用的是SIMD指令集优化,矩阵乘法部分可以嵌入汇编优化
版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。