Software for simplified Lanczos and QMR algorithms.(English)Zbl 0853.65041
The paper describes Fortran-77 implementations of some simplified versions of the three-term and coupled two-term Lanczos algorithm and the associated quasi-minimal residual (QMR) iteration algorithms for general \(J\)-symmetric and \(J\)-Hermitian matrices. These implementations represent counterparts to the algorithms already contained in the authors software package QMRPACK.
Section 2 briefly reviews the Lanczos process and the QMR method. In Section 3, the general concept of simplified Lanczos algorithms is discussed, and a few examples are given. In Section 4, the authors describe implementation issues for the simplified algorithms. Section 5 considers one of the algorithms in more detail. In Section 6, a list of the implemented simplified algorithms is given. Section 7 describes an example driver for two of the algorithms, and in Section 8, results of numerical experiments are reported. In Section 9, the authors make some concluding remarks.
Section 2 briefly reviews the Lanczos process and the QMR method. In Section 3, the general concept of simplified Lanczos algorithms is discussed, and a few examples are given. In Section 4, the authors describe implementation issues for the simplified algorithms. Section 5 considers one of the algorithms in more detail. In Section 6, a list of the implemented simplified algorithms is given. Section 7 describes an example driver for two of the algorithms, and in Section 8, results of numerical experiments are reported. In Section 9, the authors make some concluding remarks.
Reviewer: D.Petcu (Timişoara)
MSC:
| 65F10 | Iterative numerical methods for linear systems |
| 65F15 | Numerical computation of eigenvalues and eigenvectors of matrices |
| 15-04 | Software, source code, etc. for problems pertaining to linear algebra |
Keywords:
quasi-minimal residual iteration;eigenvalue computation;\(J\)-symmetric matrices;Lanczos algorithm;\(J\)-Hermitian matrices;software package QMRPACK;QMR method;numerical experimentsSoftware:
QMRPACKCite
Full Text:DOI
References:
| [1] | Axelsson, O., A survey of preconditioned iterative methods for linear systems of algebraic equations, BIT, 25, 166-187 (1985) ·Zbl 0566.65017 |
| [2] | Bunch, J. R.; Parlett, B. N., Direct methods for solving symmetric indefinite systems of linear equations, SIAM J. Numer. Anal., 8, 639-655 (1971) ·Zbl 0199.49802 |
| [3] | Chan, R. H.; Strang, G., Toeplitz equations by conjugate gradients with circulant preconditioner, SIAM J. Sci. Statist. Comput., 10, 104-119 (1989) ·Zbl 0666.65030 |
| [4] | Cullum, J. K.; Willoughby, R. A., (Lanczos Algorithms for Large Symmetric Eigenvalue Computations Vol. 1: Theory (1985), Birkhäuser: Birkhäuser Basel) ·Zbl 0574.65028 |
| [5] | Cullum, J. K.; Willoughby, R. A., A practical procedure for computing eigenvalues of large sparse nonsymmetric matrices, (Cullum, J.; Willoughby, R. A., Large Scale Eigenvalue Problems (1986), North-Holland: North-Holland Amsterdam), 193-240 ·Zbl 0605.65027 |
| [6] | Dongarra, J. J.; Grosse, E. H., Distribution of mathematical software via electronic mail, Comm. ACM, 30, 403-407 (1987) |
| [7] | Eisenstat, S. C., Efficient implementation of a class of preconditioned conjugate gradient methods, SIAM J. Sci. Statist. Comput., 2, 1-4 (1981) ·Zbl 0474.65020 |
| [8] | Feldmann, P.; Freund, R. W., Efficient linear circuit analysis by Padé approximation via the Lanczos process, (Proceedings EURO-DAC ’94 with EURO-VHDL ’94 (1994), IEEE Computer Society Press: IEEE Computer Society Press Los Alamitos), 170-175 |
| [9] | Freund, R. W., Conjugate gradient-type methods for linear systems with complex symmetric coefficient matrices, SIAM J. Sci. Statist. Comput., 13, 425-448 (1992) ·Zbl 0761.65018 |
| [10] | Freund, R. W., A transpose-free quasi-minimal residual algorithm for non-Hermitian linear systems, SIAM J. Sci. Comput., 14, 470-482 (1993) ·Zbl 0781.65022 |
| [11] | Freund, R. W., Transpose-free quasi-minimal residual methods for non-Hermitian linear systems, (Golub, G.; Greenbaum, A.; Luskin, M., Recent Advances in Iterative Methods. Recent Advances in Iterative Methods, The IMA Volumes in Mathematics and its Applications, 60 (1994), Springer: Springer New York), 69-94 ·Zbl 0804.65032 |
| [12] | Freund, R. W., The look-ahead Lanczos process for nonsymmetric matrices and its applications, (Brown, J. D.; Chu, M. T.; Ellison, D. C.; Plemmons, R. J., Proceedings of the Cornelius Lanczos International Centenary Conference (1994), SIAM: SIAM Philadelphia, PA), 33-47 ·Zbl 1260.65025 |
| [13] | Freund, R. W., Lanczos-type algorithms for structured non-Hermitian eigenvalue problems, (Brown, J. D.; Chu, M. T.; Ellison, D. C.; Plemmons, R. J., Proceedings of the Cornelius Lanczos International Centenary Conference (1994), SIAM: SIAM Philadelphia, PA), 243-245 |
| [14] | Freund, R. W.; Golub, G. H.; Nachtigal, N. M., Iterative solution of linear systems, Acta Numer., 1, 57-100 (1992) ·Zbl 0762.65019 |
| [15] | Freund, R. W.; Gutknecht, M. H.; Nachtigal, N. M., An implementation of the look-ahead Lanczos algorithm for non-Hermitian matrices, SIAM J. Sci. Comput., 14, 137-158 (1993) ·Zbl 0770.65022 |
| [16] | Freund, R. W.; Jarre, F., A QMR-based interior-point algorithm for solving linear programs, (Numerical Analysis Manuscript 94-19 (1994), AT&T Bell Laboratories: AT&T Bell Laboratories Murray Hill, NJ) ·Zbl 0824.90127 |
| [17] | also:Math. Programming (to appear); also:Math. Programming (to appear) |
| [18] | Freund, R. W.; Mehrmann, V., A symplectic look-ahead Lanczos algorithm for the Hamiltonian eigenvalue problem, (Numerical Analysis Manuscript (1995), AT&T Bell Laboratories: AT&T Bell Laboratories Murray Hill, NJ) |
| [19] | Freund, R. W.; Nachtigal, N. M., QMR: a quasi-minimal residual method for non-Hermitian linear systems, Numer. Math., 60, 315-339 (1991) ·Zbl 0754.65034 |
| [20] | Freund, R. W.; Nachtigal, N. M., An implementation of the QMR method based on coupled two-term recurrences, SIAM J. Sci. Comput., 15, 313-337 (1994) ·Zbl 0803.65036 |
| [21] | Freund, R. W.; Nachtigal, N. M., QMRPACK: a package of QMR algorithms, (Numerical Analysis Manuscript 94-16 (1994), AT&T Bell Laboratories: AT&T Bell Laboratories Murray Hill, NJ) ·Zbl 0884.65027 |
| [22] | also:ACM Trans. Math. Software (to appear); also:ACM Trans. Math. Software (to appear) |
| [23] | Freund, R. W.; Szeto, T., A transpose-free quasi-minimal residual squared algorithm for non-Hermitian linear systems, (Vichnevetsky, R.; Knight, D.; Richter, G., Advances in Computer Methods for Partial Differential Equations, VII (1992), IMACS: IMACS New Brunswick, NJ), 258-264 |
| [24] | Freund, R. W.; Zha, H., Simplifications of the nonsymmetric Lanczos process and a new algorithm for Hermitian indefinite linear systems, (Numerical Analysis Manuscript (1995), AT&T Bell Laboratories: AT&T Bell Laboratories Murray Hill, NJ) |
| [25] | Gill, P. E.; Murray, W.; Picken, S. M.; Wright, M. H., The design and structure of a Fortran program library for optimization, ACM Trans. Math. Softw., 5, 259-283 (1979) ·Zbl 0411.68029 |
| [26] | Gill, P. E.; Murray, W.; Ponceleón, D. B.; Saunders, M. A., Preconditioners for indefinite systems arising in optimization, SIAM J. Matrix Anal. Appl., 13, 292-311 (1992) ·Zbl 0749.65037 |
| [27] | Gohberg, I.; Lancaster, P.; Rodman, L., Matrices and Indefinite Scalar Products (1983), Birkhäuser: Birkhäuser Basel ·Zbl 0513.15006 |
| [28] | Gunzburger, M. D., Finite Element Methods for Viscous Incompressible Flows (1989), Academic Press: Academic Press San Diego ·Zbl 0697.76031 |
| [29] | Krogh, F. T., VODQ/SVDQ/DVDQ—Variable order integrators for the numerical solution of ordinary differential equations, (Subroutine Write-Up, Sec. 314 (1969), Jet Propulsion Lab: Jet Propulsion Lab Pasadena, CA) |
| [30] | Horn, R. A.; Johnson, C. R., Matrix Analysis (1985), Cambridge University Press: Cambridge University Press Cambridge ·Zbl 0576.15001 |
| [31] | Huckle, T., Iterative methods for Toeplitz-like matrices, (Manuscript SCCM-94-05 (1994), Scientific Computing and Computational Mathematics Program, Stanford University: Scientific Computing and Computational Mathematics Program, Stanford University Stanford, CA) ·Zbl 0685.15020 |
| [32] | Lanczos, C., An iteration method for the solution of the eigenvalue problem of linear differential and integral operators, J. Res. Nat. Bur. Standards, 45, 255-282 (1950) |
| [33] | Lanczos, C., Solution of systems of linear equations by minimized iterations, J. Res. Nat. Bur. Standards, 49, 33-53 (1952) |
| [34] | Lanczos, C., Applied Analysis (1956), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ ·Zbl 0111.12403 |
| [35] | Laub, A. J., A Schur method for solving algebraic Riccati equations, IEEE Trans. Automat. Control, 24, 913-921 (1979) ·Zbl 0424.65013 |
| [36] | Mehrmann, V., The Autonomous Linear Quadratic Control Problem, (Lecture Notes in Control and Information Sciences, 163 (1991), Springer: Springer Berlin) ·Zbl 0746.93001 |
| [37] | Paige, C. C.; Saunders, M. A., Solution of sparse indefinite systems of linear equations, SIAM J. Numer. Anal., 12, 617-629 (1975) ·Zbl 0319.65025 |
| [38] | Parlett, B. N.; Chen, H. C., Use of indefinite pencils for computing damped natural modes, Linear Algebra Appl., 140, 53-88 (1990) ·Zbl 0725.65055 |
| [39] | Parlett, B. N.; Taylor, D. R.; Liu, Z. A., A look-ahead Lanczos algorithm for unsymmetric matrices, Math. Comp., 44, 105-124 (1985) ·Zbl 0564.65022 |
| [40] | Roebuck, P. A.; Barnett, S., A survey of Toeplitz and related matrices, Internat. J. Systems Sci., 9, 921-934 (1978) ·Zbl 0385.15010 |
| [41] | Silvester, D. J.; Kechkar, K., Stabilised bilinear-constant velocity-pressure finite elements for the conjugate gradient solution of the Stokes problem, Comput. Methods Appl. Mech. Engrg., 79, 71-86 (1990) ·Zbl 0706.76075 |
| [42] | Taylor, D. R., Analysis of the look ahead Lanczos algorithm, (Ph.D. thesis (1982), University of California: University of California Berkeley, CA) ·Zbl 0564.65021 |
| [43] | Tismenetsky, M., A decomposition of Toeplitz matrices and optimal circulant preconditioning, Linear Algebra Appl., 154/155/156, 105-121 (1991) ·Zbl 0734.65039 |
| [44] | Zhou, L.; Walker, H. F., Residual smoothing techniques for iterative methods, SIAM J. Sci. Comput., 15, 297-312 (1994) ·Zbl 0802.65041 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
