New Remedial Approaches to the Breakdown of Lanczos-type Algorithms

There are numerous algorithms for the solution of systems of linear equations and eigenvalue problems. Among such methods, one of the best known iterative schemes is the Lanczos algorithm. It has however, a very serious shortcoming in that it break down frequently before achieving convergence to an acceptable solution. This project focuses on investigating this breakdown issue. There are a number of attempts to address it. Restarting and Switching as implemented previously by Farooq and Maharani, which rely on guessing the appropriate number of iterations before halting the Lanczos process and restarting it or switching to a different one. This guess is very sensitive to the type of problem solved, its data and size. If underestimated then the process is stopped too early, too often. This means that a lot of stable iterations are wasted, potentially. If, on the other hand, this number is over-estimated, then the process will breakdown which means that restarting and / or switching will be more costly. The aim of this thesis is to avoid guessing the number of iteration by monitoring the parameters of the recurrence relations on which the given Lanczos-type algorithms are based, which cause breakdown. This monitoring is targeted to the appropriate or problematic parameters. In this thesis we show that this approach is effective as it does not require too much extra work. At the same time it cuts on the wasted iterations and the full blown breakdown caused by inaccurate guesses of the number of iterations one has to let the algorithm run before halting it. Although this is the core of our contributions in this thesis, we have also suggested new Lanczos-type algorithms and tested them against existing ones. This work complements that of Farooq, Mahrani, Baheux and the Brezinski team. The results show that we have made Lanczos-type algorithms old and new more reliable and robust.