《稀疏矩阵直接法》PPT课件

《《稀疏矩阵直接法》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、7/19/2021稀疏矩阵直接解法7/19/2021www.naritech.cn稀疏矩阵1稀疏矩阵直接解法2UMFPACK3软件工程--结对编程47/19/2021www.naritech.cn稀疏矩阵基本参数稀疏性，对称性，非零元分布敏感性，病态矩阵条件数多种格式Harwell-BoeingExchangeFormat...测试集UFsparematrixcollectionHarwell-BoeingSparseMatrixCollection7/19/2021www.naritech.cn稀疏矩阵稀疏矩阵的广泛应用矩阵求解是数值计算的核心[1]稀疏矩

2、阵求解是数值计算的关键之一：偏微分方程，积分方程，特征值，优化…万阶以上densematrix不可行稀疏矩阵求解往往是资源瓶颈：时间瓶颈，内存、外存等瓶颈电力系统网络接线的特点决定了其计算用的节点矩阵是稀疏的7/19/2021www.naritech.cn稀疏矩阵的存储稀疏矩阵的存储如何存储，减少内存占用率便于查找、赋值、计算常见存储方法三元组十字链表，双十字链表带宽存储，变带宽存储压缩存储（CRS,CCS)三角检索存储……7/19/2021www.naritech.cn稀疏矩阵存储CRS（CompressedRowStorage)按行压缩存储AN：按行存储

3、所有非零元AJ：按行存储每个非零元的列号AI：每行首个非零元在AN中的序号AN和AJ大小一样，需要足够大AI大小与矩阵行数一样AI[K+1]-AI[K]：第k行有几个非零元AN[AI[K]]~AN[AI[K+1]-1]：非零元的列号稀疏矩阵存储7/19/2021www.naritech.cnCCS（CompressedColumnStorage)按列压缩存储AN：按列存储所有非零元AJ：按列存储每个非零元的列号AI：每列首个非零元在AN中的序号AN和AJ大小一样，需要足够大AI大小与矩阵列数一样AI[K+1]-AI[K]：第k列有几个非零元AN[AI[K]]

4、~AN[AI[K+1]-1]：非零元的行号CCS可以看作是CRS的转置UMFPACK是CCS存储的7/19/2021www.naritech.cn稀疏矩阵存储状态估计中稀疏矩阵的存储采用CRS方式SE_LOCALCMN.INC：HP，jHP，iHPHQ，jHQ，iHQHPt，jHPt，iHPtHQt，jHQt，iHQtZZP，jZZP，iZZPZZQ，jZZQ，iZZQ上面前两列存储的大小是矩阵里所有非零元，在网络规模很大时需要注意这些数组的大小，越限时会有莫名其妙的问题发生7/19/2021www.naritech.cn稀疏矩阵存储基于STL的一种存储格式

5、行内非零元map列号，数据类型（int,float,double,complex,…）矩阵存储vector>动态存储进一步可以将map和vector封装为类，将元素级一些操作封装进类参考rtnet/GaussSubs.h,rtnet/GaussSubs.cpp（近期版本库已添加）稀疏矩阵求解结合稀疏矩阵特点选择合适解法稀疏性：带状化，随机化，分块化对称性/非对称性：需要考虑的几个问题：减少非零元的产生尽量让节点出线少的节点排在前面节点排序（行列式交换）：静态、半动态、动态保证数据精度保证计算

6、稳定性7/19/2021www.naritech.cn7/19/2021www.naritech.cn稀疏矩阵解法迭代法如何构造解Ax=b的有效迭代法？收敛性和收敛速度GMRES,BICG,…[2]直接法[3][4]线性方程组可以用直接解法，计算实践表明，对电力系统来说很有效。电力系统中常见的大型线性方程组的系数矩阵十分稀疏，直接解法的计算速度很快。与迭代法相比，没有收敛性问题。高斯消去LU分解数学库BLAS，LAPACK，UMFPACK，SuiteSparse稀疏矩阵直接法高斯消去法按列、按行消去全主元、列主元算法和解线性方程组相同消元过程会产生新的非零元

7、7/19/2021www.naritech.cn7/19/2021www.naritech.cn稀疏矩阵直接解法LU分解保持稀疏性（优于QR分解等）百万阶的矩阵的LU可在PC上求解。较高的稳定性（优于迭代法）[5]列选主元，代价较小(O())多种技巧处理病态矩阵可充分发挥CPU的效率（优于迭代法）flops>50%*CPU主频稀疏矩阵做LU分解后，其L,U矩阵仍然是稀疏的，在利用其做前代、回代求解时，只需要将稀疏存储的数据取出计算即可，可以极大的节省计算时间。UMFPACKUMFPACK是求解非对称稀疏线性方程Ax=b的函数库，使用非对称多波前法和直接稀疏L

8、U分解法，使用C语言编写。依赖Level-3的BLA