\batchmode
\documentclass[11pt]{article}
\makeatletter
\usepackage{psfig}



















































 















\textheight 9in
\textwidth 6.5in
\oddsidemargin 0.0in
\evensidemargin 0.0in
\topmargin -0.5in

\title{Making Sparse Gaussian Elimination Scalable by Static Pivoting}

\author{
Xiaoye S. Li
	\thanks{This research used resources of the National Energy
	Research Scientific Computing Center, which is supported by
	the Office of Energy Research of the U.S. Department of Energy
	under Contract No. DE-AC03-76SF00098.} \\ 
	NERSC, Lawrence Berkeley National Lab\\ 
	1 Cyclotron Rd, MS 50F\\ 
	Berkeley, CA 94720.\\ 
	xiaoye@nersc.gov \\ 
	http://www.nersc.gov/$\sim$xiaoye
\and
        James W. Demmel
	\thanks{This research was supported in part by 
        NSF grant ASC-9313958, DOE grant DE-FG03-94ER25219,
        UT Subcontract No.\ ORA4466 from ARPA Contract No.\ DAAL03-91-C0047,
        DOE grant DE-FG03-94ER25206, 
	NSF Infrastructure grants CDA-8722788 and CDA-9401156
	and DOE grant DE-FC03-98ER25351.} \\ 
        Computer Science Division\\ 
	University of California\\ 
	Berkeley, CA 94720.\\ 
	demmel@cs.berkeley.edu \\ 
	http://www.cs.berkeley.edu/$\sim$demmel
}
\date{}



\def\spa{\mbox{\small SPA}}

\def\SuperLU{\mbox{SuperLU}}

\def\SupCol{\mbox{SupCol}}

\def\SupColF{\mbox{SupCol-F}}

\def\SupColC{\mbox{SupCol-C}}

\def\GP{\mbox{GP}}

\def\GPmod{\mbox{GP-Mod}}

\def\MA48{\mbox{\sc MA48}}

\def\MUPS{\mbox{\sc MUPS}}

\def\UMFPACK{\mbox{\sc UMFPACK}}

\def\NSPIV{\mbox{\sc NSPIV}}

\def\LAPACK{\mbox{\sc LAPACK}}

\def\BLAS{\mbox{\sc BLAS}}

\def\AXPY{\mbox{\sc AXPY}}

\def\DTRSV{\mbox{\sc DTRSV}}

\def\DGEMV{\mbox{\sc DGEMV}}

\def\DGEMM{\mbox{\sc DGEMM}}

\def\SGEMV{\mbox{\sc SGEMV}}

\def\SGEMM{\mbox{\sc SGEMM}}

\def\ILAENV{\mbox{\sc ILAENV}}

\def\MFLOPS{\mbox{Mflops}}

\def\ESSL{\mbox{\sc ESSL}}

\newcommand {\ignore}[1]{}

\newcommand {\edgeto}{\rightarrow}

\newcommand {\pathto}{\Longrightarrow}

