This dissertation investigates the application of multivariate Chebyshev polynomials in the algebraic signal processing theory for the development of FFT-like algorithms for discrete cosine transforms on weight lattices of compact Lie groups. After an introduction of the algebraic signal processing theory, a multivariate Gauss-Jacobi procedure for the development of orthogonal transforms is proven. Two theorems on fast algorithms in algebraic signal processing, one based on a decomposition property of certain polynomials and the other based on induced modules, are proven as multivariate generalizations of prior theorems. The definition of multivariate Chebyshev polynomials based on the theory of root systems is recalled. It is shown how to use these polynomials to define discrete cosine transforms on weight lattices of compact Lie groups. Furthermore it is shown how to develop FFT-like algorithms for these transforms. Then the theory of matrix-valued, multivariate Chebyshev polynomials is developed based on prior ideas. Under an existence assumption a formula for generating functions of these matrix-valued Chebyshev polynomials is deduced. / Diese Dissertation beschäftigt sich mit der Anwendung multivariater Tschebyschow-Polynome in der algebraischen Signalverarbeitungstheorie im Hinblick auf die Entwicklung FFT-artiger Algorithmen für diskrete Kosinus-Transformationen auf Gewichts-Gittern kompakter Lie-Gruppen. Nach einer Einführung in die algebraische Signalverarbeitungstheorie wird eine multivariate Gauss-Jacobi Prozedur für die Entwicklung orthogonaler Transformationen bewiesen. Zwei Theoreme über schnelle Algorithmen in der algebraischen Signalverarbeitung, eines basierend auf einer Dekompositionseigenschaft gewisser Polynome, das andere basierend auf induzierten Moduln, werden als multivariate Verallgemeinerungen vorgängiger Theoreme bewiesen. Die Definition multivariater Tschebyschow-Polynome basierend auf der Theorie der Wurzelsysteme wird vergegenwärtigt. Es wird gezeigt, wie man diese Polynome nutzen kann um diskrete Kosinustransformationen auf den Gewichts-Gittern kompakter Lie-Gruppen zu definieren. Des Weiteren wird gezeigt, wie man FFT-artige Algorithmen für diese Transformationen entwickeln kann. Sodann wird die Theorie Matrix-wertiger, multivariater Tschebyschow-Polynome basierend auf vorgängigen Ideen entwickelt. Unter einer Existenz-Annahme wird eine Formel für die erzeugenden Funktionen dieser Matrix-wertigen Tschebyschow-Polynome hergeleitet

No description available.

The display of an Airy function via an optical image processing technique is demonstrated. Using a two-dimensional object with a cubic amplitude transmittance, one can observe a Fourier transformed image of which intensity variation is identical to that of the Airy function. A lens system is used to achieve the Fourier transformation of the object which is a two-dimensional binary filter. A set of computer simulations are performed prior to the optical experiments. Using the same method of optical display, the transient wave propagation in a dispersive medium is optically displayed based on the analogous relationship found between two equations: One is the Fourier form of a transient wave field propagating in a dispersive medium and the other is an equation of the diffraction pattern of an object constructed with two juxtaposed two-dimensional filters. A theoretical analysis is provided along with computer simulations. The use of a Spatial Light Modulator is proposed as the source of the input object in the optical experiment. / Master of Science

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

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.

Made available in DSpace on 2014-10-09T12:52:08Z (GMT). No. of bitstreams: 0 / Made available in DSpace on 2014-10-09T13:58:01Z (GMT). No. of bitstreams: 0 / Tese (Doutoramento) / IPEN/T / Instituto de Pesquisas Energeticas e Nucleares - IPEN/CNEN-SP

Made available in DSpace on 2014-10-09T12:35:59Z (GMT). No. of bitstreams: 0 / Made available in DSpace on 2014-10-09T13:59:37Z (GMT). No. of bitstreams: 0 / Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) / Tese (Doutoramento) / IPEN/T / Instituto de Pesquisas Energeticas e Nucleares - IPEN-CNEN/SP / FAPESP:08/57338-5