Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

   
 
 

 

A Lanczos-type method
for multiple starting vectors


Authors: J. I. Aliaga, D. L. Boley, R. W. Freund and V. Hernández
Journal: Math. Comp. 69 (2000), 1577-1601
MSC (1991): Primary 65F10, 65F15; Secondary 65F25, 65F30
DOI: https://doi.org/10.1090/S0025-5718-99-01163-1
Published electronically: May 20, 1999
MathSciNet review: 1665942
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Given a square matrix and single right and left starting vectors, the classical nonsymmetric Lanczos process generates two sequences of biorthogonal basis vectors for the right and left Krylov subspaces induced by the given matrix and vectors. In this paper, we propose a Lanczos-type algorithm that extends the classical Lanczos process for single starting vectors to multiple starting vectors. Given a square matrix and two blocks of right and left starting vectors, the algorithm generates two sequences of biorthogonal basis vectors for the right and left block Krylov subspaces induced by the given data. The algorithm can handle the most general case of right and left starting blocks of arbitrary sizes, while all previously proposed extensions of the Lanczos process are restricted to right and left starting blocks of identical sizes. Other features of our algorithm include a built-in deflation procedure to detect and delete linearly dependent vectors in the block Krylov sequences, and the option to employ look-ahead to remedy the potential breakdowns that may occur in nonsymmetric Lanczos-type methods.


References [Enhancements On Off] (What's this?)

  • 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.
  • 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.
  • 5. D. L. Boley, Krylov space methods on state-space control models, Circuits Systems Signal Process. 13 (1994), 733-758. MR 95e:93036
  • 6. D. L. Boley and G. H. Golub, The nonsymmetric Lanczos algorithm and controllability, Systems Control Lett. 16 (1991), 97-105. MR 92e:93004
  • 7. O. H. Bosgra and A. J. J. Van der Weiden, Input-output invariants for linear multivariable systems, IEEE Trans. Automat. Control AC-25 (1980), 20-36. MR 81m:93022
  • 8. A. Bultheel, Recursive algorithms for the matrix Padé problem, Math. Comp. 35 (1980), 875-892. MR 81h: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. J. K. Cullum and R. A. Willoughby, Lanczos algorithms for large symmetric eigenvalue computations, Volume 1, Theory, Birkhäuser, Basel, 1985. MR 87h:65064a
  • 11. -, A practical procedure for computing eigenvalues of large sparse nonsymmetric matrices, Large Scale Eigenvalue Problems (J. Cullum and R. A. Willoughby, eds.), North-Holland, Amsterdam, The Netherlands, 1986, pp. 193-240. MR 88a:65040
  • 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. R. W. Freund, The look-ahead Lanczos process for nonsymmetric matrices and its applications, Proceedings of the Cornelius Lanczos International Centenary Conference (J. D. Brown et al., eds.), SIAM, Philadelphia, 1994, pp. 33-47. MR 95f:65076
  • 15. -, Computation of matrix Padé approximations of transfer functions via a Lanczos-type process, Approximation Theory VIII, Vol. 1: Approximation and Interpolation (C. K. Chui and L. L. Schumaker, eds.), World Scientific Publishing Co., Inc., Singapore, 1995, pp. 215-222. MR 98d:41001
  • 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. R. W. Freund, M. H. Gutknecht, and N. M. Nachtigal, An implementation of the look-ahead Lanczos algorithm for non-Hermitian matrices, SIAM J. Sci. Comput. 14 (1993), 137-158. MR 93h:65048
  • 18. R. W. Freund and M. Malhotra, A block QMR algorithm for non-Hermitian linear systems with multiple right-hand sides, Linear Algebra Appl. 254 (1997), 119-157. MR 98g:65027
  • 19. R. W. Freund and N. M. Nachtigal, QMR: a quasi-minimal residual method for non-Hermitian linear systems, Numer. Math. 60 (1991), 315-339. MR 92g:65034
  • 20. -, An implementation of the QMR method based on coupled two-term recurrences, SIAM J. Sci. Comput. 15 (1994), 313-337. MR 95f:65067
  • 21. G. H. Golub and R. Underwood, The block Lanczos method for computing eigenvalues, Mathematical Software III (J. R. Rice, ed.), Academic Press, New York, 1977, pp. 361-377. MR 57:14376
  • 22. W. B. Gragg, Matrix interpretations and applications of the continued fraction algorithm, Rocky Mountain J. Math. 4 (1974), 213-225. MR 49:6576
  • 23. W. B. Gragg and A. Lindquist, On the partial realization problem, Linear Algebra Appl. 50 (1983), 277-319. MR 84h:93020
  • 24. M. H. Gutknecht, A completed theory of the unsymmetric Lanczos process and related algorithms, part I, SIAM J. Matrix Anal. Appl. 13 (1992), 594-639. MR 93e:65053
  • 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.
  • 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. MR 13:163d
  • 28. -, Solution of systems of linear equations by minimized iterations, J. Res. Nat. Bur. Standards 49 (1952), 33-53. MR 14:501g
  • 29. M. Malhotra, R. W. Freund, and P. 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), 173-196. MR 98d:76104
  • 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), 1135-1153. MR 97e:65032
  • 31. D. P. O'Leary, The block conjugate gradient algorithm and related methods, Linear Algebra Appl. 29 (1980), 293-322. MR 81i:65027
  • 32. B. N. Parlett, Reduction to tridiagonal form and minimal realizations, SIAM J. Matrix Anal. Appl. 13 (1992), 567-593. MR 93c:65059
  • 33. B. N. Parlett, D. R. Taylor, and Z. A. Liu, A look-ahead Lanczos algorithm for unsymmetric matrices, Math. Comp. 44 (1985), 105-124. MR 86f:65072
  • 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. MR 48:7577
  • 35. A. Ruhe, Implementation aspects of band Lanczos algorithms for computation of eigenvalues of large sparse symmetric matrices, Math. Comp. 33 (1979), 680-687. MR 81b:65034
  • 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, Internat. J. Control 32 (1980), 489-537. MR 81j:93036
  • 41. G.-L. Xu and A. Bultheel, Matrix Padé approximation: definitions and properties, Linear Algebra Appl. 137/138 (1990), 67-136. MR 91g:41020

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (1991): 65F10, 65F15, 65F25, 65F30