\newcommand {\EDGETO}[1]{\stackrel{#1}{\rightarrow}}

\newcommand {\LEDGETO}[1]{\stackrel{#1}{\longrightarrow}}

\newcommand {\PATHTO}[1]{\stackrel{#1}{\Longrightarrow}}

\newcommand {\bmat}{\left( \begin{array}}

\newcommand {\emat}{\end{array} \right) }

\newcommand {\0}{\space}

\newcommand {\s}{\space}

\newcommand {\x}{\bullet}

\newcommand {\f}{\circ}

\newcommand {\TK}{\tilde{K}}

\newcommand {\myrule}{\rule{.7in}{.005in}\ }

\newcommand {\LU}{$LU$}

\newcommand {\QR}{$QR$}

\def\ssp{\def  \baselinestretch{1.0}\large\normalsize}

\def\dsp{\def  \baselinestretch{1.37}\large\normalsize}

\newcommand {\chap}[1]{Chapter~\ref{chap:#1}}

\newcommand {\fig}[1]{Figure~\ref{fig:#1}}

\newcommand {\eqn}[1]{Equation~(\ref{eqn:#1})}

\newcommand {\lem}[1]{Lemma~\ref{lem:#1}}

\renewcommand {\sec}[1]{Section~\ref{sec:#1}}

\newcommand {\thm}[1]{Theorem~\ref{thm:#1}}

\newcommand {\cor}[1]{Corollary~\ref{cor:#1}}

\newcommand {\prp}[1]{Proposition~\ref{prp:#1}}

\newcommand {\stp}[1]{Step~\ref{stp:#1}}

\newcommand {\alg}[1]{Algorithm~\ref{alg:#1}}

\newcommand {\tab}[1]{Table~\ref{tab:#1}}

\newcommand {\rem}[1]{Remark~\ref{rem:#1}}

\newenvironment {@abssec}[1]{\if@twocolumn
       \section*{#1}\else
       \vspace{.05in}\footnotesize
       \parindent .2in
         {\upshape\bfseries #1. }\ignorespaces
     \fi}
     {\if@twocolumn\else\par\vspace{.1in}\fi}

\newenvironment {AMS}{\begin{@abssec}{\AMSname}}{\end{@abssec}}

\newenvironment {AM}{\begin{@abssec}{\AMname}}{\end{@abssec}}

\newenvironment {PII}{\begin{@abssec}{\PIIname}}{\end{@abssec}}

\newenvironment {keywords}{\par\smallskip{\bf Keywords:}}{\par}

\makeatother
\newenvironment{tex2html_wrap}{}{}
\newwrite\lthtmlwrite
\def\lthtmltypeout#1{{\let\protect\string\immediate\write\lthtmlwrite{#1}}}%
\newbox\sizebox
\begin{document}
\pagestyle{empty}
{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{${\begingroup ||x_{true}-x||_\infty \endgroup \over ||x||_\infty }$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline967: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\mathop {\mathgroup \symoperators max}_i{\begingroup |A\cdot x-b|_i\endgroup \over (|A|\cdot |x|+|b|)_i}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline969: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$L\cdot x=b$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline977: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\sim$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline981: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

\stepcounter{section}
\stepcounter{section}
\stepcounter{subsection}
{\newpage
\clearpage
\samepage \begin{figure}\begin{tabbing}
jnk \= jnk \= jnk \= jnk \= jnk \= jnk \= xxxxx \= xxxxxxxxxxxxxxx \kill
\>(1) Row/column equilibration and row permutation:  
$A \leftarrow P_r \cdot D_r\cdot A\cdot D_c$, \\ 
\> \>	where $D_r$ and $D_c$ are diagonal matrices and $P_r$ is a row permutation\\ 
\> \>   chosen to make the diagonal large compared to the off-diagonal \\ 
\>(2) Find a column permutation $P_c$ to preserve sparsity:
	$A\leftarrow P_c\cdot A\cdot P_c^T$ \\ 
\>(3) Factorize $A=L\cdot U$ with control of diagonal magnitude \\ 
\>\>\> {\bf if} ( $|a_{ii}| < \sqrt{\varepsilon}\cdot ||A||$ ) {\bf then} \\ 
\>\>\>\> set $a_{ii}$ to $\sqrt{\varepsilon}\cdot ||A||$\\ 
\>\>\> {\bf endif} \\ 
\>(4) Solve $A\cdot x=b$ using the $L$ and $U$ factors, with the following
	iterative refinement \\ 
\>\>\>{\bf iterate}:\\ 
\>\>\>\>$r = b - A\cdot x$  \hspace{1in} $\ldots$ sparse matrix-vector 
multiply \\ 
\>\>\>\>Solve $A\cdot dx = r$     \hspace{.78in} $\ldots$ triangular solve \\ 
\>\>\>\>$berr = \max_i\frac{|r|_i}{(|A|\cdot|x|+|b|)_i}$
                    \hspace{.3in} $\ldots$ componentwise backward error \\ 
\>\>\>\>{\bf if} ( $berr > \varepsilon$ and 
		   $berr \le \frac{1}{2}\cdot lastberr$ )
{\bf then} \\ 
\>\>\>\>\>$x = x + dx$   \\ 
 \>\>\>\>\>$lastberr = berr$\\ 
\>\>\>\>\>{\bf goto iterate} \\ 
\>\>\>\>{\bf endif} \\ 
\end{tabbing}
\vspace*{-.3in}

\label{fig:GESP_alg}
\end{figure}
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$a_{ii}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1033: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\sum_{j \neq i} |a_{ij}|$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1035: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\sum_{j \neq i} |a_{ji}|$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1037: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$D_r$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1039: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$D_c$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1041: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$P_r$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1043: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$n \times n$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1047: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$a_{ij}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1055: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$D_r A D_c$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1063: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$P_r D_r A D_c$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1067: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\pm 1$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1077: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$O(n \cdot nnz(A) \cdot \log n)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1079: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$P_c$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1085: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$A^TA$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1087: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$A+A^T$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1091: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\sqrt{\varepsilon}\cdot \|A\|$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1099: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\varepsilon$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1101: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$berr \leq \varepsilon$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1107: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$(A + \delta A) x = b$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1109: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

\stepcounter{subsection}
{\newpage
\clearpage
\samepage \begin{table}\begin{tabular}{|l|l|}\hline
Discipline		  &Matrices \\ \hline
fluid flow, CFD	&af23560, bbmat, bramley1, bramley2, ex11, fidapm11, garon2,\\  
	&graham1, lnsp3937, lns\_3937, raefsky3, rma10, venkat01, wu\\ \hline
fluid mechanics		&goodwin, rim	\\ \hline
circuit simulation	&add32, gre\_1107, jpwh\_991, memplus, onetone1, onetone2, 
twotone\\ \hline
device simulation	&wang3, wang4, ecl32	\\ \hline
chemical engineering	&extr1, hydr1, lhr01, radfr1, rdist1, rdist2, rdist3a, 
west2021\\ \hline
petroleum engineering  	&orsirr\_1, orsreg\_1, sherman3, sherman4, 
sherman5\\ \hline
finite element PDE	&av4408, av11924 \\ \hline
stiff ODE		&fs\_541\_2 \\ \hline
Olmstead flow model	&olm5000	\\ \hline
aeroelasticity		&tols4000	\\ \hline
reservoir modelling		&pores\_2 \\ \hline
crystal growth simulation	&cry10000\\ \hline
power flow modelling		&gemat11	\\ \hline
dielectric waveguide 		&dw8192	(eigenproblem)	\\ \hline
astrophysics			&mcfe		\\ \hline
plasma physics			&utm5940	\\ \hline
demography			&psmigr\_1	\\ \hline
economics			&mahindas, orani678	\\ \hline
\end{tabular}

\label{tab:matrices}
\end{table}
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$x_{true}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1127: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\approx 10^{-16}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1129: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$10^{-12}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1131: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\sqrt{\varepsilon}\cdot ||A||$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1135: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{figure}\begin{minipage}{3.2in}
\centerline{\psfig{figure=char.eps,height=3in,width=3.2in}}
\vspace*{-.1in}

\label{fig:char}
\end{minipage}
\begin{minipage}{3.2in}
\centerline{\psfig{figure=spitSteps.eps,height=3in,width=3.2in}}
\vspace*{-.1in}

\label{fig:spitSteps}
\end{minipage}
\end{figure}
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\max_i\frac{|A\cdot x-b|_i}{(|A|\cdot|x|+|b|)_i}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1139: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\frac{||x_{true}-x||_\infty}{||x||_\infty}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1137: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{figure}\begin{minipage}{3.2in}
\centerline{\psfig{figure=spit_pp.eps,height=3in,width=3.2in}}
\vspace*{-.1in}

\label{fig:spit_pp}
\end{minipage}
\begin{minipage}{3.2in}
\centerline{\psfig{figure=spBERR.eps,height=3in,width=3.2in}}
\vspace*{-.1in}

\label{fig:spBERR}
\end{minipage}
\end{figure}
}

{\newpage
\clearpage
\samepage \begin{figure}\centerline{\psfig{figure=percenttime.eps,height=4.5in,width=5in}}

\label{fig:percenttime}
\end{figure}
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$r=b- A \cdot x$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1163: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$A \cdot dx = r$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1165: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

\stepcounter{section}
{\newpage
\clearpage
\samepage \begin{table}\begin{center}
\begin{tabular}{|l|r|r|r|r|r|r|} \hline
& 	&	&	&			&$nnz(L+U-I)$	&Flops \\ 
	&Order 	&$nnz(A)$ &NumSym &StrSym &$(\times 10^6)$&$(\times 10^9)$\\ 
\hline	 
AF23560	&23560	&460598   &.0512  &.9465	&12.8	&4.9\\ 
BBMAT	&38744	&1771722  &.0224  &.5398	&49.1	&4.3\\ 
ECL32	&51993	&380415	  &.6572  &.9325	&73.5	&120.4\\ 
EX11 	&16614	&1096948  &.9999  &1.0000	&14.1	&8.4\\ 
FIDAPM11&22294	&623554	  &.5476  &.9965	&23.0	&17.9\\ 
RMA10	&46835	&2374001  &.2443  &.9809	&14.7	&1.8\\ 
TWOTONE &120750	&1224224  &.1418  &.2738	&22.6	&8.7\\ 
WANG4	&26068	&177196	  &.1868  &1.0000	&27.7	&35.3\\ 
\hline
\end{tabular}		
\end{center}
\vspace*{-.1in}

\label{tab:largematrices}
\end{table}
}

\stepcounter{subsection}
{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$P_r\times P_c$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1191: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$N^2$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1207: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$0\le I, J\le N-1$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1213: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$\lceil{N/P_c}\rceil$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1239: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{figure}\centerline{\psfig{figure=lu_2d.eps,height=3.0in,width=4.6in}}

\label{fig:lu_2d}
\end{figure}
}

\stepcounter{subsection}
{\newpage
\clearpage
\samepage \begin{figure}\begin{tabbing}
jnk \= jnk \= jnk \= jnk \= jnk \= jnk \= xxxxx \= xxxxxxxxxxxxxxx \kill
Let $mycol$ ($myrow$) be my process column (row) number in the process grid\\ 
Let $PROC_C(K)$ ($PROC_R(K)$) be the column (row) processes that own block 
column (row) $K$ \\ 
{\bf for} block $K = 1$ {\bf to} $N$ {\bf do} \\ 
\> (1) {\bf if} ( $mycol = PROC_C(K)$ ) \\ 
\> \> \> Obtain the block column factor $L(K:N, K)$ \\ 
\> \> \> Send $L(K:N,K)$ to the processes in my row who need it \\ 
\> \> {\bf else} \\ 
\> \> \> Receive $L(K:N,K)$ from processes $PROC_C(K)$ if I need it \\ 
\> \> {\bf endif} \\ 
\> (2) {\bf if} ( $myrow = PROC_R(K)$ ) \\ 
\> \> \> Perform parallel triangular solves : $U(K, K+1:N) = L(K,K)^{-1}\cdot 
A(K,K+1:N)$ \\ 
\> \> \> Send $U(K,K+1:N)$ to processes in my column who need it \\ 
\> \> {\bf else} \\ 
\> \> \> Receive $U(K,K+1:N)$ from processes $PROC_R(K)$ if I need it\\ 
\> \> {\bf endif} \\ 
\> (3) {\bf for} $J = K+1$ to $N$ {\bf do} \\ 
\> \> \> {\bf for} $I = K+1$ to $N$ {\bf do} \\ 
\> \> \> \> {\bf if} ( $myrow = PROC_R(I)\ \&\ mycol = PROC_C(J)\ \&\ 
L(I,K)\ne 0
			\ \&\ U(K,J)\ne 0$ ) \\ 
\> \> \> \> \> $A(I,J) = A(I,J) - L(I,K)\cdot U(K,J)$ \\ 
\> \> \> \> {\bf endif} \\ 
{\bf end for}
\end{tabbing}
\vspace*{-.2in}

\label{fig:dist_lu}
\end{figure}
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$PROC_C(K+1)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1331: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$4\times 8$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1375: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

\stepcounter{subsection}
{\newpage
\clearpage
\samepage \begin{figure}\begin{tabbing}
jnk \= jnk \= jnk \= jnk \= jnk \= jnk \= xxxxx \= xxxxxxxxxxxxxxx \kill
\>Let $mycol$ ($myrow$) be my process column (row) number in the process grid\\ 
\>Let $PROC_C(K)$ be the column processes that own block column $K$ \\ 
\>$x = b$ \\ 
\>$lsum = 0$ \\ 
\>{\bf for} each block $K$ that I own \hspace*{1.0in} $\ldots$ Compute leaf 
nodes\\ 
\>\> {\bf if} ( $myrow=K\mbox{ mod } P_r \ \&\ mycol=K\mbox{ mod } P_c\ \&\ 
frecv[K]=0$ )\\ 
\>\> \> $x(K) = L(K,K)^{-1}\cdot x(K)$\\ 
\>\> \> Send $x(K)$ to the column processes $PROC_C(K)$\\ 
\>\> {\bf endif}\\ 
\>{\bf end for} \\ 
\>{\bf while} ( I have more work ) {\bf do}\hspace*{.9in} $\ldots$ 
	Compute internal nodes\\ 
\>\> Receive a message \hspace*{2in}(*)\\ 
\>\> {\bf if} ( message is $lsum(K)$ ) \\ 
\>\> \> $x(K) = x(K) + lsum(K)$; \\ 
\>\> \> $frecv(K) = frecv(K) - 1$ \\ 
\>\> \> {\bf if} ( $frecv(K) = 0$ ) \\ 
\>\> \> \> $x(K) = L(K,K)^{-1}\cdot x(K)$\\ 
\>\> \> \> Send $x(K)$ to the column processes $PROC_C(K)$\\ 
\>\> \> {\bf endif}\\ 
\>\> {\bf else if} ( message is $x(K)$ ) \\ 
\>\> \> {\bf for} each $I>K$, $L(I,K)\ne 0$ that I own\\ 
\>\> \> \> $lsum(I) = lsum(I) - L(I,K)\cdot x(K)$ \\ 
\>\> \> \> $fmod(I) = fmod(I) - 1$\\ 
\>\> \> \> {\bf if} ( $fmod(I)=0$ ) \\ 
\>\> \> \> \> Send $lsum(I)$ to the diagonal process who owns $L(I,I)$ \\ 
\>\> \> \> {\bf endif} \\ 
\>\> \> {\bf end for} \\ 
\>\> {\bf endif} \\ 
\>{\bf end while}
\end{tabbing}
\vspace*{-.2in}

\label{fig:dist_Lsolve}
\end{figure}
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$PROC_R(K)$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1467: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

\stepcounter{subsection}
{\newpage
\clearpage
\samepage \begin{table}\begin{center}
\begin{tabular}{|l|r||r|r|r|r|r|r|r||r|} \hline
	&\multicolumn{1}{c||}{Symbolic}
	&\multicolumn{8}{c|}{Numeric} \\  \cline{3-10}
&	&\multicolumn{1}{c}{P=4}
	&\multicolumn{1}{c}{16}
	&\multicolumn{1}{c}{32}
	&\multicolumn{1}{c}{64}
	&\multicolumn{1}{c}{128}
	&\multicolumn{1}{c}{256}
	&\multicolumn{1}{c||}{512}
	&\multicolumn{1}{c|}{Mflops}\\  \hline
AF23560	&1.69	& 32.26 &11.05	&7.33	&5.94	&{\bf 5.88}	&7.08	&7.16	&856\\ 
BBMAT	&11.81	&636.52 &163.48	&92.72	&52.07	&32.10	&22.85	&{\bf 18.52}	&2493\\ 
ECL32	&14.02	&462.74 &123.95	&68.55	&37.47	&23.33	&17.50	&{\bf 14.97}	&8352\\ 
EX11 	&1.77	& 27.45 &8.80	&5.35	&3.81	&{\bf 3.19}	&3.47	&3.39	&2628\\ 
FIDAPM11&4.10	&162.37 &45.33	&26.53	&15.55	&10.22	&8.34	&{\bf 7.85}	&2291\\ 
RMA10 	&1.67	&21.20	&9.36	&7.00	&6.86	&{\bf 6.49}	&7.58	&7.47	&511\\ 
TWOTONE &6.61	&152.27	&70.22	&42.44	&33.36	&31.46	&{\bf 29.96}	&31.72	&297\\ 
WANG4	&4.28	&104.73 &29.71	&16.45	&10.19	&7.13	&7.11	&{\bf 6.59}	&5542\\ 
\hline
\end{tabular}		
\end{center}
\vspace*{-.1in}

\label{tab:lu_time}
\end{table}
}

{\newpage
\clearpage
\samepage \begin{table}\begin{center}
\begin{tabular}{|l||r|r|r|r|r||r|} \hline
	&\multicolumn{1}{c}{P=4}
	&\multicolumn{1}{c}{8}
	&\multicolumn{1}{c}{16}
	&\multicolumn{1}{c}{32}
	&\multicolumn{1}{c||}{64}
	&\multicolumn{1}{c|}{Mflops}\\ \hline
AF23560		&0.94	&0.90	&0.69	&0.67	&0.64 	&42\\ 
BBMAT		&3.69	&3.42	&2.27	&2.23	&1.83	&56\\ 
ECL32		&2.95	&2.60	&1.66	&1.57	&1.17	&128\\ 
EX11		&0.50	&0.46	&0.32	&0.31	&0.26	&112\\ 
FIDAPM11	&1.39	&1.26	&0.83	&0.83	&0.68	&70\\ 
RMA10		&0.77	&0.74	&0.58	&0.53	&0.50	&60\\ 
TWOTONE		&4.37	&4.37	&3.65	&3.15	&2.95	&16 \\ 
WANG4		&1.09	&0.99	&0.67	&0.63	&0.50	&112\\ \hline
\end{tabular}
\end{center}
\vspace*{-.1in}

\label{tab:solves_time}
\end{table}
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$f_i$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1511: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$B = \frac{\sum_i(f_i)}{P\;\max_i(f_i)}$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1515: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \setbox\sizebox=\hbox{$0<B\le 1$}\lthtmltypeout{latex2htmlSize :tex2html_wrap_inline1519: \the\ht\sizebox::\the\dp\sizebox.}\box\sizebox
}

{\newpage
\clearpage
\samepage \begin{table}\begin{center}
\begin{tabular}{|l|c|c|c|c|c|c|c|c|}\hline
	&AF23560&BBMAT	&ECL32	&EX11	&FIDAPM11 &RMA10&TWOTONE &WANG4\\ \hline
$B_{fact}$&.82	&.77	&.94	&.87	&.70	&.73	&.43	&.92\\ 
$B_{sol}$ &.84	&.81	&.92	&.83	&.81	&.76	&.66	&.88\\ 
\hline
Comm  	&	&	&	&	&	&	&	&\\ 
\ \ \ $fact$&.82&.54	&.54	&.77	&.59	&.92	&.92	&.62\\ 
\ \ \ $sol$ &.97&.97	&.96	&.97	&.97	&.96	&.96	&.97\\ \hline
\end{tabular}
\end{center}
\vspace*{-.1in}

\label{tab:balance}
\end{table}
}

\stepcounter{section}
\stepcounter{subsection}
\stepcounter{subsection}
\stepcounter{section}
\stepcounter{section}
\appendix
\stepcounter{section}
\stepcounter{section}

\end{document}
