稀疏三角矩阵线性系统的基于树结构并行求解  

M-TREE BASED PARALLEL ALGORITHM FOR SOLVING SPARSE TRIANGULAR SYSTEM ON DISTRIBUTED MEMORY MULTIPROCESSOR SYSTEMS

作　　者：李程 田新民[1] 王鼎兴[1] 郑纬民[1] 

机构地区：[1]清华大学计算机科学与技术系

出　　处：《软件学报》1995年第8期479-485,共7页Journal of Software

基　　金：国家自然科学基金;国家863高技术项目

摘　　要：本文分析了大型稀疏矩阵线性方程组直接法求解的回代过程．基于改进的树结构（Ｍ—ｔｒｅｅ），提出了一种新的面向分布存储多机系统的稀疏三角矩阵线性系统并行Ｆｏｒｗａｒｄ求解算法ＭＰＦＳ．文中讨论了Ｍ—ｔｒｅｅ的结构特征，并将所提出的并行求解算法与基于Ｅｌｉｍｉｎａｔｉｏｎ—ｔｒｅｅ求解算法进行了分析和比较．结果表明，ＭＰＦＳ算法不仅适用于更多的稀疏矩阵系统，而且在求解过程中可以开发Ｅｌｉｍｉｎａｔｉｏｎ—ｔｒｅｅ算法不能开发的计算并行性，从而使求解性能得到显著改进．In this paper, underlying the architecture of distributed memory.multiprocessors, a new forward substitution algorithm for the direct solution of large sparse linear system is presented. In the presented parallel algorithm, the Modified tree (M-tree) isproposed and adopted. Furthermore, a detailed comparison with the Elimination-tree based algorithm is carried out specially. The results show that more effective parallelism is exploited, and significant performance improvement can be obtained.

关 键 词：分布存储系统 树结构 稀疏相角矩阵 线性系统 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] O241.6[自动化与计算机技术—计算机科学与技术]