article

Free access

QMRPACK: a package of QMR algorithms

Editor: Ronald Boisvert Authors:

Roland W. Freund,

Noël M. NachtigalAuthors Info & Claims

ACM Transactions on Mathematical Software (TOMS), Volume 22, Issue 1

Pages 46 - 77

https://doi.org/10.1145/225545.225551

Published: 01 March 1996 Publication History

PDF eReader

Abstract

The quasi-minimal residual (QMR) algorithm is a Krylov-subspace method for the iterative solution of large non-Hermitian linear systems. QMR is based on the look-ahead Lanczos algorithm that, by itself, can also be used to obtain approximate eigenvalues of large non-Hermitian matrices. QMRPACK is a software package with Fortran 77 implementations of the QMR algorithm and variants thereof, and of the three-term and coupled two-term look-ahead Lanczos algorithms. In this article, we discuss some of the features of the algorithms in the package, with emphasis on the issues related to using the codes. We describe in some detail two routines from the package, one for the solution of linear systems and the other for the computation of eigenvalue approximations. We present some numerical examples from applications where QMRPACK was used.

References

[1]

ARNOLD{, W. E. 1951. The principle of minimized iterations in the solution of the matrix eigenvalue problem. Q. Appl. Math. 9, 1, 17-29.

Google Scholar

[2]

AXEI~SON, O. 1985. A survey of preconditioned iterative methods for linear systems of algebraic equations. BIT25, 1, 166 187.

Google Scholar

[3]

BEAM, R. M. AND WARMING, R.F. 1976. An implicit finite-difference algorithm for hyperbolic systems in conservation-law form. J. Comput. Phys. 22, 1, 87-110.

Google Scholar

[4]

CULLUM, J. AND WILLOUGHBY, R.A. 1986. A practical procedure for computing eigenvalues of large sparse nonsymmetric matrices. In Large Scale Eigenvalue Problems, J. Cullum and R. A. Willoughby, Eds. North-Holland, Amsterdam, 193-240.

Google Scholar

[5]

DONGARRA, J. J. AND GROSSE, E.H. 1987. Distribution of mathematical sot~ware via electronic mail. Comrnun. ACM 30, 5,403-407.

Crossref

Google Scholar

[6]

EISENSTAT, S.C. 1981. Efficient implementation of a class of preconditioned conjugate gradient methods. SIAM J. Sci. Star. Comput. 2, 1, 1-4.

Google Scholar

[7]

FELDMANN, P. ~ FP~tmo, R.W. 1994. Efficient linear circuit analysis by Padl approximation via the Lanczos process. Numerical Analysis Manuscript 94-01, AT&T Bell Laboratories, Murray Hill, N.J.

Google Scholar

[8]

FREU~W, R. W. 1989. Conjugate gradient type methods for linear systems with complex symmetric coefficient matrices. RIACS Tech. Report 89.54, NASA Ames Research Center, Moffett Field, Calif.

Google Scholar

[9]

FREUND, R. W. 1992a. Conjugate gradient-type methods for linear systems with complex symmetric coefficient matrices. SIAM J. Sci. Stat. Cornput. 13, 1, 425-448.

Crossref

Google Scholar

[10]

FREVNI), R. W. 1992b. Quasi-kernel polynomials and their use in non-Hermitian matrix iterations. J. Cornput. Appl. Math. 43, 1-2, 135-158.

Crossref

Google Scholar

[11]

FR.~UNO, R.W. 1992c. Quasi-kernel polynomials and convergence results for quasi-minimal residual iterations. In Numerical Methods of Approximation Theory, D. Braess and L. Schumaker, Eds. Birkhaiiser, Basel, Switzerland, 77-95.

Google Scholar

[12]

FREUNO, R.W. 1993. A transpose-free quasi-minimal residual algorithm for non-Hermitian linear systems. SIAM J. Sci. Comput. 14, 2, 470-482.

Crossref

Google Scholar

[13]

FaruNI), R. W. 1994. The look-ahead Lanczos process for nonsymmetric matrices and its applications. In Proceedings of the Cornelius Lanczos International Centenary Conference, J. D. Brown, M. T. Chu, D. C. Ellison, and R. J. Plemmons, Eds. SIAM, Philadelphia, Pa., 33-47.

Google Scholar

[14]

FRELrI~, R. W. AND NAC~maAL, N. M. 1991. QMR: A quasi-minimal residual method for non-Hermitian linear systems. Numer. Math. 60, 3, 315-339.

Google Scholar

[15]

F~VNo, R. W. AND NACHTlaAL, N. M. 1993. Implementation details of the coupled QMR algorithm. In Numerical Linear Algebra, L. Reichel, A. Ruttan, and R. S. Varga, Eds. W. de Gruyter, Berlin, 101-121.

Google Scholar

[16]

FR~VNO, R. W. AND NACh'nG~, N.M. 1994. An implementation of the QMR method based on coupled two-term recurrences. SIAM J. Sci. Comput. 15, 2, 313-337.

Crossref

Google Scholar

[17]

