zbMATH — the first resource for mathematics

An estimator for the diagonal of a matrix. (English) Zbl 1123.65026
Summary: A number of applications require to compute an approximation of the diagonal of a matrix when this matrix is not explicitly available but matrix-vector products with it are easy to evaluate. In some cases, it is the trace of the matrix rather than the diagonal that is needed. This paper describes methods for estimating diagonals and traces of matrices in these situations. The goal is to obtain a good estimate of the diagonal by applying only a small number of matrix-vector products, using selected vectors.
We begin by considering the use of random test vectors and then explore special vectors obtained from Hadamard matrices. The methods are tested in the context of computational materials science to estimate the diagonal of the density matrix which holds the charge densities. Numerical experiments indicate that the diagonal estimator may offer an alternative method that in some cases can greatly reduce computational costs in electronic structures calculations.

65F30 Other matrix algorithms (MSC2010)
15A15 Determinants, permanents, traces, other special matrix functions
Full Text: DOI
[1] Cheney, C.C., Introduction to approximation theory, (1966), McGraw-Hill New York · Zbl 0161.25202
[2] Coleman, T.F.; Moré, J.J., Estimation of sparse Jacobian matrices and graph coloring problems, SIAM J. numer. anal., 20, 1, 187-209, (1983) · Zbl 0527.65033
[3] Conway, J.H.; Hardin, R.H.; Sloane, N.J.A., Packing lines, planes etc.: packings in Grassmannian spaces, Exper. math., 5, 2, 139-159, (1996) · Zbl 0864.51012
[4] Curtis, A.R.; Powel, M.J.D.; Reid, J.K., On the estimation of sparse Jacobian matrices, J. inst. math. appl., 13, 117-119, (1974) · Zbl 0273.65036
[5] D. Girard, Un algorithme simple et rapide pour la validation croisée généralisée sur des problèmes de grande taille, RR 669-M, Grenoble, France: Informatique et Mathématiques Appliquées de Grenoble, 1987
[6] Goedecker, S., Linear scaling electronic structure methods, Rev. modern phys., 71, 1085-1123, (1999)
[7] Goedecker, S.; Teter, M., Tight-binding electronic-structure calculations and tight-binding molecular dynamics with localized orbitals, Phys. rev. B, 51, 19455, (1995)
[8] Golub, G.H.; Heath, M.; Wahba, G., Generalized cross-validation as a method for choosing a good ridge parameter, Technometrics, 21, 215-223, (1979) · Zbl 0461.62059
[9] Golub, G.H.; von Matt, U., Generalized cross-validation for large scale problems, J. comput. graph. statist., 6, 1, 1-34, (1997)
[10] Hutchinson, M.F., A stochastic estimator of the trace of the influence matrix for Laplacian smoothing splines, J. commun. statist. simul., 19, 2, 433-450, (1990) · Zbl 0718.62058
[11] Jackson, D., The theory of approximation, Amer. math. soc. colloq. publ., vol. XI, (1930), Amer. Math. Soc. Providence, RI · JFM 56.0936.01
[12] Jay, L.O.; Kim, H.; Saad, Y.; Chelikowsky, J.R., Electronic structure calculations in plane-wave codes without diagonalization, Comput. phys. comm., 118, 21-30, (1998) · Zbl 1001.65038
[13] Parket, G.A.; Zhu, W.; Huang, Y.; Hoffman, D.K.; Kouri, D.J., Matrix pseudo-spectroscopy: iterative calculation of matrix eigenvalues and eigenvectors of large matrices using a polynomial expansion of the Dirac delta function, Comput. phys. comm., 96, 27-35, (1996) · Zbl 0921.65029
[14] Rivlin, T.J., An introduction to the approximation of functions, (1969), Dover New York · Zbl 0189.06601
[15] Sarwate, D.V., Meeting the welch bound with equality, (1999), Springer Berlin, pp. 79-102 · Zbl 1013.94510
[16] Silver, R.N.; Roeder, H.; Voter, A.F.; Kress, J.D., Kernel polynomial approximations for densities and spectral functions, J. comput. phys., 124, 115-130, (1996) · Zbl 0863.65080
[17] Wallis, W.D.; Penfold Street, A.; Wallis, J.S., Combinatorics: room squares, sum-free sets, Hadamard matrices, Lecture notes in mathematics, vol. 292, (1972), Springer Berlin · Zbl 1317.05003
[18] Welch, L., Lower bounds on the maximum cross correlation of signals, IEEE trans. inform. theory, 20, 3, 397-399, (1974) · Zbl 0298.94006
[19] Wyatt, R.E., Matrix spectroscopy: computation of interior eigenstates of large matrices using layered iteration, Phys. rev. E, 51, 3643-3658, (1995)
[20] Xia, P.; Zhou, S.; Giannakis, G.B., Achieving the welch bound with difference sets, IEEE trans. inform. theory, 51, 5, 1900-1907, (2005) · Zbl 1237.94007
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.