Enhancing the Stability of Lanczos-type Algorithms by Embedding Interpolation and Extrapolation for the Solution of Systems of Linear Equations
DOI:
https://doi.org/10.5614/j.math.fund.sci.2018.50.2.4Keywords:
breakdown, extrapolation, EIEM A13/B6, EIEM A13/B13, interpolation, Lanczos-type algorithms, patternsAbstract
A new method to treat the inherent instability of Lanczos-type algorithms is introduced. It enables us to capture the properties of the sequence of iterates generated by a Lanczos-type algorithm by interpolating on this sequence of points. The interpolation model found is then used to generate a point that is outside the range. It is expected that this new point will link up the rest of the sequence of points generated by the Lanczos-type algorithm if breakdown does not occur. However, because we assume that the interpolation model captures the properties of the Lanczos sequence, the new point belongs to that sequence since it is generated by the model. This paper introduces the so-called Embedded Interpolation and Extrapolation Model in Lanczos-type Algorithms (EIEMLA). The model was implemented in algorithms A13/B6 and A13/B13, which are new variants of the Lanczos algorithm. Individually, these algorithms perform badly on high dimensional systems of linear equations (SLEs). However, with the embedded interpolation and extrapolation models, EIEM A13/B6 and EIEM A13/B13, a substantial improvement in the performance on SLEs with up to 105 variables can be achieved.
References
Golub, G.H. & Overton, M.L., Convergence of a Two-stage Richardson Iterative Procedure for Solving Systems of Linear Equations, Numerical Analysis, 912, pp. 125-139, 1982.
Barret, R., Berry, M., Cahn, T.F., Demmel, J., Dongarra, J., Eijkhout, V. and Pozo, R., Romine, C. & Van der Vorst, V.A., Templates for the Solutions of Linear Systems: Building Block for Iterative Methods, Philadelphia: SIAM, pp. 3-155, 1994.
Young Jr., D.M., Iterative Methods for Solving Partial Difference Equations of Elliptic type, Ph.D dissertation, Department of Mathematics, Harvard University, Cambridge, 1950.
Magnus, R.H. & Stiefel, E., Methods of Conjugate Gradients for Solving Linear Systems, Journal of Research of the National Bureau of Standards, 49(6), pp. 409-436, 1952.
Gutknecht, M.H., Lanczos-type Solvers for Nonsymmetric Linear Systems of Equations, Cambridge University Press, pp. 271-397, 1997.
Morgan, R.B., On Restarting the Arnoldi Method for Large Nonsymmetric Eigenvalue Problems, Mathematics of Computation, 65(4), pp. 1213-1230, 1996.
Lanczos, C., An Iteration Method for The Solution of the Eigenvalue Problem of Linear Differential and Integral Operator, Journal of Research of the National Bureau of Standards, 45, pp. 255-282, 1950.
Lanczos, C., Solution of Systems of Linear Equations by Minimized Iteration, Journal of Research of the National Bureau of Standards, 49, pp. 33-53, 1952.
Saad, Y., Krylov Subspace Method for Solving Large Unsymmetric Linear Systems, Mathematics of Computations, 37(155), pp. 105-126, 1981.
Saad, Y., Iterative Methods for Sparse Linear Systems, Philadelphia: Society for Industrial and Applied Mathematics, 3rd Ed., pp. 5-10, 2003.
Brezinski, C. & Zaglia, R.H., A New Presentation of Orthogonal Polynomials with Applications to Their Computation, Numerical Algorithm, 1, pp. 207-221, 1991.
Farooq, M. & Salhi, A., A Preemptive Restarting Approach to Beating Inherent Instability, Iranian Journal of Science and Technology Transaction a Science, 37(Special Issue), pp. 349-358, 2013.
Farooq, M. & Salhi, A., A Switching Approach to Beating the Inherent Instability of Lanczos-type Algorithms, Journal of Applied Mathematics and Information Systems, 8(5), pp. 2161-2169, 2014.
Maharani, M. & Salhi, A., Restarting from Specific Points to Cure Breakdown in Lanczos-type Algorithms, Journal of Mathematical and Fundamental Sciences, 2(47), pp. 167-184, 2015.
Brezinski, C. & Sadok, H., Lanczos-type Algorithms for Solving Systems of Linear Equation, Applied Numerical Mathematics, 11, pp. 443-473, 1993.
Brezinski, C., Zaglia, R.H. & Sadok, H., The Matrix and Polynomial Approaches to Lanczos-type Algorithms, Journal Of Computational and Applied Mathematics, 123, 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.
Ullah, Z., Farooq, M. & Salhi, A., A19/B6: A New Lanczos-type Algorithm and its Implementation, Journal of Prime Research in Mathematics, 11, pp.106-122, 2015.
Suharto, Rifka, A., Maharani, Maryani, S. & Juliansyah, A., New Lanczos Formula Types A13/B6 and A13/B10 for Solving Large Scale of Linear Systems, 1st International Conference on Mathematics, Science, and Education (ICOMSE 2017), 2017.
Inselberg, A. & Dimsdale, B., Parallel Coordinates: A Tool for Visualizing Multi-Dimensional Geometry, IEEE Computer Society Press, Conference, pp. 361-378, 1990.
Kosara, R., Parallel Coordinates, Cambridge University Press, http://eagereyes.org/techniques/parallel-coordinates.html, 2012.
Shanon, R., Holland, T. & Quigley, A., Multivariate Graph Drawing using Parallel Coordinate Visualization, University College Dublin, pp. 361-378, 2008.
Few, S., Multivariate Analysis Using Parallel Coordinates, https://www.perceptualedge.com/articles/b-eye/parallel_coordinates.pdf, (30 June 2012).
Sidi, A., William, F.F. & Smith, D.A., Acceleration of Convergence of Vector Sequences, SIAM Journal on Numerical Analysis, 23(1), pp. 178-196, 1986.
Delbourgo, R. & Gregory, J.A., Shape Preserving Piecewise Rational Interpolation, SIAM Journal on Scientific and Statistical Computing, 10, 1983.
Kelley, C.T., Iterative Methods for Linear and Nonlinear Equations, Philadelphia: Society for Industrial and Applied Mathematics, pp. 25-30, 1995.
Baheux, C., New Implementations of Lanczos Method, Journal of Computational and Applied Mathmatics, 57(3), pp. 3-155, 1995.
Datta, B.N., Numerical Linear Algebra and Applications, Philadelphia: Society for Industrial and Applied Mathematics, 5th Ed., pp. 5-10, 2000.
Farooq, M. & Salhi, A., Improving the Solvability of Ill-Conditioned Systems of Linear Equations by Reducing the Condition Number of their Matrices, Journal of the Korean Mathematical Society, 48(5), pp. 939-952, 2011.
Higham, N.J., Accuracy and Stability of Numerical Algorithms, Philadelphia: Society for Industrial and Applied Mathematics, 3rd Ed., pp. 5-10, 2002.
Maharani, M., Salhi, A. & Khan, W., Enhanced the Stability of Lanczos-type Algorithms by Restarting the Point Generated by EIEMLA for the Solution of Systems of Linear Equations, International Science Journal, Lahore, 28(4), pp. 3325-3335, 2016.
