Structured backward error analysis of linearized structured polynomial eigenvalue problems

Dopico, Froilán; Pérez, Javier; Van Dooren, Paul

doi:10.1090/mcom/3360

Structured backward error analysis of linearized structured polynomial eigenvalue problems
HTML articles powered by AMS MathViewer

by Froilán M. Dopico, Javier Pérez and Paul Van Dooren HTML | PDF

Math. Comp. 88 (2019), 1189-1228 Request permission

Abstract:

We start by introducing a new class of structured matrix polynomials, namely, the class of $\mathbf {M}_A$-structured matrix polynomials, to provide a common framework for many classes of structured matrix polynomials that are important in applications: the classes of (skew-)symmetric, (anti-) palindromic, and alternating matrix polynomials. Then, we introduce the families of $\mathbf {M}_A$-structured strong block minimal bases pencils and of $\mathbf {M}_A$-structured block Kronecker pencils, which are particular examples of block minimal bases pencils recently introduced by Dopico, Lawrence, Pérez and Van Dooren, and show that any $\mathbf {M}_A$-structured odd-degree matrix polynomial can be strongly linearized via an $\mathbf {M}_A$-structured block Kronecker pencil. Finally, for the classes of (skew-)symmetric, (anti-)palindromic, and alternating odd-degree matrix polynomials, the $\mathbf {M}_A$-structured framework allows us to perform a global and structured backward stability analysis of complete structured polynomial eigenproblems, regular or singular, solved by applying to a $\mathbf {M}_A$-structured block Kronecker pencil a structurally backward stable algorithm that computes its complete eigenstructure, like the palindromic-QR algorithm or the structured versions of the staircase algorithm. This analysis allows us to identify those $\mathbf {M}_A$-structured block Kronecker pencils that yield a computed complete eigenstructure which is the exact one of a slightly perturbed structured matrix polynomial. These pencils include (modulo permutations) the well-known block-tridiagonal and block-anti-tridiagonal structure-preserving linearizations. Our analysis incorporates structure to the recent (unstructured) backward error analysis performed for block Kronecker linearizations by Dopico, Lawrence, Pérez and Van Dooren, and share with it its key features, namely, it is a rigorous analysis valid for finite perturbations, i.e., it is not a first order analysis, it provides precise bounds, and it is valid simultaneously for a large class of structure-preserving strong linearizations.

References

