The computation of the Coulomb potentials and forces in charged particle systems under 3d-periodic boundary conditions is possible in an efficient way by utilizing the Ewald summation formulas and applying the fast Fourier transform (FFT). In this paper we consider the particle-particle NFFT (P2NFFT) approach, which is based on the fast Fourier transform for nonequispaced data (NFFT) and compare the error behaviors regarding different window functions, which are used in order to approximate the given continuous charge distribution by a mesh based charge density. While typically B-splines are applied in the scope of particle mesh methods, we consider for the first time also an approximation by Bessel functions. We show how the resulting root mean square errors in the forces can be predicted precisely and efficiently. The results show that if the parameters are tuned appropriately the Bessel window function can keep up with the B-spline window and is in many cases even the better choice with respect to computational costs.

The computation of the Coulomb potentials and forces in charged particle systems under 3d-periodic boundary conditions is possible in an efficient way by utilizing the Ewald summation formulas and applying the fast Fourier transform (FFT). In this paper we consider the particle-particle NFFT (P2NFFT) approach, which is based on the fast Fourier transform for nonequispaced data (NFFT) and compare the error behaviors regarding different window functions, which are used in order to approximate the given continuous charge distribution by a mesh based charge density. While typically B-splines are applied in the scope of particle mesh methods, we consider for the first time also an approximation by Bessel functions. We show how the resulting root mean square errors in the forces can be predicted precisely and efficiently. The results show that if the parameters are tuned appropriately the Bessel window function can keep up with the B-spline window and is in many cases even the better choice with respect to computational costs.

We present an efficient method to compute the electrostatic fields, torques and forces in dipolar systems, which is based on the fast Fourier transform for nonequispaced data (NFFT). We consider 3d-periodic, 2d-periodic, 1d-periodic as well as 0d-periodic (open) boundary conditions. The method is based on the corresponding Ewald formulas, which immediately lead to an efficient algorithm only in the 3d-periodic case. In the other cases we apply the NFFT based fast summation in order to approximate the contributions of the nonperiodic dimensions in Fourier space. This is done by regularizing or periodizing the involved functions, which depend on the distances of the particles regarding the nonperiodic dimensions. The final algorithm enables a unified treatment of all types of periodic boundary conditions, for which only the precomputation step has to be adjusted.

The computation of the Coulomb potentials and forces in charged particle systems under 3d-periodic boundary conditions is possible in an efficient way by utilizing the Ewald summation formulas and applying the fast Fourier transform (FFT). In this paper we consider the particle-particle NFFT (P2NFFT) approach, which is based on the fast Fourier transform for nonequispaced data (NFFT) and compare the error behaviors regarding different window functions, which are used in order to approximate the given continuous charge distribution by a mesh based charge density. Typically B-splines are applied in the scope of particle mesh methods, as for instance within the well-known particle-particle particle-mesh (P3M) algorithm. The publicly available P2NFFT algorithm allows the application of an oversampled FFT as well as the usage of different window functions. We consider for the first time also an approximation by Bessel functions and show how the resulting root mean square errors in the forces can be predicted precisely and efficiently. The results show that, if the parameters are tuned appropriately, the Bessel window function is in many cases even the better choice in terms of computational costs. Moreover, the results indicate that it is often advantageous in terms of efficiency to spend some oversampling within the NFFT while using a window function with a smaller support.

