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 nonequispaced fast Fourier transform (NFFT) allows the fast approximate evaluation of trigonometric polynomials with frequencies supported on full box-shaped grids at arbitrary sampling nodes. Due to the curse of dimensionality, the total number of frequencies and thus, the total arithmetic complexity can already be very large for small refinements at medium dimensions. In this paper, we present an approach for the fast approximate evaluation of trigonometric polynomials with frequencies supported on an arbitrary subset of the full grid at arbitrary sampling nodes, which is based on Taylor expansion and rank-1 lattice methods. For the special case of symmetric hyperbolic cross index sets in frequency domain, we present error estimates and numerical results.

In this paper we describe a parallel algorithm for calculating nonequispaced fast Fourier transforms on massively parallel distributed memory architectures. These algorithms are implemented in an open source software library called PNFFT. Furthermore, we derive a parallel fast algorithm for the computation of the Coulomb potentials and forces in a charged particle system, which is based on the parallel nonequispaced fast Fourier transform. To prove the high scalability of our algorithms we provide performance results on a BlueGene/P system using up to 65536 cores.

We present a MPI based software library for computing the fast Fourier transforms on massively parallel, distributed memory architectures. Similar to established transpose FFT algorithms, we propose a parallel FFT framework that is based on a combination of local FFTs, local data permutations and global data transpositions. This framework can be generalized to arbitrary multi-dimensional data and process meshes. All performance relevant building blocks can be implemented with the help of the FFTW software library. Therefore, our library offers great flexibility and portable performance. Likewise FFTW, we are able to compute FFTs of complex data, real data and even- or odd-symmetric real data. All the transforms can be performed completely in place. Furthermore, we propose an algorithm to calculate pruned FFTs more efficiently on distributed memory architectures. For example, we provide performance measurements of FFTs of size 512^3 and 1024^3 up to 262144 cores on a BlueGene/P architecture.

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 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 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.

To measure the speed of a vehicle, the revolution of a wheel or a rigid axle is traditionally used. Therefore non corrigible systematic errors occur which are caused by slip, spin and by the change of wheel diameter due to fretting. Train control and traction systems require new robust as well as precise methods of speed measurement. Because of their physical properties, Doppler-radar-sensors attached to the vehicle and measuring ground speed are first choice for this range of applications. Currently used sensors cannot fulfil the high demands under all operating conditions, because they are unable to completely compensate the various interferences and systematic deviations. This is the starting point of this dissertation. Two independent diverse methods with optimised reliability and accuracy must be used to meet all requirements. Limited resources of the embedded digital signal processor system under real-time conditions have to be taken into account. According to the boundary conditions, the introductory chapters critically discuss the frequency analysis methods currently used and describe starting points for further development. This leads to the design of a new, robust, wide-band spectral analysis which combines techniques of the dyadic wavelet transformation with the fast Fourier transformation. At the same time a new frame procedure and general model for the estimation of motion parameters is developed which features short delays. The disadvantages of the block-based discrete spectral analysis applied over continuous approaches are extensively compensated. The block structure of spectral data enables the selective use of new knowledge-based spectral filters for the compensation of the remaining intense interferences which are typical of this kind of application. / Die Fahrzeuggeschwindigkeitsmessung über die Drehzahl eines Rades weist in Schlupf- und Schleuderzuständen erhebliche systematische Abweichungen auf. Deshalb erfordern Zugbeeinflussungs- und Antriebssysteme neue gleichzeitig robuste und präzise Geschwindigkeitsmessmethoden. Die Mikrowellensensorik unter Nutzung des Dopplereffekts zwischen Fahrzeug und Gleisbett wird wegen ihrer physikalischen Eigenschaften für dieses Einsatzgebiet favorisiert. Bisherige Sensorapplikationen erfüllen aber die hohen Ansprüche nicht in allen Betriebszuständen. Hier setzt die in dieser Arbeit beschriebene Sensorentwicklung auf. Zwei getrennt hergeleitete und nach Zuverlässigkeit und Genauigkeit optimierte neue Verfahren können bei gleichzeitiger Anwendung die gestellten Anforderungen erfüllen. Dabei müssen auch die beschränkten Ressourcen des eingebetteten digitalen Signalverarbeitungssystems unter Echtzeitbedingungen berücksichtigt werden. Entsprechend dieser Randbedingungen findet einleitend eine kritische Betrachtung bestehender Frequenzanalysemethoden statt und Ansätze für die Weiterentwicklung werden herausgearbeitet. Einerseits führt dies zur Konstruktion einer neuen störunempfindlichen Weitbereichsspektralzerlegung, welche Ansätze der dyadischen Wavelettransformation mit der Diskreten Fourier-Transformation verbindet. Andererseits wird ein neues Rahmenverfahren für die verzögerungsarme Schätzung der Bewegungsparameter des Fahrzeuges aufgrund seines physikalischen Bewegungsmodells hergeleitet und mit einem hochgenauen Frequenzauswerteverfahren kombiniert. Beide Verfahren basieren auf blockweisen diskreten Spektralzerlegungen, deren prinzipielle Nachteile gegenüber kontinuierlichen Ansätzen weitgehend kompensiert werden können. Durch die Blockorganisation lassen sich neuartige wissensbasierte Spektralfilter selektiv zur Unterdrückung starker bahnanwendungstypischer Störeinflüsse einsetzen.

