# 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
##### Keywords:
matrix functional; extrapolation; moment matching
##### Software:
mctoolbox; mftoolbox; Regularization tools; SuiteSparse
Full Text:
##### References:
  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  Golub, G. H.; Meurant, G., Matrices, Moments and Quadrature with Applications (2010), Princeton University Press: Princeton University Press Princeton · Zbl 1217.65056  Arrigo, F.; Benzi, M., Updating and downdating techniques for optimizing network communicability, SIAM J. Sci. Comput., 38, B25-B49 (2016) · Zbl 1328.05174  Benzi, M.; Klymko, C., Total communicability as a centrality measure, J. Complex Netw., 1, 124-149 (2013)  Estrada, E.; Higham, D. J., Network properties revealed through matrix functions, SIAM Rev., 52, 4, 696-714 (2010) · Zbl 1214.05077  Higham, N. J., Functions of Matrices: Theory and Computation (2008), SIAM: SIAM Philadelphia, USA · Zbl 1167.15001  Alqahtani, H.; Reichel, L., Simplified anti-Gauss quadrature rules with applications in linear algebra, Numer. Algorithms, 77, 577-602 (2018) · Zbl 1390.41036  Alqahtani, H.; Reichel, L., Multiple orthogonal polynomials applied to matrix function evaluation, BIT, 58, 835-849 (2018) · Zbl 06989580  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  Brezinski, C., Error estimates for the solution of linear systems, SIAM J. Sci. Comput., 21, 764-781 (1999) · Zbl 0944.65050  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  Datta, B. N., Numerical Linear Algebra and Applications (2010), SIAM: SIAM Philadelphia  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  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  Wilkinson, J. H., Rounding Errors in Algebraic Processes (1963) · Zbl 1041.65502  Higham, N. J., Accuracy and Stability of Numerical Algorithms (1996), SIAM: SIAM Philadelphia, USA · Zbl 0847.65010  Fan, J.; Liao, Y.; Liu, H., An overview on the estimation of large covariance and precision matrices, Econom. J., 19, C1-C32 (2016)  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  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  Bekas, C.; Curioni, A.; Fedulova, I., Low-cost data uncertainty quantification, Concurr. Comput.: Pract. Exp., 24, 8, 908-920 (2012)  Craven, P.; Wahba, G., Smoothing noisy data with spline functions, Numer. Math., 31, 377-403 (1979) · Zbl 0377.65007  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  Hansen, P. C., Regularization tools version 4.0 for MATLAB 7.3, Numer. Algorithms, 46, 189-194 (2007) · Zbl 1128.65029  Benzi, M.; Boito, P., Quadrature rule-based bounds for functions of adjacency matrices, Linear Algebra Appl., 433, 637-652 (2010) · Zbl 1191.65046  Estrada, E.; Rodríguez-Velázquez, J. A., Subgraph centrality in complex networks, Phys. Rev. E, 71, Article 056103 pp. (2005)  Benzi, M.; Estrada, E.; Klymko, C., Ranking hubs and authorities using matrix functions, Linear Algebra Appl., 438, 2447-2474 (2013) · Zbl 1258.05067  Arrigo, F.; Benzi, M.; Fenu, C., Computation of generalized matrix functions, SIAM J. Matrix Anal. Appl., 37, 836-860 (2016) · Zbl 1342.65121  The SuiteSparse Matrix Collection, https://sparse.tamu.edu/.  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  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  T. Davis, Y. Hu, The SuiteSparse Matrix Collection, https://sparse.tamu.edu/.  The MATLAB gallery, http://www.mathworks.com/help/matlab/ref/gallery.html.  A. Taylor, D.J. Higham, CONTEST: toolbox files and documentation, http://www.mathstat.strath.ac.uk/research/groups/numerical_analysis/contest/toolbox.  Hawkins, J. B.; Ben-Israel, A., On generalized matrix functions, Linear Multilinear Algebra, 1, 163-171 (1973) · Zbl 0291.15004  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.