{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:24:33Z","timestamp":1787333073751,"version":"build-2736575974"},"reference-count":28,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/100006132","name":"Office of Science","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006132","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006210","name":"Workforce Development for Teachers and Scientists","doi-asserted-by":"publisher","award":["DE-AC05-06OR23100"],"award-info":[{"award-number":["DE-AC05-06OR23100"]}],"id":[{"id":"10.13039\/100006210","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF 1218349"],"award-info":[{"award-number":["CCF 1218349"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["ACI S12-SSE 1440700"],"award-info":[{"award-number":["ACI S12-SSE 1440700"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"publisher","award":["DE-FC02-12ER41890"],"award-info":[{"award-number":["DE-FC02-12ER41890"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"publisher","award":["DE-FG02-04ER41302"],"award-info":[{"award-number":["DE-FG02-04ER41302"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"publisher","award":["DE-AC05-06OR23177"],"award-info":[{"award-number":["DE-AC05-06OR23177"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2017,1]]},"abstract":"<jats:p>Many fields require computing the trace of the inverse of a large, sparse matrix. Since dense matrix methods are not practical, the typical method used for such computations is the Hutchinson method, which is a Monte Carlo (MC) averaging over matrix quadratures. To improve its slow convergence, several variance reduction techniques have been proposed. In this paper, we study the effects of deflating the near null singular value space. We make two main contributions: one theoretical, and one by engineering a solution to a real-world application. First, we analyze the variance of the Hutchinson method as a function of the deflated singular values and vectors. By assuming additionally that the singular vectors are random unitary matrices, we arrive at concise formulas for the deflated variance that include only the variance and the mean of the singular values. In this case, we make the remarkable observation that deflation may increase variance for Hermitian matrices but not for non-Hermitian ones. The theory can be used as a model for predicting the benefits of deflation. Experimentation shows that the model is robust even when the singular vectors are not random. Second, we use deflation in the context of a large scale application of \u201cdisconnected diagrams\u201d in lattice quantum chromodynamics. On lattices, hierarchical probing (HP) has previously provided significant variance reduction over MC by removing \u201cerror\u201d from neighboring nodes of increasing distance in the lattice. Although deflation used directly on MC yields a limited improvement of 30% in our problem, when combined with HP they reduce variance by a factor of about 60 over MC. We explain this synergy theoretically and provide a thorough experimental analysis. One of the important steps of our solution is the precomputation of 1000 smallest singular values of an ill-conditioned matrix of size 25 million. Using the state-of-the-art packages PRIMME and a domain-specific algebraic multigrid preconditioner, we solve this large eigenvalue computation on 32 nodes of a Cray Edison in about 1.5 hours and at a fraction of the cost of our trace computation.<\/jats:p>","DOI":"10.1137\/16m1066361","type":"journal-article","created":{"date-parts":[[2017,4,6]],"date-time":"2017-04-06T11:37:40Z","timestamp":1491478660000},"page":"A532-A558","source":"Crossref","is-referenced-by-count":34,"title":["Deflation as a Method of Variance Reduction for Estimating the Trace of a Matrix Inverse"],"prefix":"10.1137","volume":"39","author":[{"given":"Arjun Singh","family":"Gambhir","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andreas","family":"Stathopoulos","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kostas","family":"Orginos","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2017,4,6]]},"reference":[{"key":"atypb1","first-page":"036","author":"Abdel-Rehim A.","year":"2009","journal-title":"LAT"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1145\/1944345.1944349"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.105.201602"},{"key":"atypb4","volume-title":"Exploring Strange Nucleon Form Factors on the Lattice, preprint, https:\/\/arxiv.org\/abs\/1012.0562v2","author":"Babich R.","year":"2011"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1145\/1645413.1645421"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/j.apnum.2007.01.003"},{"key":"atypb7","volume-title":"Integrals over $SU(N)$, preprint, https:\/\/arxiv.org\/abs\/0802.3409","author":"Carlsson J.","year":"2008"},{"key":"atypb8","volume-title":"Cambridge Monographs on Mathematical Physics","author":"Creutz M.","year":"1983"},{"key":"atypb9","first-page":"1","volume":"38","author":"Davis T. A.","year":"2011","journal-title":"ACM Trans. Math. Softw."},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevD.92.031501"},{"key":"atypb11","first-page":"83","volume-title":"Proceedings, Summer School in Theoretical Physics, NATO Advanced Study Institute, 68th session, Pts. 1 and 2","author":"Gupta R.","year":"1997"},{"key":"atypb12","volume-title":"AMS","author":"Hiai F.","year":"2006"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1080\/03610919008812866"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.69.057701"},{"key":"atypb15","volume-title":"How Many Entries of a Typical Orthogonal Matrix Can Be Approximated by Independent Normals?, preprint, https:\/\/arxiv.org\/abs\/math\/0601457","author":"Jiang T.","year":"2006"},{"key":"atypb16","unstructured":"R. Morgan and W. Wilcox,\n                      Deflated Iterative Methods for Linear Equations with Multiple Right-Hand Sides\n                      , Tech. Report BU-HEPP-04-01, Baylor University, 2004."},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevD.83.114505"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718003"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1016\/0375-9474(93)90098-I"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1137\/120881452"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1145\/1731022.1731031"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1137\/080725532"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1137\/100799939"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1146\/annurev.nucl.50.1.343"},{"key":"atypb25","volume-title":"Noise Methods for Flavor Singlet Quantities, preprint, https:\/\/arxiv.org\/abs\/hep-lat\/9911013","author":"Wilcox W. M.","year":"1999"},{"key":"atypb26","unstructured":"M. N. Wong, F. J. Hickernell, and K. I. Liu,\n                      Computing the Trace of a Function of a Sparse Matrix via Hadamard-Like Sampling\n                      , Tech. Report 377(7\/04), Hong Kong Baptist University, 2004."},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2016.09.001"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevD.93.114506"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/16M1066361","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:29:57Z","timestamp":1787329797000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/16M1066361"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,1]]}},"alternative-id":["10.1137\/16M1066361"],"URL":"https:\/\/doi.org\/10.1137\/16m1066361","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,1]]}}}