Mathematics of Computation

Author(s): J. I. Aliaga; D. L. Boley; R. W. Freund; V. Hernández.
Journal: Math. Comp. 69 (2000), 1577-1601.
MSC (1991): Primary 65F10, 65F15; Secondary 65F25, 65F30
Posted: May 20, 1999
Retrieve article in: PDF DVI PostScript
This article is available free of charge

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.

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

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

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: 10.1090/S0025-5718-99-01163-1
PII: S 0025-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
Posted: 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.
Copyright of article: Copyright 2000, Lucent Technologies

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS