A Lanczos-type method for multiple starting vectors. (English) Zbl 0953.65018
A Lanczos type algorithm is proposed with multiple starting vectors. Two sequences of biorthogonal basis vectors are generated for the right and left block Krylov subspaces induced by the given data. A built-in deflation procedure is introduced to detect and delete linearly dependent vectors in the block Krylov sequences.
Reviewer: F.Szidarovszky (Tucson)
MSC:
| 65F10 | Iterative numerical methods for linear systems |
Keywords:
Lanczos algorithm; nonsymmetric matrix; block Krylov subspaces; biorthogonalization; oblique projection; deflation; breakdown; look-aheadSoftware:
ABLEReferences:
| [1] | J. I. Aliaga, Algoritmos paralelos basados en el método de Lanczos. Aplicaciones en problemas de control, Doctoral Thesis, Departamento de Sistemas Informáticos y Computación, Universidad Politécnica de Valencia, Valencia, Spain, 1995. |
| [2] | J. I. Aliaga, D. L. Boley, R. W. Freund, and V. Hernández, A Lanczos-type algorithm for multiple starting vectors, Numerical Analysis Manuscript No. 96-18, Bell Laboratories, Murray Hill, NJ, 1996. Also available online from http://cm.bell-labs.com/cs/doc/96. · Zbl 0953.65018 |
| [3] | J. I. Aliaga, D. L. Boley, and V. Hernández, A block clustered Lanczos algorithm, Presentation at the workshop on “Numerical Linear Algebra with Applications”, Oberwolfach, Germany, April 1994. |
| [4] | Z. Bai, D. Day, and Q. Ye, ABLE: an adaptive block Lanczos method for non-Hermitian eigenvalue problems, Research Report 95-04, Department of Mathematics, University of Kentucky, Lexington, KY, 1995. · Zbl 0932.65045 |
| [5] | Daniel L. Boley, Krylov space methods on state-space control models, Circuits Systems Signal Process. 13 (1994), no. 6, 733 – 758. · Zbl 0833.93024 · doi:10.1007/BF02523124 |
| [6] | Daniel Boley and Gene Golub, The nonsymmetric Lanczos algorithm and controllability, Systems Control Lett. 16 (1991), no. 2, 97 – 105. · Zbl 0732.93004 · doi:10.1016/0167-6911(91)90003-W |
| [7] | Okko H. Bosgra and Antonius J. J. van der Weiden, Input-output invariants for linear multivariable systems, IEEE Trans. Automat. Control 25 (1980), no. 1, 20 – 36. · Zbl 0432.93011 · doi:10.1109/TAC.1980.1102260 |
| [8] | Adhemar Bultheel, Recursive algorithms for the matrix Padé problem, Math. Comp. 35 (1980), no. 151, 875 – 892. · Zbl 0442.41017 |
| [9] | J. K. Cullum and W. E. Donath, A block Lanczos algorithm for computing the \(q\) algebraically largest eigenvalues and a corresponding eigenspace for large, sparse symmetric matrices, Proc. 1974 IEEE Conference on Decision and Control, IEEE Press, New York, 1974, pp. 505-509. |
| [10] | Jane K. Cullum and Ralph A. Willoughby, Lánczos algorithms for large symmetric eigenvalue computations. Vol. I, Progress in Scientific Computing, vol. 3, Birkhäuser Boston, Inc., Boston, MA, 1985. Theory. Jane K. Cullum and Ralph A. Willoughby, Lánczos algorithms for large symmetric eigenvalue computations. Vol. II, Progress in Scientific Computing, vol. 4, Birkhäuser Boston, Inc., Boston, MA, 1985. Programs. · Zbl 0574.65028 |
| [11] | Jane Cullum and Ralph A. Willoughby, A practical procedure for computing eigenvalues of large sparse nonsymmetric matrices, Large scale eigenvalue problems (Oberlech, 1985) North-Holland Math. Stud., vol. 127, North-Holland, Amsterdam, 1986, pp. 193 – 240. · Zbl 0605.65027 · doi:10.1016/S0304-0208(08)72647-1 |
| [12] | P. Feldmann and R. W. Freund, Efficient linear circuit analysis by Padé approximation via the Lanczos process, IEEE Trans. Computer-Aided Design 14 (1995), 639-649. |
| [13] | -, Reduced-order modeling of large linear subcircuits via a block Lanczos algorithm, Proc. 32nd Design Automation Conference, ACM, New York, 1995, pp. 474-479. |
| [14] | Roland W. Freund, The look-ahead Lanczos process for nonsymmetric matrices and its applications, Proceedings of the Cornelius Lanczos International Centenary Conference (Raleigh, NC, 1993) SIAM, Philadelphia, PA, 1994, pp. 33 – 47. · Zbl 1260.65025 |
| [15] | C. K. Chui and L. L. Schumaker , Approximation theory VIII. Vol. 1, Series in Approximations and Decompositions, vol. 6, World Scientific Publishing Co., Inc., River Edge, NJ, 1995. Approximation and interpolation. · Zbl 0928.00035 |
| [16] | R. W. Freund and P. Feldmann, Efficient circuit analysis by Padé approximation via the Lanczos process, Presentation at the workshop on “Numerical Linear Algebra with Applications”, Oberwolfach, Germany, April 1994. |
| [17] | Roland W. Freund, Martin H. Gutknecht, and Noël M. Nachtigal, An implementation of the look-ahead Lanczos algorithm for non-Hermitian matrices, SIAM J. Sci. Comput. 14 (1993), no. 1, 137 – 158. · Zbl 0770.65022 · doi:10.1137/0914009 |
| [18] | Roland W. Freund and Manish Malhotra, A block QMR algorithm for non-Hermitian linear systems with multiple right-hand sides, Proceedings of the Fifth Conference of the International Linear Algebra Society (Atlanta, GA, 1995), 1997, pp. 119 – 157. · Zbl 0873.65021 · doi:10.1016/S0024-3795(96)00529-0 |
| [19] | Roland W. Freund and Noël M. Nachtigal, QMR: a quasi-minimal residual method for non-Hermitian linear systems, Numer. Math. 60 (1991), no. 3, 315 – 339. · Zbl 0754.65034 · doi:10.1007/BF01385726 |
| [20] | Roland W. Freund and Noël M. Nachtigal, An implementation of the QMR method based on coupled two-term recurrences, SIAM J. Sci. Comput. 15 (1994), no. 2, 313 – 337. Iterative methods in numerical linear algebra (Copper Mountain Resort, CO, 1992). · Zbl 0803.65036 · doi:10.1137/0915022 |
| [21] | G. H. Golub and R. Underwood, The block Lanczos method for computing eigenvalues, Mathematical software, III (Proc. Sympos., Math. Res. Center, Univ. Wisconsin, Madison, Wis., 1977) Academic Press, New York, 1977, pp. 361 – 377. Publ. Math. Res. Center, No. 39. · Zbl 0407.68040 |
| [22] | William B. Gragg, Matrix interpretations and applications of the continued fraction algorithm, Proceedings of the International Conference on Padé Approximants, Continued Fractions and Related Topics (Univ. Colorado, Boulder, Colo., 1972; dedicated to the memory of H. S. Wall), 1974, pp. 213 – 225. · Zbl 0321.65001 · doi:10.1216/RMJ-1974-4-2-213 |
| [23] | William B. Gragg and Anders Lindquist, On the partial realization problem, Linear Algebra Appl. 50 (1983), 277 – 319. · Zbl 0519.93024 · doi:10.1016/0024-3795(83)90059-9 |
| [24] | Martin H. Gutknecht, A completed theory of the unsymmetric Lanczos process and related algorithms. I, SIAM J. Matrix Anal. Appl. 13 (1992), no. 2, 594 – 639. · Zbl 0760.65039 · doi:10.1137/0613037 |
| [25] | H. M. Kim and R. R. Craig, Jr., Structural dynamics analysis using an unsymmetric block Lanczos algorithm, Internat. J. Numer. Methods Engrg. 26 (1988), 2305-2318. · Zbl 0661.73062 |
| [26] | -, Computational enhancement of an unsymmetric block Lanczos algorithm, Internat. J. Numer. Methods Engrg. 30 (1990), 1083-1089. CMP 91:01 |
| [27] | C. Lanczos, An iteration method for the solution of the eigenvalue problem of linear differential and integral operators, J. Res. Nat. Bur. Standards 45 (1950), 255-282. |
| [28] | -, Solution of systems of linear equations by minimized iterations, J. Res. Nat. Bur. Standards 49 (1952), 33-53. |
| [29] | Manish Malhotra, Roland W. Freund, and Peter M. Pinsky, Iterative solution of multiple radiation and scattering problems in structural acoustics using a block quasi-minimal residual algorithm, Comput. Methods Appl. Mech. Engrg. 146 (1997), no. 1-2, 173 – 196. · Zbl 0901.76059 · doi:10.1016/S0045-7825(96)01227-3 |
| [30] | A. A. Nikishin and A. Yu. Yeremin, Variable block CG algorithms for solving large sparse symmetric positive definite linear systems on parallel computers. I. General iterative scheme, SIAM J. Matrix Anal. Appl. 16 (1995), no. 4, 1135 – 1153. · Zbl 0837.65029 · doi:10.1137/S0895479893247679 |
| [31] | Dianne P. O’Leary, The block conjugate gradient algorithm and related methods, Linear Algebra Appl. 29 (1980), 293 – 322. · Zbl 0426.65011 · doi:10.1016/0024-3795(80)90247-5 |
| [32] | Beresford N. Parlett, Reduction to tridiagonal form and minimal realizations, SIAM J. Matrix Anal. Appl. 13 (1992), no. 2, 567 – 593. · Zbl 0754.65040 · doi:10.1137/0613036 |
| [33] | Beresford N. Parlett, Derek R. Taylor, and Zhishun A. Liu, A look-ahead Lánczos algorithm for unsymmetric matrices, Math. Comp. 44 (1985), no. 169, 105 – 124. · Zbl 0564.65022 |
| [34] | J. Rissanen, Algorithms for triangular decomposition of block Hankel and Toeplitz matrices with application to factoring positive matrix polynomials, Math. Comp. 27 (1973), 147 – 154. · Zbl 0252.65029 |
| [35] | Axel Ruhe, Implementation aspects of band Lanczos algorithms for computation of eigenvalues of large sparse symmetric matrices, Math. Comp. 33 (1979), no. 146, 680 – 687. · Zbl 0443.65022 |
| [36] | T.-J. Su, A decentralized linear quadratic control design method for flexible structures, Ph.D. Thesis, Department of Aerospace and Engineering Mechanics, The University of Texas at Austin, Austin, TX, 1989. |
| [37] | T.-J. Su and R. R. Craig, Jr., Model reduction and control of flexible structures using Krylov vectors, J. Guidance Control Dynamics 14 (1991), 260-267. |
| [38] | D. R. Taylor, Analysis of the look ahead Lanczos algorithm, Ph.D. Thesis, Department of Mathematics, University of California, Berkeley, CA, 1982. |
| [39] | R. Underwood, An iterative block Lanczos method for the solution of large sparse symmetric eigenproblems, Ph.D. Thesis, Computer Science Department, Stanford University, Stanford, CA, 1975. |
| [40] | A. J. J. van der Weiden and O. H. Bosgra, The determination of structural properties of a linear multivariable system by operations of system similarity. II. Nonproper systems in generalized state-space, Internat. J. Control 32 (1980), no. 3, 489 – 537. · Zbl 0449.93040 · doi:10.1080/00207178008922870 |
| [41] | Guo Liang Xu and Adhemar Bultheel, Matrix Padé approximation: definitions and properties, Linear Algebra Appl. 137/138 (1990), 67 – 136. · Zbl 0704.41011 · doi:10.1016/0024-3795(90)90127-X |
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.
