CS 531:
Spring 2000-2001
Location of seminars:
Herrin Hall, Durand Building and Gates Building, Stanford University. Please note room number.
Eric Darve - Monday, April 2, 2001
Liliana Borcea - Monday, April 9, 2001
William Kahan - Tuesday, April 17, 2001
Haesun Park - Monday, April 23, 2001
Beresford Parlett - Monday, April 30, 2001
Timo Eirola - Monday, May 7, 2001
Hongyuan Zha - Wednesday, May 9, 2001
Omar Ghattas - Monday, May 14, 2001
Timothy Barth - Monday, June 4, 2001
Valerie Fraysse - Monday, June 11, 2001
ABSTRACT:
The Fast Multipole Method (FMM) is a numerical method which has found
a wide acceptance in the scientific community. It is a fast summation
method for potentials in 1/r and has applications in many areas such
as Laplace and Poisson equations, particle simulations, Molecular
Dynamics, etc. Another application of the FMM to Maxwell and
Helmholtz equations (kernel in exp(ikr)/r) was initiated by
V.Rokhlin. However the derivation of the FMM for Maxwell/Helmholtz has
two major drawbacks. First, the method fails when the size of the
clusters becomes very small compared to the wavelength. This problem
is known as sub-wavelength breakdown. The second limitation is the
fact that numerically the approximation error of the method cannot be
reduced beyond 10^-4 relative error even when the number of poles is
increased. This is due to numerical instabilities which, when coupled
to roundoff errors, lead to a divergence of the method as the number
of poles is increased beyond a certain threshold. In particular these
two limitations mean that the FMM cannot be used for computations
where the distribution of points is highly inhomogeneous
(discretization of small details on the surface of the object for
example) or when high accuracy is required (because of cavity
resonances for example). We have developed a new variant of the FMM
with complexity n log(n) which is based on plane wave expansions. This
new formulation leads to a method which is stable at all frequencies
(no sub-wavelength breakdown) and is arbitrarily accurate. This method
is more efficient and mathematically simpler than other methods for
low frequency scattering. The method is applicable to potentials in
1/r as well. It leads to a method which is more efficient (less
floating-point operations) than the traditional FMM and the newer
variants of the same algorithm.
Back to top
ABSTRACT:
We propose a nonlinear multigrid approach for imaging the electrical
conductivity and permittivity of a body, given partial, usually noisy
knowledge of the Neumann to Dirichlet map at the boundary.
The algorithm is a nested iteration, where the image is constructed
on a sequence of grids, starting from the coarse grid and advancing
towards the finest one. We show various numerical examples that
demonstrate the effectiveness and robustness of the algorithm and
prove local convergence.
Back to top
ABSTRACT:
The computation of a tetrahedron's volume has
been chosen as a didactic example elementary enough to
be tolerated by the intended audience (who have forgotten
most of the calculus and linear algebra they encountered
in college) yet difficult enough to impart an appreciation
of the challenges faced by applications programmers lacking
in numerical experience though clever about other things.
These challenges are exacerbated by programming languages
like C++ and Java that perpetuate practices, accepted
only as expedients in the 1960s, that now inflate the
languages capture cross-section for error. By treating
the tetrahedron's volume as a case study we can formulate
better guidelines for programming languages to handle
floating-point arithmetic in ways compatible with the few
rules of thumb that should be (but are still not being)
taught to the vast majority of programmers, who learn no
more about floating-point than they hear in a programming
class or read in a programming language manual. Complaining
about education rarely improves it; our efforts are better
spent redesigning computer systems and languages to
attenuate occasional harm caused by well-intentioned
ignorance among the multitudes.
Back to top
ABSTRACT:
Dimension reduction in today's vector space based information
retrieval system is essential for improving computational efficiency.
We propose a mathematical framework for lower dimensional
representation of text data in vector space based information retrieval
using minimization and matrix rank reduction formula.
We illustrate how the commonly used Latent Semantic Indexing based on the
Singular Value Decomposition (LSI/SVD) can be derived as a method for
dimension reduction from our mathematical framework.
Then we propose new methods for dimension reduction
based on the centroids of the clusters.
We also adapt and extend the discriminant analysis projection used
in pattern recognition. A limitation of of the current methods in
discriminant analysis is that some of the scatter matrices must be
nonsingular,
which restricts its application to document sets. We show that by using
the
generalized singular value decomposition (GSVD), we can achieve the same
goal regardless of the of the singularity of scatter matrices. In
addition,
applying the GSVD allows us to avoid the explicit formation of the
scatter
matrices in favor of working directly with the data matrix.
Experimental results are presented to illustrate the effectiveness
of our methods in certain classification problems in a reduced
dimensional space. The results indicate that for
a successful lower dimensional representation of data, it is important to
incorporate a priori knowledge on data in dimension reduction.
Back to top
ABSTRACT:
We consider computing eigenpairs of symmetric tridiagonal matrices.
The situation for small (n < 500) matrices is in good
shape as users of Matlab well know. However there is one outstanding
problem: the method that computes orthogonal eigenvectors (QR) takes
O(n^3) operations and theory says that the job can be done in O(n^2)
operations. Current O(n^2) methods break down when the eigenvalues
are close together and then resort to Gram-Schmidt to be safe.
We will present some new ideas that lead to a way to compute
eigenvectors for different eigenvalues with no mutual communication
(perhaps on different processors) however close those eigenvalues
may be. The cost is O(n) per eigenvalue.
One idea is that the given tridiagonal T must be discarded and
replaced by a better representation (the triangular factors).
Another key ingredient is some new non-linear transformations
called differential qd algorithms. Next there is a neat and
inexpensive way to obtain a good starting vector for inverse
iteration. In some cases it is necessary to create a tree of
representations of translates of the original matrix. Finally
there is a quick way to deal with clusters of close eigenvalues
that happen to be well separated from the rest of the spectrum.
The last technique helps with test cases that consist of many
copies of a small matrix "glued" together with small off-diagonal
entries.
This is joint work with Inderjit Dhillon.
Back to top
ABSTRACT:
The stable and unstable manifolds of a hyperbolic equilibrium or
periodic trajectory of an ODE or a discrete system are considered. They
are as
smooth as the system. The talk is a review of techniques to compute
numerical
approximations of these.
First we consider local approximations. The series expansions give
smooth approximations while the box methods give sets that include the
local
piece of the manifold. Then different methods are considered to globalize
the
local manifolds. These include continuation techniques and boundary value
methods. Some of these involve Newton like methods for nondifferentiable
maps.
These are also discussed.
Back to top
ABSTRACT:
Cluster analysis is an important tool for exploratory data mining
applications arising from many diverse disciplines. In this talk,
I will discuss a class of clustering methods based on graph-theoretic
models. In particular I will talk about spectral methods for
graph partitioning and the related eigenvalue problems and
singular value problems. I will illustrate the effectiveness of
the clustering methods using document clustering as an example.
(joint work with C. Ding, X. He, M. Gu and H. Simon)
Back to top
ABSTRACT:
Optimal design, optimal control, and parameter estimation often give
rise to very large scale PDE-constrained optimization problems. To
overcome their challenges, we need to develop parallel optimization
algorithms that exploit the PDE nature of the constraints, scale to
the millions of constraints and variables that arise upon
discretization, and capitalize on highly parallel supercomputers. We
describe parallel Newton-Krylov methods for these problems, and
illustrate with applications to optimal control of Navier-Stokes flows
and inverse wave propagation.
This work is joint with former PhD student George Biros (now at
Courant), and current PhD students Volkan Akcelik and Ioannis
Epanomeritakis.
Back to top
ABSTRACT:
In recent years, the Hamilton-Jacobi and level set equations have been
successfully applied in the modeling of a large number of problems arising
in image processing, computer vision, fluid mechanics, obstacle navigation
(http://www.nas.nasa.gov/~barth/images/obstacle.gif), path planning
For numerous further
examples, see the books by Sethian (1996) and Shapiro (2001) as well as
the review article of Osher and Fedkiw (2000).
In the present talk, we consider the fast high order accurate numerical
approximation of the eikonal equation on triangulated manifolds using
linear, quadratic, and cubic isoparametric (curved) element approximation
(http://www.nas.nasa.gov/~barth/images/eikonal2.gif). Previous methods
based on explicit space marching have been limited to low order accuracy
and barrier theorems exist for the linear hyperbolic counterpart of the
eikonal equation which confirm this restriction. We then consider
a new *scalar* form of the stabilized discontinuous Galerkin
discretization
for the eikonal equation and show how fast solution methods are produced
which circumvent the accuracy barrier theorems produced by explicit
marching
methods. The discontinuous Galerkin method generalizes to high order
accuracy on irregular meshes and readily permits the generalization to
piecewise isoparametric element approximation of curved (possibly
non-orientable)
manifolds. Numerical eikonal examples containing obstacles, variable
refractive index materials, and curved surfaces are shown throughout
the talk to demonstrate the generality of the techniques.
(http://www.nas.nasa.gov/~barth/terrain/mars.gif), and moving interfaces
(http://www.nas.nasa.gov/~barth/movies/hj_movie.mpg).
Back to top
ABSTRACT:
Embedded iterative solvers are more and more often used in Linear
Algebra. A challenging issue is how to tune the level of accuracy
of the inner solver to guarantee the convergence of the outer solver
at the best global cost. In this talk, we will focus on Krylov methods
with inexact matrix-vector products, which can be viewed as a particular
case of inner-outer iterations. We will present numerical experiments
with a relaxation strategy applied to monitor the accuracy of
matrix-vector
products in Krylov methods for linear systems. We will illustrate the
robustness of inexact Krylov methods and we will discuss several
applications,
in particular to domain decomposition methods.
NB. Part of this work is joint work with Amina Bouras (University of
Toulouse I) and Luc Giraud (CERFACS). The work presented here was
performed while the speaker was in the Parallel Algorithms Project at
CERFACS.
Back to top