×

Grid-based lattice summation of electrostatic potentials by assembled rank-structured tensor approximation. (English) Zbl 1360.78016

Summary: Our recent method for low-rank tensor representation of sums of the arbitrarily positioned electrostatic potentials discretized on a 3D Cartesian grid reduces the 3D tensor summation to operations involving only 1D vectors however retaining the linear complexity scaling in the number of potentials. Here, we introduce and study a novel tensor approach for fast and accurate assembled summation of a large number of lattice-allocated potentials represented on 3D \(N \times N \times N\) grid with the computational requirements only weakly dependent on the number of summed potentials. It is based on the assembled low-rank canonical tensor representations of the collected potentials using pointwise sums of shifted canonical vectors representing the single generating function, say the Newton kernel. For a sum of electrostatic potentials over \(L \times L \times L\) lattice embedded in a box the required storage scales linearly in the 1D grid-size, \(O(N)\), while the numerical cost is estimated by \(O(N L)\). For periodic boundary conditions, the storage demand remains proportional to the 1D grid-size of a unit cell, \(n = N / L\), while the numerical cost reduces to \(O(N)\), that outperforms the FFT-based Ewald-type summation algorithms of complexity \(O(N^3 \log N)\). The complexity in the grid parameter \(N\) can be reduced even to the logarithmic scale \(O(\log N)\) by using data-sparse representation of canonical \(N\)-vectors via the quantics tensor approximation. For justification, we prove an upper bound on the quantics ranks for the canonical vectors in the overall lattice sum. The presented approach is beneficial in applications which require further functional calculus with the lattice potential, say, scalar product with a function, integration or differentiation, which can be performed easily in tensor arithmetics on large 3D grids with 1D cost. Numerical tests illustrate the performance of the tensor summation method and confirm the estimated bounds on the tensor ranks.

MSC:

78A30 Electro- and magnetostatics

Software:

