Preprint 65/2015

Fast tensor method for summation of long-range potentials on 3D lattices with defects

Venera Khoromskaia and Boris N. Khoromskij

Contact the author: Please use for correspondence this email.
Submission date: 21. Oct. 2015 (revised version: October 2015)
Pages: 30
published in: Numerical linear algebra with applications, 23 (2016) 2, p. 249-271 
DOI number (of the published article): 10.1002/nla.2023
Bibtex
MSC-Numbers: 65F30, 65F50, 65N35, 65F10
Keywords and phrases: long-range potential sums, tensor numerical methods, defected lattice in a box
Download full preprint: PDF (2459 kB)

Abstract:
In this paper, we present a method for fast summation of long-range potentials on 3D lattices with multiple defects and having non-rectangular geometries, based on rank-structured tensor representations. This is a significant generalization of our recent technique for the grid-based summation of electrostatic potentials on the rectangular L × L × L lattices by using the canonical tensor decompositions and yielding the O(L) computational complexity instead of O(L3) by traditional approaches. The resulting lattice sum is calculated as a Tucker or canonical representation whose directional vectors are assembled by the 1D summation of the generating vectors for the shifted reference tensor, once precomputed on large N × N × N representation grid in a 3D bounding box. The tensor numerical treatment of defects is performed in an algebraic way by simple summation of tensors in the canonical or Tucker formats. To diminish the considerable increase in the tensor rank of the resulting potential sum the 𝜀-rank reduction procedure is applied based on the generalized reduced higher-order SVD scheme. For the reduced higher-order SVD approximation to a sum of canonical/Tucker tensors, we prove the stable error bounds in the relative norm in terms of discarded singular values of the side matrices. The required storage scales linearly in the 1D grid-size, O(N), while the numerical cost is estimated by O(NL). The approach applies to a general class of kernel functions including those for the Newton, Slater, Yukawa, Lennard-Jones, and dipole-dipole interactions. Numerical tests confirm the efficiency of the presented tensor summation method: we demonstrate that a sum of millions of Newton kernels on a 3D lattice with defects/impurities can be computed in seconds in Matlab implementation. The tensor approach is advantageous in further functional calculus with the lattice potential sums represented on a 3D grid, like integration or differentiation, using tensor arithmetics of 1D complexity.

03.07.2017, 01:42