FR~UND, R. W. AND SZETO, T. 1992. A transpose-free quasi-minimal residual squared algorithm for non-Hermitian linear systems. In Advances in Computer Methods for Partial Differential Equations--Vll, R. Vichnevetsky, D. Knight, and G. Richter, Eds. IMACS, 258-264.

Google Scholar

[18]

FR~VND, R. W. ~ ZItA, H. 1995. Simplifications of the nonsymmetric Lanczos process and a new algorithm for Hermitian indefinite linear systems. AT & T Numerical Analysis Manuscript, Bell Laboratories, Murray Hill, N.J.

Google Scholar

[19]

FP, EuNo, R. W., Gtrr~Cl~r, M. H., AND NACHTIOAL, N.M. 1993. An implementation of the look-ahead Lanczos algorithm for non-Hermitian matrices. SIAM J. Sci. Comput. 14, 1, 137-158.

Crossref

Google Scholar

[20]

GILL, P. E., MURRAY, W., PICKEN, S. M., AND WRIGHT, M.H. 1979. The design and structure of a Fortran program library for optimization. ACM Trans. Math. Sofiw. 5, 3, 259-283.

Crossref

Google Scholar

[21]

GRACe, W. B. 1974. Matrix interpretations and applications of the continued fraction algorithm. Rocky Mountain J. Math. 4, 2, 213-225.

Google Scholar

[22]

GRAc-a, W. B. AND LlNOQVllrr, A. 1983. On the partial realization problem. Linear Algebra Appl. 50, 277-319.

Google Scholar

[23]

KaoG~, F.T. 1969. VODQ/SVDQ/DVDQ--Variable order integrators for the numerical selution of ordinary differential equations. Subroutine Write-Up, Sec. 314, Jet Propulsion Lab., Pasadena, Calif.

Google Scholar

[24]

_,zNczos, C. 1950. An iteration method for the solution of the eigenvalue problem of linear differential and integral operators. J. Res. Nat. Bur. Standards 45, 4, 255-282.

Google Scholar

[25]

LaNCZOS, C. 1952. Solution of systems of linear equations by minimized iterations. J. Res. Nat. Bur. Standards 49, 1, 33-53.

Google Scholar

[26]

L~czos, C. 1956. Applied Analysis. Prentice-Hall, Englewoed Cliffs, N.J.

Google Scholar

[27]

NAC~TIGAL, N. M. AND SEMERARO, B.D. 1995. QMR methods in computational fluid dynamics. In Solution Techniques for Large-Scale CFD Problems, W. G. Habashi, Ed. John Wiley & Sons, New York.

Google Scholar

[28]

NACHTIO~m, N. M., SHELTON, W. A., AND STOCKS, G.M. 1994. Combining the QMR method with first principles electronic structure codes. Tech. Pep. ORNL/TM-12873, Oak Ridge National Laboratory, Oak Ridge, Tenn.

Google Scholar

[29]

PASLh-Tr, B. N., TAYLOR, D. R., AND LIu, Z.A. 1985. A look-ahead Lanczos algorithm for unsymmetric matrices. Math. Comput. 44, 105-124.

Google Scholar

[30]

SAAO, Y. 1992. ILUT: A dual threshold incomplete LU factorization. Res. Pep. UMSI 92/38, Univ. of Minnesota Supercomputer Institute, Minneapolis, Minn.

Google Scholar

[31]

TAYLOR, D. R. 1982. Analysis of the look ahead Lanczos algorithm. Ph.D. thesis, Dept. of Mathematics, Univ. of California, Berkeley, Calif.

Google Scholar

[32]

VENKATAKRISHNAN, V. AND B~TH, T.J. 1992. Unstructured grid solvers on the iPSC/860. In Parallel Computational Fluid Dynamics. Rutgers, N.J.

Google Scholar

Cited By

View all

Adrian JTezkan BCandansayar M(2022)Exploration of a Copper Ore Deposit in Elbistan/Turkey Using 2D Inversion of the Time-Domain Induced Polarization Data by Using Unstructured MeshPure and Applied Geophysics10.1007/s00024-022-03071-3179:6-7(2255-2272)Online publication date: 27-Jun-2022
https://doi.org/10.1007/s00024-022-03071-3
Wang YRagusa J(2017) Diffusion Synthetic Acceleration for High-Order Discontinuous Finite Element S N Transport Schemes and Application to Locally Refined Unstructured Meshes Nuclear Science and Engineering10.13182/NSE09-46166:2(145-166)Online publication date: 10-Apr-2017
https://doi.org/10.13182/NSE09-46
Güttel STisseur F(2017)The nonlinear eigenvalue problemActa Numerica10.1017/S096249291700003426(1-94)Online publication date: 5-May-2017
https://doi.org/10.1017/S0962492917000034
Show More Cited By

Index Terms

QMRPACK: a package of QMR algorithms

Recommendations

An augmented LSQR method

The LSQR iterative method for solving least-squares problems may require many iterations to determine an approximate solution with desired accuracy. This often depends on the fact that singular vector components of the solution associated with small ...
Computing Probabilistic Bounds for Extreme Eigenvalues of Symmetric Matrices with the Lanczos Method

