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

开发者社区> 问答> 正文

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

2016-06-07 21:04:09 1862 1

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

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

C++
取消 提交回答
全部回答(1)
  • a123456678
    2019-07-17 19:31:02

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

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

    0 0
相关问答

40

回答

[@徐雷frank][¥20]什么是JAVA的平台无关性

大河人家 2018-10-29 23:55:20 144699浏览量 回答数 40

53

回答

OSS C/C++ SDK分享交流区

否极泰来 2015-06-15 17:05:09 48056浏览量 回答数 53

3

回答

安全狗VS云锁

ap0453m0g 2014-11-09 16:20:00 15590浏览量 回答数 3

10

回答

windows版本oss c sdk如何上传和下载包含中文名的文件

yjseu 2015-11-20 17:14:30 15948浏览量 回答数 10

1

回答

【开源分享】-4期 Notepads 一款国人开发的UWP超好用文本编辑器

montos 2020-05-06 13:34:43 28966浏览量 回答数 1

58

回答

技术入门问答集锦,涉及多种技术方向,解决新人学习困惑

管理贝贝 2016-08-03 10:13:27 52744浏览量 回答数 58

4

回答

上传到OSS的文件md5hash值如何获取?!!

asker 2015-08-05 16:52:10 21231浏览量 回答数 4

38

回答

【论战!】访问压力大,你会选择升级ECS配置or选择再买1台ECS做负载均衡SLB

qilu 2014-12-25 17:32:40 20806浏览量 回答数 38

12

回答

电信云VS阿里云

米蛋 2013-12-13 23:25:52 15981浏览量 回答数 12

23

回答

【云服务器分享】网站访问速度快才是硬道理

dreamdoo 2012-10-15 10:15:02 85352浏览量 回答数 23
+关注
0
文章
14879
问答
问答排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载