\documentclass[landscape,dvips]{foils}

\usepackage{amsmath,amsthm,amssymb,amscd}
\usepackage{alltt}
\usepackage{epsf}
\def\w{{\cal W}}
\usepackage{latexsym}
\usepackage{times}
\usepackage{bookman}
\usepackage{graphics}
\usepackage{color}
\usepackage{epsfig}
\usepackage{psfrag}
\usepackage[ps2pdf]{hyperref}

\newcommand{\img}[2]{{\\epsfxsize=#1truecm\epsfbox{Images/PS/#2}}}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{definition}{Definition}
\newtheorem{proposition}{Proposition}

\def\basswidt{4.0in}
\def\gutter{0.2in}

\newenvironment{comment}{\setbox0=\vbox\bgroup}{\egroup}
\newenvironment{singlespace}{\def\baselinestretch{1.0}\large\normalsize}{\par}

\setlength{\textheight}{8in}
\setlength{\textwidth}{9in}
\voffset=-0.9in
\renewcommand\arraystretch{1.15}

\newcommand{\ie}{{\sl i.e.}}

\newcommand{\blue}[1]{{\color{blue} #1}}
\definecolor{mygreen}{rgb}{0.1,0.6,0.1} 
\newcommand{\green}[1]{{\color{mygreen} #1}}
\newcommand{\red}[1]{{\color{red} #1}}
\newcommand{\stitle}[1]{\foilhead{\red{#1}}\vspace{-0.5in}}
\newcommand{\bigitem}[2]{\item{#1\begin{small}\begin{itemize}#2\end{itemize}\end{small}}}
\newcommand{\mcite}[2]{{\small{\green{[#1, #2]}}}}
\newcommand{\eg}{{\sl e.g.}}
\newcommand{\etal}{{\sl et al.}}

\begin{document}

\title{\red{
Scalable Preconditioning Techniques Based on
Weighted Bandwidth Reduction 
}}

\author{}
%\\\\
%\blue{Murat Manguoglu, Mehmet Koyuturk, and Ananth Grama}\\
%\green{Department of Computer Science, Purdue University}\\\\\\
%{\tt \{mmanguog,koyuturk,ayg\}@cs.purdue.edu}
%}
%
\date{}

\maketitle

%\vspace{1.5in}
%{\small{\blue{Acknowledgment:} Funding for this work was provided by 
%the US Department of Defense under the High Productivity Computing
%Systems Program.}}

\thispagestyle{empty}


\stitle{Background}

\begin{itemize}
\item{Emerging architectures increasingly rely on parallelism
(chip-level and system-level) for performance.}

\item{Concurrency and localization play critical roles in
overall performance of programs.}

\item{Chip multiprocessors (multicore, multiscalar, cell-type)
put increasing pressure on the memory subsystem.}

\item{Algorithms and programs for such platforms must explicitly
account for concurrency and memory references as primary metrics
(as opposed to FLOP counts).}

\end{itemize}



\stitle{Conventional Architectures}

\begin{center}
\begin{tabular*}{\textwidth}%
     {@{\extracolsep{\fill}}cc}
\green{IBM Power 5} &  \green{Intel/Conroe}\\
 \psfig{file=power5.ps, height=3.0in} &
 \psfig{file=intel.ps, height=3.0in}\\
\green{Sun Niagara 2} &  \green{AMD Opteron}\\
 \psfig{file=sun.ps, height=3.0in} &
 \psfig{file=amd.ps, height=3.0in}\\
\end{tabular*}
\end{center}



\stitle{Implications for Sparse Linear System Solvers}

\begin{itemize}
\item
Maximal use of dense kernels in sparse solvers.
\item
Develop methods that optimize concurrency -- iterative methods with
preconditioners that have dense kernels.
\item
A natural candidate for such a preconditioner is a banded matrix.
\end{itemize}

\stitle{Banded Preconditioners for Iterative Methods}

\begin{itemize}
\item
Derive banded approximations to the matrix, which can act as good
preconditioners.
\item
Bands must be narrow and capture much of the matrix norm.
\item
Use banded solvers with high FLOP counts and concurrency.
\end{itemize}

\noindent
{\bf Key questions:}

\begin{itemize}
\item
How do we derive such narrow-banded preconditioners (non-symmetric
permutations)?
\item
Can such simple preconditioners be competitive against
traditional preconditioners in terms of iteration counts, FLOPS,
FLOP counts, and parallelism?
\end{itemize}



\stitle{Contributions and Results}

\begin{itemize}
\item
Banded preconditioners (with suitable reordering) can significantly
outperform ILU preconditioners in terms of iteration counts, FLOP
counts, as well as concurrency for large classes of matrices!
\item
Reordering schemes based on weighted spectral methods are highly
effective in deriving narrow banded preconditioners.
\item
The overhead of such reordering schemes is easily offset by the
lower solution cost for the system.
\item
A number of banded solvers (LAPACK, Spike) can be used for the
inner solve.
\end{itemize}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\stitle{Bandwidth Reduction}

\begin{itemize}
\item{Traditional algorithms (\eg, Cuthill-McKee \mcite{Cuthill \& McKee}{1969}, 
      Spectral reordering \mcite{Barnard \etal}{1995}) are aimed at minimizing the
      bandwidth
      \begin{displaymath}
       BW(A) = \max_{i,j: A(i,j) > 0}{|i-j|}
      \end{displaymath}
}

\bigitem {\red{Heavy} (high-magnitude) nonzeros that are \blue{distant} from the 
diagonal may significantly \red{degrade} the performance (convergence 
rate)}{
\item Particularly, for ill conditioned matrices.
}

%\item{
%We define {\bf \blue{weighted bandwidth}} as
%\begin{displaymath}
%WBW(A) = \frac{\sum_{i,j}{|A(i,j)|\times|i-j|}}{||A||_F}
%\end{displaymath}
%}

\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\stitle{Accounting for Heavy Entries}

\begin{itemize}
\item{We \green{generalize} the definition of bandwith}

\item{For given $b$, we define \blue{bandweight} as
\begin{displaymath}
w_b(A) = \sum_{i,j: |i-j| < b}{|A(i,j)|}
\end{displaymath}
}
\bigitem{Then, for given $\alpha$, we define \blue{$\alpha$-bandwidth} as
the \green{smallest bandwidth} that encapsulates an $\alpha$ fraction of \red{total
matrix weight}
\begin{displaymath}
BW_{\alpha}(A) = \min{b}~\text{such that}~{w_b(A) \geq \alpha \times \sum_{i,j}{|A(i,j)|}} 
\end{displaymath}
}
{\item Observe that this is a generalization of bandwidth, such that $BW_1(A) = BW(A)$}

\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\stitle{Spectral Ordering}

\begin{itemize}

\item{Commonly used in graph-theoretic applications and matrix algorithms}

\bigitem{
Find $x$ that \red{minimizes}
\begin{displaymath}
\sum_{i,j: A(i,j) > 0}{(x(i)-x(j))^2}
\end{displaymath}}
{\item Reorder rows and columns of $A$ accordingly
}

\bigitem{The eigenvector that corresponds to the smallest non-zero eigenvalue of the \blue{Laplacian} 
\begin{displaymath}
\begin{array}{l}
L(i,j) = -1~~~~~~~~~~~~~~~~~~~~~~~~~
{\bf if}~i \neq j \wedge A(i,j) > 0\\
L(i,i) = |\{j: A(i,j) > 0 \}|,
\end{array}
\end{displaymath}
a.k.a, \blue{Fiedler vector}, minimizes this  cost function \mcite{Fiedler}{1973}}{
\item{Can be computed effectively using iterative techniques (\eg, CG \mcite{Kruyt}{1995})}
}
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\stitle{Weighted Spectral Ordering}

\begin{itemize}
\item{Fiedler's result generalizes to \green{weighted} graphs (matrices) as well}

\item{Define \blue{Weighted Laplacian} as
\begin{displaymath}
\begin{array}{l}
\bar{L}(i,j) = -|A(i,j)|~~~~~~~~~~~
{\bf if}~i \neq j \\
\bar{L}(i,i) = \sum_j{|A(i,j)|}
\end{array}
\end{displaymath}
}
\item{The eigenvector that corresponds to the smallest non-zero eigenvalue 
of the weighted Laplacian \red{minimizes}
\begin{displaymath}
x^T\bar{L}x = \sum_{i,j}{|A(i,j)|(x(i)-x(j))^2},
\end{displaymath}
}
\item{Observe that $x^TLx$ is closely related to $\sum_{i,j}{|A(i,j)|}-w_b(A)$, with
proper quantization}

\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\stitle{Weighted Bandwidth Reduction}

\begin{itemize}

\bigitem{For \green{large enough $\alpha$}, use Weighted Spectral Ordering as a heuristic
to minimize $\alpha$-bandwidth}
{\item Find $\hat{x}$, the eigenvector corresponding to smallest non-zero eigenvalue 
       of $\bar{L}$
 \item Find permutation $\Pi=\{i_1,i_2,...,i_n:~\text{if}~j<k,~x(i_j) < x(i_k)\}$
 \item Reorder rows and columns of $A$ accordingly to obtain $\bar{A}=A(\Pi,\Pi)$
} 

\item{Observe that the heavy entries of the reordered matrix, $\bar{A}$ are close
to its diagonal, \ie, $\bar{A}$ has a smaller $\alpha$-bandwidth compared to $A$}

\item{\red{Drop} all entries that are outside $\alpha$-bandwidth of $\bar{A}$}
\begin{displaymath}
\tilde{A} = \{\tilde{A}(i,j):\tilde{A}(i,j)=\bar{A}(i,j)~\text{if}~|i-j|\leq 
              BW_\alpha(\bar{A}),~0~\text{else}\} 
\end{displaymath}

\item{Use $\tilde{A}$ as a \blue{banded preconditioner} to solve the system $A$}
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\stitle{Experimental Results}

\begin{itemize}
\bigitem{Matrices gathered from \green{UF Sparse Matrix Collection}}
{
 \item All software is implemented in \green{Fortran}
 \item Sequential timings were done on a clovertown machine
 \item \green{BICGSTAB} is used as the iterative solver
 \item All matrices are first reordered using \green{MC64}, to move heaviest
       entries to the diagonal
}



\stitle{Experimental Results}
\bigitem{Application of \blue{Weighted Spectral Ordering (WSO)}}
{
\item Reorder $|A|+|A^T|$ using \blue{MC73}
\item Find the bandwidth that encapsulates \blue{99\%} of overall matrix norm ($\alpha=0.99$)
\item Drop entries that fall out of this bandwidth to obtain the \blue{Weighted Spectral
Preconditioner}
}



\stitle{Experimental Results}
\bigitem{Comparison with \red{no preconditioner} and \red{ILU}}
{
\item \red{ILUT} \mcite{Saad}{1994} is used as a basis for comparison.
\item Fill-in is set to match the storage required for dense storage
of WSO's required bandwidth (\red{ILUBW}) 
\item Drop tolerance is set to $10^{-1}$ (\red{ILU1}), $10^{-3}$ (\red{ILU3})
}
\end{itemize}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\stitle{epb0 Matrix}

\begin{itemize}
\bigitem{Plate-fin heat exchanger w/ simple model}
{\item $1794\times1794$, $7764$ non-zeros
}
\end{itemize}

\begin{center}
\begin{tabular*}{\textwidth}%
     {@{\extracolsep{\fill}}cc}
\green{Original Matrix} &  \green{Reordered Matrix}\\
 \epsfig{file=figures/epb0.eps, width=0.475\textwidth} & 
 \epsfig{file=figures/epb0_p.eps, width=0.475\textwidth}\\
Bandwidth: $3587$  & Bandwidth: $76$\\
 & \\
\multicolumn{2}{l}{$99\%$ of matrix norm lies within a bandwidth of $19$ after WSO}\\
\end{tabular*}
\end{center}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\stitle{epb0 Results}

\begin{center}
\begin{tabular*}{\textwidth}%
     {@{\extracolsep{\fill}}cc}
\green{Residual Plot} & \green{Runtime Performance}\\
 \epsfig{file=figures/epb0_residue.eps,width=0.475\textwidth} &
 \epsfig{file=figures/epb0_performance.eps, width=0.475\textwidth}\\
\end{tabular*}
\end{center}

\begin{itemize}
\bigitem{BICGSTAB converges in 14 iterations with WSO preconditioner}
{\item No convergence after 300 iterations with no preconditioner or ILU with
drop tolerance $10^{-1}$
}
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\stitle{ASIC\_680k Matrix}

\begin{itemize}
\bigitem{Sandia, Xyce circuit simulation matrix (stripped)}
{\item $682862\times682862$, $2638997$ non-zeros
}
\end{itemize}

\begin{center}
\begin{tabular*}{\textwidth}%
     {@{\extracolsep{\fill}}cc}
\green{Original Matrix} &  \green{Reordered Matrix}\\
 \epsfig{file=figures/ASIC_680k.eps, width=0.475\textwidth} & 
 \epsfig{file=figures/ASIC_680k_p.eps, width=0.475\textwidth}\\
Bandwidth: $1328578$  & Bandwidth: $1328726$\\
 & \\
\multicolumn{2}{l}{$99\%$ of matrix norm lies within a bandwidth of $5$ after WSO}\\
\end{tabular*}
\end{center}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\stitle{ASIC\_680k Results}

\begin{center}
\begin{tabular*}{\textwidth}%
     {@{\extracolsep{\fill}}cc}
\green{Residual Plot} & \green{Runtime Performance}\\
 \epsfig{file=figures/ASIC_680k_residue.eps,width=0.475\textwidth} &
 \epsfig{file=figures/ASIC_680k_performance.eps, width=0.475\textwidth}\\
\end{tabular*}
\end{center}

\begin{itemize}
\bigitem{BICGSTAB converges in 9 iterations with WSO preconditioner}
{
\item ILU with fill-in equivalent to bandwith of WSO preconditioner
converges faster (4 iterations), but factorization takes too much time
\item ILU factorization unsucessful for drop tolerance $10^{-1}$,$10^{-3}$ 
\item No convergence after 300 iterations with no preconditioner 
}
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\stitle{lhr01 Matrix}

\begin{itemize}
\bigitem{Light hydrocarbon recovery}
{\item $14777\times14777$, $18427$ non-zeros
}
\end{itemize}

\begin{center}
\begin{tabular*}{\textwidth}%
     {@{\extracolsep{\fill}}cc}
\green{Original Matrix} &  \green{Reordered Matrix}\\
 \epsfig{file=figures/lhr01.eps, width=0.475\textwidth} & 
 \epsfig{file=figures/lhr01_p.eps, width=0.475\textwidth}\\
Bandwidth: $2537$  & Bandwidth: $1341$\\
 & \\
\multicolumn{2}{l}{$99\%$ of matrix norm lies within a bandwidth of $601$ after WSO}\\
\end{tabular*}
\end{center}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\stitle{lhr01 Results}

\begin{center}
\begin{tabular*}{\textwidth}%
     {@{\extracolsep{\fill}}cc}
\green{Residual Plot} & \green{Runtime Performance}\\
 \epsfig{file=figures/lhr01_residue.eps,width=0.475\textwidth} &
 \epsfig{file=figures/lhr01_performance.eps, width=0.475\textwidth}\\
\end{tabular*}
\end{center}

\begin{itemize}
\bigitem{BICGSTAB converges in only 4 iterations with WSO preconditioner!}{
 \item No convergence with no preconditioner in 300 iterations
 \item ILU factorization unsucessful for all variants
}
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\stitle{west0479 Matrix}

\begin{itemize}
\bigitem{U8 stage column section, all sections rigorous (chemical engineering)}
{\item $479\times479$, $1888$ non-zeros
 \item Known as a \red{horror matrix}
}
\end{itemize}

\begin{center}
\begin{tabular*}{\textwidth}%
     {@{\extracolsep{\fill}}cc}
\green{Original Matrix} &  \green{Reordered Matrix}\\
 \epsfig{file=figures/west0479.eps, width=0.475\textwidth} & 
 \epsfig{file=figures/west0479_p.eps, width=0.475\textwidth}\\
Bandwidth: $726$  & Bandwidth: $872$\\
 & \\
\multicolumn{2}{l}{$99\%$ of matrix norm lies within a bandwidth of $221$ after WSO}\\
\end{tabular*}
\end{center}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\stitle{west0479 Results}

\begin{center}
\begin{tabular*}{\textwidth}%
     {@{\extracolsep{\fill}}cc}
\green{Residual Plot} & \green{Runtime Performance}\\
 \epsfig{file=figures/west0479_residue.eps,width=0.475\textwidth} &
 \epsfig{file=figures/west0479_performance.eps, width=0.475\textwidth}\\
\end{tabular*}
\end{center}

\begin{itemize}
\bigitem{BICGSTAB converges in 293 iterations with WSO preconditioner}{
 \item No convergence with no preconditioner in 300 iterations
 \item ILU factorization unsucessful for all variants
}
\end{itemize}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\stitle{fp Matrix}

\begin{itemize}
\bigitem{2-D Fokker Planck equation, electron dynamics in external field}
{\item $7548\times7548$, $834222$ non-zeros
}
\end{itemize}

\begin{center}
\begin{tabular*}{\textwidth}%
     {@{\extracolsep{\fill}}cc}
\green{Original Matrix} &  \green{Reordered Matrix}\\
 \epsfig{file=figures/fp.eps, width=0.475\textwidth} & 
 \epsfig{file=figures/fp_p.eps, width=0.475\textwidth}\\
Bandwidth: $15086$  & Bandwidth: $12368$\\
 & \\
\multicolumn{2}{l}{$99\%$ of matrix norm lies within a bandwidth of $5$ after WSO}\\
\end{tabular*}
\end{center}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\stitle{fp Results}

\begin{center}
\begin{tabular*}{\textwidth}%
     {@{\extracolsep{\fill}}cc}
\green{Residual Plot} & \green{Runtime Performance}\\
 \epsfig{file=figures/fp_residue.eps,width=0.475\textwidth} &
 \epsfig{file=figures/fp_performance.eps, width=0.475\textwidth}\\
\end{tabular*}
\end{center}

\begin{itemize}
\bigitem{BICGSTAB converges in 2 iterations with WSO preconditioner, as well as
 ILU with $10^{-3}$ drop tolerance, $2$ fill-in}
{\item Convergence in 7 iterations with no preconditioner
 \item Reordering, factorization take too much time as compared to
preconditioner savings
}
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\stitle{matrix\_9 Matrix}

\begin{itemize}
\bigitem{Semiconductor device problem}
{\item $103430\times103430$, $1205518$ non-zeros
}
\end{itemize}

\begin{center}
\begin{tabular*}{\textwidth}%
     {@{\extracolsep{\fill}}cc}
\green{Original Matrix} &  \green{Reordered Matrix}\\
 \epsfig{file=figures/matrix_9.eps, width=0.475\textwidth} & 
 \epsfig{file=figures/matrix_9_p.eps, width=0.475\textwidth}\\
Bandwidth: $107410$  & Bandwidth: $198951$\\
 & \\
\multicolumn{2}{l}{$99\%$ of matrix norm lies within a bandwidth of $10673$ after WSO}\\
\end{tabular*}
\end{center}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\stitle{fp Results}

\begin{center}
\begin{tabular*}{\textwidth}%
     {@{\extracolsep{\fill}}cc}
\green{Residual Plot} & \green{Runtime Performance}\\
 \epsfig{file=figures/matrix_9_residue.eps,width=0.475\textwidth} &
 \epsfig{file=figures/matrix_9_performance.eps, width=0.475\textwidth}\\
\end{tabular*}
\end{center}

\begin{itemize}
\bigitem{BICGSTAB runs out of memory with WSO preconditioner}
{ \item BICGSTAB does not converge with no preconditioner
 \item ILU with $10^{-3}$ fill-in tolerance converges in 16 iterations
}
\end{itemize}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\stitle{Summary}

\begin{center}
\begin{tabular}{lccccc}
\hline
& \multicolumn{5}{c}{\red{Preconditioner}}\\
\red{Matrix} & \blue{None} & \blue{ILUBW} & \blue{ILU1} & \blue{ILU3} & \blue{WSO}\\
\hline
\green{epb0} & $>0.019$ & $0.018$ & $>0.029$ & $0.059$ & $0.009$ \\
              & $>300$    & $33$     & $>300$    & $135$    & $14$ \\
\hline
\green{ASIC\_680k} & $>38.2$ & $329.8$ & $\infty$ & $\infty$ & $10.1$\\
                   & $>300$ & $4$ & $\infty$ & $\infty$ &  $9$\\ 
\hline
\green{lhr01} & $>0.02$ & $\infty$ & $\infty$ & $\infty$ & $0.11$\\
              & $>300$ &  $\infty$ & $\infty$ & $\infty$ & $4$\\
\hline
\green{west0479} & $>0.009$ & $\infty$ & $\infty$ & $\infty$ & $0.094$\\
                 & $>300$ & $\infty$ & $\infty$ & $\infty$ & $293$\\
\hline
\green{fp} & $0.05$ & $21.97$ & $\infty$ & $2.09$ & $0.68$\\
           & $7$ & $2$ & $\infty$ & $2$ & $2$ \\
\hline
\green{matrix\_9} & $>8.2$ & $39.2$ & $\infty$ & $3.5$ & $\infty$\\
                  & $>300$ & $91$ & $\infty$ & $16$ & $\infty$\\
\hline
\end{tabular}
\end{center}

\vspace{0.2in}
\centerline{Total runtime (reordering+factorization+bicgstab) is reported in seconds.}
\vspace{0.1in}
\centerline{Number of iterations are reported on the row below.}


\stitle{Banded Preconditioners: Parallel Performance}

\vspace*{0.75in}

\begin{center}
\begin{tabular}{lcc}
\hline
Processors & bstd1.3M & astd650K \\
\hline
2&	1	&1 \\
4&	1.83	&1.75 \\
8&	3.38	&3.27 \\
16&	6.30	&6.04 \\
32&	12.44	&11.04 \\
64&	22.78	&20.08 \\
128&	39.91	&34.85 \\ \hline
\end{tabular}
\end{center}
\vspace*{0.75in}
\centerline{Scaling characteristics of banded preconditioned BiCG solver.}



\stitle{Concluding Remarks}

\begin{itemize}
\item
Banded preconditioners with suitable reordering techniques can be
very powerful for diverse classes of applications.
\item
Banded preconditioners typically yield much better CPU performance and
parallel performance.
\item
Due to memory reuse associated with dense kernels, they are well-suited
to conventional chip multiprocessor architectures.
\end{itemize}

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\stitle{References}

\begin{thebibliography}{1}

%\bibitem{chan94}
%P.~K. Chan, M.~D.~F. Schlag, and J.Y. Zien.
%\newblock Spectral k-way ratio-cut partitioning and clustering.
%\newblock {\em IEEE Transactions on Computer-Aided Design of Integrated
%  Circuits and Systems}, 13(9):1088--96, 1994.

\bibitem{cuthill69}
E.~Cuthill and J.~McKee.
\newblock Reducing the bandwidth of sparse symmetric matrices.
\newblock In {\em In Proc. 24th Nat. Conf. ACM}, pages 157--172, 1969.

\bibitem{fiedler73}
M.~Fiedler.
\newblock Algebraic connectivity of graphs.
\newblock {\em Czechoslovak Mathematical Journal}, 1973.

\bibitem{saad94}
Y.~Saad. I
\newblock {ILUT}: A dual threshold incomplete {ILU} factorization. 
\newblock {\em Numerical Linear Algebra with Applications}, 1:387--402, 
1994.

\bibitem{barnard95}
S.~T. Barnard, A. Pothen, and H. Simon.
\newblock A spectral algorithm for envelope reduction of sparse matrices.
\newblock {\em Numerical Linear Algebra with Applications}, 2(4):317--334,
  1995.

\bibitem{kruyt96}
N.~P.~Kruyt.
\newblock A conjugate gradient method for the spectral partitioning of 
graphs.
\newblock {\em Parallel Computing}, 22(11):1493--1502, 1996.



%\bibitem{koren03}
%Yehuda Koren.
%\newblock On spectral graph drawing.
%\newblock In {\em Computing and Combinatorics: 9th Annual International
%  Conference, COCOON 2003}, pages 496 -- 508, 2003.

\end{thebibliography}

\end{document}
