对于一个矩阵

这个平方和计算在某些机器学习的算法中、或者特殊的优化问题中都会涉及到。

通常而言前面的公式就给出了计算的方法无论怎么做都会涉及到对矩阵中的每一个元素进行平方然后求和。

O(m*n)

当然还有可能会有一些特殊的优化方法比如矩阵的特殊性质可以通过一些特殊的方法来计算这里不做考虑。

最后就是并行指令集的使用比如SIMD指令集这里也不进行相关的讨论。

下面就主要是对在Matlab中实现矩阵平方和的几种方法进行比较。

其实比较的是Matlab中访问矩阵元素的方式的性能差异。

其中最重要的就是所谓的基线方法。

这个方法通常选择一个最简单/直观的方法便于抓住算法中的核心要素。

这种研究办法是一种常见的研究方法。

例如在优化算法中通常选择格子搜索或者随机搜索作为基线方法。

提出一种新的方法通常希望能够对比基线方法有更好的性能并且这种性能提升是显著的。

此外也会结合新算法与基线算法的执行过程来解释算法优势的原理这就是一般算法研究文章中非常重要的理论分析。

function

end上面这个最为直观的算法就是对矩阵的每一行进行遍历然后对每一行的每一个元素进行平方然后求和。

function

2;endendend考虑到Matlab能够直接索引列我们就可以考虑对每列进行循环直接对列进行操作。

或者换成对行进行操作。

下面几个算法就是行、列操作的形式这里又有一个小小的差别就是使用更多内存来直接进行向量加法最后调用sum求和。

\mathcal{O}(n)

2);endend接下来我们利用矩阵的向量访问方式来构造一个算法。

function

2;endend此外sum函数也提供了两个算法变体一个是调用两次默认对行求和

function

end还可以把sum与矩阵列向量访问形式结合起来构成一种算法。

function

end最后还是利用矩阵的向量展开方式就是两个其实一样的算法因为dot函数内部就是调用矩阵乘法。

function

end这些算法都非常平常但是通过上面的联系也能提升我们对Matlab的矩阵操作的理解。

性能比较

时间性能比较一般可以直接利用timeit函数来完成这个函数会对一个函数进行多次调用然后求中位数。

Benchmark

对每一个n进行测试直接采用for循环不使用arrayfunfor

1:numel(n)A

我们把前面的算法代码和上面的性能比较代码放在一个benchobjs的目录中就构成一个namespace命名空间通过import

Matlab

同时把线型标签也存储在一个cell数组中这样可以方便的对这些线型进行遍历%%

calculation

这里试图考虑到多线程的影响目前在12核心的及其上进行了不同线程数的测试

Visualize

endlegend(cellfun((f)cellref(split(func2str(f),

.),

../matlab-img/compareMatrixSquareSum-time.png,

...

endlegend(cellfun((f)cellref(split(func2str(f),

.),

...functions(2:numel(functions)),

UniformOutput,

../matlab-img/compareMatrixSquareSum-acc.png,

...

endlegend(cellfun((f)cellref(split(func2str(f),

.),

...functions(2:numel(functions)

2),

../matlab-img/compareMatrixSquareSum-acc-2.png,...

Resolution,

首先不同算法的性能有一定差异。

基本上算法分为两组也可以视为三组。

第一组是基线算法对每一行进行遍历然后对每一个元素进行平方然后求和。

第二组是向量展开访问并调用矩阵乘法mtimes直接调用BLAS二进制库的两个算法性能相当。

其他就是各种循环的组合以及sum函数的组合。

向量展开矩阵乘法的算法在1000~10000的规模下性能均有显著提升从15倍到40倍。

除去基线算法和向量化算法其他算法的关系较为复杂但是也能通过进行列访问、部分向量化来获得几倍的性能提升。

进行算法开发一定要按照基线算法、算法优化的思路来考虑。

对算法的效率进行比较最好选择不同的规模来分析问题。

加速比是一个很好的指标能够直观的看出算法的性能提升。