Greedy and randomized versions of the multiplicative Schwarz method (Q445816)

The authors consider subspace correction methods for the iterative solution of a large linear system arising from a variational problem with symmetric positive definite bilinear form. The (finite dimensional) space is splitted into subspaces (not necessarily a direct sum) and the order of the subspace corrections is the main concern. The authors prove theorems on the error in the energy norm of the iterative solution for 2 versions: taking a subspace with maximal residuum first (``greedy'' or Southwell method), or choosing the subspace randomly. Discussing the exponential convergence obtained (and connections to results like that of \textit{T. Strohmer} and \textit{R. Vershynin} [J. Fourier Anal. Appl. 15, No. 2, 262--278 (2009; Zbl 1169.68052)]), they propose a third, intermediate version, to select randomly a fixed number \(k\) of subspaces and applying there the greedy version. Numerical results are shown for a Toeplitz system and a multilevel approximation of the Dirichlet problem for the Poisson equation, using bilinear finite elements. The outcome here is that though the Southwell version is best when looking at the accuracy reached after a fixed number of iterations, but much cheaper and nearly the same accuracy is obtained by the combined method for moderate values of \(k\) (like \(3\leq k\leq 8\)).