The present thesis is dedicated to the efficient computation of electrostatic interactions in particle systems, which is of great importance in the field of molecular dynamics simulations. In order to compute the therefor required physical quantities with only O(N log N) arithmetic operations, so called particle-mesh methods make use of the well-known Ewald summation approach and the fast Fourier transform (FFT). Typically, such methods are able to handle systems of point charges subject to periodic boundary conditions in all spatial directions. However, periodicity is not always desired in all three dimensions and, moreover, also interactions to dipoles play an important role in many applications. Within the scope of the present work, we consider the particle-particle NFFT method (P²NFFT), a particle-mesh approach based on the fast Fourier transform for nonequispaced data (NFFT). An extension of this method for mixed periodic as well as open boundary conditions is presented. Furthermore, the method is appropriately modified in order to treat particle systems containing both charges and dipoles. Consequently, an efficient algorithm for mixed charge-dipole systems, that additionally allows a unified handling of various types of periodic boundary conditions, is presented for the first time. Appropriate error estimates as well as parameter tuning strategies are developed and verified by numerical examples. / Die vorliegende Arbeit widmet sich der Berechnung elektrostatischer Wechselwirkungen in Partikelsystemen, was beispielsweise im Bereich der molekulardynamischen Simulationen eine zentrale Rolle spielt. Um die dafür benötigten physikalischen Größen mit lediglich O(N log N) arithmetischen Operationen zu berechnen, nutzen sogenannte Teilchen-Gitter-Methoden die Ewald-Summation sowie die schnelle Fourier-Transformation (FFT). Typischerweise können derartige Verfahren Systeme von Punktladungen unter periodischen Randbedingungen in allen Raumrichtungen handhaben. Periodizität ist jedoch nicht immer bezüglich aller drei Dimensionen erwünscht. Des Weiteren spielen auch Wechselwirkungen zu Dipolen in vielen Anwendungen eine wichtige Rolle. Zentraler Gegenstand dieser Arbeit ist die Partikel-Partikel-NFFT Methode (P²NFFT), ein Teilchen-Gitter-Verfahren, welches auf der schnellen Fouriertransformation für nichtäquidistante Daten (NFFT) basiert. Eine Erweiterung dieses Verfahrens auf gemischt periodische sowie offene Randbedingungen wird vorgestellt. Außerdem wird die Methode für die Behandlung von Partikelsystemen, in denen sowohl Ladungen als auch Dipole vorliegen, angepasst. Somit wird erstmalig ein effizienter Algorithmus für gemischte Ladungs-Dipol-Systeme präsentiert, der zusätzlich die Behandlung sämtlicher Arten von Randbedingungen mit einem einheitlichen Zugang erlaubt. Entsprechende Fehlerabschätzungen sowie Strategien für die Parameterwahl werden entwickelt und anhand numerischer Beispiele verifiziert.

The computation of the Coulomb potentials and forces in charged particle systems under 3d-periodic boundary conditions is possible in an efficient way by utilizing the Ewald summation formulas and applying the fast Fourier transform (FFT). In this paper we consider the particle-particle NFFT (P2NFFT) approach, which is based on the fast Fourier transform for nonequispaced data (NFFT) and compare the error behaviors regarding different window functions, which are used in order to approximate the given continuous charge distribution by a mesh based charge density. Typically B-splines are applied in the scope of particle mesh methods, as for instance within the well-known particle-particle particle-mesh (P3M) algorithm. The publicly available P2NFFT algorithm allows the application of an oversampled FFT as well as the usage of different window functions. We consider for the first time also an approximation by Bessel functions and show how the resulting root mean square errors in the forces can be predicted precisely and efficiently. The results show that, if the parameters are tuned appropriately, the Bessel window function is in many cases even the better choice in terms of computational costs. Moreover, the results indicate that it is often advantageous in terms of efficiency to spend some oversampling within the NFFT while using a window function with a smaller support.

We present an efficient method to compute the electrostatic fields, torques and forces in dipolar systems, which is based on the fast Fourier transform for nonequispaced data (NFFT). We consider 3d-periodic, 2d-periodic, 1d-periodic as well as 0d-periodic (open) boundary conditions. The method is based on the corresponding Ewald formulas, which immediately lead to an efficient algorithm only in the 3d-periodic case. In the other cases we apply the NFFT based fast summation in order to approximate the contributions of the nonperiodic dimensions in Fourier space. This is done by regularizing or periodizing the involved functions, which depend on the distances of the particles regarding the nonperiodic dimensions. The final algorithm enables a unified treatment of all types of periodic boundary conditions, for which only the precomputation step has to be adjusted.

