Abstract
The subject of this work is accelerating data uncertainty quantification. In particular, we are interested in expediting the stochastic estimation of the diagonal of the inverse covariance (precision) matrix that holds a wealth of information concerning the quality of data collections, especially when the matrices are symmetric positive definite and dense. Schemes built on direct methods incur a prohibitive cubic cost. Recently proposed iterative methods can remedy this but the overall cost is raised again as the convergence of stochastic estimators can be slow. The motivation behind our approach stems from the fact that the computational bottleneck in stochastic estimation is the application of the precision matrix on a set of appropriately selected vectors. The proposed method combines block conjugate gradient with a block-seed approach for multiple right-hand sides, taking advantage of the nature of the right-hand sides and the fact that the diagonal is not sought to high accuracy. Our method is applicable if the matrix is only known implicitly and also produces a matrix-free diagonal preconditioner that can be applied to further accelerate the method. Numerical experiments confirm that the approach is promising and helps contain the overall cost of diagonal estimation as the number of samples grows.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Abdel-Rehim, A.M., Morgan, R.B., Nicely, D.A., Wilcox, W.: Deflated and restarted symmetric Lanczos methods for eigenvalues and linear equations with multiple right-hand sides. SIAM J. Sci. Comput. 32, 129–149 (2010)
Abdel-Rehim, A.M., Morgan, R.B., Wilcox, W.: Improved seed methods for symmetric positive definite linear equations with multiple right-hand sides (2008). http://arxiv.org/abs/0810.0330 [math-ph]
Anitescu, M., Chen, J., Wang, L.: A matrix-free approach for solving the Gaussian process maximum likelihood problem. SIAM J. Sci. Comput. 34(1), A240–A262 (2012)
Avron, H., Toledo, S.: Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix. J. ACM 58(2), 8 (2011)
Bai, Z., Fahey, M., Golub, G.: Some large-scale matrix computation problems. J. Comput. Appl. Math. 74, 71–89 (1996)
Bai, Z., Golub, G.H.: Bounds for the trace of the inverse and the determinant of symmetric positive definite matrices. Ann. Numer. Math. 4, 29–38 (1997)
Bekas, C., Curioni, A., Fedulova, I.: Low cost high perf. uncertainty quantification. In: Worskhop on High Performance Computational Finance, Supercomputing’09, Portland. Portland, Oregon (2009)
Bekas, C., Curioni, A., Fedulova, I.: Low-cost data uncertainty quantification. Concurr. Comput.: Practice and Experience 24(8), 908–920 (2012)
Bekas, C., Kokiopoulou, E., Saad, Y.: An estimator for the diagonal of a matrix. Appl. Numer. Math. 57, 1214–1229 (2007)
Bekas, C., Kokiopoulou, E., Saad, Y.: Computation of large invariant subspaces using polynomial filtered Lanczos iterations with applications in density functional theory. SIAM J. Matrix Anal. Appl. 30, 397–418 (2008)
Bouyouli, R., Jbilou, K., Sadaka, R., Sadok, H.: Convergence properties of some block Krylov subspace methods for multiple linear systems. J. Comput. Appl. Math. 196(2), 498–511 (2006)
Brezinski, C., Fika, P., Mitrouli, M.: Moments of a linear operator, with applications to the trace of the inverse of matrices and the solution of equations. Numer. Linear Algebra Appl. (2011)
Cao, G., Bachega, L.R., Bouman, C.A.: The sparse matrix transform for covariance estimation and analysis of high dimensional signals. IEEE Trans. Image Process 20, 625–640 (2011)
Chan, T.F., Wan, W.L.: Analysis of projection methods for solving linear systems with multiple right-hand sides. SIAM J. Sci. Statist. Comput 18(6), 1698–1721 (1997)
Chen, J.: A deflated version of the block conjugate gradient algorithm with an application to Gaussian process maximum likelihood estimation. Argonne National Laboratory (2011, Preprint). ANL/MCS-P1927-0811
Du, L., Sogabe, T., Yu, B., Yamamoto, Y., Zhang, S.L.: A block IDR(s) method for nonsymmetric linear systems with multiple right-hand sides. J. Comput. Appl. Math. 235(14), 4095–4106 (2011)
Giraud, L., Ruiz, D., Touhami, A.: A comparative study of iterative solvers exploiting spectral information for spd systems. SIAM J. Sci. Comput. 27(5), 1760–1786 (2006)
Golub, G.H., Meurant, G.: Matrices, Moments and Quadrature with Applications. Princeton University Press (2010)
Golub, G.H., Ruiz, D., Touhami, A.: A hybrid approach combining Chebyshev filter and conjugate gradient for solving linear systems with multiple right-hand sides. SIAM J. Matrix Anal. Appl. 29, 774–795 (2007)
Gutknecht, M.: Block Krylov space methods for linear systems with multiple right-hand sides: an introduction. In: Siddiqi, A.H., Duff, I.S., Christensen, O. (eds.) Modern Mathematical Models, Methods and Algorithms for Real World Systems, pp. 420–447. Anamaya Publishers, New Delhi (2007)
Hartlap, J., Simon, P., Schneider, P.: Why your model parameter confidences might be too optimistic—unbiased estimation of the inverse covariance matrix. Astron. Astrophys 464, 399–404 (2007)
Hutchinson, .M.: A stochastic estimator for the trace of the influence matrix for Laplacian smoothing splines. Commun. Stat. Simul. Comput. 18, 1059–1076 (1989)
Kilmer, M., Miller, E., Rappaport, C.: QMR-based projection techniques for the solution of non-Hermitian systems with multiple right-hand sides. SIAM J. Sci. Comput. 23(3), 761–780 (2001)
Ledoit, O., Wolf, M.: A well-conditioned estimator for large-dimensional covariance matrices. J. Multivar. Anal. 88, 365–411 (2004)
Lin, L., Yang, C., Meza, J.C., Lu, J., Ying, L., Weinan, E.: SelInv—an algorithm for selected inversion of a sparse symmetric matrix. ACM Trans. Math. Softw. 7(4), 40:1–40:19 (2011)
Meurant, G.: Estimates of the trace of the inverse of a symmetric matrix using the modified Chebyshev algorithm. Numer. Algor. 51, 309–318 (2009)
O’Leary, D.P.: The block conjugate gradient algorithm and related methods. Linear Algebra Appl. 29, 293–322 (1980)
Oliver, D.S.: Calculation of the inverse of the covariance. Math. Geol. 30(7), 911–933 (1998)
Parks, M.L., de, S.turler., E., Mackey, G., Johnson, D.D., Maiti, S.: Recycling Krylov subspaces for sequences of linear systems. SIAM J. Sci. Comput. 28(5), 1651–1674 (2006)
Parlett, B.N.: A new look at the Lanczos algorithm for solving symmetric systems of linear equations. Linear Algebra Appl. 29, 323–346 (1980)
Saad, Y.: On the Lanczos method for solving symmetric systems with several right hand sides. Math. Comput. 48, 651–662 (1987)
Simoncini, V., Gallopoulos, E.: An iterative method for nonsymmetric systems with multiple right-hand sides. SIAM J. Sci. Comput. 16(4), 917–933 (1995)
Smith, C.F., Peterson, A.F., Mittra, R.: A conjugate gradient algorithm for the treatment of multiple incident electromagnetic fields. IEEE Trans. Antennas Propag. 37, 1490–1493 (1989)
Stathopoulos, A., Orginos, K.: Computing and deflating eigenvalues while solving multiple right-hand hide linear systems with an application to quantum chromodynamics. SIAM J. Sci. Comput 32, 439–462 (2010)
Stevens, G.V.G.: On the inverse of the covariance matrix in portfolio analysis. J. Finance 53, 1821–1827 (1998)
Tang, J.M., Saad, Y.: A probing method for computing the diagonal of a matrix inverse. Numer. Linear Algebra Appl. 19(3), 485–501 (2012)
Visweswariah, K., Olsen, P., Gopinath, R., Axelrod, S.: Maximum likelihood training of subspaces for inverse covariance modeling. In: Proc. ICASSP, vol. 1, pp. 848–851 (2003)
Author information
Authors and Affiliations
Corresponding author
Additional information
Dedicated to Professor Claude Brezinski.
Rights and permissions
About this article
Cite this article
Kalantzis, V., Bekas, C., Curioni, A. et al. Accelerating data uncertainty quantification by solving linear systems with multiple right-hand sides. Numer Algor 62, 637–653 (2013). https://doi.org/10.1007/s11075-012-9687-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11075-012-9687-2