Restarting from Specific Points to Cure Breakdown in Lanczos-type Algorithms

Breakdown in Lanczos-type algorithms is a common phenomenon which is due to the non-existence of some orthogonal polynomials. It causes the solution process to halt. It is, therefore, important to deal with it to improve the resilience of the algorithms and increase their usability. In this paper, we consider restarting from a number of different approximate solutions that seem to be attractive starting points. They are: (a) the last iterate preceding breakdown, (b) the iterate with minimum residual norm found so far, and (c) the approximate solution whose entries are the median values of entries of all iterates generated by the Lanczos-type algorithm considered. Although it has been shown theoretically in the context of Arnoldi-type algorithms as well as Lanczos-type algorithms that restarting mitigates breakdown and allows the iterative process to continue and converge to good solutions, here we give an alternative theorem to that effect and a proof of it. However, emphasis is on the quality of the restarting points. Numerical results are included.