An algorithm for 3D numerical integration that scales linearly with the size of the molecule

The cost of numerical integration in density-functional theory scales as the cube of the size of the molecule: it is proportional to the number of grid points and to the square of the number of basis functions. We describe a scheme that makes this cost independent of the number of basis functions, thus yielding an algorithm that scales linearly with the size of the molecule. The error introduced by the present scheme can be made as small as desired by lowering a threshold T. The method can be applied to any quadrature rule and local basis set.