Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Fast methods for electrostatic calculations in molecular dynamics simulations
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Numerical Analysis, NA.
2018 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

This thesis deals with fast and efficient methods for electrostatic calculations with application in molecular dynamics simulations. The electrostatic calculations are often the most expensive part of MD simulations of charged particles. Therefore, fast and efficient algorithms are required to accelerate these calculations. In this thesis, two types of methods have been considered: FFT-based methods and fast multipole methods (FMM).

The major part of this thesis deals with fast N.log(N) and spectrally accurate methods for accelerating the computation of pairwise interactions with arbitrary periodicity. These methods are based on the Ewald decomposition and have been previously introduced for triply and doubly periodic problems under the name of Spectral Ewald (SE) method. We extend the method for problems with singly periodic boundary conditions, in which one of three dimensions is periodic. By introducing an adaptive fast Fourier transform, we reduce the cost of upsampling in the non periodic directions and show that the total cost of computation is comparable with the triply periodic counterpart. Using an FFT-based technique for solving free-space harmonic problems, we are able to unify the treatment of zero and nonzero Fourier modes for the doubly and singly periodic problems. Applying the same technique, we extend the SE method for cases with free-space boundary conditions, i.e. without any periodicity.

This thesis is also concerned with the fast multipole method (FMM) for electrostatic calculations. The FMM is very efficient for parallel processing but it introduces irregularities in the electrostatic potential and force, which can cause an energy drift in MD simulations. In this part of the thesis we introduce a regularized version of the FMM, useful for MD simulations, which approximately conserves energy over a long time period and even for low accuracy requirements. The method introduces a smooth transition over the boundary of boxes in the FMM tree and therefore it removes the discontinuity at the error level inherent in the FMM.

Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology, 2018. , p. 58
Series
TRITA-MAT-A ; 2018:02
National Category
Computational Mathematics
Research subject
Applied and Computational Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-219775ISBN: 978-91-7729-640-9 (print)OAI: oai:DiVA.org:kth-219775DiVA, id: diva2:1165219
Public defence
2018-01-26, F3, Lindstedtsvägen 26, Stockholm, 10:00 (English)
Opponent
Supervisors
Funder
Swedish e‐Science Research Center
Note

QC 20171213

Available from: 2017-12-13 Created: 2017-12-12 Last updated: 2017-12-13Bibliographically approved
List of papers
1. A comparison of the Spectral Ewald and Smooth Particle Mesh Ewald methods in GROMACS
Open this publication in new window or tab >>A comparison of the Spectral Ewald and Smooth Particle Mesh Ewald methods in GROMACS
(English)Manuscript (preprint) (Other academic)
Abstract [en]

The smooth particle mesh Ewald (SPME) method is an FFT based methodfor the fast evaluation of electrostatic interactions under periodic boundaryconditions. A highly optimized implementation of this method is availablein GROMACS, a widely used software for molecular dynamics simulations.In this article, we compare a more recent method from the same family ofmethods, the spectral Ewald (SE) method, to the SPME method in termsof performance and efficiency. We consider serial and parallel implementa-tions of both methods for single and multiple core computations on a desktopmachine as well as the Beskow supercomputer at KTH Royal Institute ofTechnology. The implementation of the SE method has been well optimized,however not yet comparable to the level of the SPME implementation thathas been improved upon for many years. We show that the SE method isvery efficient whenever used to achieve high accuracy and that it already atthis level of optimization can be competitive for low accuracy demands.

Keywords
Fast Ewald summation, Fast Fourier transform, Coulomb potentials, SE, SPME, GROMACS
National Category
Computational Mathematics
Research subject
Applied and Computational Mathematics
Identifiers
urn:nbn:se:kth:diva-219771 (URN)
Funder
Swedish e‐Science Research CenterSwedish Research Council for Environment, Agricultural Sciences and Spatial Planning, 2011-3178
Note

QC 20171213

Available from: 2017-12-12 Created: 2017-12-12 Last updated: 2017-12-18Bibliographically approved
2. The Spectral Ewald method for singly periodic domains
Open this publication in new window or tab >>The Spectral Ewald method for singly periodic domains
2017 (English)In: Journal of Computational Physics, ISSN 0021-9991, E-ISSN 1090-2716, Vol. 347, p. 341-366Article in journal (Refereed) Published
Abstract [en]

