高斯消去法破坏了矩阵的稀疏性
我用高斯消去法去求解一个由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秒
前三个程序运行都十分缓慢，你们有同样问题吗？
我遇到过同样的问题，n*n的矩阵只有3n个非零元素，但越消越多，总的时间复杂度依然是O(n^3)，至今仍未找到优化方法
我后来放弃了求解精确解，改用迭代法求近似解，将时间复杂度降到了O(n*w*log^3(n))，其中w是近似解的精度位数 不要自己写代码了，去找点别人写的开源的代码，
这些问题，应该有很成熟的代码，不要浪费自己的智力与时间 O(n^3)也不算慢，还可以 A_b.zip文件里是矩阵A和向量b，COO格式。
shuoming.zip里有说明文件，还有一个COO格式文件读取程序，C语言好像是。
所有文件都来自于《超大规模稀疏线性方程组求解》贴的例子问题。
磁盘读写速度比内存访问慢了10倍以上。尽量规避磁盘读写次数。
页:
[1]