Restarting from Specific Points to Cure Breakdown in Lanczos-type Algorithms
DOI:
https://doi.org/10.5614/j.math.fund.sci.2015.47.2.5Keywords:
breakdown, formal orthogonal polynomial, Lanczos-type algorithms, systems of linear equations, restarting.Abstract
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.
References
Brezinski, C., Zaglia, R. & Sadok, H., Avoiding Breakdown and Near-Breakdown in Lanczos-type Algorithms, Numerical Algorithms, 1, pp. 261-284, 1991.
Joubert, W., On Restarting the Arnoldi Method for Large Nonsymmetric Eigenvalue Problems, SIAM J. Matrix Anal. App, 1992.
Brezinski, C., Zaglia, R. & Sadok, H., A Breakdown-free Lanczos-type Algorithms for Solving Linear Systems, Numerical Mathematics, 63, pp. 29-38, 1992.
Farooq, M., New Lanczos-type Algorithms and their Implementation, Ph.D dissertation, Department of Mathematical Sciences, University of Essex, Colchester, 2011.
Farooq, M. & Salhi, A., A Preemptive Restarting Approach to Beating Inherent Instability, Iranian Journal of Science and Technology Transaction a Science, 37A3, pp. 349-358, 2013.
Farooq, M. & Salhi, A., A Switching Approach to Avoid Breakdown in Lanczos-type Algorithms, Applied Mathematics and Information Sciences, 5(8), pp. 2161-2169, 2014.
Brezinski, C. & Zaglia, R.H., A New Presentation of Orthogonal Polynomials with Applications to their Computation, Numerical Algorithm, 1, pp. 207-221, 1991.
Grave-Morris, P., A Look-Around Lanczos Algorithms for Solving a Systems of Linear Equations, Numerical Algorithm, 15, pp. 247-274, 1997.
Guennouni, E.A, Unified Approach to Some Strategies for the Treatment of Breakdown in Lanczos-type Algorithms, Application Mathematics, 26, pp. 477-488, 1999.
Morgan, R.B., Lanczos Methods for the Solution of Nonsymmetric Systems of Linear Equations, Mathematics of Computation, 5(215), pp. 1213-1230, 1992.
Saad, Y., Iterative Methods for Sparse Linear Systems, 3rd ed., Philadelphia: Society for Industrial and Applied Mathematics, pp. 122-124 & 144-145, 2003.
Baheux, C., New Implementations of Lanczos Method, Journal Of Computational and Applied Mathematics, 57, pp. 3-155, 1995.
Brezinski, C. & Sadok, H., Lanczos-type Algorthms for Solving Systems of Linear Equation, Applied Numerical Mathematics, 11, pp. 443-473, 1993.
Brezinski, C., Zaglia, R. & Sadok, H., The Matrix and Polynomial Approaches to Lanczos-type Algorithms, Journal of Computational and Applied Mathematics, 123(1-2), pp. 241-260,2000.
Farooq, M. & Salhi, A., New Recurrence Relationships between Orthogonal Polynomials which Lead to New Lanczos-type Algorithms, Journal of Prime Research in Mathematics, 8, pp. 61-75, 2012.
Brezinski, C. & Zaglia, R.H., Breakdowns in the Computation of Orthogonal Polynomials, Nonlinear Numerical Methods and Rational Approximation, pp. 49-59, 1994.
