Enhanced Lanczos Algorithms for Solving Systems of Linear Equations with Embedding Interpolation and Extrapolation

摘要

Lanczos-type algorithms are prone to breaking down before convergence to an acceptable solution is achieved. This study investigates a number of ways to deal with this issue. In the first instance, we investigate the quality of three types of restarting points in the restarting strategy when applied to a particular Lanczos-type algorithm namely Orthodir. The main contribution of the thesis, however, is concerned with using regression as an alternative way to deal with breakdown. A Lanczos-type algorithm is run for a number of iterations and then stopped, ideally, just before breakdown occurs. The sequence of generated iterates is used to build up a regression model that captures the characteristic of this sequence. The model is then used to generate new iterates that belong to that sequence. Since the iterative process of Lanczos is circumvented, or ignored, while using the model to find new points, the breakdown issue is resolved, at least temporarily, unless convergence is achieved. This new approach, called EIEMLA, is shown formally, through extrapolation, that it generates a new point which is at least as good as the last point generated by the Lanczos-type algorithm prior to stoppage. The remaining part of the thesis reports on the implementation of EIEMLA sequentially and in parallel on a standard parallel machine provided locally and on a Cloud Computing platform, namely Domino Data Lab. Through these implementations, we have shown that problems with up to $10^6$ variables and equations can be solved with the new approach. Extensive numerical results are included in this thesis. Moreover, we point out some important issues for further investigation.