Accession Number : ADA326874

Title :   An Evaluation of Left-Looking, Right-Looking and Multifrontal Approaches to Sparse Cholesky Factorization on Hierarchical-Memory Machines,

Corporate Author : STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Rothberg, Edward ; Gupta, Anoop

PDF Url : ADA326874

Report Date : AUG 1991

Pagination or Media Count : 49

Abstract : In this paper we present a comprehensive analysis of the performance of a variety of sparse Cholesky factorization methods on hierarchical-memory machines. We investigate methods that vary along two different axel along the first axis, we consider three different high-level approaches to sparse factorization: left-looking, right-looking, and multifrontal. Along the second axis, we consider the implementation of each of these high-level approaches using different sets of primitives. The primitives vary based on the structures they manipulate. One important structure in sparse Cholesky factorization is a single column of the matrix. We first consider primitives that manipulate single columns. These are the most commonly used primitives for expressing the sparse Cholesky computation. Another important structure is the supemode, a set of columns with identical non-zero structure. We consider sets of primitives that exploit the supemodal structure of the matrix to varying degrees. We find that primitives that manipulate larger structures greatly increase the amount of exploitable data reuse, thus leading to dramatically higher performance on hierarchical-memory machines.

Descriptors :   *DISTRIBUTED DATA PROCESSING, *SYSTEMS ANALYSIS, ALGORITHMS, DATA MANAGEMENT, COMPUTER COMMUNICATIONS, MULTIPROCESSORS, SPARSE MATRIX, STRUCTURED PROGRAMMING, COMPUTER BENCHMARKING.

Subject Categories : Computer Systems
      Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE