\batchmode
\documentstyle[makeidx,epsf,psfig,fleqn,comment]{book}
\makeatletter
\pagenumbering{roman}

\setcounter{tocdepth}{2}
\makeindex
\addtolength{\textwidth}{4pc}
\addtolength{\textheight}{6pc}
\emergencystretch=25pt

\renewcommand{\floatpagefraction}{.75}
\renewcommand{\topfraction}{.85}
\advance\textfloatsep-8pt
\def\inv{^{-1}}
\newcommand{\ii}[1]{{\it #1}}
\newcommand{\tty}[1]{{\tt #1}}
\long\def\glossaryentry#1#2{\glossitem#1<<}\long\def\glossitem#1:#2<<{\item[#1]\ignorespaces #2}
\hyphenation{Eijk-hout}



\def\glossaryentry#1#2{\glossitem#1<<}

\def\glossitem#1:#2<<{\item[#1]\ignorespaces #2}

\def\half{{\frac{1}{2}}}

\def\cgs{{CGS}}

\def\cg{{ CG}}

\def\bicg{{BiCG}}

\def\cgstab{{ Bi-CGSTAB}}

\def\qmstab{QMRCGSTAB}

\def\qmrcgstab{QMRCGSTAB}

\def\tfqmr{TFQMR}

\def\qmrcgs{QMRCGS}

\def\qmr{QMR}

\def\bcg{{BiCG}}

\def\ncofm{M_1\inv AM_2\inv}

\def\omip{\Omega'_i}

\def\omi{\Omega_i}

\makeatother
\newenvironment{tex2html_wrap}{}{}
\begin{document}
\pagestyle{empty}
\setcounter{tocdepth}{2}
\newcounter{utk-thanks}
\newcounter{ornl-thanks}
\newcounter{ucla-thanks}
\setcounter{utk-thanks}{\value{footnote}}
\setcounter{ucla-thanks}{\value{footnote}}
\setcounter{ornl-thanks}{\value{footnote}}
\newpage

{\samepage \clearpage $^,$
}


\newpage

{\samepage \clearpage \begin{tabular}% latex2html id marker 64
{l l}
      $A, \ldots, Z$    & matrices \\ 
      $a, \ldots, z$    & vectors       \\ 
      $\alpha, \beta, \ldots, \omega$ & scalars \\ 
      $A^{T}$         & matrix transpose \\ 
      $A^{H}$         & conjugate transpose (Hermitian) of $A$ \\ 
      $A^{-1}$        & matrix inverse \\ 
      $A^{-T}$        & the inverse of $A^T$ \\ 
      $a_{i,j}$       & matrix element \\ 
      $a_{.,j}$       & $j$th matrix column \\ 
      $A_{i,j}$       & matrix subblock \\ 
      $a_{i}$         & vector element \\ 
      $u_x,u_{xx}$    & first, second derivative with respect to~$x$ \\ 
      $(x,y)$, $x^Ty$        & vector dot product (inner product) \\ 
      $x^{(i)}_j$     & $j$th component of vector $x$ in the $i$th iteration\\ 
      diag($A$)       & diagonal of matrix $A$ \\ 
      diag($\alpha, \beta \ldots$) & diagonal matrix constructed 
      from scalars $\alpha, \beta \ldots$\\ 
      span($a,b \ldots$) & spanning space of vectors $a,b \ldots$ \\ 
      $\cal R$        &  set of real numbers \\ 
      ${\cal R}^{n}$  &  real $n$-space\\ 
      $|| x ||_{2}$   &  2-norm \\ 
      $|| x ||_{p}$   &  $p$-norm \\ 
      $|| x ||_{A}$   &  the ``$A$-norm'', defined as $(Ax,x)^{1/2}$ \\ 
      $\lambda_{\max}(A), \lambda_{\min}(A)$ & eigenvalues of $A$ with
      maximum (resp. minimum) modulus \\ 
      $\sigma_{\max}(A), \sigma_{\min}(A)$ & largest and smallest
      singular values of $A$ \\ 
      $\kappa_2 (A)$  & spectral condition number of matrix $A$ \\ 
      $\cal L$                &       linear operator \\ 
      $\overline{\alpha} $    &  complex conjugate of the scalar $\alpha$ \\ 
      $\max \{S\}$    &  maximum value in set $S$ \\ 
      $\min \{S\}$    &  minimum value in set $S$ \\ 
      $\sum $                 &  summation \\ 
      $O(\cdot)$   &  ``big-oh'' asymptotic bound \\ 
      & \\ 
    \end{tabular}
}


\newpage

{\samepage \clearpage \begin{tabular}{l l}
      \multicolumn{2}{c}{Conventions Used in this Book}\\ 
      & \\ 
      $D$             &  diagonal matrix \\ 
      $L$             &  lower triangular matrix \\ 
      $U$             &  upper triangular matrix \\ 
      $Q$             &  orthogonal matrix \\ 
      $M$             &  preconditioner \\ 
      $I,\; I^{n \times n}$   & $n \times n$ identity matrix \\ 
      $\hat{x}$ & typically, the exact solution to $Ax=b$\\ 
      $h$ & discretization mesh width \\ 
    \end{tabular}
}


\stepcounter{chapter}
\newpage

{\samepage \clearpage $A$
}


\newpage

{\samepage \clearpage $y=A \cdot x$
}


\newpage

{\samepage \clearpage $z=A^T \cdot x$
}


\newpage

{\samepage \clearpage $y$
}


\newpage

{\samepage \clearpage $z$
}


\newpage

{\samepage \clearpage $x$
}


\stepcounter{section}
\stepcounter{section}
\stepcounter{chapter}
\stepcounter{section}
\newpage

{\samepage \clearpage $\omega$
}


\newpage

{\samepage \clearpage $Ax=b$
}


\newpage

{\samepage \clearpage $(A A^T) y = b$
}


\newpage

{\samepage \clearpage $x=A^T y$
}


\newpage

{\samepage \clearpage $(A^TA) x = \tilde{b}$
}


\newpage

{\samepage \clearpage $\tilde{b} = A^T b$
}


\newpage

{\samepage \clearpage $A A^T$
}


\newpage

{\samepage \clearpage $A^TA$
}


\newpage

{\samepage \clearpage $A^T$
}


\stepcounter{section}
\newpage

{\samepage \clearpage \begin{equation}  x^{(k)} = B x^{(k-1)} + c
  \label{eqn:stationary}
\end{equation}
}


\newpage

{\samepage \clearpage $B$
}


\newpage

{\samepage \clearpage $c$
}


\newpage

{\samepage \clearpage $k$
}


\stepcounter{subsection}
\newpage

{\samepage \clearpage $n$
}


\newpage

{\samepage \clearpage $i$
}


\newpage

{\samepage \clearpage \begin{displaymath}  \sum_{j=1}^n a_{i,j} x_j = b_i,
\end{displaymath}
}


\newpage

{\samepage \clearpage $x_i$
}


\newpage

{\samepage \clearpage \begin{equation}% latex2html id marker 226
  x_i = (b_i - \sum_{j \neq i} a_{i,j} x_j) / a_{i,i}.
  \label{eqn:ith-equation}
\end{equation}
}


\newpage

{\samepage \clearpage \begin{equation}  x^{(k)}_i = (b_i - \sum_{j \neq i} a_{i,j} x^{(k-1)}_j) / a_{i,i},
  \label{eqn:jacobi-pointwise}
\end{equation}
}


\newpage

{\samepage \clearpage \begin{equation}  x^{(k)} = D^{-1} (L+U) x^{(k-1)} + D^{-1}  b,
  \label{eqn:jacobi-matrixwise}
\end{equation}
}


\newpage

{\samepage \clearpage $D$
}


\newpage

{\samepage \clearpage $-L$
}


\newpage

{\samepage \clearpage $-U$
}


\newpage

{\samepage \clearpage $\bar{x}$
}


\newpage

{\samepage \clearpage $x^{(k-1)}$
}


\newpage

{\samepage \clearpage $x^{(k)}$
}


\newpage

{\samepage \clearpage \begin{figure}[tp]
  \begin{center}
    \leavevmode
    \framebox[4.0in]
    {\vbox{
        \begin{tabbing}
          Choose an initial guess $x^{(0)}$ to the solution $x$. \\ 
          {\bf for } \= $ k = 1, 2, \ldots$ \\ 
          \> {\bf for } \= $ i = 1, 2, \ldots , n$ \\ 
          \> \> $\bar{x}_i = 0 $ \\ 
          \> \> {\bf for } \= $ j = 1, 2, \ldots, i-1, i+1, \ldots, n$ \\ 
          \> \> \> $\bar{x}_i = \bar{x}_i + a_{i,j} x^{(k-1)}_j $ \\ 
          \> \> {\bf end} \\ 
          \> \> $\bar{x}_i = (b_i - \bar{x}_i) / a_{i,i} $ \\ 
          \> {\bf end} \\ 
          \> $ x^{(k)} = \bar{x} $ \\ 
          \> check convergence; continue if necessary \\ 
          {\bf end}
        \end{tabbing}
        }}
    
    \label{fig:jacobi}
  \end{center}
\end{figure}
}


\stepcounter{subsubsection}
\newpage

{\samepage \clearpage \begin{displaymath}  {\cal L}u=-u_{xx}=f\qquad\hbox{on $(0,1)$},
  \qquad u(0)=u_0,\quad u(1)=u_1,
\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}  Lu(x_i)=2u(x_i)-u(x_{i-1})-u(x_{i+1})=f(x_i)/N^2\qquad
  \hbox{for $x_i=i/N$, $i=1\ldots N-1$}.
\end{displaymath}
}


\newpage

{\samepage \clearpage $\cal L$
}


\newpage

{\samepage \clearpage $L$
}


\newpage

{\samepage \clearpage $n=1\ldots N-1$
}


\newpage

{\samepage \clearpage $u_n(x)=\sin n\pi x$
}


\newpage

{\samepage \clearpage $\lambda=4\sin^2n\pi/(2N)$
}


\newpage

{\samepage \clearpage $\lambda(B)=1-\lambda(L)/2=1-2\sin^2n\pi/(2N)$
}


\newpage

{\samepage \clearpage $u_n$
}


\newpage

{\samepage \clearpage $1$
}


\newpage

{\samepage \clearpage $\approx 1-10/N^2$
}


\newpage

{\samepage \clearpage $u(x)=\sin\pi x$
}


\newpage

{\samepage \clearpage $\max\{|\lambda(A)|\}$
}


\newpage

{\samepage \clearpage $1-O(h^2)$
}


\newpage

{\samepage \clearpage $h$
}


\newpage

{\samepage \clearpage $h=N^{-d}$
}


\newpage

{\samepage \clearpage $N$
}


\newpage

{\samepage \clearpage $d$
}


\stepcounter{subsection}
\newpage

{\samepage \clearpage \begin{equation}  x^{(k)}_i = (b_i - \sum_{j<i} a_{i,j} x^{(k)}_j - \sum_{j>i} a_{i,j}
  x^{(k-1)}_j) / a_{i,i}.
  \label{eqn:gauss-seidel-pointwise}
\end{equation}
}


\newpage

{\samepage \clearpage \begin{equation}  x^{(k)} = (D-L)^{-1}  (Ux^{(k-1)} + b).
  \label{eqn:gauss-seidel-matrixwise}
\end{equation}
}


\newpage

{\samepage \clearpage \begin{figure}[tp]
  \begin{center}
    \leavevmode
    \framebox[4.0in]
    {\vbox{
        \begin{tabbing}
          Choose an initial guess $x^{(0)}$ to the solution $x$. \\ 
          {\bf for } \= $ k = 1, 2, \ldots$ \\ 
          \> {\bf for } \= $ i = 1, 2, \ldots , n$ \\ 
          \> \> $ \sigma = 0 $ \\ 
          \> \> {\bf for } \= $j = 1, 2, \ldots, i-1$ \\ 
          \> \> \> $ \sigma = \sigma + a_{i,j} x^{(k)}_j $ \\ 
          \> \> {\bf end} \\ 
          \> \> {\bf for } $j = i+1, \ldots, n$ \\ 
          \> \> \> $ \sigma = \sigma + a_{i,j} x^{(k-1)}_j $ \\ 
          \> \> {\bf end} \\ 
          \> \> $ x^{(k)}_i = (b_i - \sigma) / a_{i,i} $ \\ 
          \> {\bf end} \\ 
          \> check convergence; continue if necessary \\ 
          {\bf end}
        \end{tabbing}
        }}
    
    \label{fig:gs}
  \end{center}
\end{figure}
}


\stepcounter{subsection}
\newpage

{\samepage \clearpage \begin{displaymath}  x_i^{(k)} = \omega \bar{x}_i^{(k)} + (1 - \omega )x_i^{(k-1)}
\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{equation}  x^{(k)} = (D - \omega L)^{-1} (\omega U + (1-\omega)D) x^{(k-1)}
  + \omega (D - \omega L)^{-1} b .
  \label{eqn:sor-matrix}
\end{equation}
}


\newpage

{\samepage \clearpage \begin{figure}[tp]
  \begin{center}
    \leavevmode
    \framebox[4.0in]
    {\vbox{
        \begin{tabbing}
          Choose an initial guess $x^{(0)}$ to the solution $x$. \\ 
          {\bf for } \= $ k = 1, 2, \ldots$ \\ 
          \> {\bf for } \= $ i = 1, 2, \ldots , n$ \\ 
          \> \> $ \sigma = 0 $ \\ 
          \> \> {\bf for } \= $j = 1, 2, \ldots, i-1$ \\ 
          \> \> \> $ \sigma = \sigma + a_{i,j} x^{(k)}_j $ \\ 
          \> \> {\bf end} \\ 
          \> \> {\bf for } $j = i+1, \ldots, n$ \\ 
          \> \> \> $ \sigma = \sigma + a_{i,j} x^{(k-1)}_j $ \\ 
          \> \> {\bf end} \\ 
          \> \> $ \sigma = (b_i - \sigma) / a_{i,i} $ \\ 
          \> \> $ x^{(k)}_i = x^{(k-1)}_i + \omega (\sigma - x^{(k-1)}_i) $ \\ 
          \> {\bf end} \\ 
          \> check convergence; continue if necessary \\ 
          {\bf end}
        \end{tabbing}
        }}
    
    \label{fig:sor}
  \end{center}
\end{figure}
}


\stepcounter{subsubsection}
\newpage

{\samepage \clearpage $\omega = 1$
}


\newpage

{\samepage \clearpage $(0,2)$
}


\newpage

{\samepage \clearpage $0 < \omega < 1$
}


\newpage

{\samepage \clearpage $\omega \in (0,2)$
}


\newpage

{\samepage \clearpage $\omega = 2 -
O(h)$
}


\newpage

{\samepage \clearpage $M$
}


\newpage

{\samepage \clearpage $a_{i,j}=a_{j,i}$
}


\newpage

{\samepage \clearpage $j$
}


\newpage

{\samepage \clearpage $x^TAx>0$
}


\newpage

{\samepage \clearpage $a_{ii}>\sum_{j\not=i}|a_{ij}|$
}


\newpage

{\samepage \clearpage $a_{i,j}\leq0$
}


\newpage

{\samepage \clearpage $i\not=j$
}


\newpage

{\samepage \clearpage $(A^{-1})_{i,j}\geq0$
}


\newpage

{\samepage \clearpage $\rho$
}


\newpage

{\samepage \clearpage \begin{equation}  \omega_{\rm opt} = \frac{2}{1 + \sqrt{1 - \rho^2}}.
  \label{eqn:sta:optimal:omega}
\end{equation}
}


\stepcounter{subsection}
\newpage

{\samepage \clearpage \begin{equation}  x^{(k)} = B_1 B_2 x^{(k-1)} + \omega (2-\omega)(D-\omega U)^{-1}
  D (D- \omega L)^{-1} b,
  \label{eqn:ssor-matrix}
\end{equation}
}


\newpage

{\samepage \clearpage \begin{displaymath}  B_1 = (D- \omega U)^{-1} (\omega L + (1-\omega) D),
\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}  B_2 = (D- \omega L)^{-1} (\omega U + (1-\omega) D).
\end{displaymath}
}


\newpage

{\samepage \clearpage $B_2$
}


\newpage

{\samepage \clearpage $B_1$
}


\newpage

{\samepage \clearpage $U$
}


\newpage

{\samepage \clearpage \begin{figure}[tp]

\begin{center}
  \leavevmode
  \framebox[4.0in]
  {\vbox{
      \begin{tabbing}
        Choose an initial guess $x^{(0)}$ to the solution $x$. \\ 
	Let $x^{({\frac{1}{2}})}=x^{(0)}$.\\ 
        {\bf for } \= $ k = 1, 2, \ldots$ \\ 
        \> {\bf for } \= $ i = 1, 2, \ldots , n$ \\ 
        \> \> $ \sigma = 0 $ \\ 
        \> \> {\bf for } \= $j = 1, 2, \ldots, i-1$ \\ 
        \> \> \> $ \sigma = \sigma + a_{i,j} x^{(k-{\frac{1}{2}})}_j $ \\ 
        \> \> {\bf end} \\ 
        \> \> {\bf for } $j = i+1, \ldots, n$ \\ 
        \> \> \> $ \sigma = \sigma + a_{i,j} x^{(k-1)}_j $ \\ 
        \> \> {\bf end} \\ 
        \> \> $ \sigma = (b_i - \sigma) / a_{i,i} $ \\ 
        \> \> $ x^{(k-{\frac{1}{2}})}_i = x^{(k-1)}_i + \omega (\sigma - x^{(k-1)}_i) $ \\ 
        \> {\bf end} \\ 
        \> {\bf for } $ i = n, n-1, \ldots , 1$ \\ 
        \> \> $ \sigma = 0 $ \\ 
        \> \> {\bf for} $j = 1, 2, \ldots, i-1$ \\ 
        \> \> \> $ \sigma = \sigma + a_{i,j} x^{(k-{\frac{1}{2}})}_j $ \\ 
        \> \> {\bf end} \\ 
        \> \> {\bf for} $j = i+1, \ldots, n$ \\ 
        \> \> \> $ \sigma = \sigma + a_{i,j} x^{(k)}_j $ \\ 
        \> \> {\bf end} \\ 
        \> \> $ x^{(k)}_i = x^{(k-{\frac{1}{2}})}_i + \omega (\sigma -
        x^{(k-{\frac{1}{2}})}_i) $ \\ 
        \> {\bf end} \\ 
        \> check convergence; continue if necessary \\ 
        {\bf end}
      \end{tabbing}
      }}
  
  \label{fig:ssor}
\end{center}
\end{figure}
}


\stepcounter{subsection}
\stepcounter{section}
\stepcounter{subsection}
\newpage

{\samepage \clearpage $x^{(i)}$
}


\newpage

{\samepage \clearpage % latex2html id marker 5039
$(\alpha_i)$
}


\newpage

{\samepage \clearpage $p^{(i)}$
}


\newpage

{\samepage \clearpage \begin{displaymath}% latex2html id marker 515
  x^{(i)} = x^{(i-1)}+\alpha_i p^{(i)}.
\end{displaymath}
}


\newpage

{\samepage \clearpage $r^{(i)}=b-Ax^{(i)}$
}


\newpage

{\samepage \clearpage \begin{equation}% latex2html id marker 523
  r^{(i)} = r^{(i-1)}-\alpha q^{(i)}\qquad\hbox{where}\qquad q^{(i)}=Ap^{(i)}.
  \label{eqn:cg:res-update}
\end{equation}
}


\newpage

{\samepage \clearpage % latex2html id marker 5045
$\alpha = \alpha_i=r^{(i-1)^T}r^{(i-1)}/p^{(i)^T}Ap^{(i)}$
}


\newpage

{\samepage \clearpage $r^{(i)^T}A^{-1}r^{(i)}$
}


\newpage

{\samepage \clearpage % latex2html id marker 5049
$\alpha$
}


\newpage

{\samepage \clearpage \begin{equation}  p^{(i)} = r^{(i)}+\beta_{i-1}p^{(i-1)},
  \label{eqn:cg:dir-update}
\end{equation}
}


\newpage

{\samepage \clearpage $\beta_i=r^{(i)^T}r^{(i)}/r^{(i-1)^T}r^{(i-1)}$
}


\newpage

{\samepage \clearpage $Ap^{(i-1)}$
}


\newpage

{\samepage \clearpage $r^{(i)}$
}


\newpage

{\samepage \clearpage $r^{(i-1)}$
}


\newpage

{\samepage \clearpage $\beta_i$
}


\newpage

{\samepage \clearpage $Ap^{(j)}$
}


\newpage

{\samepage \clearpage $r^{(j)}$
}


\newpage

{\samepage \clearpage $M=I$
}


\newpage

{\samepage \clearpage $z^{(i-1)}$
}


\newpage

{\samepage \clearpage $z^{(0)}$
}


\newpage

{\samepage \clearpage $r^{(0)}$
}


\newpage

{\samepage \clearpage \begin{figure}% latex2html id marker 567
[tp]
  \begin{center}
    \leavevmode
    \framebox[4.5in]{\vbox{
        \begin{tabbing}
          Compute $r^{(0)} = b - Ax^{(0)}$ for some initial guess $x^{(0)}$ \\ 
          {\bf for } \= $ i = 1, 2, \ldots$ \\ 
          \> {\bf solve} $Mz^{(i-1)}=r^{(i-1)}$\\ 
          \> $\rho_{i-1}=r^{(i-1)^T}z^{(i-1)}$\\ 
          \> {\bf if} \= $i = 1$ \\ 
          \> \> $p^{(1)} = z^{(0)}$ \\ 
          \> {\bf else} \\ 
          \> \>$\beta_{i-1} = \rho_{i-1} / \rho_{i-2} $ \\ 
          \> \>$p^{(i)} = z^{(i-1)} + \beta_{i-1}p^{(i-1)} $ \\ 
          \>{\bf endif} \\ 
          \> $q^{(i)}=Ap^{(i)}$ \\ 
          \>$\alpha_i = \rho_{i-1}/p^{(i)^T}q^{(i)}$ \\ 
          \>$x^{(i)} = x^{(i-1)} + \alpha_ip^{(i)} $ \\ 
          \>$r^{(i)} = r^{(i-1)} - \alpha_iq^{(i)} $ \\ 
          \>check convergence; continue if necessary \\ 
          {\bf end}
        \end{tabbing}
        }}
    
    \label{fig:pcg}
  \end{center}
\end{figure}
}


\stepcounter{subsubsection}
\newpage

{\samepage \clearpage $x^{(0)}+\mbox{span}\{r^{(0)},\ldots,A^{i-1}r^{(0)}\}$
}


\newpage

{\samepage \clearpage $(x^{(i)}-\hat{x})^TA(x^{(i)}-\hat{x})$
}


\newpage

{\samepage \clearpage $\hat{x}$
}


\newpage

{\samepage \clearpage $M\inv$
}


\newpage

{\samepage \clearpage $r^{(i)^T}
M^{-1} r^{(j)} = 0$
}


\newpage

{\samepage \clearpage $\mbox{span}\{r^{(0)},\ldots,A^{i-1}r^{(0)}\}$
}


\newpage

{\samepage \clearpage $\{A^ix\}_{i\geq0}$
}


\newpage

{\samepage \clearpage $LU$
}


\stepcounter{subsubsection}
\newpage

{\samepage \clearpage $\kappa_2$
}


\newpage

{\samepage \clearpage $M^{-1}A$
}


\newpage

{\samepage \clearpage $\lambda_{\max}$
}


\newpage

{\samepage \clearpage $\lambda_{\min}$
}


\newpage

{\samepage \clearpage $\kappa_2 (B) = \lambda_{\max}(B) / \lambda_{\min}(B)
)$
}


\newpage

{\samepage \clearpage \begin{equation}% latex2html id marker 648
\label{cg_cond}
\|x^{(i)} - \hat{x}\|_A \le 2 \alpha^i\|x^{(0)} - \hat{x}\|_A
\end{equation}
}


\newpage

{\samepage \clearpage % latex2html id marker 5171
$\alpha = (\sqrt{\kappa_2} - 1)/(\sqrt{\kappa_2}+1)$
}


\newpage

{\samepage \clearpage $\|y\|^2_A \equiv (y,Ay)$
}


\newpage

{\samepage \clearpage $\epsilon$
}


\newpage

{\samepage \clearpage $\sqrt{\kappa_2}$
}


\newpage

{\samepage \clearpage $\kappa_2 (A)=O(h^{-2})$
}


\newpage

{\samepage \clearpage $h^{-1}$
}


\stepcounter{subsubsection}
\stepcounter{subsubsection}
\stepcounter{subsection}
\newpage

{\samepage \clearpage $2$
}


\stepcounter{subsubsection}
\newpage

{\samepage \clearpage \begin{displaymath}  Ar^{(i)}=r^{(i+1)}t_{i+1,i}+r^{(i)}t_{i,i}+r^{(i-1)}t_{i-1,i},
\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}  AR_i=R_{i+1}\bar{T}_i,
\end{displaymath}
}


\newpage

{\samepage \clearpage $\bar{T}_i$
}


\newpage

{\samepage \clearpage $(i+1) \times i$
}


\newpage

{\samepage \clearpage \begin{displaymath}  \bar{T}_i=
  \begin{array}{cc}
    \begin{array}{ccc}
      \leftarrow & i &\rightarrow
    \end{array} &
    \begin{array}{c}
      \mbox{~~}
    \end{array}  \\ 
    \left(
    \begin{array}{cccc}
      \ddots & \ddots &    &      \\ 
      \ddots & \ddots & \ddots &     \\ 
      & \ddots & \ddots & \ddots \\ 
      &        & \ddots & \ddots \\ 
      &        &        & \ddots
    \end{array}
  \right) . &
  \begin{array}{c}
    \uparrow \\ 
    \mbox{~} \\ 
    i+1\\ 
    \mbox{~} \\ 
    \downarrow
  \end{array}
\end{array}
\end{displaymath}
}


\newpage

{\samepage \clearpage $(\cdot ,\cdot )_A$
}


\newpage

{\samepage \clearpage \begin{displaymath}  x^{(i)} \in \{r^{(0)}, Ar^{(0)}, \ldots,
  A^{i-1}r^{(0)}\},\mbox{~~}x^{(i)}=R_i\bar{y}
\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}  \|Ax^{(i)}-b\|_2 = \|AR_i\bar{y}-b\|_2
  =\|R_{i+1}\bar{T}_iy-b\|_2 .
\end{displaymath}
}


\newpage

{\samepage \clearpage $D_{i+1} \equiv \mbox{diag}
(\|r^{(0)}\|_2,\|r^{(1)}\|_2, ... , \|r^{(i)}\|_2)$
}


\newpage

{\samepage \clearpage $R_{i+1}D_{i+1}^{-1}$
}


\newpage

{\samepage \clearpage \begin{displaymath}  \|Ax^{(i)}-b\|_2=\|D_{i+1}\bar{T}_iy-\|r^{(0)}\|_2e^{(1)}\|_2
\end{displaymath}
}


\newpage

{\samepage \clearpage $(i+1,i)$
}


\newpage

{\samepage \clearpage $T_iy=\|r^{(0)}\|_2e^{(1)}$
}


\newpage

{\samepage \clearpage $T_i$
}


\newpage

{\samepage \clearpage $i \times i$
}


\newpage

{\samepage \clearpage $LQ$
}


\stepcounter{subsection}
\stepcounter{subsubsection}
\newpage

{\samepage \clearpage $A^T A x = A^T b$
}


\newpage

{\samepage \clearpage \begin{displaymath}  \left(
  \begin{array}{cc}
    I &  A \\ 
    A^T & 0
  \end{array} \right)
  \left(
  \begin{array}{c}
    r \\ 
    x \
  \end{array} \right) = \left(
  \begin{array}{c}
    b \\ 
    0
  \end{array} \right) .
\end{displaymath}
}


\newpage

{\samepage \clearpage $(p,A^TAp)$
}


\newpage

{\samepage \clearpage $(Ap,Ap)$
}


\stepcounter{subsection}
\newpage

{\samepage \clearpage $\mbox{span}\{r^{(0)},Ar^{(0)},A^2r^{(0)},\ldots\}$
}


\newpage

{\samepage \clearpage \begin{tabbing}xxxxxx\= \kill
\>  $w^{(i)} = A v^{(i)}$ \\ 
\>  {\bf for} \= $k = 1, \ldots , i$ \\ 
\>  \> $w^{(i)} = w^{(i)} - (w^{(i)}, v^{(k)}) v^{(k)}$ \\ 
\>  {\bf end} \\ 
\>  $v^{(i+1)} = w^{(i)} / \| w^{(i)} \|$
\end{tabbing}
}


\newpage

{\samepage \clearpage $\{A^kr^{(0)}\}$
}


\newpage

{\samepage \clearpage $(w^{(i)},v^{(k)})$
}


\newpage

{\samepage \clearpage $\|w^{(i)}\|$
}


\newpage

{\samepage \clearpage \begin{displaymath}  x^{(i)}=x^{(0)}+y_1v^{(1)}+\cdots+y_iv^{(i)},
\end{displaymath}
}


\newpage

{\samepage \clearpage $y_k$
}


\newpage

{\samepage \clearpage $\| b-Ax^{(i)} \|$
}


\newpage

{\samepage \clearpage $m$
}


\newpage

{\samepage \clearpage $(m)$
}


\newpage

{\samepage \clearpage \begin{figure}[tp]
  \begin{center}
    \leavevmode
    \framebox[4.5in]{\vbox{
        \begin{tabbing}
          $x^{(0)} $ is an initial guess  \\ 
          {\bf for} \= $j=1,2,....$  \\ 
          \> Solve $r$ from $Mr=b-Ax^{(0)}$  \\ 
          \> $v^{(1)}=r/\|r\|_2$  \\ 
          \> $s:=\|r\|_2e_1$  \\ 
          \> {\bf for} \= $i=1,2,...,m$  \\ 
          \>\> Solve $w$ from $Mw=Av^{(i)}$  \\ 
          \>\> {\bf for} \= $k=1,...,i$  \\ 
          \>\>\> $h_{k,i}=(w,v^{(k)})$  \\ 
          \>\>\> $w=w-h_{k,i}v^{(k)}$ \\ 
          \>\> {\bf end}  \\ 
          \>\> $h_{i+1,i}=\|w\|_2$ \\ 
          \>\> $v^{(i+1)}=w/h_{i+1,i}$  \\ 
          \>\> apply $J_1 ,..., J_{i-1}$ on $(h_{1,i},...,h_{i+1,i})$  \\ 
          \>\> construct $J_i$, acting on $i$th and $(i+1)$st component\\ 
          \>\> of $h_{.,i}$, such that $(i+1)$st component of $J_ih_{.,i}$ is 0 \\ 
          \>\> $s:=J_is$  \\ 
          \>\> if $s(i+1)$ is small enough then (UPDATE($\tilde{x},i$) and quit)  \\ 
          \> {\bf end}  \\ 
          \> UPDATE($\tilde{x},m$)  \\ 
          \>check convergence; continue if necessary \\ 
          {\bf end} \\ 
          \mbox{~}\\ 
          \mbox{In this scheme UPDATE($\tilde{x},i$)} \\ 
          \mbox{replaces the following computations:} \\ 
          \mbox{~} \\ 
          Compute $y$ as the solution of $Hy=\tilde{s}$, in which  \\ 
          the upper $i \times i$ triangular part of $H$ has $h_{i,j}$ as \\ 
          its elements (in least squares sense if $H$ is singular), \\ 
          $\tilde{s}$ represents the first $i$ components of $s$  \\ 
          $\tilde{x}=x^{(0)}+y_1 v^{(1)}+y_2 v^{(2)}+ . . . +y_i v^{(i)}$ \\ 
          $s^{(i+1)} = \|b-A\tilde{x}\|_2$ \\ 
          if $\tilde{x}$ is an accurate enough approximation then quit  \\ 
          else $x^{(0)}=\tilde{x}$
        \end{tabbing}
        }}
    
    \label{fig:pgmres}
  \end{center}
\end{figure}
}


\stepcounter{subsubsection}
\stepcounter{subsubsection}
\stepcounter{subsection}
\newpage

{\samepage \clearpage \begin{displaymath}% latex2html id marker 912
  r^{(i)}=r^{(i-1)}-\alpha_iAp^{(i)},\qquad
  \tilde r^{(i)}=\tilde r^{(i-1)}-\alpha_iA^T\tilde p^{(i)},
\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}  p^{(i)}=r^{(i-1)}+\beta_{i-1}p^{(i-1)},\qquad
  \tilde p^{(i)}=\tilde r^{(i-1)}+\beta_{i-1}\tilde p^{(i-1)}.
\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}% latex2html id marker 931
  \alpha_i={\tilde r^{(i-1)^T}r^{(i-1)}\over \tilde p^{(i)^T}Ap^{(i)}},
  \qquad
  \beta_i={\tilde r^{(i)^T}r^{(i)}\over \tilde r^{(i-1)^T}r^{(i-1)}}
\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}  \tilde r^{(i)^T}r^{(j)}=\tilde p^{(i)^T}Ap^{(j)}=0\qquad
  \hbox{if $i\not=j$}.
\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{figure}% latex2html id marker 950
[tp]
  \begin{center}
    \leavevmode
    \framebox[4.5in]{\vbox{
        \begin{tabbing}
          xxxx\=xxxx\=xxxx\=xxxx\= \kill
          Compute $r^{(0)} = b - Ax^{(0)}$ for some initial guess $x^{(0)}$. \\ 
          Choose $\tilde{r}^{(0)}$  (for example, $\tilde{r}^{(0)} = r^{(0)}$).\\ 
          {\bf for } \= $ i = 1, 2, \ldots $ \\ 
          \> solve $Mz^{(i-1)} = r^{(i-1)}$  \\ 
          \> solve $M^T\tilde{z}^{(i-1)}=\tilde{r}^{(i-1)}$ \\ 
          \> $\rho_{i-1}=z^{(i-1)^T}\tilde{r}^{(i-1)}$\\ 
          \> {\bf if} $\rho_{i-1} = 0$, {\bf method fails} \\ 
          \> {\bf if} $i = 1$ \\ 
          \> \> $p^{(i)} = z^{(i-1)}$\\ 
          \> \> $\tilde{p}^{(i)} = \tilde{z}^{(i-1)}$ \\ 
          \> {\bf else} \\ 
          \> \> $\beta_{i-1}=\rho_{i-1}/\rho_{i-2}$ \\ 
          \> \> $p^{(i)} = z^{(i-1)} + \beta_{i-1} p^{(i-1)}$ \\ 
          \> \> $\tilde{p}^{(i)} = \tilde{z}^{(i-1)} + \beta_{i-1} \tilde{p}^{(i-1)}$ \\ 
          \> {\bf endif} \\ 
          \> $q^{(i)} = Ap^{(i)}$ \\ 
          \> $\tilde{q}^{(i)} = A^T \tilde{p}^{(i)}$ \\ 
          \> $\alpha_i = \rho_{i-1} / \tilde{p}^{(i)^T} q^{(i)}$ \\ 
          \> $x^{(i)} = x^{(i-1)} + \alpha_i p^{(i)}$ \\ 
          \> $r^{(i)} = r^{(i-1)} - \alpha_i q^{(i)}$ \\ 
          \> $\tilde{r}^{(i)} = \tilde{r}^{(i-1)} - \alpha_i \tilde{q}^{(i)}$ \\ 
          \>check convergence; continue if necessary \\ 
          {\bf end}
        \end{tabbing}
        }}
    
    \label{fig:pbcg}
  \end{center}
\end{figure}
}


\stepcounter{subsubsection}
\newpage

{\samepage \clearpage $z^{(i-1)^T}\tilde{r}^{(i-1)}\approx 0$
}


\newpage

{\samepage \clearpage $\tilde{p}^{(i)^T}q^{(i)}\approx 0$
}


\stepcounter{subsubsection}
\newpage

{\samepage \clearpage $Ap^{(k)}$
}


\newpage

{\samepage \clearpage $A^T\tilde{p}^{(k)}$
}


\stepcounter{subsection}
\newpage

{\samepage \clearpage \begin{figure}% latex2html id marker 1063
[tp]
  \begin{center}
    \leavevmode
    \framebox[4.5in]{
      \vbox{
        \begin{tabbing}
          Compute $r^{(0)} = b - Ax^{(0)}$ for some initial guess $x^{(0)}$ \\ 
          $\tilde{v}^{(1)} = r^{(0)}$; {\bf solve} $M_1 y = \tilde{v}^{(1)}$; $\rho_1 = \|y\|_2$ \\ 
          Choose $\tilde{w}^{(1)}$ , for example $\tilde{w}^{(1)}=r^{(0)}$ \\ 
          {\bf solve} $M_2^t z = \tilde{w}^{(1)}$; $\xi_1 =\|z\|_2 $\\ 
          $\gamma_0 = 1; \eta_0 = -1$\\ 
          {\bf for } \= $ i = 1, 2, \ldots$ \\ 
          \>{\bf if} $\rho_{i} = 0$ or $\xi_{i} = 0$ {\bf method fails}  \\ 
          \>$v^{(i)} = \tilde{v}^{(i)} / \rho_{i}$; $y=y/ \rho_{i}$ \\ 
          \>$w^{(i)} = \tilde{w}^{(i)} / \xi_{i}$;  $z=z/ \xi_{i}$ \\ 
          \>$\delta_i=z^Ty$; {\bf if} $\delta_i = 0$ {\bf method fails} \\ 
          \>{\bf solve } $M_2\tilde{y}=y$\\ 
          \>{\bf solve } $M_1^T\tilde{z}=z$ \\ 
          \> {\bf if } \= $i = 1$ \\ 
          \> \> $p^{(1)} = \tilde{y}$; $q^{(1)} = \tilde{z}$ \\ 
          \> \> {\bf else} \\ 
          \>   \>$p^{(i)} = \tilde{y} - (\xi_i\delta_i / \epsilon_{i-1})p^{(i-1)}$ \\ 
          \>   \>$q^{(i)} = \tilde{z} - (\rho_i\delta_i / \epsilon_{i-1})q^{(i-1)}$ \\ 
          \> {\bf endif } \\ 
          \> $\tilde{p}=Ap^{(i)}$  \\ 
          \> $\epsilon_i = q^{(i)^T} \tilde{p}$; {\bf if} $\epsilon_i = 0 $ {\bf method fails} \\ 
          \> $\beta_i = \epsilon_i / \delta_i$;
          {\bf if} $\beta_i = 0$ {\bf method fails} \\ 
          \> $\tilde{v}^{(i+1)} = \tilde{p} - \beta_i v^{(i)}$ \\ 
          \> {\bf solve} $M_1 y = \tilde{v}^{(i+1)}$ \\ 
          \> $\rho_{i+1} = \|y\|_2$ \\ 
          \> $\tilde{w}^{(i+1)} = A^Tq^{(i)} - \beta_i w^{(i)}$ \\ 
          \> {\bf solve} $M_2^T z = \tilde{w}^{(i+1)}$ \\ 
          \> $\xi_{i+1} = \|z\|_2$ \\ 
          \> $\theta_i = \rho_{i+1} / (\gamma_{i-1}|\beta_i|)$;
          $\gamma_i = 1 / {\sqrt{1 + \theta_i^2}}$;
          {\bf if} $\gamma_i = 0$ {\bf method fails} \\ 
          \> $\eta_i = -\eta_{i-1} \rho_i \gamma_i^2 / (\beta_i \gamma_{i-1}^2)$ \\ 
          \> {\bf if } $i = 1$ \\ 
          \> \> $d^{(1)} = \eta_1 p^{(1)}$; $s^{(1)} = \eta_1\tilde{p}$\\ 
          \> {\bf else } \\ 
          \> \>$d^{(i)} = \eta_i p^{(i)} + (\theta_{i-1}\gamma_i)^2 d^{(i-1)}$ \\ 
          \> \>$s^{(i)}=\eta_i\tilde{p}+(\theta_{i-1}\gamma_i)^2s^{(i-1)}$ \\ 
          \> {\bf endif } \\ 
          \> $x^{(i)} = x^{(i-1)} + d^{(i)}$ \\ 
          \> $r^{(i)} = r^{(i-1)} - s^{(i)}$ \\ 
          \> check convergence; continue if necessary \\ 
          {\bf end}
        \end{tabbing}
        }}
    \vspace{.1in}\\ 

    
    \label{fig:pqmr}
  \end{center}
\end{figure}
}


\stepcounter{subsubsection}
\stepcounter{subsubsection}
\newpage

{\samepage \clearpage $M = M_1M_2$
}


\newpage

{\samepage \clearpage $M_1=I$
}


\newpage

{\samepage \clearpage $\|r^{(i)}\|$
}


\newpage

{\samepage \clearpage $\sqrt{i+1}$
}


\stepcounter{subsection}
\newpage

{\samepage \clearpage \begin{equation}  \label{eqn:cgs}
  r^{(i)} = P_i(A)r^{(0)}.
\end{equation}
}


\newpage

{\samepage \clearpage $\widetilde{r}^{(i)}=P_i(A^T)\widetilde{r}^{(0)}$
}


\newpage

{\samepage \clearpage \begin{equation}  \label{eqn:cgs2}
  \rho_i = (\tilde{r}^{(i)},r^{(i)}) = (P_i(A^T)\tilde{r}^{(0)},
  P_i(A)r^{(0)}) = (\tilde{r}^{(0)},P_i^2(A)r^{(0)}).
\end{equation}
}


\newpage

{\samepage \clearpage $P_i(A)$
}


\newpage

{\samepage \clearpage $P_i^2(A)r^{(0)}$
}


\newpage

{\samepage \clearpage \begin{figure}% latex2html id marker 1233
[tp]
  \begin{center}
    \leavevmode
    \framebox[4.5in]{\vbox{
        \begin{tabbing}
          Compute $r^{(0)} = b - Ax^{(0)}$ for some initial guess $x^{(0)}$ \\ 
          Choose $\tilde{r}$ (for example, $\tilde{r} = r^{(0)}$) \\ 
          {\bf for } \= $ i = 1, 2, \ldots $ \\ 
          \>$ \rho_{i-1} = \tilde{r}^Tr^{(i-1)} $ \\ 
          \>{\bf if} $\rho_{i-1} = 0$ {\bf method fails} \\ 
          \> {\bf if } \= $i = 1$ \\ 
          \>\> $u^{(1)}=r^{(0)}$ \\ 
          \>\> $p^{(1)}=u^{(1)}$ \\ 
          \> {\bf else } \\ 
          \>\> $\beta_{i-1} = \rho_{i-1} / \rho_{i-2}$ \\ 
          \>\> $ u^{(i)} = r^{(i-1)} + \beta_{i-1} q^{(i-1)} $ \\ 
          \>\> $ p^{(i)} = u^{(i)} + \beta_{i-1} (q^{(i-1)} + \beta_{i-1} p^{(i-1)})$ \\ 
          \> {\bf endif } \\ 
          \> {\bf solve} $M\hat{p} = p^{(i)} $ \\ 
          \> $ \hat{v} = A\hat{p} $ \\ 
          \> $ \alpha_i = \rho_{i-1} / \tilde{r}^T\hat{v} $ \\ 
          \> $ q^{(i)} = u^{(i)} - \alpha_i \hat{v} $ \\ 
          \> {\bf solve} $M\hat{u} = u^{(i)} + q^{(i)} $ \\ 
          \> $x^{(i)}=x^{(i-1)}+\alpha_i \hat{u}$ \\ 
          \> $\hat{q}=A\hat{u}$ \\ 
          \> $r^{(i)} = r^{(i-1)} - \alpha_i \hat{q} $ \\ 
          \> check convergence; continue if necessary \\ 
          {\bf end}
        \end{tabbing}
        }}

    
    \label{fig:pcgs}
  \end{center}
\end{figure}
}


\stepcounter{subsubsection}
\newpage

{\samepage \clearpage $r^{(k)} = P_k(A)r^{(0)}$
}


\stepcounter{subsubsection}
\stepcounter{subsection}
\newpage

{\samepage \clearpage $i\mapsto P_i^2(A)r^{(0)}$
}


\newpage

{\samepage \clearpage $i\mapsto Q_i(A)P_i(A)r^{(0)}$
}


\newpage

{\samepage \clearpage $Q_i$
}


\newpage

{\samepage \clearpage \begin{figure}% latex2html id marker 1320
[tp]
  \begin{center}
    \leavevmode
    \framebox[4.5in]{\vbox{
        \begin{tabbing}
          Compute $r^{(0)} = b - Ax^{(0)}$ for some initial guess $x^{(0)}$ \\ 
          Choose $\tilde{r}$ (for example, $\tilde{r} = r^{(0)}$) \\ 
          {\bf for } \= $ i = 1, 2, \ldots$ \\ 
          \>$\rho_{i-1} = \tilde{r}^Tr^{(i-1)}$ \\ 
          \> {\bf if} $\rho_{i-1} = 0$ {\bf method fails} \\ 
          \> {\bf if} \= $i = 1$ \\ 
          \>\> $p^{(i)}=r^{(i-1)}$ \\ 
          \> {\bf else} \\ 
          \>\> $\beta_{i-1}  = (\rho_{i-1}/\rho_{i-2})(\alpha_{i-1}/\omega_{i-1})$ \\ 
          \>\> $p^{(i)} = r^{(i-1)} + \beta_{i-1} (p^{(i-1)} - \omega_{i-1}v^{(i-1)})$ \\ 
          \> {\bf endif} \\ 
          \>{\bf solve} $M\hat{p} = p^{(i)}$ \\ 
          \>$v^{(i)} = A\hat{p}$ \\ 
          \>$\alpha_i = \rho_{i-1}/\tilde{r}^Tv^{(i)}$ \\ 
          \>$s = r^{(i-1)} - \alpha_i v^{(i)}$ \\ 
          \>check norm of $s$; if small enough: set $x^{(i)}=x^{(i-1)}+\alpha_i\hat{p}$
          and stop \\ 
          \>{\bf solve} $M\hat{s} = s$ \\ 
          \>$t = A\hat{s}$ \\ 
          \>$\omega_i = t^Ts/t^Tt$ \\ 
          \>$x^{(i)} = x^{(i-1)} + \alpha_i \hat{p} + \omega_i\hat{s}$ \\ 
          \>$r^{(i)} = s - \omega_i t$ \\ 
          \>check convergence; continue if necessary \\ 
          \> for continuation it is necessary that $\omega_i \neq 0$ \\ 
          {\bf end}
        \end{tabbing}
        }}
    
    \label{fig:pbcgstab}
  \end{center}
\end{figure}
}


\stepcounter{subsubsection}
\newpage

{\samepage \clearpage $\omega_i$
}


\newpage

{\samepage \clearpage $s$
}


\stepcounter{subsubsection}
\stepcounter{subsection}
\stepcounter{subsubsection}
\newpage

{\samepage \clearpage $d > 0$
}


\newpage

{\samepage \clearpage $d + c$
}


\newpage

{\samepage \clearpage $d - c$
}


\newpage

{\samepage \clearpage $r$
}


\newpage

{\samepage \clearpage \begin{equation}\label{eqn:minr}
r = {a + \sqrt{a^2 - c^2}\over {d + \sqrt{d^2 - c^2}}},
\end{equation}
}


\newpage

{\samepage \clearpage $a$
}


\newpage

{\samepage \clearpage $[ \lambda _{min}, \lambda _{max} ] $
}


\stepcounter{subsubsection}
\stepcounter{subsubsection}
\newpage

{\samepage \clearpage $w$
}


\newpage

{\samepage \clearpage $p$
}


\newpage

{\samepage \clearpage \begin{figure}% latex2html id marker 1448
[tp]
  \begin{center}
    \leavevmode
    \framebox[4.5in]{\vbox{
        \begin{tabbing}
          Compute $r^{(0)} = b - Ax^{(0)}$ for some initial guess $x^{(0)}$.\\ 
          $d=(\lambda_{\max}+\lambda_{\min})/2$, $c=(\lambda_{\max}-\lambda_{\min})/2$. \\ 
          {\bf for } \= $ i = 1, 2, \ldots$ \\ 
          \>{\bf solve} $Mz^{(i-1)} = r^{(i)} $.\\ 
          \> {\bf if } \= $i = 1$ \\ 
          \>\> $p^{(1)}=z^{(0)} $ \\ 
          \>\> $\alpha_1=2/d$ \\ 
          \> {\bf else}  \\ 
          \>\> $\beta_{i-1}=\alpha_{i-1}(c/2)^2$\\ 
          \>\> $\alpha_i=1/(d-\beta_{i-1})$ \\ 
          \>\> $ p^{(i)} = z^{(i-1)} + \beta_{i-1}p^{(i-1)} $.\\ 
          \> {\bf endif } \\ 
          \> $x^{(i)} = x^{(i-1)} + \alpha_ip^{(i)} $.\\ 
          \> $r^{(i)} = b - Ax^{(i)} \mbox{~~~}(=r^{(i-1)}-\alpha_iAp^{(i)})$.\\ 
          \> check convergence; continue if necessary \\ 
          {\bf end}
        \end{tabbing}
        }}
    
    \label{fig:pcheby}
  \end{center}
\end{figure}
}


\stepcounter{section}
\newpage

{\samepage \clearpage \begin{table}[tv]
  \begin{minipage}{\textwidth}
    \begin{center}
    \begin{tabular}{|l|c|c|c|c|}      \hline
                &          &       & Matrix- &         \\ 
                & Inner   &       & Vector  & Precond \\ 
Method          & Product & {\tt SAXPY} & Product & Solve   \\  \hline
JACOBI    &       &       & $1^a$\footnotetext[1]{This
  method performs no real matrix vector product or preconditioner
  solve, but the number of operations is equivalent to a matrix-vector
  multiply.}
                                &         \\ 
GS        &       & 1     & $1^a$ &       \\ 
SOR       &       & 1     & $1^a$ &       \\ 
CG        & 2     & 3     & 1     & 1     \\ 
GMRES     & $i+1$ & $i+1$ & 1     & 1     \\ 
BiCG      & 2     & 5     & 1/1   & 1/1   \\ 
QMR       & 2     & 8+$4^{bc}$\footnotetext[2]{True {\tt SAXPY} operations
$+$ vector scalings.}\footnotetext[3]{Less for
                                 implementations that do not
                                 recursively update the residual.}
                          & 1/1   & 1/1   \\ 
CGS       & 2     & 6     & 2     & 2     \\ 
Bi-CGSTAB & 4     & 6     & 2     & 2     \\ 
CHEBYSHEV &       & 2     & 1     & 1     \\  \hline
\end{tabular}\end{center}

\label{perf_ops_tbl}
\end{minipage}
\end{table}
}


\newpage

{\samepage \clearpage \begin{table}[tv]
\begin{minipage}{\textwidth}
\begin{center}
\begin{tabular}{|l|c|}      \hline

Method  & Storage   \\ 
        & Reqmts    \\  \hline
JACOBI  & $\mbox{matrix} + 3n$   \\ 
SOR     & $\mbox{matrix} + 2n$   \\ 
CG      & $\mbox{matrix} + 6n$    \\ 
GMRES   & $\mbox{matrix} + (i+5)n$    \\ 
BiCG    & $\mbox{matrix} + 10n$    \\ 
CGS     & $\mbox{matrix} + 11n$    \\ 
Bi-CGSTAB &$\mbox{matrix} + 10n$    \\ 
QMR     & $\mbox{matrix} + 16n^c$\footnotetext[3]{Less for
                                 implementations that do not
                                 recursively update the residual.}   \\ 
CHEBYSHEV & $\mbox{matrix} + 5n$ \\  \hline
\end{tabular}

\label{store_tbl}
\end{center}
\end{minipage}
\end{table}
}


\newpage

{\samepage \clearpage $\omega > 1$
}


\stepcounter{section}
\stepcounter{section}
\newpage

{\samepage \clearpage $T$
}


\stepcounter{chapter}
\stepcounter{section}
\newpage

{\samepage \clearpage \begin{displaymath}  M^{-1}Ax=M^{-1}b
\end{displaymath}
}


\newpage

{\samepage \clearpage $A\inv$
}


\stepcounter{subsection}
\stepcounter{subsection}
\newpage

{\samepage \clearpage $A\rightarrow M^{-1}A$
}


\newpage

{\samepage \clearpage $M^{-1}$
}


\newpage

{\samepage \clearpage \begin{displaymath}  M_1^{-1} AM_2\inv(M_2x)=M_1^{-1} b.
\end{displaymath}
}


\newpage

{\samepage \clearpage $M_1=M_2^t$
}


\newpage

{\samepage \clearpage \begin{displaymath}  \mbox{solve $u$ from $Mu = v$},
\end{displaymath}
}


\newpage

{\samepage \clearpage $M_1$
}


\newpage

{\samepage \clearpage $M_2$
}


\newpage

{\samepage \clearpage $r_0\leftarrow M_1^{-1}r_0$
}


\newpage

{\samepage \clearpage $x_n\leftarrow M_2^{-1}x_n$
}


\newpage

{\samepage \clearpage $I$
}


\newpage

{\samepage \clearpage $\ncofm$
}


\newpage

{\samepage \clearpage \begin{displaymath}r_0\leftarrow M_1^{-1}r_0\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}x\leftarrow M_2^{-1}x\end{displaymath}
}


\newpage

{\samepage \clearpage $M_1=\nobreak I$
}


\stepcounter{section}
\newpage

{\samepage \clearpage \begin{displaymath}  m_{i,j} =
  \left\{
  \begin{array}{ll}
    a_{i,i} & \mbox{if $i=j$} \\ 
    0 & \mbox{otherwise}.
  \end{array}
  \right.
\end{displaymath}
}


\stepcounter{subsection}
\newpage

{\samepage \clearpage $S=\{1,\ldots,n\}$
}


\newpage

{\samepage \clearpage $S=\bigcup_i S_i$
}


\newpage

{\samepage \clearpage $S_i$
}


\newpage

{\samepage \clearpage \begin{displaymath}  m_{i,j} = \left\{ \begin{array}{ll}
  a_{i,j} & \mbox{if $i$ and $j$ are in the same index subset} \\ 
  0 & \mbox{otherwise}.
  \end{array}
  \right.
\end{displaymath}
}


\stepcounter{subsection}
\stepcounter{section}
\newpage

{\samepage \clearpage $P_n(x)=x^n$
}


\newpage

{\samepage \clearpage \begin{displaymath}  A=D+L+L^T
\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}  M=(D+L)D^{-1} (D+L)^T,
\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}  M(\omega)={1\over 2-\omega}({1\over\omega}D+L)
  ({1\over\omega}D)^{-1}({1\over\omega}D+L)^T.
\end{displaymath}
}


\newpage

{\samepage \clearpage $\kappa(M_{\omega_{\rm opt}}^{-1}
A)=O(\sqrt{\kappa(A)})$
}


\stepcounter{section}
\newpage

{\samepage \clearpage $M=LU$
}


\stepcounter{subsection}
\newpage

{\samepage \clearpage % latex2html id marker 6031
$A+\alpha I$
}


\newpage

{\samepage \clearpage % latex2html id marker 6033
$\alpha$
}


\stepcounter{subsubsection}
\newpage

{\samepage \clearpage $Mx=y$
}


\newpage

{\samepage \clearpage \begin{figure}[tp]
  \begin{center}
    \leavevmode
    \framebox[4.5in]{\vbox{
	\begin{tabbing}
	Let $M=LU$ and $y$ be given.\\ 
	{\bf for } \= $ i = 1, 2, \ldots$ \\ 
	\> $z_i=\ell_{ii}^{-1}(y_i-\sum_{j<i}\ell_{ij}z_j)$\\ 
	{\bf for } \= $ i = n,n-1, n-2, \ldots$ \\ 
	\> $x_i=u_{ii}^{-1}(z_i-\sum_{j>i}u_{ij}x_j)$
	\end{tabbing}
	}}
    
    \label{fig:lu-solv}
  \end{center}
\end{figure}
}


\newpage

{\samepage \clearpage $M=(D+L)D^{-1}(D+U)$
}


\newpage

{\samepage \clearpage \begin{displaymath} (D+L)z=y,\qquad (I+D^{-1} U)x=z\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath} (I+LD^{-1})z=y,\qquad (D+U)x=z.\end{displaymath}
}


\newpage

{\samepage \clearpage $D\inv$
}


\newpage

{\samepage \clearpage $M=(D+L)D^{-1}(D+U)=(D+L)(I+D^{-1} U)$
}


\newpage

{\samepage \clearpage \begin{figure}[tp]
  \begin{center}
    \leavevmode
    \framebox[4.5in]{\vbox{
	\begin{tabbing}
	Let $M=(D+L)(I+D^{-1} U)$ and $y$ be given.\\ 
	{\bf for } \= $ i = 1, 2, \ldots$ \\ 
	\> $z_i=d_{ii}^{-1}(y_i-\sum_{j<i}\ell_{ij}z_j)$\\ 
	{\bf for } \= $ i = n,n-1, n-2, \ldots$ \\ 
	\> $x_i=z_i-d_{ii}^{-1}\sum_{j>i}u_{ij}x_j$
	\end{tabbing}
	}}
    
    \label{fig:ldu-solv}
  \end{center}
\end{figure}
}


\newpage

{\samepage \clearpage $LD\inv$
}


\newpage

{\samepage \clearpage $D^{-1}
U$
}


\stepcounter{subsection}
\newpage

{\samepage \clearpage $S$
}


\newpage

{\samepage \clearpage $(i,j)$
}


\newpage

{\samepage \clearpage $a_{i,j}\not=0$
}


\newpage

{\samepage \clearpage $ILU(0)$
}


\newpage

{\samepage \clearpage $k+1$
}


\newpage

{\samepage \clearpage \begin{displaymath}  \mbox{for each $k$, $i,j>k$:}\quad
  a_{i,j}\leftarrow 
  \left\{ \begin{array}{ll}
  a_{i,j}-a_{i,k}a_{k,k}^{-1} a_{k,j} & \mbox{if $(i,j)\in S$} \\ 
  a_{i,j} & \mbox{otherwise}.
  \end{array}
  \right.
\end{displaymath}
}


\stepcounter{subsubsection}
\newpage

{\samepage \clearpage \begin{equation}	{\rm fill}(i,j)=1+\max\{{\rm fill}(i,k),{\rm fill}(k,i)\}.
	\label{eq:fill-def}\end{equation}
}


\newpage

{\samepage \clearpage $a_{ij}$
}


\stepcounter{subsubsection}
\newpage

{\samepage \clearpage $ILU$
}


\newpage

{\samepage \clearpage $A=D_A+L_A+U_A$
}


\newpage

{\samepage \clearpage $M=(D+L_A)\allowbreak D^{-1}(D+\nobreak
U_A)$
}


\newpage

{\samepage \clearpage \begin{figure}[tp]
  \begin{center}
    \leavevmode
    \framebox[4.5in]{\vbox{
	\begin{tabbing}
	Let $S$ be the nonzero set $\{(i,j)\colon a_{ij}\not=0\}$\\ 
	{\bf for } \= $ i = 1, 2, \ldots$ \\ 
	\> {\bf set} $d_{ii}\leftarrow a_{ii}$ \\ 
	{\bf for } \= $ i = 1, 2, \ldots$ \\ 
	\> {\bf set} $d_{ii}\leftarrow 1/d_{ii}$ \\ 
	\> {\bf for } \= $ j = i+1, i+2, \ldots$ \\ 
	\>	\> if $(i,j)\in S$ and $(j,i)\in S$ then \\ 
	\>	\> {\bf set} $d_{jj}\leftarrow
			d_{jj}-a_{ji}d_{ii}a_{ij}$
	\end{tabbing}
	}}
    
    \label{fig:d-ilu}
  \end{center}
\end{figure}
}


\stepcounter{subsubsection}
\newpage

{\samepage \clearpage $(i-1,j)$
}


\newpage

{\samepage \clearpage $(i,j-1)$
}


\newpage

{\samepage \clearpage \begin{displaymath}  d_{i,i}=\left\{ \begin{array}{ll}
  a_{1,1} & \mbox{if $i=1$} \\ 
  a_{i,i}-a_{i,i-1}d_{i-1}^{-1} a_{i-1,i} & \mbox{if $1<i\leq n$} \\ 
  a_{i,i}-a_{i,i-n}d_{i-n}^{-1} a_{i-n,i} & \mbox{if $i=kn+1$ with $k\geq1$} \\ 
  \begin{array}{rcl}
    a_{i,i} &-& a_{i,i-1}d_{i-1}^{-1} a_{i-1,i} \\ 
    & & \mbox{} -a_{i,i-n}d_{i-n}^{-1} a_{i-n,i}
  \end{array} & \mbox{otherwise}.
\end{array}
\right.
\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{tabbing}xxxxxx\= \kill
\>  Initially: $d_{i,i}=a_{i,i}$ for all $i$ \\ 
\>  {\bf for} \= $i=1..nm$ do: \\ 
\>  \> $\left\{ \begin{array}{ll}
  d_{i+1,i+1}=d_{i+1,i+1}-a_{i+1,i}d_{i,i}^{-1} a_{i,i+1} &
  \mbox{if there is no $k$} \\ 
  & \mbox{such that $i=kn$} \\ 
  d_{i+n,i+n}=d_{i+n,i+n}-a_{i+n,i}d_{i,i}^{-1} a_{i,i+n} &
  \mbox{if $i+n\leq nm$}
  \end{array}
  \right.$
\end{tabbing}
}


\stepcounter{subsubsection}
\newpage

{\samepage \clearpage $a_{i,k}a_{k,k}^{-1} a_{k,j}$
}


\newpage

{\samepage \clearpage $a_{i,i}$
}


\newpage

{\samepage \clearpage $O(h^{-2})$
}


\newpage

{\samepage \clearpage $A+O(h^2)D_A$
}


\newpage

{\samepage \clearpage $\kappa(M^{-1} A)=O(h^{-1})$
}


\newpage

{\samepage \clearpage \begin{displaymath} x_0=M^{-1} b\end{displaymath}
}


\newpage

{\samepage \clearpage $r_0$
}


\newpage

{\samepage \clearpage $r_i$
}


\newpage

{\samepage \clearpage % latex2html id marker 6285
$0<\alpha<\nobreak1$
}


\stepcounter{subsubsection}
\newpage

{\samepage \clearpage $n\times n$
}


\newpage

{\samepage \clearpage $(D+L)x=u$
}


\newpage

{\samepage \clearpage $n\times\nobreak n$
}


\newpage

{\samepage \clearpage \begin{figure}[tp]
  \begin{center}
    \leavevmode
    \framebox[4.5in]{\vbox{
	\begin{tabbing}
	{\bf for } \= $ k = 1, \ldots,2n-1$ \\ 
	\> {\bf do} \= {\bf in parallel for } $ i = \max(1,k+1-n),\min(n,k)$\\ 
	\> \> $j=k-i+1$\\ 
	\> \> $x_{i+(j-1)n}\leftarrow $ \= $ D_{i+(j-1)n}y_{i+(j-1)n}$ \\ 
	\> \> \> $-L_{i+(j-1)n}{i-1+(j-1)n}x_{i-1+(j-1)n}$ \\ 
	\> \> \> $-L_{i+(j-1)n}{i+(j-2)n}x_{i+(j-2)n}$ 
	\end{tabbing}
	}}
    
    \label{fig:wave-solve}
  \end{center}
\end{figure}
}


\newpage

{\samepage \clearpage $i+j=k$
}


\newpage

{\samepage \clearpage $i+j=k-1$
}


\newpage

{\samepage \clearpage $I-L$
}


\newpage

{\samepage \clearpage \begin{equation}  (I-L)^{-1} = \cases{I+L+L^2+L^3+\cdots\cr
    (I+L)(I+L^2)(I+L^4)\cdots}
	\label{eq:IL-expansions}\end{equation}
}


\newpage

{\samepage \clearpage $L_A$
}


\newpage

{\samepage \clearpage \begin{displaymath} A=D_A+L_A+U_A,\qquad M=(D+L_A)D^{-1}(D+U_A),\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath} M=(I+L)D(I+U),\qquad \hbox{where $L=L_AD\inv$, $U=D^{-1} U_A$}.\end{displaymath}
}


\newpage

{\samepage \clearpage $L_AD\inv$
}


\newpage

{\samepage \clearpage $M^{(p)}\approx M\inv$
}


\newpage

{\samepage \clearpage $M=(I+L)D(I+U)$
}


\newpage

{\samepage \clearpage \begin{figure}[tp]
  \begin{center}
    \leavevmode
    \framebox[4.5in]{\vbox{
	\begin{tabbing}
	Let $M=(I+L)D(I+U)$ and $y$ be given.\\ 
	$t\leftarrow y$\\ 
	{\bf for } \= $ k = 1, \ldots,p$ \\ 
	\> $t\leftarrow y-Lt$ \\ 
	$x\leftarrow D^{-1} t$, $t\leftarrow x$ \\ 
	{\bf for } \= $ k = 1, \ldots,p$ \\ 
	\> $x\leftarrow t-Ux$ 
	\end{tabbing}
	}}
    
    \label{fig:lu-neuman}
  \end{center}
\end{figure}
}


\newpage

{\samepage \clearpage $L=L_AD\inv$
}


\newpage

{\samepage \clearpage $U=D^{-1} U_A$
}


\newpage

{\samepage \clearpage \begin{equation}	M^{(p)}=\sum_{k=0}^p(-U)^pD^{-1}\sum_{k=0}^p(-L)^p,
	\label{eq:M-exp}\end{equation}
}


\newpage

{\samepage \clearpage $x=M^{(p)}y$
}


\stepcounter{subsubsection}
\stepcounter{subsection}
\stepcounter{subsubsection}
\newpage

{\samepage \clearpage \begin{figure}[tp]
  \begin{center}
    \leavevmode
    \framebox[4.5in]{\vbox{
	\begin{tabbing}
	{\bf for} \= $i=1,2,\dots$ \\ 
	\> $X_i\leftarrow A_{ii}$ \\ 
	{\bf for} \= $i=1,2,\dots$ \\ 
	\> Let $Y_i\approx X_i\inv$ \\ 
	\> {\bf for} \= $j=i+1,i+2,\ldots$ \\ 
	\> \> if $A_{ij}\not=0$ and $A_{ji}\not=0$, \\ 
	\> \> then $X_j\leftarrow X_j-A_{ji}Y_iA_{ij}$ 
	\end{tabbing}
	}}
    
    \label{fig:blu-fac}
  \end{center}
\end{figure}
}


\stepcounter{subsubsection}
\newpage

{\samepage \clearpage $d_{i,i}=1/a_{i,i}$
}


\newpage

{\samepage \clearpage \begin{figure}[tp]
  \begin{center}
    \leavevmode
    \framebox[4.5in]{\vbox{
	\begin{tabbing}
	Let $X$ be a banded matrix,\\ 
	factor $X=(I+L)D^{-1}(I+U)$,\\ 
	let $Y=(I-U)D(I-L)$
	\end{tabbing}
	}}
    
    \label{fig:apx-inv}
  \end{center}
\end{figure}
}


\stepcounter{subsubsection}
\newpage

{\samepage \clearpage \begin{figure}[tp]
  \begin{center}
    \leavevmode
    \framebox[4.5in]{\vbox{
	\begin{tabbing}
	$X_1=A_{1,1}$ \\ 
	{\bf for} \= $i \geq 1$ \\ 
	\> let $Y_i\approx X_i\inv$ \\ 
	\> $X_{i+1}=A_{i+1,i+1}-A_{i+1,i}Y_iA_{i,i+1}$
	\end{tabbing}
	}}
    
    \label{fig:blu-fac-tri}
  \end{center}
\end{figure}
}


\newpage

{\samepage \clearpage $(A_{i,i})$
}


\newpage

{\samepage \clearpage $X_i$
}


\newpage

{\samepage \clearpage $Y_i$
}


\stepcounter{subsubsection}
\newpage

{\samepage \clearpage \begin{displaymath}  A=(D+L)D^{-1}(D+U)=(D+L)(I+D^{-1} U)
\end{displaymath}
}


\newpage

{\samepage \clearpage $(I+L_AD^{-1})(D+U_A)$
}


\newpage

{\samepage \clearpage $U_Q$
}


\newpage

{\samepage \clearpage $X={\rm diag}(X_i)$
}


\newpage

{\samepage \clearpage \begin{displaymath}  M=(X+L)(I+X^{-1} U)
\end{displaymath}
}


\newpage

{\samepage \clearpage $Y={\rm diag}(Y_i)$
}


\newpage

{\samepage \clearpage \begin{displaymath}  M=(Y\inv+L)(I+YU).
\end{displaymath}
}


\stepcounter{subsection}
\stepcounter{subsection}
\newpage

{\samepage \clearpage $L^{-1}AA^TL^{-T}y=b$
}


\stepcounter{section}
\newpage

{\samepage \clearpage $A=I-B$
}


\newpage

{\samepage \clearpage $A^{-1}=\sum_{k=0}^\infty B^k$
}


\newpage

{\samepage \clearpage $A=M-N$
}


\newpage

{\samepage \clearpage \begin{displaymath}  M_p^{-1}=(\sum_{i=0}^{p-1}(I-M^{-1} A)^i)M^{-1} .
\end{displaymath}
}


\newpage

{\samepage \clearpage $kp$
}


\newpage

{\samepage \clearpage $M=P_n(A)$
}


\newpage

{\samepage \clearpage $P(0)=1$
}


\newpage

{\samepage \clearpage $\|I-M^{-1} A\|$
}


\newpage

{\samepage \clearpage $\max_i\sum_j|A_{i,j}|$
}


\stepcounter{section}
\stepcounter{subsection}
\newpage

{\samepage \clearpage $(A+A^T)/2$
}


\stepcounter{subsection}
\newpage

{\samepage \clearpage \begin{displaymath}  c_1\leq{x^TAx\over x^TBx}\leq c_2\quad\hbox{for all $x$},
\end{displaymath}
}


\newpage

{\samepage \clearpage $c_1$
}


\newpage

{\samepage \clearpage $c_2$
}


\newpage

{\samepage \clearpage \begin{displaymath} -\Delta(u_{n+1}-u_n)=-({\cal L}u_n-f).\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}  -(a(x,y)u_x)_x-(b(x,y)u_y)_y=f,
\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}  -(\tilde a(x)u_x)_x-(\tilde b(y)u_y)_y=f. 
\end{displaymath}
}


\stepcounter{subsection}
\newpage

{\samepage \clearpage \begin{displaymath}  {\cal L}={\cal L}_1+{\cal L}_2,\qquad
  \hbox{where ${\cal L}_1=-{\partial^2\over \partial x^2}$,
    ${\cal L}_2=-{\partial^2\over \partial y^2}$}.
\end{displaymath}
}


\newpage

{\samepage \clearpage $L_1$
}


\newpage

{\samepage \clearpage $L_2$
}


\newpage

{\samepage \clearpage ${\cal
L}_1$
}


\newpage

{\samepage \clearpage ${\cal L}_2$
}


\newpage

{\samepage \clearpage $L_1+L_2=(I+L_1)(I+L_2)-I-L_1L_2$
}


\newpage

{\samepage \clearpage \begin{displaymath}% latex2html id marker 2220
  (1+\alpha L_1)
  (1+\alpha L_2)u^{(m+1)} = 
  \left[(1+\beta L_1)
  (1+\beta L_2)\right]u^{(m)}
\end{displaymath}
}


\newpage

{\samepage \clearpage % latex2html id marker 6531
$\alpha$
}


\newpage

{\samepage \clearpage $\beta$
}


\newpage

{\samepage \clearpage $u^{(m)}$
}


\newpage

{\samepage \clearpage % latex2html id marker 6545
$I+\alpha L_1$
}


\newpage

{\samepage \clearpage $P_x\times P_y$
}


\stepcounter{chapter}
\stepcounter{section}
\newpage

{\samepage \clearpage $A^HAx=A^Hb$
}


\newpage

{\samepage \clearpage $(x,y)=\bar x^Ty$
}


\newpage

{\samepage \clearpage $(x,y)=x^Ty$
}


\newpage

{\samepage \clearpage $x^Tx=0$
}


\newpage

{\samepage \clearpage $x\not =0$
}


\stepcounter{section}
\newpage

{\samepage \clearpage $\delta A$
}


\newpage

{\samepage \clearpage $\delta b$
}


\newpage

{\samepage \clearpage $(A+\delta A)x^{(i)}=b+\delta b$
}


\newpage

{\samepage \clearpage $\{x^{(i)}\}$
}


\newpage

{\samepage \clearpage $e^{(i)} \equiv x^{(i)} - x$
}


\newpage

{\samepage \clearpage $maxit$
}


\newpage

{\samepage \clearpage $\|b\|$
}


\newpage

{\samepage \clearpage $\|A\|$
}


\newpage

{\samepage \clearpage $b$
}


\newpage

{\samepage \clearpage $r^{(i)} = Ax^{(i)}-b$
}


\newpage

{\samepage \clearpage $ 10^{-6}$
}


\newpage

{\samepage \clearpage $\pm 10^{-6} \|A\|$
}


\newpage

{\samepage \clearpage $\pm 10^{-6}
  \|b\|$
}


\newpage

{\samepage \clearpage $\varepsilon$
}


\newpage

{\samepage \clearpage $\varepsilon = 2^{-24} \approx 10^{-7}$
}


\newpage

{\samepage \clearpage $\varepsilon = 2^{-53} \approx 10^{-16}$
}


\newpage

{\samepage \clearpage \begin{tabbing}junkjunk \= junk \= junk \= junk \= junk \= junk \kill
 \> $i=0$ \\ 
 \> {\bf repeat} \\ 
 \> \> $i = i + 1$ \\ 
 \> \> Compute the approximate solution $x^{(i)}$. \\ 
 \> \> Compute the residual $r^{(i)} = Ax^{(i)} - b$. \\ 
 \> \> Compute $\|r^{(i)}\|$ and $\|x^{(i)}\|$. \\ 
 \> {\bf until} $i \geq maxit$ or $\|r^{(i)}\| \leq {\em stop\_tol} \cdot 
( \|A\| \cdot \| x^{(i)} \| + \|b\| )$.
\end{tabbing}
}


\newpage

{\samepage \clearpage $\| x^{(i)} \|$
}


\newpage

{\samepage \clearpage \begin{tabbing}junkjunk \= junk \= junk \= junk \= junk \= junk \kill
 \> {\bf until} $i \geq maxit$ or $\|r^{(i)}\| \leq {\em stop\_tol} \cdot \|b\| \; \; .$
\end{tabbing}
}


\newpage

{\samepage \clearpage $\|e^{(i)}\| \leq  \| A^{-1} \| \cdot \|r^{(i)}\|$
}


\newpage

{\samepage \clearpage $\|A^{-1}\|$
}


\newpage

{\samepage \clearpage \begin{tabbing}junkjunk \= junk \= junk \= junk \= junk \= junk \kill
 \> {\bf until} $i \geq maxit$ or $\|r^{(i)}\| \leq {\em stop\_tol} \cdot \|x^{(i)}\| / \|A^{-1}\| \; \; ,$
\end{tabbing}
}


\newpage

{\samepage \clearpage $\|e^{(i)}\| / \|x^{(i)}\|$
}


\stepcounter{subsection}
\newpage

{\samepage \clearpage $e^{(i)} = x^{(i)} - x$
}


\newpage

{\samepage \clearpage $e^{(i)}$
}


\newpage

{\samepage \clearpage \begin{displaymath}  \begin{array}{lcl}
    \|x\|_{\infty} & \equiv & \max_j |x_j| \; , \\ 
    \|x\|_{1} & \equiv & \sum_j |x_j| \; {\rm, and} \\ 
    \|x\|_{2} & \equiv & ( \sum_j |x_j|^2 )^{1/2} \; \; .
  \end{array}
\end{displaymath}
}


\newpage

{\samepage \clearpage % latex2html id marker 6697
$\|x\|_{B,\alpha} \equiv \|Bx\|_{\alpha}$
}


\newpage

{\samepage \clearpage % latex2html id marker 6701
$\alpha$
}


\newpage

{\samepage \clearpage $\infty$
}


\newpage

{\samepage \clearpage \begin{displaymath}  \begin{array}{lcl}
    \|A\|_{\infty} & \equiv & \max_j \sum_k |a_{j,k}| \; , \\ 
    \|A\|_{1} & \equiv & \max_k \sum_j |a_{j,k}| \; {\rm, and} \\ 
    \|A\|_{F} & \equiv & ( \sum_{jk} |a_{j,k}|^2 )^{1/2} \; \; ,
  \end{array}
\end{displaymath}
}


\newpage

{\samepage \clearpage % latex2html id marker 6709
$\|A\|_{B, \alpha} \equiv \|BAB^{-1}\|_{\alpha}$
}


\newpage

{\samepage \clearpage $\|A\|_2 = ( \lambda_{\max} ( AA^T ) )^{1/2}$
}


\newpage

{\samepage \clearpage $\|x\|$
}


\newpage

{\samepage \clearpage $\|x\|_2$
}


\newpage

{\samepage \clearpage $\|A\|_F$
}


\newpage

{\samepage \clearpage $\|A\|_2$
}


\newpage

{\samepage \clearpage $\|x+y\| \leq \|x\| + \|y\|$
}


\newpage

{\samepage \clearpage $\|A+B\| \leq \|A\| + \|B\|$
}


\newpage

{\samepage \clearpage $\|Ax\| \leq \|A\| \cdot \|x\|$
}


\newpage

{\samepage \clearpage $\|x\|_{\infty} \leq 1$
}


\newpage

{\samepage \clearpage $\sqrt{n}$
}


\newpage

{\samepage \clearpage $\|x\|_1$
}


\newpage

{\samepage \clearpage $\|e^{(i)}\|$
}


\newpage

{\samepage \clearpage $\max\{ \|\delta A\| / \|A\|, \|\delta b\| / \|b\| \}$
}


\newpage

{\samepage \clearpage $(A+ \delta A) x^{(i)} =
(b+ \delta b)$
}


\newpage

{\samepage \clearpage $\delta$
}


\newpage

{\samepage \clearpage \begin{displaymath}        e^{(i)} = x^{(i)} - x = A^{-1}(Ax^{(i)} - b) = A^{-1} r^{(i)},
       \end{displaymath}
}


\newpage

{\samepage \clearpage $\|r^{(i)}\|
\le \tau$
}


\newpage

{\samepage \clearpage $\|e^{(i)}\| \leq \tau \cdot \|A^{-1}\|$
}


\newpage

{\samepage \clearpage $\| e^{(i)} \| \leq \|
\, |A^{-1}| \cdot |r^{(i)}| \, \|$
}


\newpage

{\samepage \clearpage $|X|$
}


\newpage

{\samepage \clearpage $X$
}


\newpage

{\samepage \clearpage $\| \delta A \| \leq \varepsilon  \|A\|$
}


\newpage

{\samepage \clearpage $\| \delta b \| \leq \varepsilon \|b\|$
}


\newpage

{\samepage \clearpage $\|r^{(i)}\| \leq S_1 \equiv {\em stop\_tol} \cdot ( \|A\| \cdot \|x^{(i)}\| + \|b\|)$
}


\newpage

{\samepage \clearpage $\| \delta A \| \leq {\em stop\_tol} \cdot \|A\|$
}


\newpage

{\samepage \clearpage $\| \delta b \| \leq {\em stop\_tol} \cdot \|b\|$
}


\newpage

{\samepage \clearpage \begin{displaymath}  \|e^{(i)}\| \leq \| A^{-1} \| \cdot \|r^{(i)} \| \leq {\em stop\_tol} \cdot \|A^{-1}\| 
  \cdot ( \|A\| \cdot \|x^{(i)}\| + \|b\|) \; .
\end{displaymath}
}


\newpage

{\samepage \clearpage $\|r^{(i)}\| \leq S_2 \equiv {\em stop\_tol} \cdot \|b\|$
}


\newpage

{\samepage \clearpage $\delta A =0$
}


\newpage

{\samepage \clearpage $\| \delta b \| \leq tol \cdot \|b\|$
}


\newpage

{\samepage \clearpage $\|A\| \cdot \|x\| \gg \|b\|$
}


\newpage

{\samepage \clearpage \begin{displaymath}1 \ll \frac{\|A\| \cdot \|x\|}{\|b\|} = 
\frac{\|A\| \cdot \| A^{-1} b\|}{\|b\|} \leq \|A\| \cdot \|A^{-1}\| \; \; .\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}\|e^{(i)}\| \leq \| A^{-1} \| \cdot \| r^{(i)} \| \leq
{\em stop\_tol} \cdot \|A^{-1}\| \cdot \|b\|\end{displaymath}
}


\newpage

{\samepage \clearpage $\|A^{-1}\| \cdot \|r^{(i)}\|$
}


\newpage

{\samepage \clearpage $\|r^{(i)}\| \leq S_3 \equiv {\em stop\_tol} \cdot \|x^{(i)}\| / \| A^{-1} \|$
}


\newpage

{\samepage \clearpage \begin{displaymath}\frac{\|e^{(i)}\|}{\|x^{(i)}\|} \leq \frac{\|A^{-1}\| \cdot \|r^{(i)}\|}{\|x^{(i)}\|} \leq
{\em stop\_tol} \; \; ,\end{displaymath}
}


\newpage

{\samepage \clearpage $\| \delta A\|$
}


\newpage

{\samepage \clearpage $\| \delta b \|$
}


\newpage

{\samepage \clearpage $\delta a_{j,k}$
}


\newpage

{\samepage \clearpage $\delta b_j$
}


\newpage

{\samepage \clearpage $S_4 \equiv \max_j ( |r^{(i)}|_j / (E \cdot |x^{(i)}| + f)_j ) \leq
{\em stop\_tol}$
}


