\documentclass[semrot]{seminar}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{fancybox}
\usepackage{semhelv}
\usepackage{color}
\usepackage{graphics}
\usepackage{epsfig}
\newcommand{\minni}[1]{\mbox{\scriptsize ${#1}$}}
\newdimen\prenwd \setbox0=\hbox{B} \prenwd=\wd0 
\def\mybmatrix#1{\begingroup \mathsurround=0pt
  \setbox0=\vbox{\def\cr{\crcr\noalign{\kern2pt\global\let\cr=\endline}}
    \ialign{$##$\hfil\kern2pt\kern\prenwd&\thinspace\hfil$##$\hfil
      &&\quad\hfil$##$\hfil\crcr
      \omit\strut\hfil\crcr\noalign{\kern-\baselineskip}
      #1\crcr\omit\strut\cr}}
  \setbox2=\vbox{\unvcopy0 \global\setbox1=\lastbox}
  \setbox2=\hbox{\unhbox1 \unskip \global\setbox1=\lastbox}
  \setbox2=\hbox{$\kern\wd1\kern-\prenwd \left[ \kern-\wd1
    \global\setbox1=\vbox{\box1\kern2pt}
    \vcenter{\kern-\ht1 \unvbox0 \kern-\baselineskip}\,\right]$}
  \null\;\vbox{\kern\ht1\box2}\endgroup}
\special{landscape}
\newpagestyle{house}{\hspace{\fill}\rightmark
\hspace{\fill}\thepage}{}
\pagestyle{house}
\definecolor{myblue}{rgb}{.3,0,.3}
\definecolor{mygreen}{rgb}{0,.4,0}
\definecolor{mywhite}{rgb}{1,1,1}
\markright{Accurate eigenvalues of the Laplacian}
\newcommand{\hdg}[1]{\begin{center}\Large\bf\color{myblue}\shadowbox{#1}\end{center}\vspace{1ex minus 1ex} \Large}
\newcommand{\myeq}[1]{{\color{mygreen}$#1$}}
\newcommand{\myeqd}[1]{{\color{mygreen}$$#1$$}}
\newcommand{\myeqdl}[1]{{\color{mygreen}\begin{equation}#1\end{equation}}}
\newcommand{\myeqdeqnarray}[1]{{\color{mygreen}\begin{eqnarray*}#1\end{eqnarray*}}}
\newcommand{\myeqaligns}[1]{{\color{mygreen}\begin{align*}#1\end{align*}}}
\newcommand{\eps}{\epsilon}
\newcommand\aff{\mathop{\rm aff}}
\newcommand\area{\mathop{\rm area}}	
\newcommand\asp{\mathop{\rm asp}}
\newcommand\cond{\mathop{\rm cond}}	
\newcommand\cost{\mathop{\rm cost}}	
\newcommand\dist{\mathop{\rm dist}}
\newcommand\lth{\mathop{\rm lth}}
\newcommand\maxside{\mathop{\rm maxside}}
\newcommand\minalt{\mathop{\rm minalt}}
\newcommand\rank{\mathop{\rm rank}}
\newcommand\size[1]{\mathop{\rm size}(#1)}
\newcommand\vol{\mathop{\rm vol}}	
\renewcommand\b{{\bf b}}
\newcommand\C{{\bf C}}
\newcommand\q{{\bf q}}
\newcommand\R{{\bf R}}
\renewcommand\t{{\bf t}}
\newcommand\T{{\mathcal T}}
\renewcommand\u{{\bf u}}
\renewcommand\v{{\bf v}}
\newcommand\x{{\bf x}}
\newcommand\z{{\bf z}}
\newcommand\bz{{\bf 0}}
\newcommand\grad{\nabla}
\newcommand\emach{\epsilon_{\rm mach}}
%\newcommand\bxi{{\bm \xi}}
\newcommand\bxi{\mbox{\boldmath$\xi$}}
\newcommand\pg[1]{\begin{center} \bf #1 \\ \end{center}}
\setlength{\parskip}{0.2in}
\setlength{\parindent}{0pt}
\newenvironment{mitemize}{\begin{list}{--}%
{\setlength{\labelsep}{0.05in}
\setlength{\labelwidth}{0.1in}\setlength{\topsep}{0pt}%
\setlength{\parsep}{0pt}\setlength{\itemsep}{0pt}}}{\end{list}}
\begin{document}
\begin{slide}
\begin{center}
{\color{myblue}\LARGE\bf Accurate Eigenvalues of the Laplacian} \\
\vspace{.4in}
\Large
Plamen Koev \\
Massachusetts Institute of Technology \\
Joint work with James Demmel (Berkeley) and Steve Vavasis
(Cornell \& Waterloo)
\end{center}
\end{slide}
\begin{slide}
\hdg{Main result}
\begin{itemize}
\item
The most common way to compute eigenvalues of the weighted Laplacian
is via finite element discretization.
\item
This yields a symmetric generalized eigenvalue problem of the form
\myeq{K\x=\lambda M\x}.
\item
We argue that this system has special structure allowing
high relative precision calculation of all eigenvalues 
including the smallest ones.
\end{itemize}
\end{slide}
\begin{slide}
\hdg{Membrane motion}
\begin{itemize}
\item
Consider a moving two-dimensional membrane
defined by bounded set 
\myeq{\Omega\subset \R^2}
whose boundaries are clamped. 
\item
Assume the stiffness varies
over the membrane and is given by a coefficient field \myeq{c}.
Assume the displacement is
small and all motion is elastic.  
\item
The governing equation is a two-dimensional
wave equation: \myeq{u_{tt}=\nabla\cdot (c\nabla u)} on \myeq{\Omega}
and \myeq{u=0} on \myeq{\partial\Omega}.
\end{itemize}
\end{slide}
\begin{slide}
\hdg{Standing wave}
\begin{itemize}
\item
A standing wave solution to this problem has the form
\myeq{u(x,t)=e^{i\lambda t}u_0(x)}.  
\item
Substituting this formula into the
PDE yields the continuum
eigenvalue problem \myeq{\nabla\cdot (c\nabla u_0)+\lambda^2u_0=0}.
\end{itemize}
\end{slide}
\begin{slide}
\hdg{Finite element discretization (piecewise linear)}
\begin{itemize}
\item
Assume \myeq{\T} is a {\em finite element mesh} for the domain \myeq{\Omega},
that is, a simplicial subdivision into \myeq{r} triangles.  
\item
Let \myeq{w_1,\ldots,w_n}
be the mesh nodes not on \myeq{\partial\Omega}.
\item
Let \myeq{V_h} denote the set of piecewise
linear continuous functions \myeq{u} on this triangulation
satisfying \myeq{u|_{\partial\Omega}=0}.  Note: \myeq{{\rm dim}(V_h)=n}.
\end{itemize}
\end{slide}
\begin{slide}
\hdg{Discrete linear equations}
\begin{itemize}
\item
Obtain weak form of PDE: multiply
PDE by
a test function \myeq{q} satisfying \myeq{q|_{\partial\Omega}=0};
integrate by parts:
\myeqd{\int_\Omega \nabla q \cdot c \nabla u =\int_\Omega \lambda q u}
\item
Discrete FE equations: find eigenpairs
 \myeq{u\in V_h,\lambda\in\R} such that the weak
form holds for all \myeq{q\in V_h}.
\end{itemize}
\end{slide}
\begin{slide}
\hdg{Representation with vectors}
\begin{itemize}
\item
Functions  \myeq{q\in V_h} are in 1-1 correspondence with vectors 
\myeq{\q\in\R^n} according to \myeq{q_i=q(w_i)} for \myeq{i=1:n}
(homeomorphism of vector spaces).
\item
Let \myeq{\u\in\R^n} be the vector corresponding to FE solution \myeq{u}.  
Then
\myeq{\u} satisfies: for all \myeq{\q\in\R^n}, 
\myeq{\q^T K\u=\q^T\lambda M\u} for  matrix \myeq{K}
called the {\em stiffness matrix}, and matrix \myeq{M},
called the {\em mass matrix}.
Equivalent to
\myeq{K\u=\lambda M\u}.
\end{itemize}
\end{slide}
\begin{slide}
\hdg{Stiffness matrix}
\begin{itemize}
\item
Closed-form expressions for entries of \myeq{K} are obtained by considering
\myeq{\u} of the form \myeq{[0;0;\cdots;0;1;0;\cdots0]} and similarly for 
\myeq{\q} and evaluating the weak form for the corresponding \myeq{u}
and \myeq{q}.  Expressions also available for \myeq{M}.
\item
Matrix \myeq{K} so determined is \myeq{n\times n} 
symmetric positive definite.  Matrix \myeq{M} is \myeq{n\times n} 
is symmetric and strongly positive definite.
\end{itemize}
\end{slide}
\begin{slide}
\hdg{A test case}
\begin{itemize}
\item
Consider the unit square domain with a border of width \myeq{\eta} 
that surrounds 
an inner square of width \myeq{1-2\eta}.  
\item
Assign a very high stiffness \myeq{s} to the border and a constant stiffness
of \myeq{1} to the inner square.
\item
It can be proved using classical minimax
arguments that as \myeq{s\rightarrow\infty},
the smaller eigenpairs of this domain tend to eigenpairs of the geometry
of the subsquare.
\end{itemize}
\end{slide}
\begin{slide}
\hdg{Experiments with this test case}
\begin{itemize}
\item
In exact arithmetic, one expects that as \myeq{s} gets larger, the smallest
eigenvalue of this border problem converges to the smallest eigenvalue of
the inner domain.
\item
In the presence of roundoff, convergence is noted up to a certain
threshhold value \myeq{s^*}; after this point, the solution diverges
because roundoff error prevents accurate computation of the small
eigenvalue.
\end{itemize}
\end{slide}
\begin{slide}
\hdg{Why is roundoff error a problem}
\begin{itemize}
\item
Roundoff error corrupts the solution to the problem described above
because as \myeq{s\rightarrow\infty}, we have that \myeq{\Vert K\Vert
\rightarrow\infty} proportionally.  
\item
Thus, the largest entries of \myeq{K}
as well as the larger eigenvalues increase without bound.  Under
this circumstance, conventional eigenvalue algorithms cannot recover
the smaller eigenvalues accurately.
\end{itemize}
\end{slide}

\begin{slide}
\hdg{Our Approach}
\begin{itemize}
\item Solving \myeq{Ku=\lambda Mu}, where 
\myeq{K=A^TDJ^TJDA}
\item \myeq{A} is DSTU, \myeq{D} is diagonal, \myeq{J} is well 
conditioned; assume \myeq{M} is diagonal
\item Equivalent to SVD of \myeq{J\underbrace{DAM^{1/2}}_{\mbox{DSTU}}}
\item DSTU problem solved by Demmel; also Pelaez--Moro
\item One more time for SVD of \myeq{JU\Sigma V^T}

\end{itemize}
\end{slide}

\end{document}



