Schwarz Methods With Optimal Updates

Rosemary Renaut

Arizona State University Department of Mathematics P.O. Box 871804 Tempe, AZ 85287-1804


Renaut(1997) introduced the use of optimal updates in the multisplitting algorithm(MS) for solution of the linear least squares problem. This applied a technique introduced by Ferris and Mangasarian in the context of parallelization of optimization routines. In MS the solutions to the local subproblems are typically recombined using weighting matrices to pick out the appropriate components of each subproblem solution. In the optimal update algorithm the global update is obtained as the most optimal update that can be obtained from the local solutions. The update problem can be formulated as a least squares minimization with respect to the weighting coefficients and is small relative to the original problem. The update cost is therefore small relative to the subproblem solutions each iteration, and can lead to gains in overall efficiency of the algorithm. As formulated for the least squares problem the MS is immediately equivalent to an additive Schwarz method for the normal equations. In this talk I will discuss the reformulation of Schwarz methods ( additive and multiplicative), for linear systems of equations, to include optimal updates. Theoretical results will be presented studying the convergence of the iterations, relative to subproblem size, convergence criteria and the recombination techniques.