×

Computing the weighted geometric mean of two large-scale matrices and its inverse times a vector. (English) Zbl 1383.65042

Summary: We investigate different approaches for computing the action of the weighted geometric mean of two large-scale positive definite matrices on a vector. We derive and analyze several algorithms, based on numerical quadrature and on the Krylov subspace, and compare them in terms of convergence speed and execution time. By exploiting an algebraic relation between the weighted geometric mean and its inverse, we show how these methods can be used to efficiently solve large linear systems whose coefficient matrix is a weighted geometric mean. According to our experiments, some of the algorithms proposed in both families are suitable choices for black-box implementations.

MSC:

65F60 Numerical computation of matrix exponential and similar matrix functions
47A64 Operator means involving linear operators, shorted linear operators, etc.
47A56 Functions whose values are linear operators (operator- and matrix-valued functions, etc., including analytic and meromorphic ones)
65F10 Iterative numerical methods for linear systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] M. Abramowitz and I. Stegun, {\it Handbook of Mathematical Functions}, 10th ed., Dover, New York, 1972. · Zbl 0543.33001
[2] T. Ando, {\it Concavity of certain maps on positive definite matrices and applications to Hadamard products}, Linear Algebra Appl., 26 (1979), pp. 203-241, . · Zbl 0495.15018
[3] T. Ando, C.-K. Li, and R. Mathias, {\it Geometric means}, Linear Algebra Appl., 385 (2004), pp. 305-334, . · Zbl 1063.47013
[4] M. Arioli, D. Kourounis, and D. Loghin, {\it Discrete fractional Sobolev norms for domain decomposition preconditioning}, IMA J. Numer. Anal., 33 (2011), pp. 318-342, . · Zbl 1261.65127
[5] M. Arioli and D. Loghin, {\it Discrete interpolation norms with applications}, SIAM J. Numer. Anal., 47 (2009), pp. 2924-2951, . · Zbl 1196.65080
[6] M. Arioli and D. Loghin, {\it Spectral analysis of the anisotropic Steklov-Poincaré matrix}, Linear Algebra Appl., 488 (2016), pp. 168-183, . · Zbl 1327.65260
[7] M. Berljafa and S. Güttel, {\it A Rational Krylov Toolbox for MATLAB}, MIMS EPrint 2014.56, Manchester Institute for Mathematical Sciences, University of Manchester, UK, 2014, .
[8] M. Berljafa and S. Güttel, {\it Generalized rational Krylov decompositions with an application to rational approximation}, SIAM J. Matrix Anal. Appl., 36 (2015), pp. 894-916, . · Zbl 1319.65028
[9] M. Berljafa and S. Güttel, {\it The RKFIT algorithm for nonlinear rational approximation}, SIAM J. Sci. Comput., 39 (2017), pp. A2049-A2071, . · Zbl 1373.65037
[10] R. Bhatia, {\it Matrix Analysis}, Grad. Texts in Math. 169, Springer, New York, 1997, .
[11] R. Bhatia, {\it Positive Definite Matrices}, Princeton Ser. Appl. Math., Princeton University Press, Princeton, NJ, 2007. · Zbl 1133.15017
[12] R. Bhatia, {\it The Riemannian mean of positive matrices}, in Matrix Information Geometry, F. Nielsen, R. Bhatia, eds., Springer, Berlin, Heidelberg, 2013, pp. 35-51. · Zbl 1271.15019
[13] D. Bini and B. Iannazzo, {\it The Matrix Means Toolbox}, . · Zbl 1293.65068
[14] J. R. Cardoso, {\it Computation of the matrix p-th root and its Fréchet derivative by integrals}, Electron. Trans. Numer. Anal., 39 (2012), pp. 414-436. · Zbl 1287.65035
[15] J. Castellini, {\it Krylov iterative methods for the geometric mean of two matrices times a vector}, Numer. Algorithms, 74 (2017), pp. 561-571, . · Zbl 1358.65025
[16] T. A. Davis and Y. Hu, {\it The University of Florida sparse matrix collection}, ACM Trans. Math. Softw., 38 (2011), pp. 1:1-1:25, . · Zbl 1365.65123
[17] T. A. Driscoll, {\it Algorithm 756: A MATLAB toolbox for Schwarz-Christoffel mapping}, ACM Trans. Math. Softw., 22 (1996), pp. 168-186, . · Zbl 0884.30005
[18] T. A. Driscoll, {\it Algorithm 843: Improvements to the Schwarz-Christoffel toolbox for MATLAB}, ACM Trans. Math. Softw., 31 (2005), pp. 239-251, . · Zbl 1070.30500
[19] T. A. Driscoll, N. Hale, and L. N. Trefethen, {\it Chebfun Guide}, Pafnuty Publications, Oxford, UK, 2014, .
[20] T. A. Driscoll and L. N. Trefethen, {\it Schwarz-Christoffel Mapping}, Cambridge Monogr. Appl. Comput. Math., Cambridge University Press, Cambridge, UK, 2002. · Zbl 1003.30005
[21] V. Druskin and L. Knizhnerman, {\it Extended Krylov subspaces: Approximation of the matrix square root and related functions}, SIAM J. Matrix Anal. Appl., 19 (1998), pp. 755-771, . · Zbl 0912.65022
[22] C. Estatico and F. Di Benedetto, {\it Shift-invariant approximations of structured shift-variant blurring matrices}, Numer. Algorithms, 62 (2013), pp. 615-635, . · Zbl 1263.65021
[23] A. Frommer, S. Güttel, and M. Schweitzer, {\it Efficient and stable Arnoldi restarts for matrix functions based on quadrature}, SIAM J. Matrix Anal. Appl., 35 (2014), pp. 661-683, . · Zbl 1309.65050
[24] A. Frommer and V. Simoncini, {\it Matrix Functions}, in Model Order Reduction: Theory, Research Aspects and Applications, Math. Ind. 13, Springer, Berlin, Heidelberg, 2008, pp. 275-303, . · Zbl 1153.65333
[25] W. Gautschi, {\it A Survey of Gauss-Christoffel Quadrature Formulae}, in E. B. Christoffel: The Influence of His Work on Mathematics and the Physical Sciences, Birkhäuser, Basel, 1981, pp. 72-147.
[26] L. Giraud and J. Langou, {\it When modified Gram-Schmidt generates a well-conditioned set of vectors}, IMA J. Numer. Anal., 22 (2002), pp. 521-528, . · Zbl 1027.65050
[27] G. H. Golub and C. F. Van Loan, {\it Matrix Computations}, 4th ed., Johns Hopkins University Press, Baltimore, 2013. · Zbl 1268.65037
[28] S. Güttel and L. Knizhnerman, {\it Automated parameter selection for rational Arnoldi approximation of Markov functions}, PAMM, 11 (2011), pp. 15-18, .
[29] S. Güttel and L. Knizhnerman, {\it A black-box rational Arnoldi variant for Cauchy-Stieltjes matrix functions}, BIT, 53 (2013), pp. 595-616, . · Zbl 1276.65026
[30] N. Hale, N. J. Higham, and L. N. Trefethen, {\it Computing \(a^α, \log(a)\) and related matrix functions by contour integrals}, SIAM J. Numer. Anal., 46 (2008), pp. 2505-2523, . · Zbl 1176.65053
[31] N. Hale and A. Townsend, {\it Fast and accurate computation of Gauss-Legendre and Gauss-Jacobi quadrature nodes and weights}, SIAM J. Sci. Comput., 35 (2013), pp. A652-A674, . · Zbl 1270.65017
[32] N. J. Higham, {\it Accuracy and Stability of Numerical Algorithms}, 2nd ed., SIAM, Philadelphia, 2002, . · Zbl 1011.65010
[33] N. J. Higham, {\it Functions of Matrices: Theory and Computation}, SIAM, Philadelphia, 2008. · Zbl 1167.15001
[34] N. J. Higham and L. Lin, {\it An improved Schur-Padé algorithm for fractional powers of a matrix and their Fréchet derivatives}, SIAM J. Matrix Anal. Appl., 34 (2013), pp. 1341-1360, . · Zbl 1279.65050
[35] B. Iannazzo, {\it The geometric mean of two matrices from a computational viewpoint}, Numer. Linear Algebra Appl., 23 (2015), pp. 208-229, . · Zbl 1374.65083
[36] B. Iannazzo and C. Manasse, {\it A Schur logarithmic algorithm for fractional powers of matrices}, SIAM J. Matrix Anal. Appl., 34 (2013), pp. 794––813, . · Zbl 1273.65061
[37] B. Iannazzo and B. Meini, {\it Palindromic matrix polyomials, matrix functions and integral representations}, Linear Algebra Appl., 434 (2011), pp. 174-184, . · Zbl 1211.15027
[38] C. Jagels and L. Reichel, {\it The extended Krylov subspace method and orthogonal Laurent polynomials}, Linear Algebra Appl., 431 (2009), pp. 441-458, . · Zbl 1166.65019
[39] C. Jagels and L. Reichel, {\it Recursion relations for the extended Krylov subspace method}, Linear Algebra Appl., 431 (2009), pp. 441-458, . · Zbl 1166.65019
[40] L. Knizhnerman and V. Simoncini, {\it A new investigation of the extended Krylov subspace method for matrix function evaluations}, Numer. Linear Algebra Appl., 17 (2010), pp. 615-638, . · Zbl 1240.65154
[41] J. Lawson and Y. Lim, {\it Weighted means and Karcher equations of positive operators}, Proc. Natl. Acad. Sci. USA, 110 (2013), pp. 15626-15632, . · Zbl 1310.47020
[42] J. Leskovec and A. Krevl, {\it SNAP Datasets: Stanford Large Network Dataset Collection}, (2014).
[43] S. Liu, {\it Multi-way dual cheeger constants and spectral bounds of graphs}, Adv. Math., 268 (2015), pp. 306-338, . · Zbl 1309.05122
[44] P. Mercado, F. Tudisco, and M. Hein, {\it Clustering signed networks with the geometric mean of Laplacians}, in Advances in Neural Information Processing Systems 29, D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett, eds., Curran Associates, 2016, pp. 4421-4429, .
[45] B. N. Parlett, {\it The Symmetric Eigenvalue Problem}, Classics in Appl. Math., SIAM, Philadelphia, 1998. · Zbl 0885.65039
[46] W. Pusz and S. L. Woronowicz, {\it Functional calculus for sesquilinear forms and the purification map}, Rep. Math. Phys., 8 (1975), pp. 159-170, . · Zbl 0327.46032
[47] A. Ralston and P. Rabinowitz, {\it A First Course in Numerical Analysis}, 2nd ed., Dover, New York, 1978. · Zbl 0408.65001
[48] A. Ruhe, {\it Rational Krylov sequence methods for eigenvalue computation}, Linear Algebra Appl., 58 (1984), pp. 391-405, . · Zbl 0554.65025
[49] A. Ruhe, {\it Rational Krylov algorithms for nonsymmetric eigenvalue problems. II. Matrix pairs}, Linear Algebra Appl., 197-198 (1994), pp. 283-295, . · Zbl 0810.65031
[50] A. Ruhe, {\it Rational Krylov: A practical algorithm for large sparse nonsymmetric matrix pencils}, SIAM J. Sci. Comput., 19 (1998), pp. 1535-1551, . · Zbl 0914.65036
[51] V. Simoncini, {\it A new iterative method for solving large-scale Lyapunov matrix equations}, SIAM J. Sci. Comput., 29 (2007), pp. 1268-1288, . · Zbl 1146.65038
[52] L. Trefethen and D. Bau, {\it Numerical Linear Algebra}, SIAM, Philadelphia, 1997. · Zbl 0874.65013
[53] B. von Sydow, {\it Error estimates for Gaussian quadrature formulae}, Numer. Math., 29 (1977), pp. 59-64, . · Zbl 0351.65005
[54] R. West, H. Paskov, J. Leskovec, and C. Potts, {\it Exploiting social network structure for person-to-person sentiment analysis}, Trans. Assoc. Comput. Linguist., 2 (2014), pp. 297-310, .
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.