Abstract | ||
---|---|---|
The most widely used ordering scheme to reduce fills and operations in sparse matrix computation is the minimum-degree algorithm. The notion of multiple elimination is introduced here as a modification to the conventional scheme. The motivation is discussed using the k-by-k grid model problem. Experimental results indicate that the modified version retains the fill-reducing property of (and is often better than) the original ordering algorithm and yet requires less computer time. The reduction in ordering time is problem dependent, and for some problems the modified algorithm can run a few times faster than existing implementations of the minimum-degree algorithm. The use of external degree in the algorithm is also introduced. |
Year | DOI | Venue |
---|---|---|
1985 | 10.1145/214392.214398 | ACM Trans. Math. Softw. |
Keywords | Field | DocType |
conventional scheme,sparse ordering,multiple elimination,external degree,modified algorithm,minimum-degree algorithm,ordering,computer time,elimination,fill-reducing property,minimum degree,modified version,k-by-k grid model problem | Mathematical optimization,Minimum degree algorithm,Algorithm,Nested dissection,Implementation,Theoretical computer science,Cuthill–McKee algorithm,Mathematics,Grid,Sparse matrix,Computation | Journal |
Volume | Issue | ISSN |
11 | 2 | 0098-3500 |
Citations | PageRank | References |
121 | 43.08 | 3 |
Authors | ||
1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Joseph W. H. Liu | 1 | 829 | 217.74 |