\newpage

{\samepage \clearpage $E$
}


\newpage

{\samepage \clearpage $f$
}


\newpage

{\samepage \clearpage $|z|$
}


\newpage

{\samepage \clearpage $| \delta a_{j,k} | \leq tol \cdot e_{j,k}$
}


\newpage

{\samepage \clearpage $| \delta b_{j} | \leq tol \cdot f_{j}$
}


\newpage

{\samepage \clearpage $e_{j,k} = \|A\|_{\infty}$
}


\newpage

{\samepage \clearpage $f_j=\|b\|_{\infty}$
}


\newpage

{\samepage \clearpage $\|r^{(i)}\|_{\infty} / (n \|A\|_{\infty} \|x^{(i)}\|_{\infty} + \|b\|_{\infty})$
}


\newpage

{\samepage \clearpage $e_{j,k} = |a_{j,k}|$
}


\newpage

{\samepage \clearpage $f_j = |b_j|$
}


\newpage

{\samepage \clearpage \begin{displaymath}\| e^{(i)} \|_{\infty} \leq \| \, |A^{-1}| \cdot |r^{(i)}| \, \| \leq
S_4 \cdot \| \, |A^{-1}| ( E |x^{(i)}| + f ) \|_{\infty}\end{displaymath}
}


\newpage

{\samepage \clearpage $A^{-1}$
}


\newpage

{\samepage \clearpage $\|r^{(i)}\| \leq S_5 \equiv {\em stop\_tol} \cdot \|r^{(0)}\|$
}


\newpage

{\samepage \clearpage $x^{(0)}$
}


\newpage

{\samepage \clearpage $x^{(0)} = 0$
}


\newpage

{\samepage \clearpage $r^{(0)} = b$
}


\newpage

{\samepage \clearpage $\|b\| \ll \|A\| \cdot \|x\|$
}


\newpage

{\samepage \clearpage $\|r^{(0)}\|$
}


\newpage

{\samepage \clearpage $S_5$
}


\newpage

{\samepage \clearpage $\|e^{(i)}\| \leq S_5 \cdot \|A^{-1}\|$
}


\stepcounter{subsection}
\newpage

{\samepage \clearpage $x^{(i)} = M^{-1}N x^{(i-1)} + M^{-1}b \equiv Gx^{(i-1)} + c$
}


\newpage

{\samepage \clearpage ${\hat{r}}^{(i)} = x^{(i)} - Gx^{(i)} - c = M^{-1}(A x^{(i)}-b) = M^{-1} r^{(i)}$
}


\newpage

{\samepage \clearpage ${\hat{r}}^{(i)}$
}


\newpage

{\samepage \clearpage $M^{-1}Ax = M^{-1}b$
}


\newpage

{\samepage \clearpage $\| e^{(i)} \| = \|A^{-1} M {\hat{r}}^{(i)} \| \leq \|A^{-1}M\| \cdot \|{\hat{r}}^{(i)} \|$
}


\newpage

{\samepage \clearpage $\|A^{-1}M\|$
}


\newpage

{\samepage \clearpage $A^{-1}M = (M-N)^{-1} M = (I-G)^{-1}$
}


\newpage

{\samepage \clearpage $\|A^{-1}M\| = \|(I-G)^{-1}\| \leq 1/(1-\|G\|)$
}


\newpage

{\samepage \clearpage $\|r^{(i)}\|_{M^{-1/2} , 2} =
(r^{(i)T} M^{-1} r^{(i)})^{1/2}$
}


\newpage

{\samepage \clearpage $\|r^{(i)}\|_2$
}


\newpage

{\samepage \clearpage $\|r^{(i)}\|_{M^{-1/2}
  , 2} / \|r^{(0)}\|_{M^{-1/2} , 2} \leq tol$
}


\newpage

{\samepage \clearpage $\|e^{(i)}\| \leq
\|A^{-1} M^{1/2}\| \cdot \|r^{(i)}\|_{M^{-1/2} , 2}$
}


\stepcounter{subsection}
\newpage

{\samepage \clearpage $e^{(i)} = A^{-1} r^{(i)}$
}


\newpage

{\samepage \clearpage \begin{displaymath}  x^{(i)} = M^{-1}Nx^{(i-1)} + M^{-1}b = Gx^{(i-1)} + c,
\end{displaymath}
}


\newpage

{\samepage \clearpage $I-G$
}


\newpage

{\samepage \clearpage $\|G\|$
}


\newpage

{\samepage \clearpage $\| (I-G)^{-1} \| \leq 1/(1-\|G\|)$
}


\newpage

{\samepage \clearpage $\lambda_{\max} (A)$
}


\newpage

{\samepage \clearpage $\lambda_{\min} (A)$
}


\newpage

{\samepage \clearpage $\|A^{-1}\|_2 = \lambda^{-1}_{\min} (A)$
}


\newpage

{\samepage \clearpage $\|A^{-1}\|_2 = 1/ \lambda^{1/2}_{\min} (AA^T)=1/ \lambda^{1/2}_{\min} (A^TA)$
}


\newpage

{\samepage \clearpage $\|A^{-1}\|_{\infty}$
}


\newpage

{\samepage \clearpage $O(n^2)$
}


\newpage

{\samepage \clearpage $O(n^3)$
}


\newpage

{\samepage \clearpage $\| e^{(i)} \|_{\infty} \leq \| \, |A^{-1}| \cdot |r^{(i)}| \, \|_{\infty}$
}


\newpage

{\samepage \clearpage $\| A^{-1} \|_{\infty} \cdot \|r^{(i)}\|_{\infty}$
}


\newpage

{\samepage \clearpage $\| \, |A^{-1}| \cdot |r^{(i)}| \, \|_{\infty}$
}


\newpage

{\samepage \clearpage $R$
}


\newpage

{\samepage \clearpage $\| \, |A^{-1}| \cdot |r^{(i)}| \, \|_{\infty} = \| A^{-1} R \|_{\infty}$
}


\newpage

{\samepage \clearpage $\| A^{-1} R \|_{\infty}$
}


\newpage

{\samepage \clearpage $ A^{-1} R $
}


\newpage

{\samepage \clearpage $( A^{-1} R )^T = R^T A^{-T}$
}


\newpage

{\samepage \clearpage $A^{-T}$
}


\stepcounter{subsection}
\stepcounter{subsection}
\newpage

{\samepage \clearpage $\|x\|_{\infty} = \max_j |x_j|$
}


\newpage

{\samepage \clearpage $x_j$
}


\newpage

{\samepage \clearpage $\pm \infty$
}


\newpage

{\samepage \clearpage $\|x\|_2 = ( \sum_j |x_j|^2 )^{1/2}$
}


\newpage

{\samepage \clearpage $\|x\|_{\infty}$
}


\newpage

{\samepage \clearpage $Ax^{(i)}$
}


\newpage

{\samepage \clearpage $\delta r^{(i)}$
}


\newpage

{\samepage \clearpage $\| \delta r^{(i)} \| \leq O( \varepsilon ) (\|A\| \cdot \|x^{(i)}\| + \|b\|)$
}


\newpage

{\samepage \clearpage $O( \varepsilon )$
}


\newpage

{\samepage \clearpage $n \varepsilon$
}


\newpage

{\samepage \clearpage $\sqrt{n} \varepsilon$
}


\newpage

{\samepage \clearpage ${\em stop\_tol} \leq \varepsilon$
}


\newpage

{\samepage \clearpage $O( \varepsilon ) \|A^{-1}\| \cdot ( \|A\| \cdot \|x^{(i)}\| + \|b\| )$
}


\newpage

{\samepage \clearpage $(\delta r^{(i)})_j$
}


\newpage

{\samepage \clearpage $|A| \cdot |x^{(i)}| + |b|$
}


\newpage

{\samepage \clearpage $O (\varepsilon ) \| \, |A^{-1}| \cdot (|A| \cdot |x^{(i)}| + |b|) \|$
}


\stepcounter{section}
\stepcounter{subsection}
\stepcounter{subsubsection}
\newpage

{\samepage \clearpage $3$
}


\newpage

{\samepage \clearpage ${\tt val(k)}=a_{i,j}$
}


\newpage

{\samepage \clearpage ${\tt col\_ind(k)}=j$
}


\newpage

{\samepage \clearpage ${\tt row\_ptr(i)}\leq k<{\tt row\_ptr(i+1)}$
}


\newpage

{\samepage \clearpage ${\tt row\_ptr(n+1)} = nnz+1$
}


\newpage

{\samepage \clearpage $nnz$
}


\newpage

{\samepage \clearpage $n^2$
}


\newpage

{\samepage \clearpage $2nnz+n+1$
}


\newpage

{\samepage \clearpage \begin{equation}\label{sparseA}
A =
\left(\begin{array}{rrrrrr}
      10 &  0 &  0 & 0  &-2 &  0 \\ 
       3 &  9 &  0 & 0  & 0 &  3 \\ 
       0 &  7 &  8 & 7  & 0 &  0 \\ 
       3 &  0 &  8 & 7  & 5 &  0 \\ 
       0 &  8 &  0 & 9  & 9 & 13 \\ 
       0 &  4 &  0 & 0  & 2 & -1
           \end{array}
\right) ~.
\end{equation}
}


\newpage

{\samepage \clearpage \begin{tabular}{|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|} \hline
{\tt val}     &10 &-2& 3& 9& 3& 7& 8& 7& 3 $\cdots$  9&13& 4& 2&-1 \\  \hline
{\tt col\_ind}& 1 & 5& 1& 2& 6& 2& 3& 4& 1 $\cdots$  5& 6& 2& 5& 6 \\  \hline
\end{tabular}
}


\newpage

{\samepage \clearpage \begin{tabular}{|r|r|r|r|r|r|r|r|} \hline
{\tt row\_ptr}& 1 & 3 & 6 & 9 & 13 & 17 & 20  \\  \hline
\end{tabular}
}


\stepcounter{subsubsection}
\newpage

{\samepage \clearpage \begin{tabular}{|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|} \hline
{\tt val}     &10 & 3& 3& 9& 7& 8& 4& 8& 8 $\cdots$  9& 2& 3&13&-1 \\  \hline
{\tt row\_ind}& 1 & 2& 4& 2& 3& 5& 6& 3& 4 $\cdots$  5& 6& 2& 5& 6 \\  \hline
\end{tabular}
}


\newpage

{\samepage \clearpage \begin{tabular}{|r|r|r|r|r|r|r|r|} \hline
{\tt col\_ptr}& 1 & 4 & 8 &10 & 13 & 17 & 20  \\  \hline
\end{tabular}
}


\stepcounter{subsubsection}
\newpage

{\samepage \clearpage $n_b$
}


\newpage

{\samepage \clearpage $nnzb$
}


\newpage

{\samepage \clearpage $nnz = nnzb \times n_b^2$
}


\newpage

{\samepage \clearpage $n_d$
}


\newpage

{\samepage \clearpage $ n_d = n / n_b $
}


\newpage

{\samepage \clearpage $1:nnzb$
}


\newpage

{\samepage \clearpage $1:n_b$
}


\newpage

{\samepage \clearpage $1,1$
}


\newpage

{\samepage \clearpage $1:n_d+1$
}


\stepcounter{subsubsection}
\newpage

{\samepage \clearpage $A=(a_{i,j})$
}


\newpage

{\samepage \clearpage $q$
}


\newpage

{\samepage \clearpage $i-p\leq j\leq i+q$
}


\newpage

{\samepage \clearpage ${\tt p}+{\tt
q}$
}


\newpage

{\samepage \clearpage \begin{equation}\label{sparseA2}
A =
\left(\begin{array}{rrrrrr}
      10 & -3 &  0 & 0  & 0 &  0  \\ 
       3 &  9 &  6 & 0  & 0 &  0  \\ 
       0 &  7 &  8 & 7  & 0 &  0  \\ 
       0 &  0 &  8 & 7  & 5 &  0  \\ 
       0 &  0 &  0 & 9  & 9 & 13  \\ 
       0 &  0 &  0 & 0  & 2 & -1
           \end{array}
\right) ~.
\end{equation}
}


\newpage

{\samepage \clearpage \begin{equation}\label{eqn:diag-conversion}
        {\tt val(i,j)}=a_{i,i+j}. \end{equation}
}


\newpage

{\samepage \clearpage \begin{tabular}{|r|r|r|r|r|r|r|r|r|r|r|} \hline
{\tt val(:,-1)}& 0& 3& 7& 8& 9& 2\\  \hline
{\tt val(:, 0)}&10& 9& 8& 7& 9&-1\\  \hline
{\tt val(:,+1)}&-3& 6& 7& 5&13& 0\\  \hline
\end{tabular}
}


\newpage

{\samepage \clearpage $S = \{(i,\sigma(i));~i \in I \subseteq I_n\}$
}


\newpage

{\samepage \clearpage $I_n =
\{1, \ldots,n\}$
}


\newpage

{\samepage \clearpage $\sigma$
}


\newpage

{\samepage \clearpage $(i,\sigma(i))$
}


\newpage

{\samepage \clearpage $(j,\sigma(j))$
}


\newpage

{\samepage \clearpage \begin{displaymath} i < j \rightarrow \sigma(i) < \sigma(j)\end{displaymath}
}


\newpage

{\samepage \clearpage $y=Ax$
}


\newpage

{\samepage \clearpage $(i,\sigma_k(i))$
}


\newpage

{\samepage \clearpage $S_k$
}


\newpage

{\samepage \clearpage $x_{\sigma_k(i)}$
}


\newpage

{\samepage \clearpage $y_{\sigma_k(i)}$
}


\newpage

{\samepage \clearpage $y_i$
}


\newpage

{\samepage \clearpage \begin{equation}\label{sparseA3}
A =
\left(\begin{array}{rrrrrr}
      10 & -3 &  0 & 1  & 0 &  0  \\ 
       0 &  9 &  6 & 0  &-2 &  0  \\ 
       3 &  0 &  8 & 7  & 0 &  0  \\ 
       0 &  6 &  0 & 7  & 5 &  4  \\ 
       0 &  0 &  0 & 0  & 9 & 13  \\ 
       0 &  0 &  0 & 0  & 5 & -1
           \end{array}
\right) ~,
\end{equation}
}


\newpage

{\samepage \clearpage $4$
}


\newpage

{\samepage \clearpage \begin{tabular}{|r|r|r|r|r|r|r|r|r|r|r|} \hline
{\tt val(:,-1)}& 0& 0& 3& 6& 0& 5\\  \hline
{\tt val(:, 0)}&10& 9& 8& 7& 9&-1\\  \hline
{\tt val(:,+1)}& 0&-3& 6& 7& 5&13\\  \hline
{\tt val(:,+2)}& 0& 1&-2& 0& 4& 0\\  \hline
\end{tabular}
}


\stepcounter{subsubsection}
\newpage

{\samepage \clearpage \begin{displaymath}\left(\begin{array}{rrrrrr}
      10 & -3 &  0 & 1  & 0 &  0  \\ 
       0 &  9 &  6 & 0  &-2 &  0  \\ 
       3 &  0 &  8 & 7  & 0 &  0  \\ 
       0 &  6 &  0 & 7  & 5 &  4  \\ 
       0 &  0 &  0 & 0  & 9 & 13  \\ 
       0 &  0 &  0 & 0  & 5 & -1
           \end{array}
\right) \longrightarrow
\left(\begin{array}{rrrr}
      10 & -3 &  1 \\ 
       9 &  6 & -2  \\ 
       3 &  8 &  7 \\ 
       6 &  7 & 5 &  4  \\ 
       9 & 13  \\ 
       5 & -1
           \end{array}
\right)
\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}\begin{array}{|r|r|r|r|r|r|r|}
\hline
{\tt val}(:,1) & 10 &  9 &  3 &  6 &  9 &  5 \\  \hline
{\tt val}(:,2) & -3 &  6 &  8 &  7 & 13 & -1 \\  \hline
{\tt val}(:,3) &  1 & -2 &  7 &  5 &  0 &  0 \\  \hline
{\tt val}(:,4) &  0 &  0 &  0 &  4 &  0 &  0 \\  \hline
\end{array},
\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}\begin{array}{|r|r|r|r|r|r|r|}
\hline
{\tt col\_ind}(:,1) &  1 &  2 &  1 &  2 &  5 &  5 \\  \hline
{\tt col\_ind}(:,2) &  2 &  3 &  3 &  4 &  6 &  6 \\  \hline
{\tt col\_ind}(:,3) &  4 &  5 &  4 &  5 &  0 &  0 \\  \hline
{\tt col\_ind}(:,4) &  0 &  0 &  0 &  6 &  0 &  0 \\  \hline
\end{array}.
\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{tabular}{|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|r|} \hline
          {\tt jdiag}     & 6 & 9& 3&10& 9 & 5; & 7& 6& 8              &-3&13&-1;&5 & -2 & 7 & 1; & 4; \\  \hline
{\tt col\_ind}  & 2 & 2 & 1  & 1 & 5 & 5; & 4 & 3 & 3  & 2  & 6  & 6; & 5  & 5 & 4 & 4; & 6;  \\  \hline
\end{tabular}
}