We study the Lanczos method for computing extreme eigenvalues of a symmetric or Hermitian matrix. It is not guaranteed that the extreme Ritz values are close to the extreme eigenvalues---even when the norms of the corresponding residual vectors are ...
Developing Bi-CG and Bi-CR Methods to Solve Generalized Sylvester-transpose Matrix Equations

The bi-conjugate gradients (Bi-CG) and bi-conjugate residual (Bi-CR) methods are powerful tools for solving nonsymmetric linear systems Ax = b . By using Kronecker product and vectorization operator, this paper develops the Bi-CG and Bi-CR methods ...

Reviews

Reviewer: Timothy R. Hopkins

The main purpose of this paper is to describe in detail the contents, structure, and usage of a set of Fortran 77 routines that implement variants of the quasi-minimal residual algorithm to solve both symmetric and asymmetric linear systems of equations and eigenvalue problems. Reverse communication is used to implement the matrix-vector operations, which makes the routines applicable to both sparse and dense systems. The package uses a routine naming convention that is similar to LAPACK. The paper concludes with a discussion of the performance of the package on a variety of problems. The authors provide an excellent summary of the look a head Lanczos algorithm and the resultant simplified algorithms that may be obtained for various special matrices. There is also a good introduction to some practical applications of the Lanczos algorithm.

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Mathematical Software

ACM Transactions on Mathematical Software Volume 22, Issue 1

March 1996

127 pages

ISSN:0098-3500

EISSN:1557-7295

DOI:10.1145/225545

Editor:
Ronald Boisvert
National Institute of Standards and Technology, Gaithersburg, GD

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 March 1996

Published in TOMS Volume 22, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

41
Total Citations
View Citations
1,289
Total Downloads

Downloads (Last 12 months)133
Downloads (Last 6 weeks)22

Reflects downloads up to 12 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Adrian JTezkan BCandansayar M(2022)Exploration of a Copper Ore Deposit in Elbistan/Turkey Using 2D Inversion of the Time-Domain Induced Polarization Data by Using Unstructured MeshPure and Applied Geophysics10.1007/s00024-022-03071-3179:6-7(2255-2272)Online publication date: 27-Jun-2022
https://doi.org/10.1007/s00024-022-03071-3
Wang YRagusa J(2017) Diffusion Synthetic Acceleration for High-Order Discontinuous Finite Element S N Transport Schemes and Application to Locally Refined Unstructured Meshes Nuclear Science and Engineering10.13182/NSE09-46166:2(145-166)Online publication date: 10-Apr-2017
https://doi.org/10.13182/NSE09-46
Güttel STisseur F(2017)The nonlinear eigenvalue problemActa Numerica10.1017/S096249291700003426(1-94)Online publication date: 5-May-2017
https://doi.org/10.1017/S0962492917000034
Bellavia SDe Simone Vdi Serafino DMorini B(2015)Updating Constraint Preconditioners for KKT Systems in Quadratic Programming Via Low-Rank CorrectionsSIAM Journal on Optimization10.1137/13094715525:3(1787-1808)Online publication date: Jan-2015
https://doi.org/10.1137/130947155
Björck ÅBjörck Å(2014)Iterative MethodsNumerical Methods in Matrix Computations10.1007/978-3-319-05089-8_4(613-781)Online publication date: 7-Oct-2014
https://doi.org/10.1007/978-3-319-05089-8_4
Kadalbajoo MGupta A(2011)An overview on the eigenvalue computation for matricesNeural, Parallel & Scientific Computations10.5555/2336431.233643919:1-2(129-164)Online publication date: 1-Mar-2011
https://dl.acm.org/doi/10.5555/2336431.2336439
Gupta AGeorge T(2010)Adaptive Techniques for Improving the Performance of Incomplete Factorization PreconditioningSIAM Journal on Scientific Computing10.1137/08072769532:1(84-110)Online publication date: Jan-2010
https://doi.org/10.1137/080727695
Iglesias CSonnad V(2010)Robust algorithm for computing quasi-static stark broadening of spectral linesHigh Energy Density Physics10.1016/j.hedp.2010.04.0026:4(399-405)Online publication date: Dec-2010
https://doi.org/10.1016/j.hedp.2010.04.002
Sonnad VIglesias C(2010)The Lanczos method applied to quasi-static stark broadening of spectral linesHigh Energy Density Physics10.1016/j.hedp.2010.04.0016:4(391-398)Online publication date: Dec-2010
https://doi.org/10.1016/j.hedp.2010.04.001
Gansterer WGruber APacher C(2009)Non-splitting Tridiagonalization of Complex Symmetric MatricesProceedings of the 9th International Conference on Computational Science: Part I10.1007/978-3-642-01970-8_47(481-490)Online publication date: 20-May-2009
https://dl.acm.org/doi/10.1007/978-3-642-01970-8_47
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

An augmented LSQR method

Computing Probabilistic Bounds for Extreme Eigenvalues of Symmetric Matrices with the Lanczos Method

Developing Bi-CG and Bi-CR Methods to Solve Generalized Sylvester-transpose Matrix Equations

Reviews

Access critical reviews of Computing literature here

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations