×

zbMATH — the first resource for mathematics

The e-MoM approach for approximating matrix functionals. (English) Zbl 1440.65048
The problem is to evaluate \(X^Tf(A)Y\) for \(A\) being a diagonalizable matrix and \(X\) and \(Y\) block vectors. If \(A=\sum_k \lambda_k p_k q_k^T\) is the eigenvalue decomposition, then the problem is reduced to evaluate many sums of the form \(\sum_k f(\lambda_k) \alpha_k\beta_k\) with \(\alpha_k=x^Tp_k\) and \(\beta_k=q_k^Ty\).
The e-MoM of the title stands for extrapolated Method of Moments. That means that \(f(x)\) is approximated by the initial terms of its power series expansion. Using moment matching and extrapolation, one gets relatively good approximations without having to compute the full eigenvalue decomposition. This idea was used for Hermitian matrices by P. Fika and M. Mitrouli [Linear Algebra Appl. 502, 140–158 (2016; Zbl 1336.65068)] for one or two-term estimates.
Here the method is re-derived for non-Hermitian \(A\) and also the formulas for a three-term estimate are added. A Wilkinson-type backward error analysis for each step in the computational procedure is performed. This allows to show that for certain classes one-term estimates are stable and advise whether or not to move to more term estimates can be given. Extensive numerical tests illustrate that for some classes of matrices the method is more stable and more efficient than alternative methods such as those based on the polarization identity or on quadrature formulas.
MSC:
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
65B05 Extrapolation to the limit, deferred corrections
15A18 Eigenvalues, singular values, and eigenvectors
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Fenu, C.; Reichel, L.; Rodriguez, G., GCV For tikhonov regularization via global Golub-Kahan decomposition, Numer. Linear Algebra Appl., 23, 467-484 (2016) · Zbl 1374.65064
[2] Golub, G. H.; Meurant, G., Matrices, Moments and Quadrature with Applications (2010), Princeton University Press: Princeton University Press Princeton · Zbl 1217.65056
[3] Arrigo, F.; Benzi, M., Updating and downdating techniques for optimizing network communicability, SIAM J. Sci. Comput., 38, B25-B49 (2016) · Zbl 1328.05174
[4] Benzi, M.; Klymko, C., Total communicability as a centrality measure, J. Complex Netw., 1, 124-149 (2013)
[5] Estrada, E.; Higham, D. J., Network properties revealed through matrix functions, SIAM Rev., 52, 4, 696-714 (2010) · Zbl 1214.05077
[6] Higham, N. J., Functions of Matrices: Theory and Computation (2008), SIAM: SIAM Philadelphia, USA · Zbl 1167.15001
[7] Alqahtani, H.; Reichel, L., Simplified anti-Gauss quadrature rules with applications in linear algebra, Numer. Algorithms, 77, 577-602 (2018) · Zbl 1390.41036
[8] Alqahtani, H.; Reichel, L., Multiple orthogonal polynomials applied to matrix function evaluation, BIT, 58, 835-849 (2018) · Zbl 06989580
[9] Bellalij, M.; Reichel, L.; Rodriguez, G.; Sadok, H., Bounding matrix functionals via partial global block lanczos decomposition, Appl. Numer. Math., 94, 127-139 (2015) · Zbl 1325.65060
[10] Brezinski, C., Error estimates for the solution of linear systems, SIAM J. Sci. Comput., 21, 764-781 (1999) · Zbl 0944.65050
[11] Fika, P.; Mitrouli, M., Estimation of the bilinear form \(y^\ast f ( A ) x\) for hermitian matrices, Linear Algebra Appl., 502, 140-158 (2016) · Zbl 1336.65068
[12] Datta, B. N., Numerical Linear Algebra and Applications (2010), SIAM: SIAM Philadelphia
[13] Fika, P.; Mitrouli, M., Fast estimates for the diagonal of the inverse of large scale matrices appearing in applications, J. Comput. Appl. Math., 355, 91-105 (2019) · Zbl 1433.65039
[14] Fika, P.; Mitrouli, M.; Roupa, P., Estimates for the bilinear form \(x^T A^{- 1} y\) with applications to linear algebra problems, Electron. Trans. Numer. Anal., 43, 70-89 (2014) · Zbl 1302.65100
[15] Wilkinson, J. H., Rounding Errors in Algebraic Processes (1963) · Zbl 1041.65502
[16] Higham, N. J., Accuracy and Stability of Numerical Algorithms (1996), SIAM: SIAM Philadelphia, USA · Zbl 0847.65010
[17] Fan, J.; Liao, Y.; Liu, H., An overview on the estimation of large covariance and precision matrices, Econom. J., 19, C1-C32 (2016)
[18] Kalantzis, V.; Bekas, C.; Curioni, A.; Gallopoulos, E., Accelerating data uncertainty quantification by solving linear systems with multiple right-hand sides, Numer. Algorithms, 62, 637-653 (2013) · Zbl 1263.65009
[19] Tang, J.; Saad, Y., A probing method for computing the diagonal of a matrix inverse, Numer. Linear Algebra Appl., 19, 485-501 (2012) · Zbl 1274.65132
[20] Bekas, C.; Curioni, A.; Fedulova, I., Low-cost data uncertainty quantification, Concurr. Comput.: Pract. Exp., 24, 8, 908-920 (2012)
[21] Craven, P.; Wahba, G., Smoothing noisy data with spline functions, Numer. Math., 31, 377-403 (1979) · Zbl 0377.65007
[22] Mitrouli, M.; Roupa, P., Estimates for the generalized cross-validation function via an extrapolation and statistical approach, Calcolo, 55, 1-25 (2018) · Zbl 1448.65029
[23] Hansen, P. C., Regularization tools version 4.0 for MATLAB 7.3, Numer. Algorithms, 46, 189-194 (2007) · Zbl 1128.65029
[24] Benzi, M.; Boito, P., Quadrature rule-based bounds for functions of adjacency matrices, Linear Algebra Appl., 433, 637-652 (2010) · Zbl 1191.65046
[25] Estrada, E.; Rodríguez-Velázquez, J. A., Subgraph centrality in complex networks, Phys. Rev. E, 71, Article 056103 pp. (2005)
[26] Benzi, M.; Estrada, E.; Klymko, C., Ranking hubs and authorities using matrix functions, Linear Algebra Appl., 438, 2447-2474 (2013) · Zbl 1258.05067
[27] Arrigo, F.; Benzi, M.; Fenu, C., Computation of generalized matrix functions, SIAM J. Matrix Anal. Appl., 37, 836-860 (2016) · Zbl 1342.65121
[28] The SuiteSparse Matrix Collection, https://sparse.tamu.edu/.
[29] Baglama, J.; Fenu, C.; Reichel, L.; Rodriguez, G., Analysis of directed networks via partial singular value decomposition and Gauss quadrature, Linear Algebra Appl., 456, 93-121 (2014) · Zbl 1295.05216
[30] Reichel, L.; Rodriguez, G.; Tang, T., New block quadrature rules for the approximation of matrix functions, Linear Algebra Appl., 502, 299-326 (2016) · Zbl 1338.65122
[31] T. Davis, Y. Hu, The SuiteSparse Matrix Collection, https://sparse.tamu.edu/.
[32] The MATLAB gallery, http://www.mathworks.com/help/matlab/ref/gallery.html.
[33] A. Taylor, D.J. Higham, CONTEST: toolbox files and documentation, http://www.mathstat.strath.ac.uk/research/groups/numerical_analysis/contest/toolbox.
[34] Hawkins, J. B.; Ben-Israel, A., On generalized matrix functions, Linear Multilinear Algebra, 1, 163-171 (1973) · Zbl 0291.15004
[35] Arrigo, F.; Benzi, M., Edge modification criteria for enhancing the communicability of digraphs, SIAM J. Matrix Anal. Appl., 37, 443-468 (2016) · Zbl 1336.05120
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.