Accession Number : ADA323260

Title :   Scalable Parallel Algorithms for Sparse Linear Systems,

Corporate Author : ARMY HIGH PERFORMANCE COMPUTING RESEARCH CENTER MINNEAPOLIS MN

Personal Author(s) : Gupta, Anshul ; Karypis, George ; Kumar, Vipin

PDF Url : ADA323260

Report Date : 01 APR 1997

Pagination or Media Count : 6

Abstract : Large sparse linear systems occur in many scientific and engineering applications encountered in military and civilian domains. Such systems are typically solved using either iterative or direct methods. We are developing parallel formulations of computationally intensive algorithms that underly these methods. Direct methods for solving sparse linear systems are important because of their generality and robustness. For linear systems arising in certain applications, such as linear programming and some structural engineering applications, they are the only feasible methods. Although highly parallel formulations of dense matrix factorization are well known, it has been a challenge to implement efficient sparse linear system solvers using direct methods, even on moderately parallel computers. We have recently achieved a breakthrough in developing a highly parallel sparse Cholesky factorization algorithm that substantially improves the state of the art in parallel direct solution of sparse linear systems-both in terms of scalability and overall performance. Experiments have shown that this algorithm can easily speedup Cholesky factorization by a factor of at least a few hundred up to 1024 processors, and achieve levels of performance that were unheard of and unimaginable for this problem until very recently.

Descriptors :   *ALGORITHMS, *LINEAR SYSTEMS, *LINEAR PROGRAMMING, STATE OF THE ART, COMPUTERS, FORMULATIONS, EFFICIENCY, PARALLEL PROCESSING, SCALING FACTOR, ITERATIONS, STRUCTURAL ENGINEERING.

Subject Categories : Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE