2014/11/07 by Venera Khoromskaia, Khoromskaia, Venera, Boris N. Khoromskij +1
Computer Science · Mathematics · Physics and Astronomy · #65F10 #65F30 #65F50 #65N35 #Electromagnetic Scattering and Analysis #FOS: Mathematics #Matrix Theory and Algorithms #Numerical Analysis (math.NA) #Tensor decomposition and applications
paper · pdf · doi:10.48550/arxiv.1411.1994
openalex publication_date 2014/11/07 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
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(N L). 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.