ContHutch++: Stochastic trace estimation for implicit integral operators
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916410227163136 |
|---|---|
| author | Zvonek, Jennifer Horning, Andrew Townsend, Alex |
| author_facet | Zvonek, Jennifer Horning, Andrew Townsend, Alex |
| contents | Hutchinson's estimator is a randomized algorithm that computes an $ε$-approximation to the trace of any positive semidefinite matrix using $\mathcal{O}(1/ε^2)$ matrix-vector products. An improvement of Hutchinson's estimator, known as Hutch++, only requires $\mathcal{O}(1/ε)$ matrix-vector products. In this paper, we propose a generalization of Hutch++, which we call ContHutch++, that uses operator-function products to efficiently estimate the trace of any trace-class integral operator. Our ContHutch++ estimates avoid spectral artifacts introduced by discretization and are accompanied by rigorous high-probability error bounds. We use ContHutch++ to derive a new high-order accurate algorithm for quantum density-of-states and also show how it can estimate electromagnetic fields induced by incoherent sources. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_07035 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | ContHutch++: Stochastic trace estimation for implicit integral operators Zvonek, Jennifer Horning, Andrew Townsend, Alex Numerical Analysis Hutchinson's estimator is a randomized algorithm that computes an $ε$-approximation to the trace of any positive semidefinite matrix using $\mathcal{O}(1/ε^2)$ matrix-vector products. An improvement of Hutchinson's estimator, known as Hutch++, only requires $\mathcal{O}(1/ε)$ matrix-vector products. In this paper, we propose a generalization of Hutch++, which we call ContHutch++, that uses operator-function products to efficiently estimate the trace of any trace-class integral operator. Our ContHutch++ estimates avoid spectral artifacts introduced by discretization and are accompanied by rigorous high-probability error bounds. We use ContHutch++ to derive a new high-order accurate algorithm for quantum density-of-states and also show how it can estimate electromagnetic fields induced by incoherent sources. |
| title | ContHutch++: Stochastic trace estimation for implicit integral operators |
| topic | Numerical Analysis |
| url | https://arxiv.org/abs/2311.07035 |