Fast Hessenberg reduction of some rank structured matrices
Gemignani L., Robol L
Bulge chasing Mathematics - Numerical Analysis Analysis FOS: Mathematics 65F15 Quasiseparable matrices Numerical Analysis (math.NA) CMV matrix Hessenberg reduction Complexity
We develop two fast algorithms for Hessenberg reduction of a structured matrix $A = D + UV^H$, where $D$ is a real or unitary n x n diagonal matrix and $U, V in mathbb{C}^{n times k}$. The proposed algorithm for the real case exploits a two-stage approach by first reducing the matrix to a generalized Hessenberg form and then completing the reduction by annihilation of the unwanted subdiagonals. It is shown that the novel method requires O(n^2 k) arithmetic operations and is significantly faster than other reduction algorithms for rank structured matrices. The method is then extended to the unitary plus low rank case by using a block analogue of the CMV form of unitary matrices. It is shown that a block Lanczos-type procedure for the block tridiagonalization of Re(D) induces a structured reduction on A in a block staircase CMV-type shape. Then, we present a numerically stable method for performing this reduction using unitary transformations and show how to generalize the subdiagonal elimination to this shape, while still being able to provide a condensed representation for the reduced matrix. In this way the complexity still remains linear in k and, moreover, the resulting algorithm can be adapted to deal efficiently with block companion matrices.
Source: SIAM journal on matrix analysis and applications (Print) 38 (2017): 574–598. doi:10.1137/16M1107851
Publisher: Society for Industrial and Applied Mathematics ,, Philadelphia, Pa. , Stati Uniti d'America
[2] G. S. Ammar and W. B. Gragg, O(n2) reduction algorithms for the construction of a band matrix from spectral data, SIAM J. Matrix Anal. Appl., 12 (1991), pp. 426-431, doi:10.1137/0612030, http://dx.doi.org/10.1137/0612030.
[3] P. Arbenz and G. H. Golub, On the spectral decomposition of Hermitian matrices modified by low rank perturbations with applications, SIAM J. Matrix Anal. Appl., 9 (1988), pp. 40-58, doi:10.1137/0609004, http://dx.doi.org/10.1137/0609004.
[4] Y. Arlinski˘ı, Conservative discrete time-invariant systems and block operator CMV matrices, Methods Funct. Anal. Topology, 15 (2009), pp. 201-236.
[5] R. Bevilacqua, G. M. Del Corso, and L. Gemignani, A CMV-based eigensolver for companion matrices, SIAM J. Matrix Anal. Appl., 36 (2015), pp. 1046-1068, doi:10.1137/140978065, http://dx.doi.org/10.1137/140978065.
[6] R. Bevilacqua, G. M. Del Corso, and L. Gemignani, Compression of unitary rankstructured matrices to CMV-like shape with an application to polynomial rootfinding, J. Comput. Appl. Math., 278 (2015), pp. 326-335, doi:10.1016/j.cam.2014.09.023, http://dx. doi.org/10.1016/j.cam.2014.09.023.
[7] D. A. Bini and L. Robol, On a class of matrix pencils and ℓ-ifications equivalent to a given matrix polynomial, Linear Algebra Appl., (2015), doi:10.1016/j.laa.2015.07.017.
[8] D. A. Bini and L. Robol, Quasiseparable hessenberg reduction of real diagonal plus low rank matrices and applications, Linear Algebra Appl., (2015), doi:10.1016/j.laa.2015.08.026.
[9] C. H. Bischof, B. Lang, and X. Sun, A framework for symmetric band reduction, ACM Trans. Math. Software, 26 (2000), pp. 581-601, doi:10.1145/365723.365735, http://dx.doi. org/10.1145/365723.365735.
[10] A. Bunse-Gerstner and L. Elsner, Schur parameter pencils for the solution of the unitary eigenproblem, Linear Algebra Appl., 154/156 (1991), pp. 741-778, doi:10.1016/0024-3795(91)90402-I, http://dx.doi.org/10.1016/0024-3795(91)90402-I.
[11] M. J. Cantero, L. Moral, and L. Vela´zquez, Five-diagonal matrices and zeros of orthogonal polynomials on the unit circle, Linear Algebra Appl., 362 (2003), pp. 29-56, doi:10.1016/S0024-3795(02)00457-3, http://dx.doi.org/10.1016/S0024-3795(02)00457-3.
[12] S. Delvaux and M. Van Barel, A Hessenberg reduction algorithm for rank structured matrices, SIAM J. Matrix Anal. Appl., 29 (2007), pp. 895-926 (electronic), doi:10.1137/060658953, http://dx.doi.org/10.1137/060658953.
[13] Y. Eidelman, L. Gemignani, and I. Gohberg, Efficient eigenvalue computation for quasiseparable Hermitian matrices under low rank perturbations, Numer. Algorithms, 47 (2008), pp. 253-273, doi:10.1007/s11075-008-9172-0, http://dx.doi.org/10.1007/ s11075-008-9172-0.
[14] Y. Eidelman, I. Gohberg, and L. Gemignani, On the fast reduction of a quasiseparable matrix to Hessenberg and tridiagonal forms, Linear Algebra Appl., 420 (2007), pp. 86- 101, doi:10.1016/j.laa.2006.06.028, http://dx.doi.org/10.1016/j.laa.2006.06.028.
[15] Y. Eidelman, I. Gohberg, and I. Haimovici, Separable type representations of matrices and fast algorithms. Vol. 1, vol. 234 of Operator Theory: Advances and Applications, Birkh¨auser/Springer, Basel, 2014. Basics. Completion problems. Multiplication and inversion algorithms.
[16] Y. Eidelman, I. Gohberg, and I. Haimovici, Separable type representations of matrices and fast algorithms. Vol. 2, vol. 235 of Operator Theory: Advances and Applications, Birkh¨auser/Springer Basel AG, Basel, 2014. Eigenvalue method.
[17] M. Fiedler and T. L. Markham, Completing a matrix when certain entries of its inverse are specified, Linear Algebra Appl., 74 (1986), pp. 225-237, doi:10.1016/0024-3795(86)90125-4, http://dx.doi.org/10.1016/0024-3795(86)90125-4.
[18] I. Gohberg, P. Lancaster, and L. Rodman, Matrix polynomials, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1982. Computer Science and Applied Mathematics.
[19] W. H. Gustafson, A note on matrix inversion, Linear Algebra Appl., 57 (1984), pp. 71-73, doi:10.1016/0024-3795(84)90177-0, http://dx.doi.org/10.1016/0024-3795(84)90177-0.
[20] B. K˚agstro¨m, D. Kressner, E. S. Quintana-Ort´ı, and G. Quintana-Ort´ı, Blocked algorithms for the reduction to Hessenberg-triangular form revisited, BIT, 48 (2008), pp. 563- 584, doi:10.1007/s10543-008-0180-1, http://dx.doi.org/10.1007/s10543-008-0180-1.
[21] R. Killip and I. Nenciu, CMV: the unitary analogue of Jacobi matrices, Comm. Pure Appl. Math., 60 (2007), pp. 1148-1188, doi:10.1002/cpa.20160, http://dx.doi.org/10.1002/cpa. 20160.
[22] B. Simon, CMV matrices: five years after, J. Comput. Appl. Math., 208 (2007), pp. 120-154, doi:10.1016/j.cam.2006.10.033, http://dx.doi.org/10.1016/j.cam.2006.10.033.
[23] M. Van Barel and A. Bultheel, Orthonormal polynomial vectors and least squares approximation for a discrete inner product, Electron. Trans. Numer. Anal., 3 (1995), pp. 1-23 (electronic).
[24] R. Vandebril, M. Van Barel, and N. Mastronardi, Matrix computations and semiseparable matrices. Vol. 1, Johns Hopkins University Press, Baltimore, MD, 2008. Linear systems.
[25] R. Vandebril, M. Van Barel, and N. Mastronardi, Matrix computations and semiseparable matrices. Vol. II, Johns Hopkins University Press, Baltimore, MD, 2008. Eigenvalue and singular value methods.
Metrics
Back to previous page
@article{oai:it.cnr:prodotti:374248,
title = {Fast Hessenberg reduction of some rank structured matrices},
author = {Gemignani L. and Robol L},
publisher = {Society for Industrial and Applied Mathematics ,, Philadelphia, Pa. , Stati Uniti d'America},
doi = {10.1137/16m1107851 and 10.48550/arxiv.1612.04196},
journal = {SIAM journal on matrix analysis and applications (Print)},
volume = {38},
pages = {574–598},
year = {2017}
}
0000-0002-6545-1748ISTI Repository
DOI
10.1137/16m1107851
10.48550/arxiv.1612.04196
arXiv.org e-Print Archive
SIAM Journal on Matrix Analysis and Applications
epubs.siam.org