Computer Science NASC Seminar
Algebraic Optimizable Schwarz Methods for the Solution of Banded Linear Systems and PDEs on Irregular Domains
Daniel Szyld, Temple University
April 15, 2011
Warren Weaver Hall, Room 1302
251 Mercer Street
New York, NY, 10012-1110
Spring 2011 NASC Seminars Calendar
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,
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