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