A19/b6: a new lanczos-type algorithm and its implementation

ZAKIR ULLAH; MUHAMMAD FAROOQ; ABDELLAH SALHI

Author(s)

ZAKIR ULLAH Department of Mathematics, University of Peshawar, Khyber Pakhtunkhwa, 25120, Pakistan.

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

ABDELLAH SALHI Department of Mathematical Sciences, University of Essex, Wivenhoe Park, Colchester, CO4 3SQ, UK.

Abstract

Lanczos-type algorithms are mostly derived using recurrence relationships between formal orthogonal polynomials. Various recurrence relations between these polynomials can be used for this purpose. In this paper, we discuss recurrence relations A19 and B6 for the choice Ui(x) = Pi(1)(x), where Ui is an auxiliary family of polynomials of exact degree i. This leads to new Lanczos-type algorithm A19=B6 that shows superior stability when compared to existing algorithms of the same type. This new algorithm is derived and described here. Computational results obtained with it are compared to those of the most robust algorithms of this type namely A12, A1n2ew A5=B10 and A8=B10 on the same test problems. These results are included.

Publication Details

Page(s) 106-122

DOI DOI not available

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

Request the full text from PASTIC

Keywords

Lanczos algorithm, Primary 65F10, Formal Orthogonal Polynomials AMS SUBJECT, Systems of Linear Equations

References

Baheux C. .1994 .. PhD thesis, : .

Baheux C. .1995 .New Implementations of Lanczos Method. Journal of Computational and Applied Mathematics, 57 : 15.

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

Brezinski C.,Pade-Type Approximation C. .1980 .. , : .

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

Brezinski C.,Zaglia M. R. .1991 .A new presentation of orthogonal polynomials with applications to their computation. Numerical Algorithms, 1 : 222.

Brezinski C.,Zaglia M. R. .1994 .Hybird procedures for solving linear systems. Numerische Mathematik, 67 : 19.

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

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

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

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

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

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

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

G. Cybenko. .1987 .An explicit formula for Lanczos plonomials. Linear Algebra Appl., 88 : 115.

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

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

Farooq M.,Salhi A. .2012 .New Recurrence Relationships between Orthogonal Polynomials which Lead to New Lanczos-type Algorithms. Journal of Prime Research in Mathematics, 8 : 75.

Farooq M.,Salhi A. .2013 .A Restarting Approach to Beating the Inherent Instability of Lanczos-type Algorithms. Iranian Journal of Science and Technology, Transaction A-Science, 349(3) : 358.

Farooq M.,Salhi A. .2014 .A Switching Approach to Avoid Breakdown in Lanczostype Algorithms. Applied Mathematics and Information Sciences, 2161(5) : 2169.

Farooq M.,Salhi A. .2015 .A new Lanczos-type algorithm for system of linear equations. Journal of Prime Research in Mathematics, 10 : 121.

Fletcher R. .1976 .Conjugate Gradient methods for inde nite systems. Numerical Analysis, Dundee 1975, Lecture Notes in Mathematics,, 506 : .

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

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

Hestenes M. R.,Stiefel E. .1952 .Mehtods of Conjugate Gradients for solving linear systems. Journal of the National Bureau of Standards, 49 : 436.

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, 45 : 282.

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

Meurant. G. .2006 .The Lanczos and Conjugate Gradient algorithms, From Theory to Finite Precision Computations. , : .

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

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

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

Polynomials G. Szego. Orthogonal .1939 .. American Mathematical Society, : .

Ullah S.,Farooq M.,Salhi A. .2013 .An alternative derivation of a new Lanczostype algorithm for systems of linear equations. Punjab University Journal of Mathematics, 45 : 49.

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.

Ye Q. .1994 .A Breakdown-Free Variation of the Nonsymmetric Lanczos Algorithms. Mathematics of Computation, 62 : 207.