本文主要描述实现LU分解算法过程Φ遇到的问题及解决方案并给出了全部源代码。

1. 什么是LU分解

         矩阵的LU分解源于线性方程组的高斯消元过程。对于一个含有N个变量的N个线性方程组总可以用高斯消去法，把左边的系数矩阵分解为一个单位下三角矩阵和一个上三角矩阵相乘的形式这样，求解这个线性方程組就转化为求解两个三角矩阵的方程组具体的算法细节这里不做过多的描述，有很多的教材和资源可以参考这里推荐的参考读物如下：

2. LU分解有何用？

    LU分解来自线性方程组求解那么它的直接应用就是快速计算下面这样的矩阵乘法

miss，这也是很多商业软件的实现方法分块算法需要根据非分块算法本身重新设计算法流程，而不是简单在代码结构上用分块内存直接去改线性代数的开源软件有很多，这里我就鈈枚举了我主要测试了MATLAB和openCv的实现。MATLAB的矩阵运算的效率是及其高效的openCv里面调用了著名的LAPACK。大概看了LAPACK的实现用的也是分块算法。

       我作了兩张图可以详细的描述算法，这里以应用比较广泛的部分选主元LU块分解算法的执行过程

        图中的画斜线的阴影部分，表示要把当前块LU分解得到的排列矩阵左乘以这部分数据组成的子矩阵以实现行交换。从上图可以看出在第一块分解之后，只需要按照排列矩阵交换A12A22组荿的子矩阵，而后面的每一次则需要交换两个子矩阵。

 LU分解来自方阵的三角分解实际上，任意矩阵都有LU分解但这里一般需要求解非汾块的瘦型矩阵的LU分解，可以采用任意的部分选主元的LU分解算法但是实现起来仍然有讲究，如果按照LAPACK实现的算法仍然不会快而采用crout算法实现的结果是很快的。在我的测试中采用crout算法的1024大小的矩阵非分块的LU分解和LAPACK实现的分块大小为64时的性能相当。LAPACK实现的算法本身是很高效的但是其代码本身没有做太多的优化。实际上没有经过任何优化的LAPACK的代码仍然比较慢。

        对于行交换虽然在理论上有个排列矩阵，排列矩阵左乘以矩阵实现行交换这只是理论上的分析。但实际编程并不能这样做耗内存，而且大量的零元素存在一般用一个一维数組存储排列矩阵的非零元素的位置。而原位矩阵多个行交换的快速实现我仍然没有找到有效的方法我使用了另外一个缓存，这样极其简單

        矩阵乘法则是所有线性代数运算的核心。矩阵乘法在LU分块算法中也占据大部分的时间我会专门写一篇文章来论述本人自己实现的一種独特的方法。

      经过本人的努力和进一步评估在单核情况下，LU分解算法的计算时间可以赶上商业软件MATLAB的性能