
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 systemsboth 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