\newpage

{\samepage \clearpage \begin{tabular}{|r|r|r|r|r|r|r|} \hline
{\tt perm}    & 4 & 2 & 3 & 1 & 5 & 6  \\  \hline
\end{tabular}
}


\newpage

{\samepage \clearpage \begin{tabular}{|r|r|r|r|r|} \hline
{\tt jd\_ptr} & 1 & 7 & 13 & 17 \\  \hline
\end{tabular}
}


\stepcounter{subsubsection}
\newpage

{\samepage \clearpage \begin{figure}[hbt]
\begin{tabular}{|ccccccccccccccccc|} \hline
+ & x & x &   &   &   &   &   &   &   &   &   &   &   &   &   &   \\ 
x & + & x & x &   &   &   &   &   &   &   &   &   &   &   &   &   \\ 
x & x & + & x &   &   & x &   &   &   &   &   &   &   &   &   &   \\ 
  & x & x & + & x & x & x & x &   &   &   &   &   &   &   &   &   \\ 
  &   &   & x & + & x & x & x &   &   &   &   &   &   &   &   &   \\ 
  &   & x & x & x & + & x & x &   &   &   &   &   &   &   &   &   \\ 
  &   &   &   & x & x & + & x &   &   & x &   & x &   &   &   &   \\ 
  &   &   &   & x & x & x & + & x & x & x &   & x &   &   &   &   \\ 
  &   &   &   & x & x & x & x & + & x & x &   & x &   &   &   &   \\ 
  &   &   &   &   &   &   &   & x & + & x & x & x &   &   &   &   \\ 
  &   &   &   &   &   & x & x & x & x & + & x & x &   &   &   &   \\ 
  &   &   &   &   &   &   &   &   & x & x & + & x &   &   & x &   \\ 
  &   &   &   &   &   &   &   &   & x & x & x & + & x & x & x &   \\ 
  &   &   &   &   &   &   &   &   &   &   & x & x & + & x & x &   \\ 
  &   &   &   &   &   &   &   &   &   &   &   &   &   & + & x & x \\ 
  &   &   &   &   &   &   &   &   &   &   &   & x & x & x & + & x \\ 
  &   &   &   &   &   &   &   &   &   &   &   &   &   &   &   & + \\  \hline
\end{tabular}

\end{figure}
}


\stepcounter{subsection}
\newpage

{\samepage \clearpage \begin{displaymath} y=Ax\qquad\hbox{and}\qquad y=A^Tx.\end{displaymath}
}


\stepcounter{subsubsection}
\newpage

{\samepage \clearpage \begin{displaymath} y_i=\sum_j a_{i,j}x_j\end{displaymath}
}


\newpage

{\samepage \clearpage $2n^2$
}


\newpage

{\samepage \clearpage $y=A^Tx$
}


\newpage

{\samepage \clearpage \begin{displaymath}y_i=\sum_j (A^T)_{i,j}x_j=\sum_j a_{j,i}x_j,\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath} \hbox{for all $j$, do for all $i$:}\qquad y_i\leftarrow
        y_i+a_{j,i}x_j.\end{displaymath}
}


\stepcounter{subsubsection}
\newpage

{\samepage \clearpage $j\rightarrow i+j$
}


\newpage

{\samepage \clearpage \begin{displaymath}      y_i\leftarrow y_i+a_{i,j}x_j
                \quad\Rightarrow\quad
                y_i\leftarrow y_i+a_{i,i+j}x_{i+j} ~\end{displaymath}
}


\newpage

{\samepage \clearpage $a_{i,i+j}$
}


\newpage

{\samepage \clearpage \begin{displaymath} 1\leq {\tt i},{\tt i+j}\leq n\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{eqnarray*}        y_i&\leftarrow&y_i+a_{i+j,i}x_j \\ 
        &=&y_i+a_{i+j,i+j-j}x_{i+j}
\end{eqnarray*}
}


\stepcounter{subsection}
\newpage

{\samepage \clearpage $QMR$
}


\stepcounter{subsubsection}
\newpage

{\samepage \clearpage $(D_A+L_A)D_A^{-1}(D_A+U_A)$
}


\newpage

{\samepage \clearpage ${\tt val(diag\_ptr(i))}=a_{i,i}$
}


\newpage

{\samepage \clearpage $a_{i,j}$
}


\newpage

{\samepage \clearpage $j>i$
}


\newpage

{\samepage \clearpage $a_{j,i}$
}


\newpage

{\samepage \clearpage $a_{j,j}$
}


\stepcounter{subsubsection}
\newpage

{\samepage \clearpage $LUy=x$
}


\newpage

{\samepage \clearpage \begin{displaymath} Lz=x,\qquad Uy=z.\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{eqnarray*}  LU&=&(D+L_A)D^{-1}(D+U_A)\\ 
  &=&(I+L_AD^{-1})(D+U_A)\\ 
  &=&(D+L_A)(I+D^{-1}U_A)\\ 
  &=&(I+L_AD^{-1})D(I+D^{-1}U_A)
\end{eqnarray*}
}


\stepcounter{subsubsection}
\newpage

{\samepage \clearpage $(LU)^Ty=x$
}


\newpage

{\samepage \clearpage $L^T$
}


\newpage

{\samepage \clearpage $U^T$
}


\newpage

{\samepage \clearpage $L=(l_{*1},l_{*2},\ldots~)$
}


\newpage

{\samepage \clearpage $Ly=x$
}


\newpage

{\samepage \clearpage $x=l_{*1}y_1+l_{*2}y_2+\cdots$
}


\newpage

{\samepage \clearpage $y_1$
}


\newpage

{\samepage \clearpage $x\leftarrow x-l_{*1}y_1$
}


\stepcounter{subsubsection}
\newpage

{\samepage \clearpage $ILU(k)$
}


\newpage

{\samepage \clearpage \begin{displaymath} \hbox{if {\tt xind(j)=i} then ${\tt x(j)}=x_i$.}\end{displaymath}
}


\newpage

{\samepage \clearpage % latex2html id marker 7451
${\tt This is not counting the initial zeroing of the $w$~array.} x\leftarrow {\tt \vbox{
        \begin{tabbing}{ll}
          aaa\=bbb\=ccc\=abcdefghijklmnopqrstuvwxyzabcdefg\= \kill
          \> $x^{(-1)}=x^{(0)}$= initial guess; $r^{(0)}=b-Ax^{(0)};$ \\  
          \> $p^{(-1)}=0; \beta_{-1}=0; \alpha_{-1}=0;$\\  
          \> $s=L^{-1}r^{(0)}$; \\  
          \> $\rho_0=(s,s)$ \\  
          \> {\bf for} $i=0,1,2,....$  \\  
          \> \> $w^{(i)}=L^{-T}s;$                \> \>  \\  
          \> \> $p^{(i)}=w^{(i)}+ \beta_{i-1}p^{(i-1)}$;\> \>  \\  
          \> \> $q^{(i)}=Ap^{(i)};$                   \> \>  \\  
          \> \> $\gamma =(p^{(i)},q^{(i)});$          \> \>  \\  
          \> \> $x^{(i)}=x^{(i-1)}+\alpha_{i-1}p^{(i-1)};$ \> \>  \\  
          \> \> $\alpha_i={\rho_i}/{\gamma}$;   \> \>  \\  
          \> \> $r^{(i+1)}=r^{(i)}-\alpha_{i} q^{(i)};$ \> \>  \\  
          \> \> $s=L^{-1}r^{(i+1)};$            \> \>  \\  
          \> \> $\rho_{i+1}=(s,s);$           \> \>  \\  
          \> \> {\bf if} $\|r^{(i+1)}\|$ {\em small enough}
          {\bf then}\> \>  \\  
          \> \> \> $x^{(i+1)}=x^{(i)}+\alpha_ip^{(i)}$     \>  \\  
          \> \> \> quit;                         \>  \\  
          \> \> {\bf endif} \\  
          \> \> $\beta_i={\rho_{i+1}}/{\rho_i}$; \\  
          \> {\bf end};
        \end{tabbing}
        }} x+{\tt \em or\/} y$
}


\newpage

{\samepage \clearpage $O({\tt lx}+{\tt ly})$
}


\newpage

{\samepage \clearpage $x\leftarrow x+\sum_ky^{(k)}$
}


\newpage

{\samepage \clearpage $y^{(i)}$
}


\newpage

{\samepage \clearpage $M=(D+L)(I+D^{-1} U)$
}


\stepcounter{section}
\newpage

{\samepage \clearpage $Ap^{(i)}$
}


\newpage

{\samepage \clearpage $A^T p^{(i)}$
}


\stepcounter{subsection}
\stepcounter{subsubsection}
\newpage

{\samepage \clearpage $x^{(i+1)}$
}


\newpage

{\samepage \clearpage $r^{(i+1)}$
}


\newpage

{\samepage \clearpage % latex2html id marker 7483
$\alpha_i$
}


\newpage

{\samepage \clearpage $\beta_{i-1}$
}


\newpage

{\samepage \clearpage $p^{(i)^T}Ap^{(i)}$
}


\newpage

{\samepage \clearpage $M=LL^T$
}


\newpage

{\samepage \clearpage $L^{-1}r^{(i)}$
}


\newpage

{\samepage \clearpage $r^{(i)^T}M^{-1}r^{(i)}$
}


\newpage

{\samepage \clearpage $s^Ts$
}


\newpage

{\samepage \clearpage $s=L^{-1}r^{(i)}$
}


\newpage

{\samepage \clearpage $L^{-T}s$
}


\newpage

{\samepage \clearpage \begin{figure}[ht]
  \begin{center}
    \leavevmode
    \framebox[4.0in]

    
    \label{fig:rearrangedcg}
    \end{center}
  \end{figure}
}


\newpage

{\samepage \clearpage $\gamma$
}


\newpage

{\samepage \clearpage $\rho_{i+1}$
}


\newpage

{\samepage \clearpage $q^{(i)}$
}


\newpage

{\samepage \clearpage $LDL^T$
}


\stepcounter{subsubsection}
\stepcounter{subsection}
\stepcounter{subsection}
\newpage

{\samepage \clearpage $Ap_i$
}


\newpage

{\samepage \clearpage $p_i$
}


\stepcounter{subsection}
\stepcounter{paragraph}
\stepcounter{paragraph}
\stepcounter{paragraph}
\stepcounter{subsection}
\newpage

{\samepage \clearpage $D-L$
}


\newpage

{\samepage \clearpage $i+d$
}


\stepcounter{subsection}
\newpage

{\samepage \clearpage $M^{-1}Av^{(j)}$
}


\newpage

{\samepage \clearpage $v^{(1)}$
}


\newpage

{\samepage \clearpage $v^{(2)}$
}


\newpage

{\samepage \clearpage $v^{(j)}$
}


\newpage

{\samepage \clearpage $Av^{(1)}$
}


\newpage

{\samepage \clearpage $A^mv^{(1)}$
}


\stepcounter{chapter}
\stepcounter{section}
\newpage

{\samepage \clearpage $n \times k$
}


\newpage

{\samepage \clearpage $R^{(k)}$
}


\newpage

{\samepage \clearpage \begin{displaymath}  R_k = [ r^{(0)}, ~ r^{(1)}, ~ \ldots,~ r^{(k-1)} ] ,
\end{displaymath}
}


\newpage

{\samepage \clearpage $k \times k$
}


\newpage

{\samepage \clearpage $B_k$
}


\newpage

{\samepage \clearpage \begin{displaymath}  B_k = \left [
  \begin{array}{ccccc}
    1       & - \beta_1 &              & \cdots    & 0         \\ 
    &    1      & - \beta_2    &           &\vdots     \\ 
    &  \ddots   & \ddots       &  \ddots   &           \\ 
    \vdots  &           & \ddots       &  \ddots   & - \beta_{k-1} \\ 
    0       &  \cdots   &              &           & 1         \\ 
  \end{array}
\right ] ,
\end{displaymath}
}


\newpage

{\samepage \clearpage $\{r^{(k)}\}$
}


\newpage

{\samepage \clearpage $\{\beta_k\}$
}


\newpage

{\samepage \clearpage \begin{displaymath}  p^{(j)} = r^{(j-1)} + \beta_{j-1} p^{(j-1)}, ~ j = 2,~3,~ \ldots,~ k~,
\end{displaymath}
}


\newpage

{\samepage \clearpage $p^{(1)}=r^{(0)}$
}


\newpage

{\samepage \clearpage $R_k = P_k B_k$
}


\newpage

{\samepage \clearpage \begin{displaymath}  P_k = [ p^{(1)}, ~ p^{(2)}, ~ \ldots,~ p^{(k)} ] .
\end{displaymath}
}


\newpage

{\samepage \clearpage $\{p^{(j)}\}$
}


\newpage

{\samepage \clearpage \begin{displaymath}  \hat{T}_k = R_k^T A R_k = B_k^T \hat{\Lambda}_k B_k 
\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}  \hat{\Lambda}_k  = \left [
  \begin{array}{ccccc}
    p^{(1)^T}Ap^{(1)}&   0      &              & \cdots    & 0         \\ 
    0    &p^{(2)^T}Ap^{(2)}  &              &           &\vdots     \\ 
    &  \ddots   & \ddots       &  \ddots   &           \\ 
    \vdots  &           & \ddots       &  \ddots   &  0        \\ 
    0       &  \cdots   &              &   0       & p^{(k)^T}Ap^{(k)} \\ 
  \end{array}
\right ] .
\end{displaymath}
}


\newpage

{\samepage \clearpage $p^{(1)},~p^{(2)},~\ldots,~p^{(j)}$
}


\newpage

{\samepage \clearpage $r^{(0)},~r^{(1)},~\ldots,~r^{(j-1)}$
}


\newpage

{\samepage \clearpage $\{r^{(j)}\}$
}


\newpage

{\samepage \clearpage $Q_k = R_k\Delta^{-1}$
}


\newpage

{\samepage \clearpage ${\rm span}\{b,~ Ab,~ \ldots,~ A^{k-1}b\}$
}


\newpage

{\samepage \clearpage $\Delta$
}


\newpage

{\samepage \clearpage $Q_k$
}


\newpage

{\samepage \clearpage \begin{equation}  T_k = \Delta^{-1} B_k^T \hat\Lambda_k B_k \Delta^{-1} ~.
  \label{proj}
\end{equation}
}


\newpage

{\samepage \clearpage $T_k$
}


\stepcounter{section}
\newpage

{\samepage \clearpage $n_b-1$
}


\stepcounter{section}
\newpage

{\samepage \clearpage \begin{displaymath}  M^{-1} A x = M^{-1}f
\end{displaymath}
}


\newpage

{\samepage \clearpage $Ax=f$
}


\newpage

{\samepage \clearpage $Mz=r$
}


\newpage

{\samepage \clearpage $5$
}


\newpage

{\samepage \clearpage \begin{equation}  \label{redblk}
  Ax= \left[ \begin{array}{cc} D_R & C \\  C^T & D_B
\end{array} \right]   \left[ \begin{array}{c} x_R \\  x_B
\end{array} \right] = \left[ \begin{array}{c} f_R \\  f_B
\end{array} \right]~,
\end{equation}
}


\newpage

{\samepage \clearpage $D_R$
}


\newpage

{\samepage \clearpage $D_B$
}


\newpage

{\samepage \clearpage $C$
}


\newpage

{\samepage \clearpage \begin{displaymath} \left[ \begin{array}{cc} I & O \\  -C^TD_R^{-1} & I \end{array} \right]   
 \left[ \begin{array}{cc} D_R & C \\  C^T & D_B  \end{array} \right]   
  \left[ \begin{array}{c} x_R \\  x_B \end{array} \right] = 
 \left[ \begin{array}{cc} I & O \\  -C^TD_R^{-1} & I \end{array} \right]   
  \left[ \begin{array}{c} f_R \\  f_B \end{array} \right] 
\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath} \left[ \begin{array}{cc} D_R & C \\  O & D_B-C^T{D_R}^{-1}C\end{array} \right] 
 \left[ \begin{array}{c} x_R \\  x_B \end{array} \right] = 
 \left[ \begin{array}{c} f_R \\  f_B -C^T{D_R}^{-1}f_R \end{array}
\right] .
\end{displaymath}
}