By the help of several examples the interactive work with the ClassPad330 is considered. The student can solve difficult exercises of practical applications step by step using the symbolic calculation and the graphic possibilities of the calculator. Sometimes several fields of mathematics are combined to solve a problem. Let us consider the ClassPad330 (with the actual operating system OS 03.03) and discuss on some new exercises in analysis, e.g. solving a linear differential equation by the help of the Laplace transformation and using the inverse Laplace transformation or considering the Fourier transformation in discrete time (the Fast Fourier Transformation FFT and the inverse FFT). We use the FFT- and IFFT-function to study periodic signals, if we only have a sequence generated by sampling the time signal. We know several ways to get a solution. The techniques for studying practical applications fall into the following three categories: analytic, graphic and numeric. We can use the Classpad software in the handheld or in the PC (ClassPad emulator version of the handheld).

To measure the speed of a vehicle, the revolution of a wheel or a rigid axle is traditionally used. Therefore non corrigible systematic errors occur which are caused by slip, spin and by the change of wheel diameter due to fretting. Train control and traction systems require new robust as well as precise methods of speed measurement. Because of their physical properties, Doppler-radar-sensors attached to the vehicle and measuring ground speed are first choice for this range of applications. Currently used sensors cannot fulfil the high demands under all operating conditions, because they are unable to completely compensate the various interferences and systematic deviations. This is the starting point of this dissertation. Two independent diverse methods with optimised reliability and accuracy must be used to meet all requirements. Limited resources of the embedded digital signal processor system under real-time conditions have to be taken into account. According to the boundary conditions, the introductory chapters critically discuss the frequency analysis methods currently used and describe starting points for further development. This leads to the design of a new, robust, wide-band spectral analysis which combines techniques of the dyadic wavelet transformation with the fast Fourier transformation. At the same time a new frame procedure and general model for the estimation of motion parameters is developed which features short delays. The disadvantages of the block-based discrete spectral analysis applied over continuous approaches are extensively compensated. The block structure of spectral data enables the selective use of new knowledge-based spectral filters for the compensation of the remaining intense interferences which are typical of this kind of application. / Die Fahrzeuggeschwindigkeitsmessung über die Drehzahl eines Rades weist in Schlupf- und Schleuderzuständen erhebliche systematische Abweichungen auf. Deshalb erfordern Zugbeeinflussungs- und Antriebssysteme neue gleichzeitig robuste und präzise Geschwindigkeitsmessmethoden. Die Mikrowellensensorik unter Nutzung des Dopplereffekts zwischen Fahrzeug und Gleisbett wird wegen ihrer physikalischen Eigenschaften für dieses Einsatzgebiet favorisiert. Bisherige Sensorapplikationen erfüllen aber die hohen Ansprüche nicht in allen Betriebszuständen. Hier setzt die in dieser Arbeit beschriebene Sensorentwicklung auf. Zwei getrennt hergeleitete und nach Zuverlässigkeit und Genauigkeit optimierte neue Verfahren können bei gleichzeitiger Anwendung die gestellten Anforderungen erfüllen. Dabei müssen auch die beschränkten Ressourcen des eingebetteten digitalen Signalverarbeitungssystems unter Echtzeitbedingungen berücksichtigt werden. Entsprechend dieser Randbedingungen findet einleitend eine kritische Betrachtung bestehender Frequenzanalysemethoden statt und Ansätze für die Weiterentwicklung werden herausgearbeitet. Einerseits führt dies zur Konstruktion einer neuen störunempfindlichen Weitbereichsspektralzerlegung, welche Ansätze der dyadischen Wavelettransformation mit der Diskreten Fourier-Transformation verbindet. Andererseits wird ein neues Rahmenverfahren für die verzögerungsarme Schätzung der Bewegungsparameter des Fahrzeuges aufgrund seines physikalischen Bewegungsmodells hergeleitet und mit einem hochgenauen Frequenzauswerteverfahren kombiniert. Beide Verfahren basieren auf blockweisen diskreten Spektralzerlegungen, deren prinzipielle Nachteile gegenüber kontinuierlichen Ansätzen weitgehend kompensiert werden können. Durch die Blockorganisation lassen sich neuartige wissensbasierte Spektralfilter selektiv zur Unterdrückung starker bahnanwendungstypischer Störeinflüsse einsetzen.