×

Structured generalized eigenvalue condition numbers for parameterized quasiseparable matrices. (English) Zbl 1420.65045

Summary: In this paper, when \(A\) and \(B\) are \(\{1;1\}\)-quasiseparable matrices, we consider the structured generalized relative eigenvalue condition numbers of the pair \((A, B)\) with respect to relative perturbations of the parameters defining \(A\) and \(B\) in the quasiseparable and the Givens-vector representations of these matrices. A general expression is derived for the condition number of the generalized eigenvalue problems of the pair \((A, B)\), where \(A\) and \(B\) are any differentiable function of a vector of parameters with respect to perturbations of such parameters. Moreover, the explicit expressions of the corresponding structured condition numbers with respect to the quasiseparable and Givens-vector representation via tangents for \(\{1; 1\}\)-quasiseparable matrices are derived. Our proposed condition numbers can be computed efficiently by utilizing the recursive structure of quasiseparable matrices. We investigate relationships between various condition numbers of structured generalized eigenvalue problem when \(A\) and \(B\) are \(\{1;1\}\)-quasiseparable matrices. Numerical results show that there are situations in which the unstructured condition number can be much larger than the structured ones.

MSC:

65F15 Numerical computation of eigenvalues and eigenvectors of matrices
65F35 Numerical computation of matrix norms, conditioning, scaling
15A12 Conditioning of matrices
15A18 Eigenvalues, singular values, and eigenvectors
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aurentz, J.L., Mach, T., Vandebril, R., Watkins, D.S.: Fast and backward stable computation of roots of polynomials. SIAM J. Matrix Anal. Appl. 36(3), 942-973 (2015) · Zbl 1319.65034 · doi:10.1137/140983434
[2] Bella, T., Olshevsky, V., Stewart, M.: Nested product decomposition of quasiseparable matrices. SIAM J. Matrix Anal. Appl. 34(4), 1520-1555 (2013) · Zbl 1305.65111 · doi:10.1137/12086354X
[3] Boito, P., Eidelman, Y., Gemignani, L.: Implicit QR for rank-structured matrix pencils. BIT Numer. Math. 54(1), 85-111 (2014) · Zbl 1290.65031 · doi:10.1007/s10543-014-0478-0
[4] Boito, P., Eidelman, Y., Gemignani, L.: Implicit QR for companion-like pencils. Math. Comput. 85(300), 1753-1774 (2016) · Zbl 1335.65041 · doi:10.1090/mcom/3020
[5] Boito, P., Eidelman, Y., Gemignani, L.: A real QZ algorithm for structured companion pencils. Calcolo 54(4), 1305-1338 (2017) · Zbl 1382.65097 · doi:10.1007/s10092-017-0231-6
[6] Buttà, P., Noschese, S.: Structured maximal perturbations for Hamiltonian eigenvalue problems. J. Comput. Appl. Math. 272, 304-312 (2014) · Zbl 1297.65037 · doi:10.1016/j.cam.2013.04.031
[7] Byers, R., Kressner, D.: On the condition of a complex eigenvalue under real perturbations. BIT 44(2), 209-214 (2004) · Zbl 1071.15004 · doi:10.1023/B:BITN.0000039427.46052.02
[8] Diao, H.: On componentwise condition numbers for eigenvalue problems with structured matrices. Numer. Linear Algebra Appl. 16(2), 87-107 (2009) · Zbl 1224.15013 · doi:10.1002/nla.607
[9] Diao, H.-A., Zhao, J.: On structured componentwise condition numbers for Hamiltonian eigenvalue problems. J. Comput. Appl. Math. 335, 74-85 (2018) · Zbl 1392.65090 · doi:10.1016/j.cam.2017.11.039
[10] Dopico, F.M., Olshevsky, V., Zhlobich, P.: Stability of QR-based fast system solvers for a subclass of quasiseparable rank one matrices. Math. Comput. 82(284), 2007-2034 (2013) · Zbl 1279.65033 · doi:10.1090/S0025-5718-2013-02710-X
[11] Dopico, F.M., Pomés, K.: Structured condition numbers for linear systems with parameterized quasiseparable coefficient matrices. Numer. Algorithms 73(4), 1131-1158 (2016) · Zbl 1360.65133 · doi:10.1007/s11075-016-0133-8
[12] Dopico, F.M., Pomés, K.: Structured eigenvalue condition numbers for parameterized quasiseparable matrices. Numer. Math. 134(3), 473-512 (2016) · Zbl 1364.65084 · doi:10.1007/s00211-015-0779-5
[13] Eidelman, Y., Gohberg, I.: On a new class of structured matrices. Integral Equ. Oper. Theory 34(3), 293-324 (1999) · Zbl 0934.15002 · doi:10.1007/BF01300581
[14] Eidelman, Y., Gohberg, I., Haimovici, I.: Separable Type Representations of Matrices and Fast Algorithms. Vol. 1: Basics. Completion Problems. Multiplication and Inversion Algorithms, volume 234 of Operator Theory: Advances and Applications. Birkhäuser/Springer, Basel (2014) · Zbl 1280.65027
[15] Eidelman, Y., Gohberg, I., Haimovici, I.: Separable Type Representations of Matrices and Fast Algorithms. Vol. 2, volume 235 of Operator Theory: Advances and Applications (Eigenvalue Method). Birkhäuser/Springer, Basel (2014) · Zbl 1280.65034 · doi:10.1007/978-3-0348-0606-0
[16] Frayssé, V., Toumazou, V.: A note on the normwise perturbation theory for the regular generalized eigenproblem \[{A}x=\lambda{B}x\] Ax=λBx. Numer. Linear Algebra Appl. 5(1), 1-10 (1998) · Zbl 0937.65044 · doi:10.1002/(SICI)1099-1506(199801/02)5:1<1::AID-NLA121>3.0.CO;2-X
[17] Gemignani, L.: Quasiseparable structures of companion pencils under the QZ-algorithm. Calcolo 42(3-4), 215-226 (2005) · Zbl 1150.65009 · doi:10.1007/s10092-005-0106-0
[18] Gemignani, L.: Structured Matrix Methods for Polynomial Root-Finding. In: Proceedings of the 2007 International Symposium on Symbolic and Algebraic Computation, pp. 175-180. ACM (2007) · Zbl 1190.65078
[19] Geurts, A.J.: A contribution to the theory of condition. Numer. Math. 39(1), 85-96 (1982) · Zbl 0465.65025 · doi:10.1007/BF01399313
[20] Graillat, S.: Structured condition number and backward error for eigenvalue problems. Technical Report RR-2005-01, Université de Perpignan (2005)
[21] Higham, D.J., Higham, N.J.: Structured backward error and condition of generalized eigenvalue problems. SIAM J. Matrix Anal. Appl. 20(2), 493-512 (1999) · Zbl 0935.65032 · doi:10.1137/S0895479896313188
[22] Higham, N.J.: A survey of componentwise perturbation theory in numerical linear algebra. In: Mathematics of Computation 1943-1993: A Half-Century of Computational Mathematics (Vancouver, BC, 1993), volume 48 of Proceedings of Symposia in Applied Mathematics, pp. 49-77. American Mathematical Society, Providence (1994) · Zbl 0815.65062
[23] Kågström, B., Poromaa, P.: Computing eigenspaces with specified eigenvalues of a regular matrix pair \[({A}, {B})\](A,B) and condition estimation: theory, algorithms and software. Numer. Algorithms 12(2), 369-407 (1996) · Zbl 0859.65036 · doi:10.1007/BF02142813
[24] Karow, M.: Structured pseudospectra and the condition of a nonderogatory eigenvalue. SIAM J. Matrix Anal. Appl. 31(5), 2860-2881 (2010) · Zbl 1230.15006 · doi:10.1137/070695836
[25] Karow, M., Kressner, D., Tisseur, F.: Structured eigenvalue condition numbers. SIAM J. Matrix Anal. Appl. 28(4), 1052-1068 (2006). (electronic) · Zbl 1130.65054 · doi:10.1137/050628519
[26] Meng, Q.-L., Diao, H.-A.: Structured condition number for multiple right-hand sides linear systems with parameterized quasiseparable coefficient matrices. Technical Report, Northeast Normal University (2018)
[27] Noschese, S., Pasquini, L.: Eigenvalue condition numbers: zero-structured versus traditional. J. Comput. Appl. Math. 185(1), 174-189 (2006) · Zbl 1086.65042 · doi:10.1016/j.cam.2005.01.032
[28] Noschese, S., Pasquini, L.: Eigenvalue patterned condition numbers: Toeplitz and Hankel cases. J. Comput. Appl. Math. 206(2), 615-624 (2007) · Zbl 1120.65045 · doi:10.1016/j.cam.2006.08.031
[29] Rump, S.M.: Eigenvalues, pseudospectrum and structured perturbations. Linear Algebra Appl. 413(2-3), 567-593 (2006) · Zbl 1093.15020 · doi:10.1016/j.laa.2005.06.009
[30] Stewart, G.W.: Matrix Algorithms. Vol. II: Eigensystems. SIAM, Philadelphia (2001) · Zbl 0984.65031 · doi:10.1137/1.9780898718058
[31] Stewart, G.W., Sun, J.G.: Matrix Perturbation Theory. Computer Science and Scientific Computing. Academic Press Inc, Boston (1990) · Zbl 0706.65013
[32] Stewart, M.: On the description and stability of orthogonal transformations of rank structured matrices. SIAM J. Matrix Anal. Appl. 37(4), 1505-1530 (2016) · Zbl 1349.65105 · doi:10.1137/15M1041900
[33] Vanberghen, Y., Vandebril, R., Van Barel, M.: A QZ-method based on semiseparable matrices. J. Comput. Appl. Math. 218(2), 482-491 (2008) · Zbl 1153.65038 · doi:10.1016/j.cam.2007.07.032
[34] Vandebril, R., Van Barel, M., Mastronardi, N.: A note on the representation and definition of semiseparable matrices. Numer. Linear Algebra Appl. 12(8), 839-858 (2005) · Zbl 1164.15341 · doi:10.1002/nla.455
[35] Vandebril, R., Van Barel, M., Mastronardi, N.: Matrix Computations and Semiseparable Matrices. Vol. 1: Linear Systems. Johns Hopkins University Press, Baltimore (2008) · Zbl 1141.65019
[36] Vandebril, R., Van Barel, M., Mastronardi, N.: Matrix Computations and Semiseparable Matrices. Vol. II: Eigenvalue and Singular Value Methods. Johns Hopkins University Press, Baltimore (2008) · Zbl 1175.65045
[37] Wilkinson, J.H.: The Algebraic Eigenvalue Problem. Clarendon Press, Oxford (1965) · Zbl 0258.65037
[38] Xi, Y., Xia, J.: On the stability of some hierarchical rank structured matrix algorithms. SIAM J. Matrix Anal. Appl. 37(3), 1279-1303 (2016) · Zbl 1348.65064 · doi:10.1137/15M1026195
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.