Name
Abstract | ||
|---|---|---|
This paper is concerned with the distributed parallel computation of an ordering for a symmetric positive definite sparse matrix. The purpose of the ordering is to limit fill and enhance concurrency in the subsequent Cholesky factorization of the matrix. A geometric approach to nested dissection is used based on a given Cartesian embedding of the graph of the matrix in Euclidean space. The resulting algorithm can be implemented efficiently on massively parallel, distributed memory computers. One unusual feature of the distributed algorithm is that its effectiveness does not depend on data locality, which is critical in this context, since an appropriate partitioning of the problem is not known until after the ordering has been determined. The ordering algorithm is the first component in a suite of scalable parallel algorithms currently under development for solving large sparse linear systems on massively parallel computers. |
Year | DOI | Venue |
|---|---|---|
1995 | 10.1137/S0895479892238270 | SIAM J. Matrix Analysis Applications |
Keywords | Field | DocType |
parallel computer,data locality,appropriate partitioning,cartesian embedding,cartesian parallel nested dissection,resulting algorithm,large sparse linear system,parallel computation,parallel nested dissection algorithm,scalable parallel algorithm,symmetric positive definite sparse,euclidean space,parallel algorithms,sparse matrix,cartesian coordinates,cholesky factorization,ordering | Mathematical optimization,Parallel algorithm,Massively parallel,Incomplete Cholesky factorization,Minimum degree algorithm,Algorithm,Nested dissection,Distributed algorithm,Cuthill–McKee algorithm,Sparse matrix,Mathematics | Journal |
Volume | Issue | ISSN |
16 | 1 | 0895-4798 |
Citations | PageRank | References |
24 | 9.50 | 6 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael T. Heath | 1 | 366 | 73.58 |
| Padma Raghavan | 2 | 460 | 77.54 |