Abstract
The nonsymmetric Lanczos method has recently received significant attention as a model reduction technique for large-scale systems. Unfortunately, the Lanczos method may produce an unstable partial realization for a given, stable system. To remedy this situation, unexpensive implicit restarts are developed which can be employed to stabilize the Lanczos generated model.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
M.M.M. Al-Husari, B. Hendel, I.M. Jaimoukha, E.M. Kasenally, D.J.N. Limebeer and A. Portone, Vertical stabilisation of Tokamak plasmas,Proc. 30th IEEE Conf. on Decision and Control, Brighton, England (1991).
G.A. Baker Jr.,Essentials of Padé Approximants (Academic Press, New York, 1975).
R.H. Bartels and G.W. Stewart, Solution of the matrix equationAX+XB=C, Commun. ACM 15 (1972) 820–826.
D.L. Boley, Krylov space methods on state-space control models, Technical Report, Univ. of Minnesota, Minneapolis, MN 55455 (1992).
O.H. Bosgra, G. Schoolstra and M. Steinbuch, Robust control of a compact disc player, in:Proc. 31st IEEE Conf. on Decision and Control, Tucson, AZ (1992).
M.A. Brebner and J. Grad, Eigenvalues ofAx=λBx for real symmetric matricesA andB computed by reduction to a pseudosymmetric form and theHR process, Lin. Alg. Appl. 43 (1982) 99–118.
A. Bunse-Gerstner, An analysis of theHR algorithm for computing the eigenvalues of a matrix, Lin. Alg. Appl. 35 (1981) 155–173.
A Bunse-Gerstner, On the similarity transformation to tridiagonal form, Lin. Multilin. Alg. 12 (1982) 51–56.
C.I. Byrnes and A. Lindquist, The stability and instability of partial realizations, Syst. Contr. Lett. 2 (1982) 99–105.
D. Calvetti, L. Reichel and D.C. Sorensen, An implicitly restarted Lanczos method for large symmetric eigenvalue problems, Electron. Trans. Numer. Anal. 2 (1994) 1–21.
J. Daniel, W.B. Gragg, L. Kaufman and G.W. Stewart, Reorthogonalization and stable algorithms for updating the Gram-Schmidt QR factorization, Math. Comp. 30 (1976) 772–795.
C. Davis and W.M. Kahan, The rotation of eigenvectors by a perturbation III, SIAM J. Numer. Anal. 7 (1970) 1–46.
R.W. Freund, G.H. Golub and N.M. Nachtigal, Iterative solution of linear systems, Acta Numer. 1 (1992) 57–100.
R.W. Freund and N.M. Nachtigal, QMR: a quasi-minimal residual method for non-Hermitian linear systems, Numer. Math. 60 (1991) 315–339.
K. Gallivan, E. Grimme and P. Van Dooren, Asymptotic waveform evaluation via a Lanczos method, Appl. Math. Lett. (1994), to appear.
W.B. Gragg and A. Lindquist, On the partial realization problem, Lin. Alg. Appl. 50 (1983) 277–319.
K. Glover, All optimal Hankel-norm approximations of linear multivariable systems and theirL ∞-error bounds. Int. J. Contr. 39 (1984) 1115–1193.
G.H. Golub and C. Van Loan,Matrix Computations, 2nd ed. (Johns Hopkins University Press, Baltimore, MD, 1989).
E. Grimme, D. Sorensen and P. Van Dooren, Stable partial realizations via an implicitly restarted Lanczos method,Proc. Amer. Control Conf., Baltimore, MD (1994).
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.
M.H. Gutknecht, A completed theory of the unsymmetric Lanczos process and related algorithms, part II, SIAM J. Matrix Anal. Appl. 15 (1994) 15–58.
A.S. Householder,The Numerical Treatment of a Single Nonlinear Equation (McGraw-Hill, New York, 1970).
X. Huang, A survey of Padé approximations and their applications in model reduction, Technical Report, Carnegie Mellon Univ., Pittsburgh, PA 15213 (1990).
I.M. Jaimoukha and E.M. Kasenally, Oblique projection methods for large scale model reduction, SIAM J. Matrix Anal. Appl. (1994), to appear.
C. Lanczos, An iteration method for the solution of the eigenvalue problem of linear differential and integral operators, J. Res. Nat. Bureau Stand. 45 (1950) 255–282.
B.C. Moore, Principal component analysis in linear systems: controllability, observability and model reduction, IEEE Trans. Auto. Contr. AC-26 (1981) 17–32.
C.C. Paige, The computation of eigenvalues and eigenvectors of very large sparse matrices, Ph.D. Dissertation, University of London, UK (1971).
B.N. Parlett, Reduction to tridiagonal form and minimal realizations, SIAM J. Matrix Anal. Appl. 13 (1992) 567–593.
V. Raghavan R.A. Rohrer, L.T. Pillage, J.Y. Lee, J.E. Bracken and M.M. Alaybeyi, AWE-inspired,Proc. IEEE Custom Integrated Circuits Conf. (1993).
Y. Shamash, Stable reduced-order models using Padé type approximations, IEEE Trans. Auto. Contr. AC-19 (1974) 615–616.
Y. Shamash, Model reduction using the Routh stability criterion and the Padé approximation technique, Int. J. Contr. 21 (1975) 475–484.
D.C. Sorensen, Implicit application of polynomial filters in aK-step Arnoldi method, SIAM J. Matrix Anal. Appl. 13 (1992) 357–385.
T.J. Su and R.R. Craig Jr., Model reduction and control of flexible structures using Krylov vectors, J. Guidance, Contr. Dynamics 14 (1991) 260–267.
T.J. Su and R.R. Craig Jr., An unsymmetric Lanczos algorithm for damped structural dynamics systems,Proc. 33rd Conf. on Structures, Structural Dynamics and Materials (1992).
P. Van Dooren, Numerical linear algebra techniques for large scale matrix problems in systems and control,Proc. 31st IEEE Conf. on Decision and Control Tucson, AZ (1992).
C.D. Villemagne and R.E. Skelton, Model reduction using a projection formulation, Int. J. Contr. 46 (1987) 2141–2169.
J.H. Wilkinson,The Algebraic Eigenvalue Problem (Clarendon Press, Oxford, England, 1965).
H. Xiheng, FF-Padé method of model reduction in frequency domain, IEEE Trans. Auto. Contr. AC-32 (1987) 243–246.
Author information
Authors and Affiliations
Additional information
Communicated by M.H. Gutknecht
This work was supported in part by ARPA (US Army ORA4466.01), by ARPA (Grant 60NANB2D1272), by the Department of Energy (Contract DE-FG0f-91ER25103) and by the National Science Foundation (Grants CCR-9209349 and CCR-9120008).
Rights and permissions
About this article
Cite this article
Grimme, E.J., Sorensen, D.C. & Van Dooren, P. Model reduction of state space systems via an implicitly restarted Lanczos method. Numer Algor 12, 1–31 (1996). https://doi.org/10.1007/BF02141739
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02141739