Search this site:

Directors:
Randolph E. Bank
Philip E. Gill
Michael Holst

Terry Le

Office: AP&M 7431
Phone: (858)534-9813
Fax: (858)534-5273
E-mail: tele@ucsd.edu
Schwarz Iterations: Old and New

Peter Oswald
University of California, San Diego

Abstract:

The name Schwarz iterative methods has been coined in the late 1980ies as a theoretical framework for investigating domain decomposition and multilevel methods for variational problems. They are based on the notion of stable space splittings of a Hilbert space $H$ into a family of auxiliary Hilbert spaces $H_i$, each equipped with its own variational subproblem, and in essence represent a more constructive version of the alternating directions method (ADM) which in turn is a special instance of a POCS algorithm. We consider the multiplicative Schwarz iteration $u^{j+1} = u^j + \omega_j w^j_i,$ where finding the update direction $w^j_i$ involves solving the $i$-th subproblem, and $\omega_j$ is a relaxation parameter. Which $i=i_j$ is chosen in the $j$-th update step matters, until recently only deterministic orderings have been considered.

The renewed interest in investigating random (and greedy) orderings was triggered by results by Strohmer and Vershynin on the convergence of a randomized Kaczmarz method for solving $Ax=b$ (= Gauss-Seidel with random ordering for $AA^\ast y=b$) which received much attention, both due to the simplicity of the error analysis and the sometimes improved performance. We generalized their result to the setting of Schwarz iterative methods with finitely many subproblems. Even though the a priori bounds for greedy and random orderings are identical, the numerical tests show that the greedy version leads to faster convergence in practice, and that combinations of randomization and greedy approaches can remedy slow convergence of the cheaper randomized iteration. Extensions to infinitely many subproblems are considered. For the case of solving linear systems (SOR-method), some further improvements have recently been made for both deterministic and random orderings.

In the talk, I will briefly review the setup of Schwarz iterative methods and then outline the recently obtained convergence estimates for SOR-type methods with deterministic and randomized orderings for linear systems.

Tuesday, October 6, 2015
11:00AM AP&M 2402