A reordering and mapping algorithm for parallel sparse Cholesky factorization

Author

Kumar, Bharat ; Eswar, Kalluri ; Sadayappan, P. ; Huang, C.-H.

Author_Institution

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

fYear

1994

fDate

23-25 May 1994

Firstpage

803

Lastpage

810

Abstract

A judiciously chosen symmetric permutation can significantly reduce the amount of storage and computation for the Cholesky factorization of sparse matrices. On distributed memory machines, the issue of mapping data and computation onto processors is also important. Previous research on ordering for parallelism has focussed on idealized measures like execution time on an unbounded number of processors, with zero communication costs. In this paper, we propose an ordering and mapping algorithm that attempts to minimize communication and performs load balancing of work among the processors. Performance results on an Intel iPSC/860 hypercube are presented to demonstrate its effectiveness

Keywords

distributed memory systems; hypercube networks; mathematics computing; matrix algebra; minimisation of switching nets; parallel algorithms; performance evaluation; resource allocation; Intel iPSC/860 hypercube; communication minimization; computation costs; distributed memory machines; load balancing; parallel sparse Cholesky factorization; performance evaluation; processor mapping algorithm; reordering algorithm; sparse matrices; storage costs; symmetric permutation; Clustering algorithms; Costs; Distributed computing; Hypercubes; Information science; Linear systems; Parallel processing; Processor scheduling; Symmetric matrices; Time measurement;

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.296723

Filename

296723