Numerical Analysis and Scientific Computing Seminar

Algebraic Optimizable Schwarz Methods for the Solution of Banded Linear Systems and PDEs on Irregular Domains

Speaker: Daniel Szyld, Temple University

Location: Warren Weaver Hall 1302

Date: April 15, 2011, 10 a.m.

Synopsis:

Classical Schwarz methods and preconditioners subdivide the domain of a partial differential equation into subdomains and use Dirichlet or Neumann transmission conditions at the artificial interfaces. Optimizable Schwarz methods use Robin (or higher order) transmission conditions instead, and the Robin parameter can be optimized so that the resulting iterative method has an optimal convergence rate. The usual technique used to find the optimal parameter is Fourier analysis; but this is only applicable to certain domains, for example, a rectangle.

In this talk, we present a completely algebraic view of Optimizable Schwarz methods, including an algebraic approach to find the optimal operator or a sparse approximation thereof. This approach allows us to apply this method to any banded or block banded linear system of equations, and in particular to discretizations of partial differential equations in two and three dimensions on irregular domains. This algebraic Optimizable Schwarz method is in fact a version of block Jacobi with overlap, where certain entries in the matrix are modified.

With the computable optimal modifications, we prove that the Optimizable Schwarz method converges in two iterations for the case of two subdomains. Similarly, we prove that when we use an Optimizable Schwarz preconditioner with this optimal modification, the underlying Krylov subspace minimal residual method (e.g., GMRES) converges in two iterations. Very fast convergence is attained even when the optimal operator is approximated by a sparse transmission matrix. Numerical examples illustrating these results are presented.

This is joint work with Martin Gander (Geneva) and Sebastien Loisel (Heriot-Watt U.)