| 稀疏三角矩阵线性系统的基于树结构并行求解 |
| |
| 引用本文： | 李程,田新民,王鼎兴,郑纬民. 稀疏三角矩阵线性系统的基于树结构并行求解[J]. 软件学报, 1995, 6(8): 479-485 |
| |
| 作者姓名： | 李程 田新民 王鼎兴 郑纬民 |
| |
| 作者单位： | 清华大学计算机科学与技术系,北京,100084;清华大学计算机科学与技术系,北京,100084;清华大学计算机科学与技术系,北京,100084;清华大学计算机科学与技术系,北京,100084 |
| |
| 基金项目： | 本研究受到国家自然科学基金和国家863高技术项目资助. |
| |
| 摘 要： | 本文分析了大型稀疏矩阵线性方程组直接法求解的回代过程．基于改进的树结构（Ｍ—ｔｒｅｅ），提出了一种新的面向分布存储多机系统的稀疏三角矩阵线性系统并行Ｆｏｒｗａｒｄ求解算法ＭＰＦＳ．文中讨论了Ｍ—ｔｒｅｅ的结构特征，并将所提出的并行求解算法与基于Ｅｌｉｍｉｎａｔｉｏｎ—ｔｒｅｅ求解算法进行了分析和比较．结果表明，ＭＰＦＳ算法不仅适用于更多的稀疏矩阵系统，而且在求解过程中可以开发Ｅｌｉｍｉｎａｔｉｏｎ—ｔｒｅｅ算法不能开发的计算并行性，从而使求解性能得到显著改进．
|
| 关 键 词： | 分布存储多机系统 稀疏三角矩阵线性系统 Cholesky分解 消元树 |
| 收稿时间： | 1993-12-26 |
| 修稿时间： | 1994-04-21 |
M-TREE BASED PARALLEL ALGORITHM FOR SOLVING SPARSE TRIANGULAR SYSTEM ON DISTRIBUTED MEMORY MULTIPROCESSOR SYSTEMS |
| |
| Li Cheng,Tian Xinmin,Wang Dingxing and Zheng Weimin. M-TREE BASED PARALLEL ALGORITHM FOR SOLVING SPARSE TRIANGULAR SYSTEM ON DISTRIBUTED MEMORY MULTIPROCESSOR SYSTEMS[J]. Journal of Software, 1995, 6(8): 479-485 |
| |
| Authors: | Li Cheng Tian Xinmin Wang Dingxing Zheng Weimin |
| |
| Abstract: | 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. |
| |
| Keywords: | Distributed memory multiprocessor system sparse triangular system sparse Cholesky factorization elimination-tree. |
| 本文献已被 CNKI 维普 等数据库收录！ |
| 点击此处可从《软件学报》浏览原始摘要信息 |
|
点击此处可从《软件学报》下载全文 |
