Improved Krylov subspace methods for large and sparse linear systems
215.
L. T. Yang and R. P. Brent,
Improved Krylov subspace methods for large and sparse linear systems
on Block Synchronous Parallel architectures,
Proc. IPDPS03 (Nice, France, April 2003),
IEEE Computer Society, 2003, 260b.
Paper:
available from
IEEE Computer Society.
Abstract
In this paper, we summarize some recent advances in
improved Krylov subspace methods for the solution of large and sparse
linear systems of equations with unsymmetric coefficient matrices. The
proposed methods combine elements of numerical stability and parallel
algorithm design without increasing computational costs too much. The
methods have the following common feature: all are derived so that
matrix-vector multiplication, inner products and vector updates of a single
iteration step are independent, and communication time required for inner
product can be overlapped efficiently with computation time of vector
updates. Therefore, the cost of global communication which represents the
performance bottleneck can be significantly reduced.
Here, the Bulk Synchronous Parallel (BSP) model is used to design fully
efficient, scalable and portable parallel proposed algorithms and to provide
accurate performance prediction of the algorithms for a wide range of
architectures including the Cray T3D, the Parsytec, and a cluster of
workstations connected by an Ethernet. This performance model uses only a
few system dependent parameters based on a simple cost model to provide
useful insight into the time complexity of the methods. The theoretical
performance predictions are compared with some preliminary timing results
for a numerical application from ocean flow simulation.
Go to next publication
Return to Richard Brent's index page