system improve incrementally during the solution of subsequent systems. In the second phase, after 24 right hand sides, enough eigenvectors have been obtained to significantly reduce the condition number of the deflated matrix in the classic CG. In this phase we observe speedups of 8-9 over the non-deflated CG, and, most importantly, the number of the deflated CG iterations remains almost constant as $m_{q}$ approaches $m_{critical}$, thus removing the critical slowdown.

Background and current approaches {#sec:Background}
=================================

Krylov methods provide one of the most important tools for solving large, general sparse linear systems. An excellent survey of recent developments and discussion on some of the open problems in linear systems appears in [@Valeria_Szyld_RecentDevelopments]. For symmetric (or Hermitian) positive definite (SPD) matrices, CG [@MH_ES_CG] remains the uncontested choice because it uses a three term recurrence to converge optimally, with minimum storage and computational requirements. Even for the Hermitian case, however, it remains an open question as to how best solve a system with many (say $s$) right hand sides, $$Ax_i = b_i,\ i=1,\ldots ,s.$$

One approach is to use block methods which work simultaneously on a set of vectors [@Golub_Underwood_77; @DOLeary_80a; @Guennouni_Jbilou_Sadok]. They have favorable performance characteristics in memory hierarchy computers 