Memory-adaptive parallel sparse Cholesky factorization

Author

Eswar, Kalluri ; Huang, Chua-Huang ; Sadayappan, P.

Author_Institution

Dept. of Comput. & Inf. Sci., Ohio State Univ., Columbus, OH, USA

fYear

1994

fDate

23-25 May 1994

Firstpage

317

Lastpage

323

Abstract

The problem of Cholesky factorization of sparse positive-definite matrices on distributed-memory multiprocessors is considered. A column-based algorithm with the ability to adapt to the amount of memory available on each processor is presented. Exploiting the available memory allows the local computation on each processor to be ordered so that good local efficiencies and dynamic load balance are achieved. A proof that this distributed algorithm is deadlock-free is given. Experimental results of an implementation of this algorithm on an Intel iPSC/860 multiprocessor system are reported

Keywords

concurrency control; distributed memory systems; mathematics computing; matrix algebra; parallel algorithms; resource allocation; Cholesky factorization; Intel iPSC/860 multiprocessor system; column-based algorithm; deadlock-free algorithm; distributed algorithm; distributed-memory multiprocessors; dynamic load balance; local efficiencies; memory-adaptive parallel algorithm; ordered local computation; sparse positive-definite matrices; Aggregates; Data structures; Distributed algorithms; Distributed computing; Information science; Multiprocessing systems; Partitioning algorithms; Sparse matrices; System recovery;

fLanguage

English

Publisher

ieee

Conference_Titel

Scalable High-Performance Computing Conference, 1994., Proceedings of the

Conference_Location

Knoxville, TN

Print_ISBN

0-8186-5680-8

Type

conf

DOI

10.1109/SHPCC.1994.296660

Filename

296660