We present a fast and spectrally accurate method for efficient computation of the three dimensional Coulomb potential with periodicity in one direction. The algorithm is FFT-based and uses the so-called Ewald decomposition, which is naturally most efficient for the triply periodic case. In this paper, we show how to extend the triply periodic Spectral Ewald method to the singly periodic case, such that the cost of computing the singly periodic potential is only marginally larger than the cost of computing the potential for the corresponding triply periodic system. In the Fourier space contribution of the Ewald decomposition, a Fourier series is obtained in the periodic direction with a Fourier integral over the non-periodic directions for each discrete wave number. We show that upsampling to resolve the integral is only needed for modes with small wave numbers. For the zero wave number, this Fourier integral has a singularity. For this mode, we effectively need to solve a free-space Poisson equation in two dimensions. A very recent idea by Vico et al. makes it possible to use FFTs to solve this problem, allowing us to unify the treatment of all modes. An adaptive 3D FFT can be established to apply different upsampling rates locally. The computational cost for other parts of the algorithm is essentially unchanged as compared to the triply periodic case, in total yielding only a small increase in both computational cost and memory usage for this singly periodic case.

Place, publisher, year, edition, pages
Academic Press, 2017
Keywords
Adaptive FFT, Coulomb potentials, Fast Ewald summation, Fast Fourier transform, Fourier integral, Single periodic, Spectral accuracy
National Category
Computational Mathematics
Identifiers
urn:nbn:se:kth:diva-212215 (URN)10.1016/j.jcp.2017.07.001 (DOI)000408045500017 ()2-s2.0-85024927535 (Scopus ID)
Funder
Swedish Research Council, 2011-3178Swedish e‐Science Research Center
Note

QC 20170817

Available from: 2017-08-17 Created: 2017-08-17 Last updated: 2017-12-12Bibliographically approved
3. Fast Ewald summation for free-space Stokes potentials
Open this publication in new window or tab >>Fast Ewald summation for free-space Stokes potentials
2017 (English)In: Research in the Mathematical Sciences, ISSN 2197-9847, Vol. 4, no 1Article in journal (Refereed) Published
Abstract [en]

We present a spectrally accurate method for the rapid evaluation of free-space Stokes potentials, i.e., sums involving a large number of free space Green’s functions. We consider sums involving stokeslets, stresslets and rotlets that appear in boundary integral methods and potential methods for solving Stokes equations. The method combines the framework of the Spectral Ewald method for periodic problems (Lindbo and Tornberg in J Comput Phys 229(23):8994–9010, 2010. doi: 10.1016/j.jcp.2010.08.026 ), with a very recent approach to solving the free-space harmonic and biharmonic equations using fast Fourier transforms (FFTs) on a uniform grid (Vico et al. in J Comput Phys 323:191–203, 2016. doi: 10.1016/j.jcp.2016.07.028 ). Convolution with a truncated Gaussian function is used to place point sources on a grid. With precomputation of a scalar grid quantity that does not depend on these sources, the amount of oversampling of the grids with Gaussians can be kept at a factor of two, the minimum for aperiodic convolutions by FFTs. The resulting algorithm has a computational complexity of $$O(N \log N)$$ O ( N log N ) for problems with N sources and targets. Comparison is made with a fast multipole method to show that the performance of the new method is competitive.

Place, publisher, year, edition, pages
Springer, 2017
National Category
Computational Mathematics
Research subject
Applied and Computational Mathematics
Identifiers
urn:nbn:se:kth:diva-203922 (URN)10.1186/s40687-016-0092-7 (DOI)000412664600001 ()
Funder
Göran Gustafsson Foundation for Research in Natural Sciences and MedicineSwedish Research Council, 2011-3178Swedish e‐Science Research Center
Note

QC 20170411

Available from: 2017-03-20 Created: 2017-03-20 Last updated: 2017-12-12Bibliographically approved
4. Fast Ewald summation for electrostatic potentials with arbitrary periodicity
Open this publication in new window or tab >>Fast Ewald summation for electrostatic potentials with arbitrary periodicity
(English)Manuscript (preprint) (Other academic)
Abstract [en]

