On optimal reorderings of sparse matrices for parallel Cholesky factorizations
Resource
SIAM Journal on Matrix Analysis and Applications, vol. 27, pp. 24-45
Journal
SIAM Journal on Matrix Analysis and Applications
Pages
24-45
Date Issued
2005
Date
2005
Author(s)
W. Y. Lin
C. L. Chen
Abstract
The height of the elimination tree has long acted as the only criterion for deriving a suitable fill-preserving sparse matrix ordering for parallel factorization. Although the deficiency in adopting height as the criterion for all circumstances was well recognized, no research has succeeded in alleviating this constraint. In this paper, we extend the unit-cost fill-preserving ordering into a generalized class that can adopt various aspects in parallel factorization, such as computation, communication, and algorithmic diversity. We recognize and show that if any cost function satisfies two mandatory properties, called the independence and conservation properties, a greedy ordering scheme then generates an optimal ordering with minimum completion cost. We also present an efficient implementation of the proposed ordering algorithm. Incorporating various techniques, the complexity can be improved from O(n log n + e) to O(q log q + κ), where n denotes the number of nodes, e the number of edges, q the number of maximal cliques, and κ the sum of all maximal clique sizes in the filled graph. Empirical results show that the proposed algorithm can significantly reduce the parallel factorization cost without sacrificing much in terms of time efficiency. © 2005 Society for Industrial and Applied Mathematics.
SDGs
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
902.pdf
Size
296.75 KB
Format
Adobe PDF
Checksum
(MD5):f8fff2a7f78814d6b82f445670fc6bc7