Accession Number : ADA288563

Title :   Performance Evaluation of a New Parallel Preconditioner.

Descriptive Note : Research rept.,

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Gremban, Keith D. ; Miller, Gary L. ; Zagha, Marco

PDF Url : ADA288563

Report Date : OCT 1994

Pagination or Media Count : 34

Abstract : Solution of partial differential equations by either the finite element or the finite difference methods often requires the solution of large, sparse linear systems. When the coefficient matrices associated with these linear systems are symmetric and positive definite, the systems are often solved iteratively using the preconditioned conjugate gradient method. We have developed a new class of preconditioners, which we call support tree preconditioners, that are based on the connectivity of the graphs corresponding to the coefficient matrices of the linear systems. These new preconditioners have the advantage of being well-structured for parallel implementation, both in construction and in evaluation. In this paper, we evaluate the performance of support tree preconditioners by comparing them against two common types of preconditioners: those arising from diagonal scaling, and from the incomplete Cholesky decomposition. We solved linear systems corresponding to both regular and irregular meshes on the Cray C-90 using all three preconditioners and monitored the number of iterations required to converge, and the total time taken by the iterative processes. We show empirically that the convergence properties of support tree preconditioners are similar, and superior in many cases, to those of incomplete Cholesky preconditioners, which in turn are superior to those of diagonal scaling. Support tree preconditioners require less overall storage, less work per iteration, and yield better parallel performance than incomplete Cholesky preconditioners. In terms of total execution time, support tree preconditioners outperform both diagonal scaling and incomplete Cholesky preconditioners. Hence, support tree preconditioners provide a powerful, practical tool for the solution of large sparse systems of equations on vector and parallel machines.

Descriptors :   *ALGORITHMS, *PARALLEL PROCESSING, MATHEMATICAL MODELS, LINEAR SYSTEMS, MATRICES(MATHEMATICS), FINITE ELEMENT ANALYSIS, GRAPHS, PARALLEL PROCESSORS, PROBLEM SOLVING, FINITE DIFFERENCE THEORY, PARTIAL DIFFERENTIAL EQUATIONS, CONVERGENCE, NUMERICAL METHODS AND PROCEDURES, SPARSE MATRIX, ITERATIONS, DECOMPOSITION.

Subject Categories : Computer Programming and Software
      Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE