Reliable parallel solution of bidiagonal systems |
| |
Authors: | Ilan Bar-On Mauro Leoncini |
| |
Affiliation: | (1) Department of Chemistry, Technion 32000, Haifa, Israel; e-mail: baron@cs.technion.ac.il, IL;(2) Dipartimento di Informatica, Università di Pisa, Corso Italia 40, 56125 Pisa, Italy; e-mail: leoncini@di.unipi.it, IT |
| |
Abstract: | Summary. This paper presents a new efficient algorithm for solving bidiagonal systems of linear equations on massively parallel machines. We use a divide and conquer approach to compute a representative subset of the solution components after which we solve the complete system in parallel with no communication overhead. We address the numerical properties of the algorithm in two ways: we show how to verify the à posteriori backward stability at virtually no additional cost, and prove that the algorithm is à priori forward stable. We then show how we can use the algorithm in order to bound the possible perturbations in the solution components. Received March 13, 1998 / Revised version received December 21, 1999 / Published online June 20, 2001 |
| |
Keywords: | Mathematics Subject Classification (1991): 65F05 65G10 65Y05 |
本文献已被 SpringerLink 等数据库收录! |
|