Simultaneous Similarity Reductions for a Pair of Matrices to Condensed Forms

Abstract

We present simultaneous reduction algorithms for two (nonsymmetric) matrices $A$ and $B$ to upper Hessenberg and lower Hessenberg forms, respectively. One is through the simultaneous similarity reduction and the other is through a Lanczos–Arnoldi-type iteration. The algorithm that uses the Lanczos–Arnoldi-type iteration can be considered as a generalization of both the nonsymmetric Lanczos algorithm and the standard Arnoldi algorithm. We shall also apply our reduction to construct a model reduction for certain kind second-order single-input single-output system. It is proved that the model reduction has the desirable moment matching property.

Keywords

Simultaneous reductions / Lanczos–Arnoldi iteration / Krylov subspace method / Model reduction

References

[1] Bai Z, Day D, Ye Q. ABLE: an adaptive block Lanczos method for non-Hermitian eigenvalue problems. SIAM J. Matrix Anal. Appl.. 1999, 20 1060-1082

[2] Bai Z, Freund R. Eigenvalue-based characterization and test for positive realness of scalar transfer functions. IEEE Trans. Autom. Control. 2000, 45 2396-2402

[3] Bai Z, Su Y. Dimension reduction of large-scale second-order dynamical systems via a second-order Arnoldi method. SIAM J. Sci. Comput.. 2005, 25 5 1692-1709

[4] Bai Z, Ye Q. Error estimation of the Padé approximation of transfer functions via the Lanczos process. Electron. Trans. Numer. Anal.. 1998, 7 1-17

[5] Davis T, Hu Y. The University of Florida sparse matrix collection. ACM Trans. Math. Softw.. 2011, 38 1 1-25

[6] Dax A, Kaniel S. Pivoting techniques for symmetric Gaussian elimination. Numer. Math.. 1977, 28 221-242

[7] Feldman P, Freund RW. Efficient linear circuit analysis by Padé approximation via the Lanczos process. IEEE Trans. Comput. Aided Des.. 1995, 14 639-649

[8] Freund RW, Gutknecht MH, Nachtigal NM. An implementation of the look-ahead Lanczos algorithm for non-Hermitian matrices. SIAM J. Sci. Comput.. 1993, 14 137-158

[9] Geist A. Reduction of a general matrix to tridiagonal form. SIAM J. Matrix Anal. Appl.. 1991, 12 2 362-373

[10] Golub GH, Van Loan CF. Matrix Computations. 1996 3 Baltimore: Johns Hopkins University Press

[11] Hoffnung L, Li RC, Ye Q. Krylov type subspace methods for matrix polynomials. Linear Algebra Appl.. 2006, 415 52-81

[12] Kressner, D.: Numerical Methods for General and Structured Eigenvalue Problems. Lecture Notes in Computational Science and Engineering, vol. 46. Springer, Berlin (2005)

[13] Li, R.C.: Test positive realness of a general transfer function matrix. Technical Report 2000–20, Department of Mathematics, University of Kentucky. http://www.ms.uky.edu/~math/MAreport/ (2000)

[14] Li RC, Bai Z. Structure-preserving model reductions using a Krylov subspace projection formulation. Commun. Math. Sci.. 2005, 3 2 179-199

[15] Moler CB, Stewart GW. An algorithm for generalized matrix eigenvalue problems. SIAM J. Numer. Anal.. 1973, 10 2 241-256

[16] Parlett BN, Taylor DR, Liu ZA. A look-ahead Lanczos algorithm for unsymmetric matrices. Math. Comp.. 1985, 44 105-124

[17] Weiss H, Wang Q, Speyer JL. System characterization of positive real conditions. IEEE Trans. Autom. Control. 1994, 39 541-544

[18] Ye Q. A breakdown-free variation of the nonsymmetric Lanczos algorithms. Math. Comp.. 1994, 62 179-207