Publications Details

Analysis of Krylov subspace recycling for sequences of linear systems

Many problems from engineering and the sciences require the solution of sequences of linear systems where the matrix and right-hand side change from one system to the next, and the linear systems are not available simultaneously. We review a class of Krylov subspace methods for sequences of linear systems, which can significantly reduce the cost of solving the next system in the sequence by 'recycling' subspace information from previous systems. These methods have been successfully applied to sequences of linear systems arising from several different application areas. We analyze a particular method, GCRO-DR, that recycles approximate invariant subspaces, and establish residual bounds that suggest a convergence rate similar to one obtained by removing select eigenvector components from the initial residual. We review implications of this analysis, which suggests problem classes where we expect this technique to be particularly effective. From this analysis and related numerical experiments we also demonstrate that recycling the invariant subspace corresponding to the eigenvalues of smallest absolute magnitude is often not the best choice, especially for nonsymmetric problems, and that GCRO-DR will, in practice, select better subspaces. These results suggest possibilities for improvement in the subspace selection process.