Premium
Multisplitting for regularized least squares with Krylov subspace recycling
Author(s) -
Renaut Rosemary A.,
Lin Youzuo,
Guo Hongbin
Publication year - 2012
Publication title -
numerical linear algebra with applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.02
H-Index - 53
eISSN - 1099-1506
pISSN - 1070-5325
DOI - 10.1002/nla.797
Subject(s) - krylov subspace , conjugate gradient method , mathematics , convergence (economics) , context (archaeology) , algorithm , mathematical optimization , subspace topology , least squares function approximation , iterative method , mathematical analysis , paleontology , statistics , estimator , economics , biology , economic growth
SUMMARY The method of multisplitting (MS), implemented as a restricted additive Schwarz type algorithm, is extended for the solution of regularized least squares problems. The presented non‐stationary version of the algorithm uses dynamic updating of the weights applied to the subdomains in reconstituting the global solution. Standard convergence results follow from extensive prior literature on linear MS schemes. Additional convergence results on nonstationary iterations yield convergence conditions for the presented nonstationary MS algorithm. The global iteration uses repeated solves of local problems with changing right hand sides but a fixed system matrix. These problems are solved inexactly using a conjugate gradient least squares algorithm which provides a seed Krylov subspace. Recycling of the seed system Krylov subspace to obtain the solutions of subsequent nearby systems of equations improves the overall efficiency of the MS algorithm, and is apparently novel in this context. The obtained projected solution is not always of sufficient accuracy to satisfy a reasonable inner convergence condition on the local solution. Improvements to accuracy may be achieved by reseeding the solution space either every few steps, or when the successive right hand sides are sufficiently close as measured by a provided tolerance. Restarting and augmenting the solution space are also discussed. Any time a new space is generated it is used for subsequent steps. Numerical simulations validate the use of the recycling algorithm. These numerical experiments use the standard reconstruction of the two dimensional Shepp–Logan phantom, as well as a two dimensional problem from seismic tomography. Copyright © 2011 John Wiley & Sons, Ltd.