| 摘要: |
| 本文分析了大型稀疏矩阵线性方程组直接法求解的回代过程．基于改进的树结构（Ｍ—ｔｒｅｅ），提出了一种新的面向分布存储多机系统的稀疏三角矩阵线性系统并行Ｆｏｒｗａｒｄ求解算法ＭＰＦＳ．文中讨论了Ｍ—ｔｒｅｅ的结构特征，并将所提出的并行求解算法与基于Ｅｌｉｍｉｎａｔｉｏｎ—ｔｒｅｅ求解算法进行了分析和比较．结果表明，ＭＰＦＳ算法不仅适用于更多的稀疏矩阵系统，而且在求解过程中可以开发Ｅｌｉｍｉｎａｔｉｏｎ—ｔｒｅｅ算法不能开发的计算并行性，从而使求解性能得到显著改进． |
| 关键词: 分布存储多机系统 稀疏三角矩阵线性系统 Cholesky分解 消元树 |
| DOI： |
| 分类号: |
| 基金项目:本研究受到国家自然科学基金和国家863高技术项目资助. |
|
| M-TREE BASED PARALLEL ALGORITHM FOR SOLVING SPARSE TRIANGULAR SYSTEM ON DISTRIBUTED MEMORY MULTIPROCESSOR SYSTEMS |
|
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. |
| Key words: Distributed memory multiprocessor system sparse triangular system sparse Cholesky factorization elimination-tree. |
