CSAR Noon Seminar
Joerg Liesen, UIUC/CSAR
DATE: Wednesday, November 28, 2001
TIME: 12:00 Noon
PLACE: 2240 DCL
1304 W. Springfield Ave., Urbana, IL
TITLE: Fast Solvers for Indefinite Linear Systems Applied in
Constrained Optimization and Potential Fluid Flow
ABSTRACT
In this talk we will consider the numerical solution of indefinite
linear systems. Such systems arise in a variety of applications,
including linearized Navier-Stokes equations, saddle-point and linear
least-squares problems, and constrained optimization. Our focus is on
block two-by-two systems known as KKT sytems in optimization or Stokes
systems in fluid dynamics. We will present a new class of
preconditioners for solving such systems based on splittings of the
(1,1) block, A=D-E, where D is easy to invert. Different
splittings lead to different preconditioners, and we will show some
theoretical results about the preconditioned matrices, e.g., their
eigenvalue distributions.
Results related to the eigenvalue and eigenvector structure of the
preconditioned matrices will allow us to discuss the convergence
behavior of Krylov subspace methods such as GMRES for these matrices.
In addition, we will show how to solve the preconditioned linear systems
by a fixed point iteration. This iteration is guaranteed to converge
whenever the splitting of the (1,1) block A is regular, i.e.,
whenever the spectral radius of D \ E is less than one. In
particular, the iteration converges whenever A is strictly
diagonally dominant, and D is chosen to be the diagonal of
A.
Numerical examples will include applications in constrained
optimization (arising in surface parameterization) as well as finite
element approximations of the potential fluid flow problem.
The talk is based on joint work in progress with Eric de Sturler.