by Kirk M. Soodhalter
Abstract:
erMany Krylov subspace methods for shifted linear systems take advantage of the invariance of the Krylov subspace under a shift of the matrix. However, exploiting this fact in the non-Hermitian case introduces restrictions; e.g., initial residuals must be collinear and this collinearity must be maintained at restart. Thus we cannot simultaneously solve shifted systems with unrelated right-hand sides using this strategy, and all shifted residuals cannot be simultaneously minimized over a Krylov subspace such that collinearity is maintained. It has been shown that this renders them generally incompatible with techniques of subspace recycling [Soodhalter et al. APNUM '14]. This problem, however, can be overcome. By interpreting a family of shifted systems as one Sylvester equation, we can take advantage of the known "shift invariance" of the Krylov subspace generated by the Sylvester operator. Thus we can simultaneously solve all systems over one block Krylov subspace using FOM or GMRES type methods, even when they have unrelated right-hand sides. Because residual collinearity is no longer a requirement at restart, these methods are fully compatible with subspace recycling techniques. Furthermore, we realize the benefits of block sparse matrix operations which arise in the context of high-performance computing applications. In this paper, we discuss exploiting this Sylvester equation point of view which has yielded methods for shifted systems which are compatible with unrelated right-hand sides. From this, we propose a recycled GMRES method for simultaneous solution of shifted systems.Numerical experiments demonstrate the effectiveness of the methods.
Reference:
Block Krylov Subspace Recycling for Shifted Systems with Unrelated Right-Hand Sides (Kirk M. Soodhalter), In SIAM Journal on Scientific Computing, volume 38, 2016. (Matlab code)
Bibtex Entry:
@ARTICLE{S2.2014,
author = {Kirk M. Soodhalter},
title = {Block Krylov Subspace Recycling for Shifted Systems with Unrelated Right-Hand Sides},
journal = {SIAM Journal on Scientific Computing},
volume = {38},
number = {1},
pages = {A302-A324},
year = {2016},
keywords = {paper},
doi = {10.1137/140998214},
URL = {
https://arxiv.org/abs/1412.0393
},
eprint = {
http://dx.doi.org/10.1137/140998214
},
comment = {<a href="https://zenodo.org/record/56157">Matlab code</a>},
abstract = {erMany Krylov subspace methods for shifted linear systems take advantage of the invariance of the Krylov subspace under a shift of the matrix. However, exploiting this fact in the non-Hermitian case introduces restrictions; e.g., initial residuals must be collinear and this collinearity must be maintained at restart. Thus we cannot simultaneously solve shifted systems with unrelated right-hand sides using this strategy, and all shifted residuals cannot be simultaneously minimized over a Krylov subspace such that collinearity is maintained. It has been shown that this renders them generally incompatible with techniques of subspace recycling [Soodhalter et al. APNUM '14].
This problem, however, can be overcome. By interpreting a family of shifted systems as one Sylvester equation, we can take advantage of the known "shift invariance" of the Krylov subspace generated by the Sylvester operator. Thus we can simultaneously solve all systems over one block Krylov subspace using FOM or GMRES type methods, even when they have unrelated right-hand sides. Because residual collinearity is no longer a requirement at restart, these methods are fully compatible with subspace recycling techniques. Furthermore, we realize the benefits of block sparse matrix operations which arise in the context of high-performance computing applications.
In this paper, we discuss exploiting this Sylvester equation point of view which has yielded methods for shifted systems which are compatible with unrelated right-hand sides. From this, we propose a recycled GMRES method for simultaneous solution of shifted systems.Numerical experiments demonstrate the effectiveness of the methods.
}
}