A unified treatment for fast and spectrally accurate evaluation of electrostatic potentials subject to periodic boundary conditions in any or none of the three space dimensions is presented. Ewald decomposition is used to split the problem into a real space and a Fourier space part, and the FFT based Spectral Ewald (SE) method is used to accelerate the computation of the latter. A key component in the unified treatment is an FFT based solution technique for the free-space Poisson problem in three, two or one dimensions, depending on the number of non-periodic directions. The cost of calculations is furthermore reduced by employing an adaptive FFT for the doubly and singly periodic cases, allowing for different local upsampling rates. The SE method will always be most efficient for the triply periodic case as the cost for computing FFTs will be the smallest, whereas the computational cost for the rest of the algorithm is essentially independent of the periodicity. We show that the cost of removing periodic boundary conditions from one or two directions out of three will only marginally increase the total run time. Our comparisons also show that the computational cost of the SE method for the free-space case is typically about four times more expensive as compared to the triply periodic case.

The Gaussian window function previously used in the SE method, is here compared to an approximation of the Kaiser-Bessel window function, recently introduced. With a carefully tuned shape parameter that is selected based on an error estimate for this new window function, runtimes for the SE method can be further reduced.

Keywords
Fast Ewald summation, Fast Fourier transform, Arbitrary periodicity, Coulomb potentials, Adaptive FFT, Fourier integral, Spectral accuracy
National Category
Computational Mathematics
Research subject
Applied and Computational Mathematics
Identifiers
urn:nbn:se:kth:diva-219772 (URN)
Funder
Göran Gustafsson Foundation for promotion of scientific research at Uppala University and Royal Institute of TechnologySwedish e‐Science Research Center
Note

QC 20171213

Available from: 2017-12-12 Created: 2017-12-12 Last updated: 2017-12-18Bibliographically approved
5. Regularized FMM for MD simulations
Open this publication in new window or tab >>Regularized FMM for MD simulations
(English)Manuscript (preprint) (Other academic)
Abstract [en]

A regularized fast multipole method (FMM) which approximately conserves the total energy in Molecular dynamics (MD) simulations is presented. The new algorithm introduces a regularization which eliminates the discontinuity inherent in the FMM. This allows us to use FMM in simulations as a substitute for widely used FFT based methods. For a system of N particles, the computational complexity of the resulting method is still of order N though with a larger constant compared to the plain FMM. Numerical examples are provided to confirm that the new algorithm improves the accuracy and approximately conserves the long term total energy.

Keywords
Regularization, Fast multipole method, Molecular dynamics, Energy conservation
National Category
Computational Mathematics
Research subject
Applied and Computational Mathematics
Identifiers
urn:nbn:se:kth:diva-219773 (URN)
Funder
Swedish e‐Science Research Center
Note

QC 20171213

Available from: 2017-12-12 Created: 2017-12-12 Last updated: 2017-12-13Bibliographically approved
6. A fast multipole method for evaluating exponential integral type kernels
Open this publication in new window or tab >>A fast multipole method for evaluating exponential integral type kernels
(English)Manuscript (preprint) (Other academic)
Abstract [en]

We present a fast multipole method for evaluation of sums with exponential  integral type kernels. These sums appear while solving free space Poisson problems in two dimensions and in the derivation of 1d-periodic Ewald sums. The presented method uses recurrence relations to derive multipole expansions for computing interactions between particles and far clusters.

Keywords
Fast multipole method, Exponential integral, recurrence relation, Spectral Ewald
National Category
Computational Mathematics
Research subject
Applied and Computational Mathematics
Identifiers
urn:nbn:se:kth:diva-219774 (URN)
Funder
Swedish e‐Science Research CenterSwedish Research Council for Environment, Agricultural Sciences and Spatial Planning, 2011-3178
Note

QC 20171213

Available from: 2017-12-12 Created: 2017-12-12 Last updated: 2017-12-13Bibliographically approved

Open Access in DiVA

fulltext(1246 kB)103 downloads
File information
File name FULLTEXT01.pdfFile size 1246 kBChecksum SHA-512
c4a414037d75c8f8d98a2eeb8701e36898110282e2452f0e1cdbf59e31e25533b95e5d436164680bf9f7d3d495d0aa7b1c74cd30270042448cc14b4ba437264a
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Saffar Shamshirgar, Davood
By organisation
Numerical Analysis, NA
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 103 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 534 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf