Decay bounds for the numerical quasiseparable preservation in matrix functions. (English) Zbl 1352.15011
Summary: Given matrices \(A\) and \(B\) such that \(B = f(A)\), where \(f(z)\) is a holomorphic function, we analyze the relation between the singular values of the off-diagonal submatrices of \(A\) and \(B\). We provide a family of bounds which depend on the interplay between the spectrum of the argument \(A\) and the singularities of the function. In particular, these bounds guarantee the numerical preservation of quasiseparable structures under mild hypotheses. We extend the Dunford-Cauchy integral formula to the case in which some poles are contained inside the contour of integration. We use this tool together with the technology of hierarchical matrices (\(\mathcal{H}\)-matrices) for the effective computation of matrix functions with quasiseparable arguments.
MSC:
| 15A16 | Matrix exponential and similar functions of matrices |
| 65F60 | Numerical computation of matrix exponential and similar matrix functions |
| 65D32 | Numerical quadrature and cubature formulas |
| 30C30 | Schwarz-Christoffel-type mappings |
| 65E05 | General theory of numerical methods in complex analysis (potential theory, etc.) |
Keywords:
matrix functions; quasiseparable matrices; off-diagonal singular values; decay bounds; exponential decay; \(\mathcal{H}\)-matricesSoftware:
mftoolboxReferences:
| [1] | Benzi, M.; Boito, P., Decay properties for functions of matrices over \(C^\ast \)-algebras, Linear Algebra Appl., 456, 174-198 (2014) · Zbl 1314.47020 |
| [2] | Benzi, M.; Boito, P.; Razouk, N., Decay properties of spectral projectors with applications to electronic structure, SIAM Rev., 55, 1, 3-64 (2013) · Zbl 1377.65155 |
| [3] | Benzi, M.; Simoncini, V., Decay bounds for functions of Hermitian matrices with banded or Kronecker structure, SIAM J. Matrix Anal. Appl., 36, 3, 1263-1282 (2015) · Zbl 1323.15005 |
| [4] | Bini, D. A.; Iannazzo, B.; Meini, B., Numerical Solution of Algebraic Riccati Equations, Fundam. Algorithms, vol. 9 (2012), SIAM: SIAM Philadelphia · Zbl 1244.65058 |
| [5] | Bini, D. A.; Latouche, G.; Meini, B., Numerical Methods for Structured Markov Chains, Numer. Math. Sci. Comput. (2005), Oxford University Press, Oxford Science Publications: Oxford University Press, Oxford Science Publications New York · Zbl 1076.60002 |
| [6] | Bini, D. A.; Massei, S.; Robol, L., Efficient cyclic reduction for quasi-birth-death problems with rank structured blocks, Appl. Numer. Math. (2016), in press |
| [7] | Bini, D. A.; Massei, S.; Robol, L., On the decay of the off-diagonal singular values in cyclic reduction (2016), preprint |
| [8] | Bini, D. A.; Meini, B., The cyclic reduction algorithm: from Poisson equation to stochastic processes and beyond. In memoriam of Gene H. Golub, Numer. Algorithms, 51, 1, 23-60 (2009) · Zbl 1170.65021 |
| [9] | Börm, S.; Grasedyck, L.; Hackbusch, W., Hierarchical matrices (2003), Lecture note 21 |
| [10] | Buzbee, B. L.; Golub, G. H.; Nielson, C. W., On direct methods for solving Poisson’s equations, SIAM J. Numer. Anal., 7, 627-656 (1970) · Zbl 0217.52902 |
| [11] | Canuto, C.; Simoncini, V.; Verani, M., On the decay of the inverse of matrices that are sum of Kronecker products, Linear Algebra Appl., 452, 21-39 (2014) · Zbl 1291.65144 |
| [12] | Chandrasekaran, S.; Dewilde, P.; Gu, M.; Somasunderam, N., On the numerical rank of the off-diagonal blocks of Schur complements of discretized elliptic PDEs, SIAM J. Matrix Anal. Appl., 31, 5, 2261-2290 (2010) · Zbl 1209.65032 |
| [13] | Crouzeix, M., Numerical range and functional calculus in Hilbert space, J. Funct. Anal., 244, 2, 668-690 (2007) · Zbl 1116.47004 |
| [14] | Eidelman, Y.; Gohberg, I., On generators of quasiseparable finite block matrices, Calcolo, 42, 3-4, 187-214 (2005) · Zbl 1146.15300 |
| [15] | Eidelman, Y.; Gohberg, I.; Haimovici, I., Separable type representations of matrices and fast algorithms, vol. 1, (Basics. Completion Problems. Multiplication and Inversion Algorithms. Basics. Completion Problems. Multiplication and Inversion Algorithms, Oper. Theory Adv. Appl., vol. 234 (2014), Birkhäuser/Springer: Birkhäuser/Springer Basel) · Zbl 1280.65027 |
| [16] | Ellacott, S. W., Computation of Faber series with application to numerical polynomial approximation in the complex plane, Math. Comp., 40, 162, 575-587 (1983) · Zbl 0512.65018 |
| [17] | Gantmacher, F. R., The Theory of Matrices, vol. 1 (1998), AMS Chelsea Publishing: AMS Chelsea Publishing Providence, RI, Translated from the Russian by K.A. Hirsch, reprint of the 1959 translation · Zbl 0927.15001 |
| [18] | Gavrilyuk, I. P.; Hackbusch, W.; Khoromskij, B. N., \(H\)-matrix approximation for the operator exponential with applications, Numer. Math., 92, 1, 83-111 (2002) · Zbl 1005.65113 |
| [19] | Gavrilyuk, I. P.; Hackbusch, W.; Khoromskij, B. N., Data-sparse approximation to a class of operator-valued functions, Math. Comp., 74, 250, 681-708 (2005) · Zbl 1066.65060 |
| [20] | Golub, G. H.; Van Loan, C. F., Matrix Computations, Johns Hopkins Stud. Math. Sci. (2013), Johns Hopkins University Press: Johns Hopkins University Press Baltimore, MD · Zbl 1268.65037 |
| [21] | Hackbusch, W., A sparse matrix arithmetic based on \(H\)-matrices. Part I: introduction to \(H\)-matrices, Computing, 62, 2, 89-108 (1999) · Zbl 0927.65063 |
| [22] | Hackbusch, W., Hierarchical Matrices: Algorithms and Analysis, Springer Ser. Comput. Math., vol. 49 (2015), Springer: Springer Heidelberg · Zbl 1336.65041 |
| [23] | Henrici, P., Applied and Computational Complex Analysis, vol. 1, Wiley Classics Library (1988), John Wiley & Sons, Inc.: John Wiley & Sons, Inc. New York · Zbl 0635.30001 |
| [24] | Higham, N. J., Functions of matrices, (Theory and Computation (2008), Society for Industrial and Applied Mathematics (SIAM): Society for Industrial and Applied Mathematics (SIAM) Philadelphia, PA) · Zbl 1167.15001 |
| [25] | Hockney, R. W., A fast direct solution of Poisson’s equation using Fourier analysis, J. ACM, 12, 95-113 (1965) · Zbl 0139.10902 |
| [26] | Horn, R. A.; Johnson, C. R., Topics in Matrix Analysis (1994), Cambridge University Press: Cambridge University Press Cambridge, Corrected reprint of the 1991 original · Zbl 0801.15001 |
| [27] | Lancaster, P.; Tismenetsky, M., The Theory of Matrices, Comput. Sci. Appl. Math. (1985), Academic Press, Inc.: Academic Press, Inc. Orlando, FL · Zbl 0516.15018 |
| [28] | Landkof, N. S., Foundations of Modern Potential Theory, Grundlehren Math. Wiss., vol. 180 (1972), Springer-Verlag: Springer-Verlag New York-Heidelberg, Translated from the Russian by A.P. Doohovskoy · Zbl 0253.31001 |
| [29] | Markushevich, A. I., Theory of Functions of a Complex Variable, vols. I, II, III (1977), Chelsea Publishing Co.: Chelsea Publishing Co. New York, Translated and edited by Richard A. Silverman · Zbl 0357.30002 |
| [30] | Saad, Y., Iterative Methods for Sparse Linear Systems (2003), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia, PA · Zbl 1002.65042 |
| [31] | Trefethen, L. N.; Weideman, J., The exponentially convergent trapezoidal rule, SIAM Rev., 56, 3, 385-458 (2014) · Zbl 1307.65031 |
| [32] | Vandebril, R.; Van Barel, M.; Mastronardi, N., Matrix Computations and Semiseparable Matrices. Linear Systems, vol. 1 (2008), Johns Hopkins University Press: Johns Hopkins University Press Baltimore, MD · Zbl 1141.65019 |
| [33] | Vandebril, R.; Van Barel, M.; Mastronardi, N., Matrix Computations and Semiseparable Matrices. Eigenvalue and Singular Value Methods, vol. 2 (2008), Johns Hopkins University Press: Johns Hopkins University Press Baltimore, MD · Zbl 1175.65045 |
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.
