Stable Computation of Generalized Matrix Functions via Polynomial Interpolation
Authors: 
Jared L. Aurentz, Anthony P. Austin, Michele Benzi, Vassilis KalantzisAuthors Info & Claims
Pages 210 - 234
Abstract
Generalized matrix functions (GMFs) extend the concept of a matrix function to rectangular matrices via the singular value decomposition. Several applications involving directed graphs, Hamiltonian dynamical systems, and optimization problems with low-rank constraints require the action of a GMF of a large, sparse matrix on a vector. We present a new method for applying GMFs to vectors based on Chebyshev interpolation. The method is matrix free and requires no orthogonalization and minimal additional storage. Comparisons against existing approaches based on Lanczos bidiagonalization demonstrate the competitiveness of our approach. We prove that our method is backward stable by generalizing the proof of the backward stability of Clenshaw's algorithm to the matrix case.
References
[1]
F. Andersson, M. Carlsson, and K.-M. Perfekt, Operator-Lipschitz estimates for the singular value functional calculus, Proc. Amer. Math. Soc., 144 (2016), pp. 1867--1875, https://doi.org/10.1090/proc/12843.
[2]
F. Andersson, M. Carlsson, J.-Y. Tourneret, and H. Wendt, A new frequency estimation method for equally and unequally spaced data, IEEE Trans. Signal Process., 62 (2014), pp. 5761--5774, https://doi.org/10.1109/TSP.2014.2358961.
[3]
F. Arrigo and M. Benzi, Edge modification criteria for enhancing the communicability of digraphs, SIAM J. Matrix Anal. Appl., 37 (2016), pp. 443--468, https://doi.org/10.1137/15M1034131.
[4]
F. Arrigo, M. Benzi, and C. Fenu, Computation of generalized matrix functions, SIAM J. Matrix Anal. Appl., 37 (2016), pp. 836--860, https://doi.org/10.1137/15M1049634.
[5]
J. L. Aurentz, GPU Accelerated Polynomial Spectral Transformation Methods, Ph.D. thesis, Washington State University, 2014, https://doi.org/2376/5177.
[6]
J. L. Aurentz, V. Kalantzis, and Y. Saad, Cucheb: A GPU implementation of the filtered Lanczos procedure, Comput. Phys. Commun., 220 (2017), pp. 332--340, https://doi.org/10.1016/j.cpc.2017.06.016.
[7]
J. Baglama and L. Reichel, Restarted block Lanczos bidiagonalization methods, Numer. Algorithms, 43 (2006), pp. 251--272, https://doi.org/10.1007/s11075-006-9057-z.
[8]
M. Benzi, D. A. Bini, D. Kressner, H. Munthe-Kaas, and C. Van Loan, Exploiting Hidden Structure in Matrix Computations: Algorithms and Applications, Lecture Notes in Math. 2173, Springer, New York, 2016.
[9]
M. Benzi, E. Estrada, and C. Klymko, Ranking hubs and authorities using matrix functions, Linear Algebra Appl., 438 (2013), pp. 2447--2474, https://doi.org/10.1016/j.laa.2012.10.022.
[10]
G. Berkolaiko and P. Kuchment, Introduction to Quantum Graphs, AMS, Providence, RI, 2013.
[11]
C. W. Clenshaw, A note on the summation of Chebyshev series, Math. Comp., 9 (1955), pp. 118--120, https://doi.org/10.1090/S0025-5718-1955-0071856-0.
[12]
J. J. Crofts, E. Estrada, D. J. Higham, and A. Taylor, Mapping directed networks, Electron. Trans. Numer. Anal., 37 (2010), pp. 337--350.
[13]
T. A. Davis and Y. Hu, The University of Florida sparse matrix collection, ACM Trans. Math. Soft., 38 (2011), pp. 1:1--1:25, https://doi.org/10.1145/2049662.2049663.
[14]
N. Del Buono, L. Lopez, and R. Peluso, Computation of the exponential of large sparse skew-symmetric matrices, SIAM J. Sci. Comput., 27 (2005), pp. 278--293, https://doi.org/10.1137/030600758.
[15]
N. Del Buono, L. Lopez, and T. Politi, Computation of functions of Hamiltonian and skew-symmetric matrices, Math. Comput. Simulation, 79 (2008), pp. 1284--1297, https://doi.org/10.1016/j.matcom.2008.03.011.
[16]
T. A. Driscoll, N. Hale, and L. N. Trefethen, eds., Chebfun Guide, Pafnuty Publications, Oxford, 2014.
[17]
V. L. Druskin and L. A. Knizhnerman, Two polynomial methods of calculating functions of symmetric matrices, U.S.S.R. Comput. Math. and Math. Phys., 29 (1989), pp. 112--121, https://doi.org/10.1016/S0041-5553(89)80020-5.
[18]
H.-R. Fang and Y. Saad, A filtered Lanczos procedure for extreme and interior eigenvalue problems, SIAM J. Sci. Comput., 34 (2012), pp. A2220--A2246, https://doi.org/10.1137/110836535.
[19]
F. R. Gantmacher, The Theory of Matrices. Vol. 1, AMS Chelsea Publishing, Providence, RI, 2000.
[20]
G. H. Golub and C. F. Van Loan, Matrix Computations, 4th ed., Johns Hopkins University Press, Baltimore, MD, 2013.
[21]
M. Hanke, J. Nagy, and R. Plemmons, Preconditioned iterative regularization for ill-posed problems, in Numerical Linear Algebra: Proceedings of the Conference in Numerical Linear Algebra and Scientific Computation (Kent, OH, 1992), L. Reichel, A. Ruttan, and R. S. Varga, eds., de Gruyter, Berlin, 1993, pp. 141--163.
[22]
J. B. Hawkins and A. Ben-Israel, On generalized matrix functions, Linear Multilinear Algebra, 1 (1973), pp. 163--171, https://doi.org/10.1080/03081087308817015.
[23]
N. J. Higham, Accuracy and Stability of Numerical Algorithms, 2nd ed., SIAM, Philadelphia, 2002, https://doi.org/10.1137/1.9780898718027.
[24]
N. J. Higham, Functions of Matrices: Theory and Computation, SIAM, Philadelphia, 2008, https://doi.org/10.1137/1.9780898717778.
[25]
L. Katz, A new status index derived from sociometric analysis, Psychometrika, 18 (1953), pp. 39--43, https://doi.org/10.1007/BF02289026.
[26]
J. C. Mason and D. C. Handscomb, Chebyshev Polynomials, CRC Press, Boca Raton, FL, 2003.
[27]
D. Mugnolo, Semigroup Methods for Evolution Equations on Networks, Springer, Cham, 2014.
[28]
V. Noferini, A formula for the Fréchet derivative of a generalized matrix function, SIAM J. Matrix Anal. Appl., 38 (2017), pp. 434--457, https://doi.org/10.1137/16m1072851.
[29]
H. D. Simon and H. Zha, Low-rank matrix approximation using the Lanczos bidiagonalization process with applications, SIAM J. Sci. Comput., 21 (2000), pp. 2257--2274, https://doi.org/10.1137/s1064827597327309.
[30]
A. Smoktunowicz, Backward stability of Clenshaw's algorithm, BIT, 42 (2002), pp. 600--610, https://doi.org/10.1023/A:1022001931526.
[31]
L. N. Trefethen, Approximation Theory and Approximation Practice, SIAM, Philadelphia, 2013.
[32]
Y. Zhou and R.-C. Li, Bounding the spectrum of large Hermitian matrices, Linear Algebra Appl., 435 (2011), pp. 480--493, https://doi.org/10.1016/j.laa.2010.06.034.
Recommendations
Computation of Generalized Matrix Functions
We develop numerical algorithms for the efficient evaluation of quantities associated with generalized matrix functions [J. B. Hawkins and A. Ben-Israel, Linear Multilinear Algebra, 1 (1973), pp. 163--171]. Our algorithms are based on Gaussian quadrature and ...
Low-Rank Updates of Matrix Functions II: Rational Krylov Methods
This work develops novel rational Krylov methods for updating a large-scale matrix function $f(A)$ when $A$ is subject to low-rank modifications. It extends our previous work in this context on polynomial Krylov methods, for which we present a simplified ...
A Formula for the Fréchet Derivative of a Generalized Matrix Function
We state and prove an analogue of the Daleckii--Krein theorem, thus obtaining an explicit formula for the Fréchet derivative of generalized matrix functions. Moreover, we prove the differentiability of generalized matrix functions of real matrices under ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© 2019, Society for Industrial and Applied Mathematics.
Publisher
Society for Industrial and Applied Mathematics
United States
Publication History
Published: 01 January 2019
Author Tags
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 20 Feb 2025