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
|
\relax
\bibstyle{plain}
\citation{geo81-book}
\citation{geo73-nested}
\citation{ber90-mindeg}
\citation{liu85-mmd}
\citation{ame96-amd}
\citation{ng96-mindefIdaho}
\citation{roth98-minfill}
\@writefile{toc}{\contentsline {section}{\numberline {1}Introduction}{1}}
\citation{geo73-nested}
\citation{geo81-book}
\citation{lei89-fidmat}
\citation{pot90-partition}
\citation{bar93-partition}
\citation{bui93-partition}
\citation{hen93-chaco}
\citation{hen92-partition}
\citation{kar95-multilevel}
\citation{karypis98metis}
\citation{hr98-msnd}
\citation{gup96-WGPP}
\citation{rag95-PCO}
\citation{ash97-partition}
\citation{ash98-maxflow}
\citation{ash98-multisection}
\citation{ro95-hybrid}
\@writefile{toc}{\contentsline {section}{\numberline {2}Sparse matrix orderings}{2}}
\newlabel{section:ordering}{{2}{2}}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.1}The {\tt Graph} object}{2}}
\newlabel{subsection:graph}{{2.1}{2}}
\citation{liu85-mmd}
\@writefile{lof}{\contentsline {figure}{\numberline {1}{\ignorespaces A $3 \times 4$ 9-point grid with its adjacency structure}}{3}}
\newlabel{fig:3x4-grid}{{1}{3}}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.2}Constructing an ordering}{3}}
\newlabel{subsection:order}{{2.2}{3}}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.3}Results}{5}}
\newlabel{subsection:results}{{2.3}{5}}
\citation{liu90-etree}
\citation{sch82-etree}
\@writefile{toc}{\contentsline {section}{\numberline {3}Front Trees}{6}}
\newlabel{section:front-trees}{{3}{6}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.1}Vertex elimination trees}{6}}
\newlabel{subsection:vtx-elim}{{3.1}{6}}
\citation{ash89-relaxed}
\@writefile{lof}{\contentsline {figure}{\numberline {2}{\ignorespaces R2D100: randomly triangulated, 100 grid points}}{7}}
\newlabel{fig:R2D100}{{2}{7}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.2}Fundamental supernode trees}{7}}
\newlabel{subsection:fs-tree}{{3.2}{7}}
\@writefile{lof}{\contentsline {figure}{\numberline {3}{\ignorespaces Vertex elimination tree for R2D100, 100 rows and columns}}{8}}
\newlabel{fig:R2D100-tree-vtx}{{3}{8}}
\citation{ash89-relaxed}
\citation{duf83-multifrontal}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.3}Amalgamated or relaxed supernode trees}{9}}
\newlabel{subsection:am-tree}{{3.3}{9}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.4}Splitting large fronts}{9}}
\newlabel{subsection:sp-tree}{{3.4}{9}}
\@writefile{lof}{\contentsline {figure}{\numberline {4}{\ignorespaces Top: vertex elimination tree with the vertices mapped to the fundamental supernode that contains them. Bottom: fundamental supernode tree.}}{10}}
\newlabel{fig:fs-trees}{{4}{10}}
\@writefile{lof}{\contentsline {figure}{\numberline {5}{\ignorespaces Block structure of $L$ with the fundamental supernode partition.}}{11}}
\newlabel{fig:R2D100-fs-mtx}{{5}{11}}
\@writefile{lof}{\contentsline {figure}{\numberline {6}{\ignorespaces Top: fundamental supernode tree with the supernodes mapped to the amalgamated supernode that contains them. Bottom: amalgamated supernode tree.}}{12}}
\newlabel{fig:am-trees}{{6}{12}}
\@writefile{lof}{\contentsline {figure}{\numberline {7}{\ignorespaces Block structure of $L$ with the amalgamated supernode partition.}}{13}}
\newlabel{fig:R2D100-am-mtx}{{7}{13}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.5}Results}{14}}
\newlabel{subsection:tree-results}{{3.5}{14}}
\@writefile{lof}{\contentsline {figure}{\numberline {8}{\ignorespaces Left: tree after the large supernodes have been split. Right: tree with nodes mapped back to their amalgamated supernode.}}{15}}
\newlabel{fig:sp-trees}{{8}{15}}
\@writefile{lof}{\contentsline {figure}{\numberline {9}{\ignorespaces Block structure of $L$ with the amalgamated and split supernode partition.}}{16}}
\newlabel{fig:sp-mtx}{{9}{16}}
\newlabel{table:R3D13824-tree-stats}{{3.5}{16}}
\@writefile{lot}{\contentsline {table}{\numberline {1}{\ignorespaces R3D13824: front tree transformations}}{16}}
\newlabel{table:R3D13824-comp-stats}{{3.5}{17}}
\@writefile{lot}{\contentsline {table}{\numberline {2}{\ignorespaces R3D13824: factor and solve timings for five different front trees.}}{17}}
\bibdata{spooles}
\bibcite{ame96-amd}{1}
\bibcite{ash89-relaxed}{2}
\bibcite{ash97-partition}{3}
\bibcite{ash98-multisection}{4}
\bibcite{ash98-maxflow}{5}
\bibcite{bar93-partition}{6}
\bibcite{ber90-mindeg}{7}
\bibcite{bui93-partition}{8}
\bibcite{duf83-multifrontal}{9}
\bibcite{geo73-nested}{10}
\bibcite{geo81-book}{11}
\bibcite{gup96-WGPP}{12}
\bibcite{hen92-partition}{13}
\newlabel{table:R3D13824-maxzero-maxsize}{{3.5}{19}}
\@writefile{lot}{\contentsline {table}{\numberline {3}{\ignorespaces R3D13824: the influence of {\tt maxzeros} and {\tt maxsize}.}}{19}}
\bibcite{hen93-chaco}{14}
\bibcite{hr98-msnd}{15}
\bibcite{kar95-multilevel}{16}
\bibcite{karypis98metis}{17}
\bibcite{lei89-fidmat}{18}
\bibcite{liu85-mmd}{19}
\bibcite{liu90-etree}{20}
\bibcite{ng96-mindefIdaho}{21}
\bibcite{pot90-partition}{22}
\bibcite{rag95-PCO}{23}
\bibcite{ro95-hybrid}{24}
\bibcite{roth98-minfill}{25}
\bibcite{sch82-etree}{26}
|
