高斯消去法破坏了矩阵的稀疏性

ShuXueZhenMiHu

我用高斯消去法去求解一个由1208个未知数和1208个线性方程组成的线性方程组。该方程组作为例子在《超大规模稀疏线性方程组求解》贴中给出了。
该方程组的系数矩阵是稀疏的。下图所示为该方程组的系数矩阵，每个黑点都代表一个非零元素。该系数矩阵共有12138个非零元素，占总元素的0.83%。


我使用高斯消去法求解这个线性方程组。下图为求解过程中，在某一时间节点，系数矩阵的状态。
同样每个黑点代表一个非零元素。从图中可以看出，消元过程并没有结束。事实上，在该时间节点，求解程序正在使用矩阵的第126行对第154行进行消元。


从图中可以看出，系数矩阵中的非零元素变多了。在这一时间节点，系数矩阵共有37251个非零元素。
为此可以得出结论，随着消元过程的继续，非零元素将变得越来越多，系数矩阵将不再稀疏。换句话说，高斯消去法会破坏矩阵的稀疏性。

我使用高斯消去法作为算法，编写了四个求解程序，分别称为程序一，程序二，程序三，程序四。这四个程序在高斯消去法的实现上略有区别：
程序一使用的是大数数据结构，它将求解的线性方程组的系数矩阵放在内存中，消元过程全在内存中进行；
程序二同样使用大数数据结构，但是它将求解的线性方程组的系数矩阵放在数据库中(mdb)。消元过程中的行交换操作在数据库中完成，消元过程的行替换操作在内存中完成。这个操作首先从数据库中读取数据并放到内存中，运算结束后再将运算结果写到数据库中；
程序三使用双精度数据结构进行计算，它同样将求解的线性方程组的系数矩阵放到数据库中(mdb)。它消元过程的实现方法与程序二一致， 只不过读取和存储的是双精度类型的数据；
程序四同样使用双精度数据结构进行计算，它将求解的线性方程组的系数矩阵放到内存中，消元过程全部在内存中完成。

为了测试这四个实现的效率，我还是使用的上面的线性方程组。在下面的表格，我给出了四个实现程序的运行效率情况

四个求解程序的效率
	程序一（大数数据结构+内存）	程序二（大数数据结构+mdb）	程序三（double数据结构+mdb）	程序四（double数据结构+内存）
消元到126行（155行）	17小时59分	22小时53分	消元到170行，大约用时8小时	1秒
消元到136行（419行）	34小时43分	44小时8分		1秒
	消元过程的下降阶段无法完成	消元过程的下降阶段无法完成	消元过程的下降阶段无法完成	消元过程的下降阶段用时24秒，总用时38秒

前三个程序运行都十分缓慢，你们有同样问题吗？