The present thesis provides a modularized view on the structure of fast numerical methods for computing Coulomb interactions between charged particles in three-dimensional space. Thereby, the common structure is given in terms of three self-contained algorithmic frameworks that are built on top of each other, namely fast Fourier transform (FFT), nonequispaced fast Fourier transform (NFFT) and NFFT based particle-mesh methods (P²NFFT). For each of these frameworks algorithmic enhancement and parallel implementations are presented with special emphasis on scalability up to hundreds of thousands of parallel processes. In the context of FFT massively parallel algorithms are composed from hardware adaptive low level modules provided by the FFTW software library. The new algorithmic NFFT concepts include pruned NFFT, interlacing, analytic differentiation, and optimized deconvolution in Fourier space with respect to a mean square aliasing error. Enabled by these generalized concepts it is shown that NFFT provides a unified access to particle-mesh methods. Especially, mixed-periodic boundary conditions are handled in a consistent way and interlacing can be incorporated more efficiently. Heuristic approaches for parameter tuning are presented on the basis of thorough error estimates. / Die vorliegende Dissertation beschreibt einen modularisierten Blick auf die Struktur schneller numerischer Methoden für die Berechnung der Coulomb-Wechselwirkungen zwischen Ladungen im dreidimensionalen Raum. Die gemeinsame Struktur ist geprägt durch drei selbstständige und auf einander aufbauenden Algorithmen, nämlich der schnellen Fourier-Transformation (FFT), der nicht äquidistanten schnellen Fourier-Transformation (NFFT) und der NFFT-basierten Teilchen-Gitter-Methode (P²NFFT). Für jeden dieser Algorithmen werden Verbesserungen und parallele Implementierungen vorgestellt mit besonderem Augenmerk auf massiv paralleler Skalierbarkeit. Im Kontext der FFT werden parallele Algorithmen aus den Hardware adaptiven Modulen der FFTW Softwarebibliothek zusammengesetzt. Die neuen NFFT-Konzepte beinhalten abgeschnittene NFFT, Versatz, analytische Differentiation und optimierte Entfaltung im Fourier-Raum bezüglich des mittleren quadratischen Aliasfehlers. Mit Hilfe dieser Verallgemeinerungen bietet die NFFT einen vereinheitlichten Zugang zu Teilchen-Gitter-Methoden. Insbesondere gemischt periodische Randbedingungen werden einheitlich behandelt und Versatz wird effizienter umgesetzt. Heuristiken für die Parameterwahl werden auf Basis sorgfältiger Fehlerabschätzungen angegeben.

The present thesis provides a modularized view on the structure of fast numerical methods for computing Coulomb interactions between charged particles in three-dimensional space. Thereby, the common structure is given in terms of three self-contained algorithmic frameworks that are built on top of each other, namely fast Fourier transform (FFT), nonequispaced fast Fourier transform (NFFT) and NFFT based particle-mesh methods (P²NFFT). For each of these frameworks algorithmic enhancement and parallel implementations are presented with special emphasis on scalability up to hundreds of thousands of parallel processes. In the context of FFT massively parallel algorithms are composed from hardware adaptive low level modules provided by the FFTW software library. The new algorithmic NFFT concepts include pruned NFFT, interlacing, analytic differentiation, and optimized deconvolution in Fourier space with respect to a mean square aliasing error. Enabled by these generalized concepts it is shown that NFFT provides a unified access to particle-mesh methods. Especially, mixed-periodic boundary conditions are handled in a consistent way and interlacing can be incorporated more efficiently. Heuristic approaches for parameter tuning are presented on the basis of thorough error estimates. / Die vorliegende Dissertation beschreibt einen modularisierten Blick auf die Struktur schneller numerischer Methoden für die Berechnung der Coulomb-Wechselwirkungen zwischen Ladungen im dreidimensionalen Raum. Die gemeinsame Struktur ist geprägt durch drei selbstständige und auf einander aufbauenden Algorithmen, nämlich der schnellen Fourier-Transformation (FFT), der nicht äquidistanten schnellen Fourier-Transformation (NFFT) und der NFFT-basierten Teilchen-Gitter-Methode (P²NFFT). Für jeden dieser Algorithmen werden Verbesserungen und parallele Implementierungen vorgestellt mit besonderem Augenmerk auf massiv paralleler Skalierbarkeit. Im Kontext der FFT werden parallele Algorithmen aus den Hardware adaptiven Modulen der FFTW Softwarebibliothek zusammengesetzt. Die neuen NFFT-Konzepte beinhalten abgeschnittene NFFT, Versatz, analytische Differentiation und optimierte Entfaltung im Fourier-Raum bezüglich des mittleren quadratischen Aliasfehlers. Mit Hilfe dieser Verallgemeinerungen bietet die NFFT einen vereinheitlichten Zugang zu Teilchen-Gitter-Methoden. Insbesondere gemischt periodische Randbedingungen werden einheitlich behandelt und Versatz wird effizienter umgesetzt. Heuristiken für die Parameterwahl werden auf Basis sorgfältiger Fehlerabschätzungen angegeben.