Retrieve articles in all journals with MSC (1991): 65F10, 65F15, 65F25, 65F30


Additional Information

J. I. Aliaga
Affiliation: Departamento de Informática, Universidad Jaume I, Campus de Riu Sec, 12071 Castellón, Spain
Email: aliaga@inf.uji.es

D. L. Boley
Affiliation: Department of Computer Science and Engineering, University of Minnesota, 4-192 EE/CSci Building, 200 Union Street S.E., Minneapolis, Minnesota 55455-0159
Email: boley@cs.umn.edu

R. W. Freund
Affiliation: Bell Laboratories, Lucent Technologies, Room 2C-420, 700 Mountain Avenue, Murray Hill, New Jersey 07974-0636
Email: freund@research.bell-labs.com

V. Hernández
Affiliation: Departamento de Sistemas Informáticos y Computación, Universidad Politécnica de Valencia, Apartado de Correos 22012, 46071 Valencia, Spain
Email: vhernand@dsic.upv.es

DOI: https://doi.org/10.1090/S0025-5718-99-01163-1
Keywords: Lanczos algorithm, nonsymmetric matrix, block Krylov subspaces, biorthogonalization, oblique projection, deflation, breakdown, look-ahead
Received by editor(s): October 10, 1996
Received by editor(s) in revised form: September 22, 1998
Published electronically: May 20, 1999
Additional Notes: The first and the last author were supported in part by the European ESPRIT III Basic Research Project GEPPCOM #9072. The second author was supported in part by the U.S. NSF Grants #CCR-9405380 and #CCR-9628786.
Article copyright: © Copyright 2000 Lucent Technologies

American Mathematical Society