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).
Additional Information
- Froilán M. Dopico
- Affiliation: Departamento de Matemáticas, Universidad Carlos III de Madrid, Avenida de la Universidad 30, 28911, Leganés, Spain
- MR Author ID: 664010
- Email: dopico@math.uc3m.es
- Javier Pérez
- Affiliation: Department of Mathematical Sciences, University of Montana, Montana
- Email: javier.perez-alvaro@mso.umt.edu
- Paul Van Dooren
- Affiliation: Department of Mathematical Engineering, Université catholique de Louvain, Avenue Georges Lemaître 4, B-1348 Louvain-la-Neuve, Belgium
- MR Author ID: 176855
- Email: paul.vandooren@uclouvain.be
- Received by editor(s): January 12, 2017
- Received by editor(s) in revised form: July 25, 2017, January 10, 2018, and January 23, 2018
- Published electronically: June 14, 2018
- Additional Notes: The first author was supported by Ministerio de Economía, Industria y Competitividad of Spain and Fondo Europeo de Desarrollo Regional (FEDER) of EU through grants MTM-2015-68805-REDT, MTM-2015-65798-P (MINECO/FEDER, UE)
The second author was supported by KU Leuven Research Council grant OT/14/074.
The second and third authors were supported by the Belgian network DYSCO (Dynamical Systems, Control, and Optimization), funded by the Interuniversity Attraction Poles Programme initiated by the Belgian Science Policy Office - © Copyright 2018 American Mathematical Society
- Journal: Math. Comp. 88 (2019), 1189-1228
- MSC (2010): Primary 65F15, 15A18, 15A21, 15A22, 15A54, 93B18
- DOI: https://doi.org/10.1090/mcom/3360
- MathSciNet review: 3904143