A new lanczos-type algorithm for systems of linear equations | [Journal of Prime Research in Mathematics • 2015]

Author(s):

1. MUHAMMAD FAROOQ: Department of Mathematics, University of Peshawar, Khyber Pakhtunkhwa, 25120, Pakistan.

2. ABDELLAH SALHI: Department of Mathematical Sciences, University of Essex, Wivenhoe Park, Colch- ester, CO4 3SQ, UK.

Abstract:

Lanczos-type algorithms are e±cient and easy to implement. Unfortunately they breakdown frequently and well before convergence has been achieved. These algorithms are typically based on recurrence relations which involve formal orthogonal polynomials of low degree. In this paper, we consider a recurrence relation that has not been studied before and which involves a relatively higher degree polynomial. Interestingly, it leads to an algorithm that shows superior stability when compared to existing Lanczos-type algorithms. This new algorithm is derived and described. It is then compared to the best known algorithms of this type, namely A5=B10, A8=B10, as well as Arnoldi's algorithm, on a set of standard test problems. Numerical results are included.

Page(s): 104-119

DOI: DOI not available

Published: Journal: Journal of Prime Research in Mathematics, Volume: 10, Issue: 1, Year: 2015

Keywords:

Lanczos algorithm , Systems of Linear Equations , Arnoldi algorithm , Formal Orthogonal Polynomials

References:

[1] W. E. Arnoldi. .1951 .The principal of minimized iterations in the solution of the matrix eigenvalue problem. Quarterly of Applied Mathematics, 17 : 29.

[2] Baheux C. .1995 .New Implementations of Lanczos Method. Journal of Computational and Applied Mathematics, 3 : 15.

[3] Baheux C. .1994 .. PhD thesis, : .

[4] Bj A.,Strakos Z. .1998 .Stability of Conjugate Gradient and Lanczos Methods for Linear Least Squares Problems. SIAM Journal of Matrix Analysis and Application, 720 : 736.

[5] Brezinski C. .1980 .e-Type Approximation. Internat. Ser. Nuner. Math. 50. BirkhaÄuser, : .

[6] Brezinski C.,Sadok H. .1993 .Lanczos-type algorithms for solving systems of linear equations. Applied Numerical Mathematics, 443 : 473.

[7] Brezinski C.,Zaglia M. R. .1994 .Hybird procedures for solving linear systems. Numerische Mathematik, 1 : 19.

[8] Brezinski C.,Zaglia M. R. .1991 .A New Presentation of Orthogonal Polynomials with Applications to their Computation. Numerical Algorithms, 207 : 222.

[9] Brezinski C.,Zaglia M. R.,Sadok H. .1991 .Avoiding breakdown and nearbreakdown in Lanczos type algorithms. Numerical Algorithms, 261 : 284.

[10] Brezinski C.,Zaglia M. R.,Sadok H. .1992 .A Breakdown-free Lanczos type algorithm for solving linear systems. Numerische Mathematik, 29 : 38.

[11] Brezinski C.,Zaglia M. R.,Sadok H. .2000 .The matrix and polynomial approaches to Lanczos-type algorithms. Journal of Computational and Applied Mathematics, 241 : 260.

[12] Brezinski C.,Zaglia M. R.,Sadok H. .1999 .New look-ahead Lanczos-type algorithms for linear systems. Numerische Mathematik, 53 : 85.

[13] Brezinski C.,Zaglia M. R.,Sadok H. .2002 .A review of formal orthogonality in Lanczos-based methods. Journal of Computational and Applied Mathematics, 81 : 98.

[14] Broyden C. G.,Vespucci M. T. .2004 .Krylov Solvers For Linear Algebraic Systems. , : .

[15] Calvetti D.,Reichel L.,Sgallari F.,Spaletta. A Regularizing G. .2000 .Lanczos iteration method for underdetermined linear systems. Jouranl of Computational and Applied Mathematics, 101 : 120.

