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

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秒

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

KeyTo9_Fans

我遇到过同样的问题，n*n的矩阵只有3n个非零元素，但越消越多，总的时间复杂度依然是O(n^3)，至今仍未找到优化方法

我后来放弃了求解精确解，改用迭代法求近似解，将时间复杂度降到了O(n*w*log^3(n))，其中w是近似解的精度位数

nyy

不要自己写代码了，去找点别人写的开源的代码，
这些问题，应该有很成熟的代码，不要浪费自己的智力与时间

lihpb00

O(n^3)也不算慢，还可以

ShuXueZhenMiHu

A_b.zip文件里是矩阵A和向量b，COO格式。
shuoming.zip里有说明文件，还有一个COO格式文件读取程序，C语言好像是。
所有文件都来自于《超大规模稀疏线性方程组求解》贴的例子问题。

raymond_lk

磁盘读写速度比内存访问慢了10倍以上。尽量规避磁盘读写次数。