\newpage

{\samepage \clearpage ${D_B}^{-1/2}$
}


\newpage

{\samepage \clearpage \begin{equation}  \label{rs}
  (I-H^TH)y =g ~,
\end{equation}
}


\newpage

{\samepage \clearpage $H = D_R^{-1/2}CD_B^{-1/2}$
}


\newpage

{\samepage \clearpage $y=D_B^{1/2}x_B$
}


\newpage

{\samepage \clearpage $g =
D_B^{-1/2}(f_B-C^TD_R^{-1}f_R)$
}


\newpage

{\samepage \clearpage $n^2/2$
}


\newpage

{\samepage \clearpage $(n^2-1)/2$
}


\newpage

{\samepage \clearpage $n \ge 250$
}


\stepcounter{section}
\newpage

{\samepage \clearpage \begin{eqnarray}  -\nabla \cdot (a(x,y) \nabla u) = f(x,y) \label{prob}
\end{eqnarray}
}


\newpage

{\samepage \clearpage $a(x,y)$
}


\newpage

{\samepage \clearpage $\Omega$
}


\newpage

{\samepage \clearpage $u$
}


\newpage

{\samepage \clearpage $T_H$
}


\newpage

{\samepage \clearpage $\Omega_i, i=1,...,p$
}


\newpage

{\samepage \clearpage $n_H$
}


\newpage

{\samepage \clearpage $\Omega_i$
}


\newpage

{\samepage \clearpage $T_h$
}


\newpage

{\samepage \clearpage $H, h$
}


\newpage

{\samepage \clearpage $Au=f$
}


\newpage

{\samepage \clearpage $S_Bu_B=g_B$
}


\newpage

{\samepage \clearpage $Av$
}


\newpage

{\samepage \clearpage $Sw$
}


\newpage

{\samepage \clearpage $v$
}


\newpage

{\samepage \clearpage $K^{-1}v$
}


\stepcounter{subsection}
\newpage

{\samepage \clearpage $\omip$
}


\newpage

{\samepage \clearpage $n'_i$
}


\newpage

{\samepage \clearpage $T'_i \subset T_h$
}


\newpage

{\samepage \clearpage $A'_i, A_H$
}


\newpage

{\samepage \clearpage $T'_i$
}


\newpage

{\samepage \clearpage $R^T_i$
}


\newpage

{\samepage \clearpage $R_i$
}


\newpage

{\samepage \clearpage $R^T_H$
}


\newpage

{\samepage \clearpage $R_H$
}


\newpage

{\samepage \clearpage $K_{as}$
}


\newpage

{\samepage \clearpage \begin{displaymath}K_{as}^{-1}v = R_H^T A_H^{-1} R_H v+ \sum_{i=1}^p R_i^T {A'}_i^{-1} R_i v.\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$p\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$A'_i\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$A_H\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$ R_i^T {A'}_i^{-1} R_i v \end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$v_i=R_i v\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$w_i\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$A'_i w_i=v_i\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$y_i=R^T_i w_i\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$K_{as}^{-1}A\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$H\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$h\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$\Omega_i\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$\omip\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$\delta/H\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$\delta\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$ \partial \omip\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$ \partial \Omega_i\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$h \rightarrow 0\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$O(1/H^2)\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$K_{as}\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$\Omega\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$u\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$I_i\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$n'_i\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$n'_i \times n'_i\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$A\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$R^T_i\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$n \times n'_i\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$u_i\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$T'_i\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$(R^T_i u_i)_j=(u_i)_j\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$j \in I_i\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$R_i u\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$R^T_H\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$n \times n_H\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$T_h\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$T_H\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$R_H, R^T_H\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$R^T_i, R_i, R^T_H, R_H\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$R_i, A'_i\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$A_H, R_H\end{displaymath}
}


\stepcounter{subsection}
\newpage

{\samepage \clearpage $\bigcup_{i} \partial \omip$
}


\newpage

{\samepage \clearpage $u\equiv (u_I,u_B)^T$
}


\newpage

{\samepage \clearpage $f\equiv (f_I, f_B)^T$
}


\newpage

{\samepage \clearpage \begin{eqnarray}\left( \begin{array}{cc}
       A_I      & A_{IB} \\ 
      A^T_{IB}  & A_B    
   \end{array} \right) 
\left(\begin{array}{c} u_I \\  u_B \end{array} \right) =
\left(\begin{array}{c} f_I \\  f_B \end{array} \right). \label{block-eqn1}
\end{eqnarray}
}


\newpage

{\samepage \clearpage $A_{I} = blockdiagonal(A_{i})$
}


\newpage

{\samepage \clearpage $A_i$
}


\newpage

{\samepage \clearpage \begin{eqnarray}\left(\begin{array}{cc}
       I      & 0 \\ 
      A^T_{IB}A_I^{-1}  & I 
      \end{array} \right) 
\left(\begin{array}{cc}
       A_I      & A_{IB} \\ 
      0  & S_B 
      \end{array} \right) 
\left(\begin{array}{c} u_I \\  u_B \end{array} \right) =
\left(\begin{array}{c} f_I \\  f_B \end{array} \right), \label{block-eqn2}
\end{eqnarray}
}


\newpage

{\samepage \clearpage \begin{displaymath}S_B \equiv A_B - A_{IB}^T A_I^{-1} A_{IB}\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$A_B\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$u_I\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$u_B\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{eqnarray}S_B u_B = g_B \equiv f_B-A_{IB}A_I^{-1}f_I.  \label{SB-eqn}
\end{eqnarray}
}


\newpage

{\samepage \clearpage \begin{displaymath}$S_B\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$O(h^{-1})\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$O(h^{-2})\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$v_B\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$B\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$S_B v_B\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$A_Bv_B - A_{IB}^T (A_I^{-1} (A_{IB}v_B))\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$A_{I}^{-1}\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$A_i^{-1}\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$g_B\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{eqnarray}B = E \cup V_H  \label{BPS-part}
\end{eqnarray}
}


\newpage

{\samepage \clearpage \begin{displaymath}$V_H=\bigcup_k V_k\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$V_k\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$E=\bigcup_i E_i\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$E_i\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$V_H\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$R_{E_i}\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$n_{E_i} \times n\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$n_{E_i}\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$(R_{E_i} u_B)_j = (u_B)_j\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$j \in E_i\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$S\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{eqnarray}S_B=\left(\begin{array}{cc}
       S_E     & S_{EV} \\ 
       S^T_{EV}  & S_V 
      \end{array} \right). \label{SB-block}
\end{eqnarray}
}


\newpage

{\samepage \clearpage \begin{displaymath}$S_E\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$S_{E_i}\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$S_{E_i}^{-1}\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}% latex2html id marker 8035
M_{E_i} = \alpha_{E_i} K^{1/2}\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$K\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$n_{E_i} \times n_{E_i}\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$2\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$-1\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}% latex2html id marker 8045
$\alpha_{E_i}\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$a(x,y)\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$M_{E_i}\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{eqnarray}K_{BPS}^{-1} v_B = R^T_H A^{-1}_H R_H v_B +
 \sum_{E_i} R^T_{E_i} M_{E_i}^{-1} R_{E_i} v_B. \label{BPS-def1}
\end{eqnarray}
}


\newpage

{\samepage \clearpage \begin{displaymath}$K_{BPS}^{-1}S_B\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$O(1+\log^2(H/h))\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$\log^2(H/h)\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$K_{BPS}\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$X=\bigcup_k X_k\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$X_k\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$X\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$E\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$S_{X_k}\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$R_{X_k}, R^T_{X_k}\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$K^{1/2}\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$M_{X_k}\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{eqnarray}  K_{VS}^{-1} v_B &=& R^T_H A^{-1}_H R_H v_B +
  \sum_{E_i} R^T_{E_i} M_{E_i}^{-1} R_{E_i} v_B \nonumber \\ 
  & & \mbox{} + \sum_{X_k} R^T_{X_k} M_{X_k}^{-1} R_{X_k} v_B.
  \label{VS-def1}
\end{eqnarray}
}


\newpage

{\samepage \clearpage \begin{displaymath}$K_{VS}^{-1}S_B\end{displaymath}
}


\stepcounter{subsection}
\stepcounter{subsubsection}
\stepcounter{subsubsection}
\newpage

{\samepage \clearpage ${A'}_i^{-1}, A_i^{-1}$
}


\newpage

{\samepage \clearpage $A_H^{-1}$
}


\newpage

{\samepage \clearpage $K_{as}, K_{BPS}, K_{VS}$
}


\newpage

{\samepage \clearpage ${\tilde{A'}}_i^{-1}, \tilde{A}_i^{-1}$
}


\newpage

{\samepage \clearpage $\tilde{A}_H^{-1}$
}


\newpage

{\samepage \clearpage \begin{displaymath}\tilde{K}_{as}^{-1}v = 
R_H^T \tilde{A}_H^{-1} R_H v+ \sum_{i=1}^p R_i^T {\tilde{A'}}_i^{-1} R_i v.\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$A_H^{-1}\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$\tilde{A}_H^{-1}\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$K_{VS}\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$\tilde{K}_{BPS}\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$\tilde{K}_{VS}\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$\tilde{A}_i\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$A_i\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$A_I, S_B\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$\tilde{A}_I, \tilde{S}_B\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$\tilde{S}_B\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$\tilde{A}_H\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$\tilde{A}_H^{-1}A_H\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$\tilde{A}_i^{-1}A_i\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}$A_{IB}\end{displaymath}
}


\stepcounter{subsubsection}
\newpage

{\samepage \clearpage $H$
}


\stepcounter{subsubsection}
\stepcounter{section}
\newpage

{\samepage \clearpage $2\times2$
}


\newpage

{\samepage \clearpage \begin{displaymath} A^{(i)}=\pmatrix{A^{(i)}_{1,1}&A^{(i)}_{1,2}\cr
                A^{(i)}_{2,1}&A^{(i)}_{2,2}}\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath} A^{(i+1)}\approx S^{(i)}=A^{(i)}_{2,2}-
                A^{(i)}_{2,1}A^{(i)^{-1}}_{1,1}A^{(i)}_{1,2}.\end{displaymath}
}


\stepcounter{section}
\newpage

{\samepage \clearpage \begin{displaymath} A^T=[A_1,\ldots,A_m]\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath} P_ix=A_i(A^T_iA_i)^{-1} A^T_ix.\end{displaymath}
}


\appendix
\stepcounter{chapter}
\newpage

{\samepage \clearpage \begin{tabular}{l l}
          shar filename   &           contents \\ 
\hline
         sctemplates.shar &     Single precision C routines\\ 
         dctemplates.shar &     Double precision C routines\\ 
         sftemplates.shar &     Single Precision Fortran 77 routines\\ 
         dftemplates.shar &     Double Precision Fortran 77 routines\\ 
         mltemplates.shar &     MATLAB routines\\ 
         cpptemplates.shar &    C++ template routines\\ 
\end{tabular}
}


\newpage

{\samepage \clearpage \begin{tabular}{l l}
          shar filename   &           contents \\ 
\hline
         sctemplates.shar &     Single precision C routines\\ 
         dctemplates.shar &     Double precision C routines\\ 
         sftempaltes.shar &     Single Precision Fortran 77 routines\\ 
         dftemplates.shar &     Double Precision Fortran 77 routines\\ 
         mltemplates.shar &     MATLAB kernels\\ 
\end{tabular}
}


\stepcounter{chapter}
\newpage

{\samepage \clearpage $Tx = b$
}


\newpage

{\samepage \clearpage $a_{i,j} = $
}


\newpage

{\samepage \clearpage % latex2html id marker 8227
$\alpha$
}


\newpage

{\samepage \clearpage % latex2html id marker 8233
$\alpha$
}


\newpage

{\samepage \clearpage $Ax + b$
}


\newpage

{\samepage \clearpage $b - A\hat{x}$
}


\newpage

{\samepage \clearpage $Ax$
}


\stepcounter{chapter}
\newpage

{\samepage \clearpage $a_{i,j}=0$
}


\newpage

{\samepage \clearpage $j<i-p$
}


\newpage

{\samepage \clearpage $j>i+q$
}


\newpage

{\samepage \clearpage $A=LL^T$
}


\newpage

{\samepage \clearpage $\{x^TAx:x^Tx=1\}$
}


\newpage

{\samepage \clearpage $[\lambda_{\min}(A),\lambda_{\max}(A)]$
}


\newpage

{\samepage \clearpage $A\not=LU$
}


\newpage

{\samepage \clearpage $Q$
}


\newpage

{\samepage \clearpage $A=LQ$
}


\newpage

{\samepage \clearpage $A=LU$
}


\newpage

{\samepage \clearpage $a_{i,i}>\sum_{j\not=i}|a_{i,j}|$
}


\newpage

{\samepage \clearpage $\min_i\{a_{i,i}-\sum_{j\not=i}|a_{i,j}|\}$
}


\newpage

{\samepage \clearpage $A A^T y = b$
}


\newpage

{\samepage \clearpage $A^H$
}


\newpage

{\samepage \clearpage $f:R^n\rightarrow R$
}


\newpage

{\samepage \clearpage $f(x)\geq0$
}


\newpage

{\samepage \clearpage $f(x)=0$
}


\newpage

{\samepage \clearpage $x=0$
}


\newpage

{\samepage \clearpage % latex2html id marker 8401
$f(\alpha x)=|\alpha|f(x)$
}


\newpage

{\samepage \clearpage % latex2html id marker 8403
$\alpha$
}


\newpage

{\samepage \clearpage $f(x+y)\leq f(x)+f(y)$
}


\newpage

{\samepage \clearpage $\|\cdot\|$
}


\newpage

{\samepage \clearpage \begin{displaymath}    \|Ax\|\leq \|A\|\,\|x\|.
  \end{displaymath}
}


\newpage

{\samepage \clearpage $i+j$
}


\newpage

{\samepage \clearpage $Ay-b$
}


\newpage

{\samepage \clearpage \begin{displaymath}    \|A\|_2 \cdot\|A^{-1}\|_2=\frac{\lambda^{1/2}_{\max}(A^TA)}
    {\lambda^{1/2}_{\min}(A^TA)},
  \end{displaymath}
}


\newpage

{\samepage \clearpage $j<i$
}


\stepcounter{section}
\newpage

{\samepage \clearpage $m \times n$
}


\newpage

{\samepage \clearpage $m'\times n'$
}


\newpage

{\samepage \clearpage \begin{displaymath}  A =
  \left[
  \begin{array}{ccc}
    a_{1,1} & \cdots & a_{1,n} \\ 
    \vdots & & \vdots \\ 
    a_{m,1} & \cdots & a_{m,n}
  \end{array}
\right]
\hspace{2em} (a_{i,j} \in {\cal R}) \hspace{2em}
  \left[
  \begin{array}{ccc}
    A_{1,1} & \cdots & A_{1,n'} \\ 
    \vdots & & \vdots \\ 
    A_{m',1} & \cdots & A_{m',n'}
  \end{array}
\right]
\hspace{2em} (A_{i,j} \in {\cal R^{m_i\times n_i}})
.
\end{displaymath}
}


\newpage

{\samepage \clearpage \begin{displaymath}  x = \left[
  \begin{array}{c}
    x_1 \\ 
    \vdots \\ 
    x_n
  \end{array}
\right] \hspace{2em} x_i \in {\cal R}.
\end{displaymath}
}


\newpage

{\samepage \clearpage $I^{n \times n}$
}


\newpage

{\samepage \clearpage $(a_{i,i})$
}


\newpage

{\samepage \clearpage $x_i^{(k)}$
}


\newpage

{\samepage \clearpage $i
  \neq j$
}


\newpage

{\samepage \clearpage $A = A^T$
}


\newpage

{\samepage \clearpage \begin{displaymath}    |a_{i,i}| \geq \sum_{j=1}^n |a_{i,j}|, \hspace{.2 in} j \neq i
  \end{displaymath}
}


\newpage

{\samepage \clearpage $x \neq 0,
  x^TAx > 0$
}


\newpage

{\samepage \clearpage $A^{-1} > 0$
}


\newpage

{\samepage \clearpage $\ell$
}


\stepcounter{chapter}

\end{document}

.