CRYSCOR
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Dovesi, R.; Orlando, R.; Roetti, C.; Pisani, C.; Sauders, V. R., The periodic Hartree-Fock method and its implementation in the CRYSTAL code, Phys. Status Solidi b, 217, 63 (2000)
[2] Pisani, C.; Schütz, M.; Casassa, S.; Usvyat, D.; Maschio, L.; Lorenz, M.; Erba, A., CRYSCOR: a program for the post-Hartree-Fock treatment of periodic systems, Phys. Chem. Chem. Phys., 14, 7615-7628 (2012)
[3] Kudin, K. N.; Scuseria, G. E., Revisiting infinite lattice sums with the periodic fast multipole method, J. Chem. Phys., 121, 2886-2890 (2004)
[4] Voloshina, Elena; Usvyat, Denis; Schütz, Martin; Dedkov, Yuriy; Paulus, Beate, On the physisorption of water on graphene: a CCSD(T) study, Phys. Chem. Chem. Phys., 13, 12041-12047 (2011)
[5] Lorenz, M.; Usvyat, D.; Schütz, M., Local ab initio methods for calculating optical band gaps in periodic systems. I. Periodic density fitted local configuration interaction singles method for polymers, J. Chem. Phys., 134, 094101 (2011)
[6] Cancés, E.; Ehrlacher, V.; Maday, Y., Periodic Schrödinger operator with local defects and spectral pollution, SIAM J. Numer. Anal., 50, 6, 3016-3035 (2012) · Zbl 1259.49075
[7] Losilla, S. A.; Sundholm, D.; Juselius, J., The direct approach to gravitation and electrostatics method for periodic systems, J. Chem. Phys., 132, 2, 024102 (2010)
[8] V. Khoromskaia, B.N. Khoromskij, Tensor Approach to Linearized Hartree-Fock Equation for Lattice-type and Periodic Systems. Preprint of the Max-Planck Institute MIS 62/2014, Leipzig, 2014.; V. Khoromskaia, B.N. Khoromskij, Tensor Approach to Linearized Hartree-Fock Equation for Lattice-type and Periodic Systems. Preprint of the Max-Planck Institute MIS 62/2014, Leipzig, 2014.
[9] Toukmaji, A. Y.; Board, J., Ewald summation techniques in perspective: a survey, Comput. Phys. Comm., 95, 73-92 (1996) · Zbl 0923.65090
[10] Philippe H. Hünenberger, Lattice-sum methods for computing electrostatic interactions in molecular simulations. CP492, L.R. Pratt and G. Hummer, eds., 1999, American Institute of Physics, 1-56396-906-8/99.; Philippe H. Hünenberger, Lattice-sum methods for computing electrostatic interactions in molecular simulations. CP492, L.R. Pratt and G. Hummer, eds., 1999, American Institute of Physics, 1-56396-906-8/99.
[11] Deserno, M.; Holm, C., How to mesh up Ewald sums. I. A theoretical and numerical comparison of various particle mesh routines, J. Chem. Phys., 109, 18, 7678-7693 (1998)
[12] Ewald, P. P., Die Berechnung optische und elektrostatischer Gitterpotentiale, Ann. Phys, 64, 253 (1921) · JFM 48.0566.02
[13] Darten, T.; York, D.; Pedersen, L., Particle mesh Ewald: An \(O(N \log N)\) method for Ewald sums in large systems, J. Chem. Phys., 98, 10089-10091 (1993)
[14] Pollock, E. L.; Glosli, Jim, Comments on \(P^3 M, F M M\), and the Ewald method for large periodic Coulombic systems, Comput. Phys. Comm., 95, 93-110 (1996) · Zbl 0921.65081
[15] Lindbo, D.; Tornberg, A.-K., Fast and spectrally accurate Ewald summation for 2-periodic electrostatic systems, J. Chem. Phys., 136, 164111 (2012)
[16] Greengard, L.; Rochlin, V., A fast algorithm for particle simulations, J. Comput. Phys., 73, 325 (1987) · Zbl 0629.65005
[17] Khoromskij, B. N.; Khoromskaia, V., Low rank Tucker tensor approximation to the classical potentials, Cent. Eur. J. Math., 5, 3, 1-28 (2007) · Zbl 1130.65060
[18] Venera Khoromskaia, Numerical solution of the Hartree-Fock equation by multilevel tensor-structured methods (Ph.D thesis), TU Berlin, 2010. http://opus4.kobv.de/opus4-tuberlin/frontdoor/index/index/docId/2780; Venera Khoromskaia, Numerical solution of the Hartree-Fock equation by multilevel tensor-structured methods (Ph.D thesis), TU Berlin, 2010. http://opus4.kobv.de/opus4-tuberlin/frontdoor/index/index/docId/2780
[19] Bertoglio, C.; Khoromskij, B. N., Low-rank quadrature-based tensor approximation of the Galerkin projected Newton/Yukawa kernels, Comput. Phys. Comm., 183, 4, 904-912 (2012) · Zbl 1308.65213
[20] Braess, D., Asymptotics for the approximation of wave functions by exponential-sums, J. Approx. Theory, 83, 93-103 (1995) · Zbl 0868.41012
[21] Hackbusch, W.; Khoromskij, B. N., Low-rank Kronecker product approximation to multi-dimensional nonlocal operators. Part I. Separable approximation of multi-variate functions, Computing, 76, 177-202 (2006) · Zbl 1087.65049
[22] Khoromskaia, V.; Andrae, D.; Khoromskij, B. N., Fast and accurate 3D tensor calculation of the Fock operator in a general basis, Comput. Phys. Comm., 183, 2392-2404 (2012) · Zbl 1302.81009
[23] Khoromskaia, V., Black-box Hartree-Fock solver by tensor numerical methods, Comput. Methods Appl. Math., 14, 1, 89-111 (2014) · Zbl 1285.65091
[24] Khoromskij, B. N.; Khoromskaia, V., Multigrid tensor approximation of function related multi-dimensional arrays, SIAM J. Sci. Comput., 31, 4, 3002-3026 (2009) · Zbl 1197.65215
[25] Khoromskij, B. N., \(O(d \log N)\)-quantics approximation of \(N-d\) tensors in high-dimensional numerical modeling, Constr. Approx., 34, 257-280 (2011), Preprint 55/2009 MPI MiS, Leipzig 2009 · Zbl 1228.65069
[26] White, S. R., Density-matrix algorithms for quantum renormalization groups, Phys. Rev. B, 48, 14, 10345-10356 (1993)
[27] Kolda, T. G.; Bader, B. W., Tensor decompositions and applications, SIAM Rev., 51, 3, 455-500 (2009) · Zbl 1173.65029
[28] Khoromskij, B. N., Tensors-structured numerical methods in scientific computing: Survey on recent advances, Chemometr. Intell. Lab. Syst., 110, 1-19 (2012)
[29] L. Grasedyck, D. Kressner, C. Tobler, A literature survey of low-rank tensor approximation techniques. arXiv:1302.7121v1; L. Grasedyck, D. Kressner, C. Tobler, A literature survey of low-rank tensor approximation techniques. arXiv:1302.7121v1 · Zbl 1279.65045
[30] B.N. Khoromskij, Introduction to Tensor Numerical Methods in Scientific Computing. Lecture Notes, Preprint 06-2011, University of Zuerich, Institute of Mathematics, 2011, pp. 1-238. http://www.math.uzh.ch/fileadmin/math/preprints/06_11.pdf; B.N. Khoromskij, Introduction to Tensor Numerical Methods in Scientific Computing. Lecture Notes, Preprint 06-2011, University of Zuerich, Institute of Mathematics, 2011, pp. 1-238. http://www.math.uzh.ch/fileadmin/math/preprints/06_11.pdf
[31] Khoromskij, B. N., Fast and accurate tensor approximation of a multivariate convolution with linear scaling in dimension, J. Comput. Appl. Math., 234, 3122-3139 (2010) · Zbl 1197.65216
[32] Khoromskij, B. N.; Khoromskaia, V.; Flad, H.-J., Numerical solution of the Hartree-Fock equation in multilevel tensor-structured format, SIAM J. Sci. Comput., 33, 1, 45-65 (2011) · Zbl 1227.65113
[33] Boys, S. F.; Cook, G. B.; Reeves, C. M.; Shavitt, I., Automatic fundamental calculations of molecular structure, Nature, 178, 1207-1209 (1956)
[34] Braess, D., Nonlinear Approximation Theory (1986), Springer-Verlag: Springer-Verlag Berlin · Zbl 0656.41001
[35] Gavrilyuk, I. P.; Hackbusch, W.; Khoromskij, B. N., Hierarchical tensor-product approximation to the inverse and related operators in high-dimensional elliptic problems, Computing, 74, 131-157 (2005) · Zbl 1071.65032
[36] Helgaker, T.; Jørgensen, P.; Olsen, J., Molecular Electronic-Structure Theory (1999), Wiley: Wiley New York
[37] Dolgov, S. V.; Khoromskij, B. N.; Oseledets, I., Fast solution of multi-dimensional parabolic problems in the TT/QTT formats with initial application to the Fokker-Planck equation, SIAM J. Sci. Comput., 34, 6, A3016-A3038 (2012) · Zbl 1259.82075
[38] Bloch, André, Les theoremes de M. Valiron sur les fonctions entieres et la theorie de l’uniformisation, Ann. Fac. Sci. Univ. Toulose, 17, 1-22 (1925) · JFM 52.0324.02
[39] Khoromskij, B. N., Structured rank-\((r_1, \ldots, r_d)\) decomposition of function-related tensors in \(R^d\), Comput. Methods Appl. Math., 6, 2, 194-220 (2006) · Zbl 1120.65052
[40] Verstraete, F.; Porras, D.; Cirac, J. I., DMRG and periodic boundary conditions: A quantum information perspective, Phys. Rev. Lett., 93, 22, 227205 (2004)
[41] Oseledets, I. V., Tensor-train decomposition, SIAM J. Sci. Comput., 33, 5, 2295-2317 (2011) · Zbl 1232.15018
[42] L. Grasedyck, Polynomial approximation in hierarchical Tucker format by vector-tensorization. Preprint 308, Institut fuer Geometrie und Praktische Mathematik, RWTH Aachen, 2010.; L. Grasedyck, Polynomial approximation in hierarchical Tucker format by vector-tensorization. Preprint 308, Institut fuer Geometrie und Praktische Mathematik, RWTH Aachen, 2010.
[43] Dolgov, S. V.; Khoromskij, B. N.; Savostyanov, D., Superfast Fourier transform using QTT approximation, J. Fourier Anal. Appl., 18, 5, 915-953 (2012) · Zbl 1260.65114
[44] Kazeev, V.; Khoromskij, B. N., Explicit low-rank QTT representation of Laplace operator and its inverse, SIAM J. Matrix Anal. Appl., 33, 3, 742-758 (2012) · Zbl 1268.15025
[45] Khoromskij, Boris N.; Miao, Sentao, Superfast wavelet transform using QTT approximation. I: Haar wavelets, Comput. Methods Appl. Math. (2014) · Zbl 1304.65139
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.