1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
|
\begin{thebibliography}{10}
\bibitem{ame96-amd}
P.~Amestoy, T.~Davis, and I.~Duff.
\newblock An approximate minimum degree ordering algorithm.
\newblock {\em SIAM J. Matrix Anal. Appl.}, 17:886--905, 1996.
\bibitem{ash89-relaxed}
C.~Ashcraft and R.~Grimes.
\newblock The influence of relaxed supernode partitions on the multifrontal
method.
\newblock {\em ACM Trans. Math. Software}, 15:291--309, 1989.
\bibitem{ash97-partition}
C.~Ashcraft and J.~W.~H. Liu.
\newblock Using domain decomposition to find graph bisectors.
\newblock {\em BIT}, 37, 1997.
\bibitem{ash98-multisection}
C.~Ashcraft and J.~W.~H. Liu.
\newblock Robust ordering of sparse matrices using multisection.
\newblock {\em SIAM J. Matrix. Anal.}, 19:816--832, 1998.
\bibitem{ash98-maxflow}
C.~Ashcraft and J.~W.~H. Liu.
\newblock Applications of the {D}ulmage-{M}endelsohn decomposition and network
flow to graph bisection improvement.
\newblock {\em SIAM J. Matrix. Anal.}, 19:325--354, 1999.
\bibitem{bar93-partition}
S.~T. Barnard and H.~D. Simon.
\newblock A fast multilevel implementation of recursive spectral bisection for
partitioning unstructured problems.
\newblock In {\em Proceedings of the Sixth SIAM Conference on Parallel
Processing for Scientific Computing}, pages 711--718, 1993.
\bibitem{ber90-mindeg}
P.~Berman and G.~Schnitger.
\newblock On the performance of the minimum degree ordering for {G}aussian
elimination.
\newblock {\em SIAM J. Matrix Analysis and Applic.}, 11:83--88, 1990.
\bibitem{bui93-partition}
T.~Bui and C.~Jones.
\newblock A heuristic for reducing fill-in in sparse matrix factorization.
\newblock In {\em Proceedings of Sixth SIAM Conference on Parallel Processing},
pages 445--452, 1993.
\bibitem{duf83-multifrontal}
I.~Duff and J.~Reid.
\newblock The multifrontal solution of indefinite sparse symmetric linear
equations.
\newblock {\em ACM Trans. Math. Software}, 6:302--325, 1983.
\bibitem{geo73-nested}
J.~A. George.
\newblock Nested dissection of a regular finite element mesh.
\newblock {\em SIAM J. Numer. Anal.}, 10:345--363, 1973.
\bibitem{geo81-book}
J.~A. George and J.~W.~H. Liu.
\newblock {\em Computer Solution of Large Sparse Positive Definite Systems}.
\newblock Prentice-Hall, Englewood Cliffs, NJ, 1981.
\bibitem{gup96-WGPP}
A.~Gupta.
\newblock {WGPP}: {W}atson {G}raph {P}artitioning and sparse matrix ordering
{P}ackage.
\newblock Technical Report Users Manual, IBM T.J. Watson Research Center, New
York, 1996.
\bibitem{hen92-partition}
B.~Hendrickson and R.~Leland.
\newblock An improved spectral graph partitioning algorithm for mapping
parallel computations.
\newblock Technical Report SAND92-1460, Sandia National Laboratories,
Albuquerque, NM, 1992.
\bibitem{hen93-chaco}
B.~Hendrickson and R.~Leland.
\newblock The {C}haco user's guide.
\newblock Technical Report SAND93-2339, Sandia National Laboratories,
Albuquerque, NM, 1993.
\bibitem{hr98-msnd}
B.~Hendrickson and E.~Rothberg.
\newblock Improving the runtime and quality of nested dissection ordering.
\newblock {\em SIAM J. Sci. Comput.}, 20:468--489, 1998.
\bibitem{kar95-multilevel}
G.~Karypis and V.~Kumar.
\newblock A fast and high quality multilevel scheme for partitioning irregular
graphs.
\newblock Technical Report TR 95-035, Department of Computer Science,
University of Minnesota, Minnesota, 1995.
\bibitem{karypis98metis}
G.~Karypis and V.~Kumar.
\newblock Metis~4.0: Unstructured graph partitioning and sparse matrix ordering
system.
\newblock Technical report, Department of Computer Science, University of
Minnesota, 1998.
\newblock Available on the WWW at URL {\em http://www.cs.umn.edu/\~{}metis}.
\bibitem{lei89-fidmat}
C.~E. Leiserson and J.~G. Lewis.
\newblock Orderings for parallel sparse symmetric factorization.
\newblock In {\em Parallel Processing for Scientific Computing}, pages 27--31,
1989.
\bibitem{liu85-mmd}
J.~W.~H. Liu.
\newblock Modification of the minimum degree algorithm by multiple elimination.
\newblock {\em ACM Trans. on Math. Software}, 11:141--153, 1985.
\bibitem{liu90-etree}
J.~W.~H. Liu.
\newblock The role of elimination trees in sparse factorization.
\newblock {\em SIAM J. Matrix Analysis and Applic.}, 11:134--172, 1990.
\bibitem{ng96-mindefIdaho}
E.~Ng and P.~Raghavan.
\newblock Minimum deficiency ordering.
\newblock In {\em Second SIAM Conference on Sparse Matrices}, 1996.
\newblock Conference presentation.
\bibitem{pot90-partition}
A.~Pothen, H.~Simon, and K.P. Liou.
\newblock Partitioning sparse matrices with eigenvectors of graphs.
\newblock {\em SIAM J. Matrix Analysis and Applic.}, 11:430--452, 1990.
\bibitem{rag95-PCO}
P.~Raghavan.
\newblock Parallel ordering using edge contraction.
\newblock Technical Report CS-95-293, Dept. of Computer Science, The University
of Tennessee, Knoxville, Tennessee, 1995.
\bibitem{ro95-hybrid}
E.~Rothberg.
\newblock Robust ordering of sparse matrices: a minimum degree, nested
dissection hybrid.
\newblock unpublished, 1995.
\bibitem{roth98-minfill}
E.~Rothberg and S.~C. Eisenstat.
\newblock Node selection strategies for bottom-up sparse matrix ordering.
\newblock {\em SIAM J. Matrix Anal.}, 19:682--695, 1998.
\bibitem{sch82-etree}
R.~Schreiber.
\newblock A new implementation of sparse {G}aussian elimination.
\newblock {\em ACM Trans. Math. Soft.}, pages 256--276, 1982.
\end{thebibliography}
|
