CS 531:
Winter 2000-2001
Location of seminars:
Herrin Hall and Gates Building, Stanford University. Please note room number.
Moody Chu - Tuesday, January 16, 2001
Bertil Gustafsson - Monday, January 22, 2001
Eldar Giladi - Monday, January 29, 2001
Giray Okten - Monday, February 5, 2001
Karl Meerbergen - Monday, February 12, 2001
Wilfred Gansterer - Tuesday, February 20, 2001
Heinz-Otto Kreiss - Thursday, February 22, 2001
Andrew Knyazev - Monday, February 26, 2001
Annie Cuyt - Monday, March 5, 2001
Margaret Wright - Thursday, March 8, 2001
ABSTRACT:
An inverse eigenvalue problem concerns the reconstruction
of a matrix from prescribed spectral data. The spectral
data involved may consist of the complete or only partial
information of eigenvalues or eigenvectors. The objective
of an inverse eigenvalue problem is to construct a matrix
that maintains a certain specific structure as well as that
given spectral property.
Inverse eigenvalue problems arise in a remarkable variety of
applications, including system and control theory, geophysics,
molecular spectroscopy, particle physics, structure analysis,
and so on. Generally speaking, the basic goal of an inverse
eigenvalue problem is to reconstruct the physical parameters
of a certain system from the knowledge or desire of its
dynamical behavior. Since the dynamical behavior often is
governed by the underlying natural frequencies and/or normal
modes, the spectral constraints are thus imposed. On the
other hand, in order that the resulting model is physically
realizable, additional structural constraints must also be
imposed upon the matrix. Depending on the application, inverse
eigenvalue problems appear in many different forms.
Associated with any inverse eigenvalue problem are two
fundamental questions -- the theoretic issue on solvability
and the practical issue on computability. Solvability concerns
obtaining a necessary or a sufficient condition under which
an inverse eigenvalue problem has a solution. Computability
concerns developing a procedure by which, knowing a priori
that the given spectral data are feasible, a matrix can be
constructed numerically. Both questions are difficult and
challenging.
In this expository talk the emphasis is to provide an overview
of the vast scope of this fascinating problem. The fundamental
questions, some known results, as well as several open problems
will be discussed. A case study on the inverse problem of
constructing a row stochastic matrix with prescribed spectrum
will be illustrated.
Back to top
ABSTRACT:
The deferred correction method is an efficient way of obtaining high
order accuracy for boundary value problems. A method of order is
constructed by solving a sequence of systems based on a symmetric
second order difference approximation with different right hand
sides. The advantage is particularly pronounced, when considering
domain decomposition methods, since the compact form of the second
order approximation introduces minimal coupling between the
subdomains. In the first part of the talk we shall demonstrate this by
discussing a fast high order Poisson solver for implementation on
parallel computers.
In the second part of the talk, we will discuss how the method of
deferred correction can be used also for time-discretization of
initial-boundary value problems. We use the trapezoidal rule as the
basic scheme, and because of the symmetry, we again obtain order of
accuracy by applying the scheme times for each time-step (with
different right hand sides). By slightly weakening the stability
concept, one can show that the scheme is unconditionally stable.
We shall also indicate how the principle of deferred correction can be
applied simultaneously in space and time, leading to very efficient
high order methods both in space and time.
Back to top
ABSTRACT:
We develop a hybrid asymptotic numerical method for the Helmholtz
equation. The method is a Galerkin finite element method in which the
space of trial solutions is spanned by asymptotically derived basis
functions. The basis functions are very ``efficient" in representing
the solution because each is the product of a smooth amplitude and an
oscillatory phase factor, like the asymptotic solution. The phase is
determined a-priori by solving the eikonal equation using the ray
method, while the smooth amplitude is represented by piecewise
polynomials. The number of unknowns necessary to achieve a given
accuracy with this new basis is dramatically smaller than the number
necessary with a standard method, and it is virtually independent of
the wavenumber $k$. We apply the method to the problems of scattering
from a parabola and from a circle, and compare the results with those
of a standard finite element method.
Back to top
ABSTRACT:
In this talk I will try to answer three questions:
In particular, I will talk about sequential Monte Carlo techniques and
recent progress made at CRIAMS as a part of research sponsored by Los
Alamos National Laboratory. In the remaining time, I will mention
other applications to numerical linear algebra.
Back to top
ABSTRACT:
The determination of the frequency response function of large finite
element simulations of engineering problems require the solution
of a sequence of linear systems with a linear or quadratic parameter.
In this talk, we discuss the use of Krylov methods that are well-known
for the solution of linear systems, eigenvalue computations, and model
reduction. We illustrate the theory with numerical examples arising
from applications.
Back to top
ABSTRACT:
The need for efficiently approximating eigenpairs of symmetric matrices
arises in many contexts, for example, when solving nonlinear eigenproblems
or for use as preconditioners.
In many application areas, for example, in Quantum Chemistry or Materials
Science, the matrices arising in eigenproblems are generally dense but
often have the property that their elements decrease rapidly in magnitude
when moving away from the diagonal. This makes it often possible to
approximate them by block-tridiagonal matrices with very small bandwidth.
In this talk we will discuss extensions and generalizations of the
well-established tridiagonal Divide-and-Conquer approach to more general
symmetric block-tridiagonal (including banded) matrices with semibandwidth
greater than one. We will present an algorithmic framework which can be
used to approximate eigenpairs of such matrices, as well as to compute
them "exactly" (except for rounding error).
We will illustrate that in both cases (for higher accuracy requirements and
for increasing bandwidths, respectively) the eigenvector computation can
quickly become the limiting factor in terms of efficiency of these methods
if a "naive" generalization of the tridiagonal Divide-and-Conquer method is
used. This observation motivated the investigation of alternative ways for
computing eigenvectors of a block-tridiagonal matrix with significantly
lower arithmetic complexity.
We will illustrate the potential of these approaches by the results
of numerical experiments.
Back to top
ABSTRACT:
For equations with constant coefficients one can obtain
precise growth rates via Fourier analysis. For equations
with variable coefficients, one often uses the principle
of frozen coefficients to obtain estimates.
We want to examine whether these estimates are reliable.
In particular, we want to discuss problems which are barely
well posed, like first order systems with complex characteristics
which are regularized by adding dissipative terms.
Numerical calculations of a simplified two phase flow model
are presented.
Back to top
ABSTRACT:
The preconditioned conjugate gradient method became the standard
solver for extremely large linear systems with symmetric positive
definite matrices of
coefficients. Our ultimate goal is developing a similar optimal method
for symmetric eigenproblems.
We introduce a definition of algorithm optimality for symmetric
eigenproblems, using
a generalized Krylov subspace based on polynomials of two variables.
We propose benchmarking for computing the extreme eigenpair, suggesting,
as the
ideal control algorithm, the standard preconditioned
conjugate gradient method for finding an eigenvector as an element of
the
null-space of the corresponding homogeneous system of linear equations
under the
assumption that the eigenvalue is known. We recommend every new
preconditioned eigensolver be compared with this ideal algorithm on our
model
test problems in terms of the speed of convergence, costs of every
iterations and
memory requirements.
Searching for the optimal algorithm, we describe
the Locally Optimal Block Preconditioned Conjugate Gradient (LOBPCG)
Method for symmetric eigenvalue problems, based
on a local optimization of a three-term recurrence.
Numerical results establish that our LOBPCG Method is
practically as efficient as the ideal algorithm. We also show
numerically that the LOBPCG Method provides approximations to first
eigenpairs
of about the same quality as those by the much more expensive global
optimization
method on the same generalized block Krylov subspace.
We discuss several inner-outer iterative preconditioned eigensolvers,
e.g.,
the inexact Jacobi-Davidson method, and show
that they produce approximations in the generalized Krylov subspace.
Direct numerical comparisons with the inexact Jacobi-Davidson method
show that our LOBPCG method is more robust and converges almost two
times faster.
Finally, we show numerically that the LOBPCG method is robust with
respect to
variable preconditioning.
A MATLAB code of the LOBPCG method and the Preconditioned Eigensolvers
Benchmarking are available at
http://www-math.cudenver.edu/~aknyazev/software/CG/
The talk is mostly based on the paper: "Toward the Optimal
Preconditioned Eigensolver:
Locally Optimal Block Preconditioned Conjugate Gradient Method."
Published as a
technical report UCD-CCM 149, 2000, see
http://www-math.cudenver.edu/ccmreports/rep149.ps.gz
at the Center for Computational Mathematics,
University of Colorado at Denver. A revised version accepted to SIAM
SISC.
Back to top
ABSTRACT:
Pade-approximants (the rational equivalent of Taylor series sums) and
rational interpolants have proved useful in many applications where
polynomial approximation techniques failed. We discuss some of the more
recent applications such as:
Several projects are continuing the investigation of these problems and
tools. We will give pointers to some interesting URL's and publications.
Back to top
ABSTRACT:
Methods for finding the best value of a function are relatively easy
to motivate and explain when there are no restrictions on the
variables. Once constraints are added, however, the situation is much
less clearcut. Solution techniques and convergence analysis can become
so nonintuitive and so complicated that it is difficult to determine
the connections, if any, between an apparently new approach and
previous suggestions. We shall examine some of the most popular ideas
today for treating constrained optimization problems, with special
attention to novelty and related properties.
Back to top