求解线性方程组的顺序算法和并行算法的理论时耗估价
The Theoretical Cost of Sequential and Parallel Algorithms for Solving Linear System of Equations
-
摘要: 本文讨论了求解密集型线性方程组的两种并行算法。这两种算法都在下上单元(LU)分解。法的基础上使用了前向和后向置换进行的。这些算法在数值上是稳定的,并在顺序平衡机上用各种处理程序进行试验,都得到良好效果。
-
关键词:
- 下上单元(LU)分解法 /
- 前向和后向置换 /
- 多指令多数据程序(MIMD程序) /
- 多任务 /
- 理论时耗估价
Abstract: In this paper two parallel algorithms for solving dense linear equations arediscussed. The algorithms are based on LU-decomposition followed by forward andbackward substitutions. The algorithms are numerically stable and have been testedon the Sequent Balance Machine with efficient utilization of all processors.-
Key words:
- LU decomposition /
- forward and backward substitutions /
- MIMD machine /
- multi-tasking /
- theoretical cost
-
[1] A.Sameh and D.J.Kuck,On stable linear system solver,J.Assoc.Comput.Mach.,25(1978),81-89. [2] R.E.Lord,J.S.Kowalik and S.P.Kumar,Solving linear algebraic equation on MIMD computer,J.Assoc.Comput.Mach.,30,1(1983),l03-117. [3] M.J.Quinn,Designing EJjicient Algorithm for Parallel Computers,McGraw-Hill International Editions,Computer Science Series(1988). [4] G.J.Davies,Column LU Factorization with Partial Pivoting on a Hypercube Multiprocessors,Technical Report ORNL-6219,Mathematical Science,Oak Ridge,TN37831(1985). [5] S.H.Abbas,Parallel Algorithms of Linear Systems and Initial Value Problems,Ph.D Thesis,University of Liverpool(1990).
计量
- 文章访问数: 1710
- HTML全文浏览量: 105
- PDF下载量: 504
- 被引次数: 0