Name
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+$\kappa$), where n denotes the number of nodes, e the number of edges, q the number of maximal cliques, and $\kappa$ 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. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1137/S0895479803386354 | SIAM J. Matrix Analysis Applications |
Keywords | Field | DocType |
cholesky factorization,sparse matrices,sparse matrix | Combinatorics,Mathematical optimization,Clique,Parallel algorithm,Factorization,Time complexity,Numerical linear algebra,Sparse matrix,Mathematics,Computation,Cholesky decomposition | Journal |
Volume | Issue | ISSN |
27 | 1 | 0895-4798 |
Citations | PageRank | References |
0 | 0.34 | 17 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Wen-Yang Lin | 1 | 399 | 35.72 |
| chuenliang chen | 2 | 1 | 1.03 |