Source-linked AI summary
Compression of the electron repulsion integral tensor in tensor hypercontraction format with cubic scaling cost
Jianfeng Lu, Lexing Ying
TL;DR
Electron repulsion integral tensors are widely used, making efficient representations important for ab initio calculations. The paper uses randomized selection of spatial grid points to interpolate orbital pair products and obtain tensor hypercontraction. Timing tests match the stated O(nN^2 log N) cost, while the number of auxiliary functions grows roughly linearly with N.
Problem
Efficient electron-repulsion-integral representations are needed because these tensors are used across electronic-structure theories and are a key step in accelerating ab initio computations.
Source: §I · p. 2Method
Randomized column selection chooses spatial grid points to interpolate orbital pair products and obtain the tensor hypercontraction representation.
Source: §I · pp. 3–4, §II · pp. 4–5Results
Timing tests match O(nN^2 log N), while the number of auxiliary functions grows roughly linearly with N and remains much smaller than N^2.
Source: §III · pp. 8–9Takeaways & Limitations
The selected-grid interpolation provides an auxiliary-basis strategy for obtaining tensor hypercontraction.
Source: §I · pp. 3–4The presentation assumes orbitals are represented on a real-space grid; the grid-point count n may be a large prefactor, and direct atomic-orbital algorithms remain future work.
Source: §IV · p. 11
Abstract
from arXiv · showhide
Electron repulsion integral tensor has ubiquitous applications in quantum chemistry calculations. In this work, we propose an algorithm which compresses the electron repulsion tensor into the tensor hypercontraction format with $\mathcal{O}(n N^2 \log N)$ computational cost, where $N$ is the number of orbital functions and $n$ is the number of spatial grid points that the discretization of each orbital function has. The algorithm is based on a novel strategy of density fitting using a selection of a subset of spatial grid points to approximate the pair products of orbital functions on the whole domain.
I. INTRODUCTION
The paper proposes an O(nN^2 log N) algorithm that selects spatial grid points to interpolate orbital pair products and obtain the electron repulsion integral tensor in tensor hypercontraction format. This addresses the need for efficient integral-tensor representations in ab initio calculations.
I. INTRODUCTION
- Density fitting represents orbital pair products using auxiliary basis functions, constructed explicitly or implicitly through singular value decomposition.Explicit examples include Gaussian-type atom-centered basis functions; the implicit construction uses the overlap matrix of the pair products.Source: §I · p. 2
- Other electron-repulsion-integral compression approaches include multipole moments, pseudospectral representations, and incomplete Cholesky decomposition.The resolution-of-identity approximation with O(N) auxiliary basis functions is described as costing O(N^4).Source: §I · p. 3
- Tensor hypercontraction of the electron repulsion integral had been proposed in, with weighted collocation factors and least-squares fitting.The cited passage describes costs of O(N^5) with direct quadrature and O(N^4) with density fitting.Source: §I · p. 3
- The proposed O(nN^2 log N) algorithm selects spatial grid points to interpolate pair products, with coefficients depending separately on orbital indices i and j.The authors describe the selected points as an alternative to predetermined auxiliary basis functions.Source: §I · pp. 3–4
II. ALGORITHM
The algorithm applies randomized column selection to the pair-density matrix, choosing spatial grid points that interpolate pair products. This interpolation separates the orbital-index dependence and yields the tensor hypercontraction format.
II. ALGORITHM
- The algorithm applies randomized column selection to ρij(x), arranged with orbital pairs as rows and spatial grid points as columns.The spatial quadrature grid can be chosen generally, and the authors note possible extension to other discretizations such as atomic orbitals.Source: §II · p. 4
- The selected-point approximation is interpolation, not quadrature; ψi(xμ)ψj(xμ) supplies the coefficient for each pair product.After selecting points, least-squares fitting determines the auxiliary basis functions.Source: §II · pp. 4–5
- Separating dependence on i and j lets the pair-density approximation yield the tensor hypercontraction format without further approximation.The additional (μ|ν) terms can be calculated efficiently using FFT.Source: §II · p. 5
- A random projection and pivoted QR select grid-point columns, with the error threshold ε setting the number of auxiliary basis functions.The selected columns correspond to the grid points used in the interpolation.Source: §II · pp. 5–6
- The overall column-selection cost is O(nN^2 log N), with O(nN^2) intermediate storage when Naux = O(N).The stated cost is dominated by the Fourier transforms, QR decomposition, and auxiliary-matrix operations.Source: §II · p. 6
III. NUMERICAL RESULTS
Tests in one and three dimensions show controlled fitting errors with auxiliary-basis counts that grow roughly linearly with the number of orbitals. In a graphene example, the proposed algorithm is faster than conventional density fitting for large N.
1D toy problem
- At 10^-5 relative error, Naux is around 300 for 16,384 orbital pairs, and both L2 and Coulomb errors are controlled by the threshold.The number of auxiliary functions increases mildly as the threshold is reduced.Source: §III · pp. 7–8, Table I · p. 8
1D complexity test
- With the error threshold fixed at 10^-5, timing matches O(nN^2 log N), and Naux grows linearly with N.The tests vary N and n; the reported timings were measured on a single CPU core.Source: §III · p. 8, Table II · p. 8
3D test
- In 3D, at fixed error threshold, relative error remains well controlled; Naux grows roughly linearly with N and remains much smaller than N^2, while computational time agrees with O(nN^2 log N) when n is fixed.The 3D tests require more auxiliary basis functions than the 1D case.Source: §III · p. 9
Realistic graphene example
- For large N, the proposed algorithm has lower computational cost than conventional density fitting, with N^2 log N versus N^3 scaling when n is fixed.The linear growth of Naux is clear apart from a pre-asymptotic regime at small N.Source: §III · pp. 9–10, Table IV · p. 10
IV. DISCUSSION AND CONCLUSION
The paper presents an easy-to-implement cubic-scaling algorithm for tensor hypercontraction and reports small-scale tests of its effectiveness. It identifies possible further cost reductions for localized orbitals, while noting limits related to grid representation and the error metric.
IV. DISCUSSION AND CONCLUSION
- The proposed cubic-scaling algorithm is easy to implement and can be incorporated into existing electronic-structure packages, but the numerical tests are relatively small-scale.Large-scale electronic-structure applications are identified as a natural next step.Source: §IV · p. 11
- For localized orbitals, restricting column selection to their support could reduce computational scaling to O(N) with controllable error.The algorithm itself does not assume orbital locality; this reduction is presented as a possible future direction.Source: §IV · p. 11
- The algorithm assumes orbitals are represented on a real-space grid, and its complexity depends on n, which may be a large constant factor of N.Atomic-orbital discretization can be handled by first obtaining a real-space representation with quadrature grids; working directly with atomic orbitals remains an open direction.Source: §IV · p. 11
- Column selection uses the L2 metric; the reported Coulomb-metric error is slightly larger, and selecting directly in the Coulomb metric remains an open question.The natural Fourier-domain approach is unsuitable because the Fourier transform destroys the coefficient separability on which the algorithm depends.Source: §IV · p. 11
- The authors identify fast quantum-chemistry algorithms based on their O(nN^2 log N) tensor-hypercontraction method as a future direction.The method is distinguished from RI-SVS density fitting.Source: §IV · p. 12