找回密码
 欢迎注册
查看: 179|回复: 5

[分享] 高斯消去法破坏了矩阵的稀疏性

[复制链接]
发表于 2024-11-23 11:41:56 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

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

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

从图中可以看出,系数矩阵中的非零元素变多了。在这一时间节点,系数矩阵共有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秒
  


前三个程序运行都十分缓慢,你们有同样问题吗?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2024-11-23 23:01:57 | 显示全部楼层
我遇到过同样的问题,n*n的矩阵只有3n个非零元素,但越消越多,总的时间复杂度依然是O(n^3),至今仍未找到优化方法

我后来放弃了求解精确解,改用迭代法求近似解,将时间复杂度降到了O(n*w*log^3(n)),其中w是近似解的精度位数
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2024-11-25 09:55:48 | 显示全部楼层
不要自己写代码了,去找点别人写的开源的代码,
这些问题,应该有很成熟的代码,不要浪费自己的智力与时间
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2024-11-26 16:02:06 | 显示全部楼层
O(n^3)也不算慢,还可以
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2024-11-27 10:06:36 | 显示全部楼层
A_b.zip文件里是矩阵A和向量b,COO格式。
shuoming.zip里有说明文件,还有一个COO格式文件读取程序,C语言好像是。
所有文件都来自于《超大规模稀疏线性方程组求解》贴的例子问题。

A_b.zip

90.21 KB, 下载次数: 0, 下载积分: 金币 -1 枚, 经验 1 点, 下载 1 次

shuoming.zip

227.31 KB, 下载次数: 0, 下载积分: 金币 -1 枚, 经验 1 点, 下载 1 次

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 6 天前 | 显示全部楼层
磁盘读写速度比内存访问慢了10倍以上。尽量规避磁盘读写次数。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-12-8 20:43 , Processed in 0.028938 second(s), 19 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表