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

Question

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

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

Answer 1

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

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

Answer 2

SIMD...

属于指令上的优化了...

你在哪个平台上运行，arm还是ia?