High Performance Preconditioned Iterative Methods
Department of Electrical and Computer Engineering, School of Engineering, Democritus University of Thrace, Xanthi, Greece
Matrix computations are of central importance in many engineering and scientific problems. Over the last decades the need for high performance computing has had an important effect on the design of modern computer systems. Hence research efforts were focused on the production of parallel computational methods for solving systems of linear equations. Such research work has been concentrated on multiprocessor and multi-computer systems.
Many of the well-known preconditioning methods are highly sequential and difficult to implement on parallel computers. Recently, the derivation of parallel numerical algorithms was the main objective for which several forms of approximate inverses of a given matrix, based on adaptive approximate factorization procedures have been proposed. The main motive for the derivation of the approximate inverses lies in the fact that they can be efficiently used in conjunction with explicit preconditioned iterative schemes which are appropriate for solving sparse linear systems on shared memory systems and distributed memory systems. The effectiveness of the Explicit Approximate Inverse Preconditioning schemata relies on the construction and use of efficient preconditioner factors in the sense that the preconditioners are close approximants to the coefficient matrix and are fast to compute in parallel. Since the explicit preconditioned iterative schemes are the computationally demanding part, there is a need to parallelize such methods, in order to achieve better performance.
The purpose of this work is a state-of-the-art review of explicit preconditioned iterative schemes, based on a class of parallel approximate inverse matrix algorithms for the efficient solution of finite element linear systems. The parallel construction of the approximate inverse is based on an anti-diagonal wave pattern computational approach, for overcoming the data dependencies. Further a modification of the antidiagonal wave pattern is introduced, for reducing the synchronization points and increasing the granularity. Additionally a "fish bone" computational approach with cyclic distribution of the processors satisfying an anti-diagonal data dependency, for computing classes of explicit approximate inverses, is introduced for symmetric multiprocessor systems. The Parallel Normalized Explicit Preconditioned Conjugate-Gradient type methods in conjunction with the approximate inverses are presented for symmetric multiprocessor systems and distributed memory systems.
The performance and applicability of the proposed methods on a threedimensional boundary value problem is discussed and numerical results are given for multiprocessor and multi-computer systems, using Open Multi-Processing (OpenMP) and Message Passing Interface (MPI) communication library respectively.