[16] Draux A. .1983 .. Polyn^omes Orthogonaux Formels. Application, LNM 974. SpringerVerlag, : .

[17] Farooq M. .2011 .New Lanczos-type Algorithms and their Implementation. PhD thesis, : .

[18] Farooq M.,Salhi A. .2011 .Improving the solvability of ill-conditioned systems of linear equations by reducing the condition number of their matrices. J. Korean Math. Soc., 48(5) : 952.

[19] Farooq M.,Salhi A. .2012 .New Recurrence Relationships Between Orthogonal Polynomials Which Lead to New Lanczos-type Algorithms. Journal of Prime Research in Mathematics, 61 : 75.

[20] Farooq M.,Salhi A.,Transaction A .2013 .A Preemptive Restarting Approach to Beating the Inherent Instability of Lanczos-type Algorithms. Iranian Journal of Sceince and Technology, 142(3) : 358.

[21] Farooq M.,Salhi A. .2014 .A Switching Approach to Avoid Breakdown in Lanczos-type Algorithms. Applied Mathematics and Information Sciences, 2161(5) : 190.

[22] Fletcher R. .1976 .Conjugate gradient methods for inde¯nite systems. Numerical Analysis, 73 : 89.

[23] Greenbaum A. .1997 .Iterative Methods for Solving Linear System. Society for Industrial and Applied Mathematics, : .

[24] Guennouni A. El .1999 .A uni¯ed approach to some strategies for the treatment of breakdown in Lanczos-type algorithms. Applicationes Mathematicae, 477 : 488.

[25] Hestenes M.R.,Stiefel E. .1952 .Mehtods of conjugate gradients for solving linear systems. Journal of the National Bureau of Standards, 409 : 436.

[26] Khachyan L. G. .1979 .A polynomial algorithm in linear programming. Soviet Mathematics Doklady (translated), 191 : 194.

[27] Kim H. J.,Choi K.,Lee H. B.,Jung H. K.,Hahn S. Y. .1996 .A new algorithm for solving ill-conditioned linear system. IEEE Transactions on Magnetics, 1373(3) : 1376.

[28] Lanczos C. .1950 .An Iteration Method for the Solution of the Eigenvalue Problem of Linear Di®erential and Integeral Operators. Journal of Research of the National Bureau of Standards, 255 : 282.

[29] Lanczos C. .1952 .Solution of systems of linear equations by minimized iteration. Journal of the National Bureau of Standards, 33 : 53.

[30] Lovasz L. .1980 .. The Ellipsoid Algorithm: Better or Worse than the Simplex? Mathematical Intelligencer, 141 : 146.

[31] Meurant. G. .2006 .The Lanczos and conjugate gradient algorithms, From Theory to Finite Precision Computations. , : .

[32] Parlett B. N.,Scott D. S. .1979 .The Lanczos Algorithm With Selective Orthogonaliztion. Mathematics of Computation, 217 : 238.

[33] Parlett B. N.,Taylor D. R.,Liu Z. A. .1985 .A Look-Ahead Lanczos Algorithm for Unsymmetric Matrices. Mathematics of Computation, 105 : 124.

[34] Rice J. R.,McGraw-Hill J. R. .1981 .. Matrix Computations and Mathematical Software, : .

[35] Saad Y. .1987 .On the Lanczos method for solving linear system with several right-hand sides. Mathematics of Computation, 651 : 662.

[36] Saad Y. .2003 .Iterative methods for sparse linear systems. , : .

[37] Polynomials G. SzegoÄ. Orthogonal .1939 .. American Mathematical Society, : .

[38] H. A. Van der Vorst. .1987 .An iterative solution method for solving f(A)x=b, using Krylov subspace information obtained for the symmetric positive de¯nite matrix A. Journal of Computational and Applied Mathematics, 249(2) : 263.

[39] Ye Q. .1994 .A Breakdown-Free Variation of the Nonsymmetric Lanczos Algorithms. Mathematics of Computation, 179 : 207.

Citations

Downloads

Views