Name
Abstract | ||
|---|---|---|
We describe a fill-reducing ordering algorithm for sparse, nonsymmetric LU factorizations, where the pivots are restricted to the diagonal and are selected greedily. The ordering algorithm uses only the structural information. Most of the existing methods are based on some type of symmetrization of the original matrix. Our algorithm exploits the nonsymmetric structure of the given matrix as much as possible. The new algorithm is thus more complex than classical symmetric orderings, but we show that our algorithm can be implemented in space bounded by the number of nonzero entries in the original matrix, and has the same time complexity as the analogous algorithms for symmetric matrices. We provide numerical experiments to demonstrate the ordering quality and the runtime of the new ordering algorithm. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1137/050637315 | SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS |
Keywords | Field | DocType |
sparse nonsymmetric matrices,linear equations,ordering methods | Discrete mathematics,Combinatorics,Single-entry matrix,Square matrix,Symmetric matrix,Pentadiagonal matrix,Band matrix,Diagonal matrix,Block matrix,Mathematics,Sparse matrix | Journal |
Volume | Issue | ISSN |
29 | 1 | 0895-4798 |
Citations | PageRank | References |
8 | 0.72 | 11 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Patrick R. Amestoy | 1 | 446 | 44.24 |
| Xiaoye S. Li | 2 | 1042 | 98.22 |
| Esmond Ng | 3 | 503 | 91.55 |