C程序:如何优化矩阵幂运算-问答-阿里云开发者社区-阿里云

开发者社区> 问答> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

C程序:如何优化矩阵幂运算

最近写了个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()用来计算两个计算的乘积。

不知有哪些优化的方法(可以完全改写上面的程序),可以使上面的函数效率更高,可以使用多线程,分治等。

展开
收起
a123456678 2016-06-07 21:04:09 2188 0
1 条回答
写回答
取消 提交回答
  • a123456678

    主要还是优化时间复杂度吧,主要是使用快速幂

    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指令集优化,矩阵乘法部分可以嵌入汇编优化

    2019-07-17 19:31:02
    赞同 展开评论 打赏
问答排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载