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