B. Adhikari, Backward errors and linearizations for palindromic matrix polynomials. In preparation (2018). Available as arXiv:0812.4154v1 (2008).
Bibhas Adhikari and Rafikul Alam, On backward errors of structured polynomial eigenproblems solved by structure preserving linearizations, Linear Algebra Appl. 434 (2011), no. 9, 1989–2017. MR 2780396, DOI 10.1016/j.laa.2010.12.014
Sk. Safique Ahmad and Volker Mehrmann, Perturbation analysis for complex symmetric, skew symmetric, even and odd matrix polynomials, Electron. Trans. Numer. Anal. 38 (2011), 275–302. MR 2871870
Maha Al-Ammari and Françoise Tisseur, Hermitian matrix polynomials with real eigenvalues of definite type. Part I: Classification, Linear Algebra Appl. 436 (2012), no. 10, 3954–3973. MR 2914557, DOI 10.1016/j.laa.2010.08.035
E. N. Antoniou and S. Vologiannidis, Linearizations of polynomial matrices with symmetries and their applications, Electron. J. Linear Algebra 15 (2006), 107–114. MR 2201776, DOI 10.13001/1081-3810.1222
T. Apel, V. Mehrmann, D. Watkins, Structured eigenvalue methods for the computation of corner singularities in 3D anisotropic elastic structures, Electron. J. Linear Algebra 11 (2004), 78–87.
Thomas Apel, Volker Mehrmann, and David Watkins, Numerical solution of large scale structured polynomial or rational eigenvalue problems, Foundations of computational mathematics: Minneapolis, 2002, London Math. Soc. Lecture Note Ser., vol. 312, Cambridge Univ. Press, Cambridge, 2004, pp. 137–156. MR 2189630
Publications of Volker Mehrmann (as of December 18, 2014), Numerical algebra, matrix theory, differential-algebraic equations and control theory, Springer, Cham, 2015, pp. xix–xxxv. MR 3380273
Shreemayee Bora, Structured eigenvalue condition number and backward error of a class of polynomial eigenvalue problems, SIAM J. Matrix Anal. Appl. 31 (2009), no. 3, 900–917. MR 2538658, DOI 10.1137/060675769
Shreemayee Bora, Michael Karow, Christian Mehl, and Punit Sharma, Structured eigenvalue backward errors of matrix pencils and polynomials with Hermitian and related structures, SIAM J. Matrix Anal. Appl. 35 (2014), no. 2, 453–475. MR 3194659, DOI 10.1137/130925621
Shreemayee Bora, Michael Karow, Christian Mehl, and Punit Sharma, Structured eigenvalue backward errors of matrix pencils and polynomials with palindromic structures, SIAM J. Matrix Anal. Appl. 36 (2015), no. 2, 393–416. MR 3335496, DOI 10.1137/140973839
Tobias Brüll and Christian Schröder, Dissipativity enforcement via perturbation of para-Hermitian pencils, IEEE Trans. Circuits Syst. I. Regul. Pap. 60 (2013), no. 1, 164–177. MR 3017574, DOI 10.1109/TCSI.2012.2215731
M. I. Bueno, K. Curlett, and S. Furtado, Structured strong linearizations from Fiedler pencils with repetition I, Linear Algebra Appl. 460 (2014), 51–80. MR 3250531, DOI 10.1016/j.laa.2014.07.039
María I. Bueno, Froilán M. Dopico, and Susana Furtado, Linearizations of Hermitian matrix polynomials preserving the sign characteristic, SIAM J. Matrix Anal. Appl. 38 (2017), no. 1, 249–272. MR 3629434, DOI 10.1137/151004847
M. I. Bueno, F. M. Dopico, J. Pérez, R. Saavedra, B. Zykoski, A unified approach to Fiedler-like pencils via strong block minimal bases pencils, Submitted for publication (2016). Available as arXiv:1611.07170.
M. I. Bueno and S. Furtado, Palindromic linearizations of a matrix polynomial of odd degree obtained from Fiedler pencils with repetition, Electron. J. Linear Algebra 23 (2012), 562–577. MR 2946810, DOI 10.13001/1081-3810.1541
M. I. Bueno and S. Furtado, Structured strong linearizations from Fiedler pencils with repetition II, Linear Algebra Appl. 463 (2014), 282–321. MR 3262401, DOI 10.1016/j.laa.2014.08.029
M. I. Bueno, F. M. Dopico, S. Furtado, and M. Rychnovsky, Large vector spaces of block-symmetric strong linearizations of matrix polynomials, Linear Algebra Appl. 477 (2015), 165–210. MR 3337339, DOI 10.1016/j.laa.2015.03.032
R. Byers, D. S. Mackey, V. Mehrmann, H. Xu, Symplectic, BDV, and palindromic approaches to discrete-time control problems. In: Petkov, P. Christov, N. (eds.). A collection of Papers Dedicated to the 60th Anniversary of Mihail Konstantinov, Sofia, pp. 81–102. Publishing House Rodina (2009).
Ralph Byers, Volker Mehrmann, and Hongguo Xu, A structured staircase algorithm for skew-symmetric/symmetric pencils, Electron. Trans. Numer. Anal. 26 (2007), 1–33. MR 2366088
Fernando de Terán, Froilán M. Dopico, and D. Steven Mackey, Linearizations of singular matrix polynomials and the recovery of minimal indices, Electron. J. Linear Algebra 18 (2009), 371–402. MR 2530142, DOI 10.13001/1081-3810.1320
Fernando De Terán, Froilán M. Dopico, and D. Steven Mackey, Fiedler companion linearizations and the recovery of minimal indices, SIAM J. Matrix Anal. Appl. 31 (2009/10), no. 4, 2181–2204. MR 2678963, DOI 10.1137/090772927
Fernando De Terán, Froilán M. Dopico, and D. Steven Mackey, Palindromic companion forms for matrix polynomials of odd degree, J. Comput. Appl. Math. 236 (2011), no. 6, 1464–1480. MR 2854064, DOI 10.1016/j.cam.2011.09.010
Fernando De Terán, Froilán M. Dopico, and D. Steven Mackey, Spectral equivalence of matrix polynomials and the index sum theorem, Linear Algebra Appl. 459 (2014), 264–333. MR 3247227, DOI 10.1016/j.laa.2014.07.007
Fernando De Terán, Froilán M. Dopico, D. Steven Mackey, and Paul Van Dooren, Polynomial zigzag matrices, dual minimal bases, and the realization of completely singular polynomials, Linear Algebra Appl. 488 (2016), 460–504. MR 3419795, DOI 10.1016/j.laa.2015.09.015
Fernando De Terán, Froilán M. Dopico, and Paul Van Dooren, Matrix polynomials with completely prescribed eigenstructure, SIAM J. Matrix Anal. Appl. 36 (2015), no. 1, 302–328. MR 3324973, DOI 10.1137/140964138
F. M. Dopico, J. Pérez, P. Van Dooren, Block minimal bases $\ell$-ifications of matrix polynomials. In preparation (2018).
F. M. Dopico, P. Lawrence, J. Pérez, P. Van Dooren, Block Kronecker linearizations of matrix polynomials and their backward errors. Submitted to publication (2016). Available as arXiv 1707.04843.
Andrii Dmytryshyn, Structure preserving stratification of skew-symmetric matrix polynomials, Linear Algebra Appl. 532 (2017), 266–286. MR 3688641, DOI 10.1016/j.laa.2017.06.044
R. J. Duffin, The Rayleigh-Ritz method for dissipative or gyroscopic systems, Quart. Appl. Math. 18 (1960/61), 215–221. MR 122048, DOI 10.1090/S0033-569X-1960-0122048-8
H. Fassbender, J. Pérez, N. Shayanfar, Symmetric and skew-symmetric block Kronecker linearizations. Technical report (2016). Available as arXiv:1606.01766.
G. David Forney Jr., Minimal bases of rational vector spaces, with applications to multivariable linear systems, SIAM J. Control 13 (1975), 493–520. MR 0378886
F. R. Gantmacher, The theory of matrices. Vols. 1, 2, Chelsea Publishing Co., New York, 1959. Translated by K. A. Hirsch. MR 0107649
Graham M. L. Gladwell, Inverse problems in vibration, 2nd ed., Solid Mechanics and its Applications, vol. 119, Kluwer Academic Publishers, Dordrecht, 2004. MR 2102477
I. Gohberg, P. Lancaster, and L. Rodman, Matrix polynomials, Computer Science and Applied Mathematics, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1982. MR 662418
Nicholas J. Higham, D. Steven Mackey, Niloufer Mackey, and Françoise Tisseur, Symmetric linearizations for matrix polynomials, SIAM J. Matrix Anal. Appl. 29 (2006/07), no. 1, 143–159. MR 2288018, DOI 10.1137/050646202
Nicholas J. Higham, D. Steven Mackey, and Françoise Tisseur, Definite matrix polynomials and their linearization by definite pencils, SIAM J. Matrix Anal. Appl. 31 (2009), no. 2, 478–502. MR 2530260, DOI 10.1137/080721406
A. Hilligues, C. Mehl, V. Mehrmann, On the Solution of Palindromic Eigenvalue Problems, Proceedings of the 4th European Congress on Computational Methods in Applied Sciences and Engineering (ECCOMAS), Jyväskylä (2004).
M. Hofer, N. Finger, J. Schöberl, S. Zaglmayr, U. Langer, R. Lerch. Finite element simulation of wave propagation in periodic piezoelectric SAW structures. IEEE Trans. Ultrason. Ferroelectr. Freq. Control, 53, pp. 1192–1201 (2006).
Roger A. Horn and Charles R. Johnson, Topics in matrix analysis, Cambridge University Press, Cambridge, 1994. Corrected reprint of the 1991 original. MR 1288752
Roger A. Horn and Dennis I. Merino, A real-coninvolutory analog of the polar decomposition, Linear Algebra Appl. 190 (1993), 209–227. MR 1230359, DOI 10.1016/0024-3795(93)90227-F
Tsung-Ming Huang, Wen-Wei Lin, and Wei-Shuo Su, Palindromic quadratization and structure-preserving algorithm for palindromic matrix polynomials of even degree, Numer. Math. 118 (2011), no. 4, 713–735. MR 2822497, DOI 10.1007/s00211-011-0370-7
Thomas Kailath, Linear systems, Prentice-Hall Information and System Sciences Series, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1980. MR 569473
Daniel Kressner, Christian Schröder, and David S. Watkins, Implicit QR algorithms for palindromic and even eigenvalue problems, Numer. Algorithms 51 (2009), no. 2, 209–238. MR 2505842, DOI 10.1007/s11075-008-9226-3
Peter Lancaster, Lambda-matrices and vibrating systems, International Series of Monographs in Pure and Applied Mathematics, Vol. 94, Pergamon Press, Oxford-New York-Paris, 1966. MR 0210345
Peter Lancaster, Strongly stable gyroscopic systems, Electron. J. Linear Algebra 5 (1999), 53–66. MR 1676259, DOI 10.13001/1081-3810.1031
Piers W. Lawrence and Javier Pérez, Constructing strong linearizations of matrix polynomials expressed in Chebyshev bases, SIAM J. Matrix Anal. Appl. 38 (2017), no. 3, 683–709. MR 3679917, DOI 10.1137/16M105839X
Tiexiang Li, Chun-Yueh Chiang, Eric King-wah Chu, and Wen-Wei Lin, The palindromic generalized eigenvalue problem $A^*x=\lambda Ax$: numerical solution and applications, Linear Algebra Appl. 434 (2011), no. 11, 2269–2284. MR 2776795, DOI 10.1016/j.laa.2009.12.020
D. Steven Mackey, Niloufer Mackey, Christian Mehl, and Volker Mehrmann, Vector spaces of linearizations for matrix polynomials, SIAM J. Matrix Anal. Appl. 28 (2006), no. 4, 971–1004. MR 2276550, DOI 10.1137/050628350
D. Steven Mackey, Niloufer Mackey, Christian Mehl, and Volker Mehrmann, Structured polynomial eigenvalue problems: good vibrations from good linearizations, SIAM J. Matrix Anal. Appl. 28 (2006), no. 4, 1029–1051. MR 2276552, DOI 10.1137/050628362
D. Steven Mackey, Niloufer Mackey, Christian Mehl, and Volker Mehrmann, Numerical methods for palindromic eigenvalue problems: computing the anti-triangular Schur form, Numer. Linear Algebra Appl. 16 (2009), no. 1, 63–86. MR 2477566, DOI 10.1002/nla.612
D. Steven Mackey, Niloufer Mackey, Christian Mehl, and Volker Mehrmann, Jordan structures of alternating matrix polynomials, Linear Algebra Appl. 432 (2010), no. 4, 867–891. MR 2577634, DOI 10.1016/j.laa.2009.10.002
D. Steven Mackey, Niloufer Mackey, Christian Mehl, and Volker Mehrmann, Smith forms of palindromic matrix polynomials, Electron. J. Linear Algebra 22 (2011), 53–91. MR 2781038, DOI 10.13001/1081-3810.1426
D. Steven Mackey, Niloufer Mackey, Christian Mehl, and Volker Mehrmann, Skew-symmetric matrix polynomials and their Smith forms, Linear Algebra Appl. 438 (2013), no. 12, 4625–4653. MR 3039215, DOI 10.1016/j.laa.2013.02.010
D. Steven Mackey, Niloufer Mackey, Christian Mehl, and Volker Mehrmann, Möbius transformations of matrix polynomials, Linear Algebra Appl. 470 (2015), 120–184. MR 3314310, DOI 10.1016/j.laa.2014.05.013
V. Markine, A. D. Man, S. Jovanovic, C. Esveld, Optimal Design of Embedded Rail Structure for High-speed Railway Lines, Railway Engineering 2000, 3rd International Conference, London (2000).
Christian Mehl, Jacobi-like algorithms for the indefinite generalized Hermitian eigenvalue problem, SIAM J. Matrix Anal. Appl. 25 (2004), no. 4, 964–985. MR 2081126, DOI 10.1137/S089547980240947X
Volker Mehrmann and David Watkins, Structure-preserving methods for computing eigenpairs of large sparse skew-Hamiltonian/Hamiltonian pencils, SIAM J. Sci. Comput. 22 (2000), no. 6, 1905–1925. MR 1856293, DOI 10.1137/S1064827500366434
Volker Mehrmann and Heinrich Voss, Nonlinear eigenvalue problems: a challenge for modern eigenvalue methods, GAMM Mitt. Ges. Angew. Math. Mech. 27 (2004), no. 2, 121–152 (2005). MR 2124762, DOI 10.1002/gamm.201490007
V. Mehrmann, C. Schröder, and V. Simoncini, An implicitly-restarted Krylov subspace method for real symmetric/skew-symmetric eigenproblems, Linear Algebra Appl. 436 (2012), no. 10, 4070–4087. MR 2914564, DOI 10.1016/j.laa.2009.11.009
C. B. Moler and G. W. Stewart, An algorithm for generalized matrix eigenvalue problems, SIAM J. Numer. Anal. 10 (1973), 241–256. MR 345399, DOI 10.1137/0710024
Yuji Nakatsukasa, Vanni Noferini, and Alex Townsend, Vector spaces of linearizations for matrix polynomials: a bivariate polynomial approach, SIAM J. Matrix Anal. Appl. 38 (2017), no. 1, 1–29. MR 3592075, DOI 10.1137/15M1013286
Vanni Noferini, The behaviour of the complete eigenstructure of a polynomial matrix under a generic rational transformation, Electron. J. Linear Algebra 23 (2012), 607–624. MR 2966794, DOI 10.13001/1081-3810.1545
Vanni Noferini and Javier Pérez, Fiedler-comrade and Fiedler-Chebyshev pencils, SIAM J. Matrix Anal. Appl. 37 (2016), no. 4, 1600–1624. MR 3569555, DOI 10.1137/16M1055943
Leonardo Robol, Raf Vandebril, and Paul Van Dooren, A framework for structured linearizations of matrix polynomials in various bases, SIAM J. Matrix Anal. Appl. 38 (2017), no. 1, 188–216. MR 3623695, DOI 10.1137/16M106296X
H. H. Rosenbrock, State-space and multivariable theory, John Wiley & Sons, Inc. [Wiley Interscience Division], New York, 1970. MR 0325201
C. Schröder, Palindromic and Even Eigenvalue Problems - Analysis and Numerical Methods, PhD. Dissertation, Technische Universität Berlin, 2008. http://dx.doi.org/10.14279/depositonce-1852.
C. Schröder, URV decomposition bases structured methods for palindromic and even eigenvalue problems, Technical report, Preprint 375, TU Berlin, MATHEON, Germany (2007).
C. Schröder, A QR-like algorithm for the palindromic eigenvalue problem, Technical report, Preprint 388, TU Berlin, Matheon, Germany (2007).
G. W. Stewart, On the sensitivity of the eigenvalue problem $Ax=\lambda Bx$, SIAM J. Numer. Anal. 9 (1972), 669–686. MR 311682, DOI 10.1137/0709056
Françoise Tisseur and Karl Meerbergen, The quadratic eigenvalue problem, SIAM Rev. 43 (2001), no. 2, 235–286. MR 1861082, DOI 10.1137/S0036144500381988
P. Van Dooren, The computation of Kronecker’s canonical form of a singular pencil, Linear Algebra Appl. 27 (1979), 103–140. MR 545726, DOI 10.1016/0024-3795(79)90035-1
Paul Van Dooren and Patrick Dewilde, The eigenstructure of an arbitrary polynomial matrix: computational aspects, Linear Algebra Appl. 50 (1983), 545–579. MR 699575, DOI 10.1016/0024-3795(83)90069-1
Charles F. Van Loan, The ubiquitous Kronecker product, J. Comput. Appl. Math. 123 (2000), no. 1-2, 85–100. Numerical analysis 2000, Vol. III. Linear algebra. MR 1798520, DOI 10.1016/S0377-0427(00)00393-9
Y. Wu, Y. Yang, E. Yau, Three-dimensional analysis of train-rail-bridge interaction problems, Veh. Syst. Dyn. 36 (2001), 1–35.
S. Zaglmayr, Eigenvalue problems in SAW-filter simulations, Diplomarbeit, Johannes Kepler Universität Linz (2002).