We consider the problem of numerical integration, where one aims to approximate an integral of a given continuous function from the function values at given sampling points, also known as quadrature points. A useful framework for such an approximation process is provided by the theory of reproducing kernel Hilbert spaces and the concept of the worst case quadrature error. However, the computation of optimal quadrature points, which minimize the worst case quadrature error, is in general a challenging task and requires efficient algorithms, in particular for large numbers of points. The focus of this thesis is on the efficient computation of optimal quadrature points on the torus T^d, the sphere S^d, and the rotation group SO(3). For that reason we present a general framework for the minimization of the worst case quadrature error on Riemannian manifolds, in order to construct numerically such quadrature points. Therefore, we consider, for N quadrature points on a manifold M, the worst case quadrature error as a function defined on the product manifold M^N. For the optimization on such high dimensional manifolds we make use of the method of steepest descent, the Newton method, and the conjugate gradient method, where we propose two efficient evaluation approaches for the worst case quadrature error and its derivatives. The first evaluation approach follows ideas from computational physics, where we interpret the quadrature error as a pairwise potential energy. These ideas allow us to reduce for certain instances the complexity of the evaluations from O(M^2) to O(M log(M)). For the second evaluation approach we express the worst case quadrature error in Fourier domain. This enables us to utilize the nonequispaced fast Fourier transforms for the torus T^d, the sphere S^2, and the rotation group SO(3), which reduce the computational complexity of the worst case quadrature error for polynomial spaces with degree N from O(N^k M) to O(N^k log^2(N) + M), where k is the dimension of the corresponding manifold. For the usual choice N^k ~ M we achieve the complexity O(M log^2(M)) instead of O(M^2). In conjunction with the proposed conjugate gradient method on Riemannian manifolds we arrive at a particular efficient optimization approach for the computation of optimal quadrature points on the torus T^d, the sphere S^d, and the rotation group SO(3). Finally, with the proposed optimization methods we are able to provide new lists with quadrature formulas for high polynomial degrees N on the sphere S^2, and the rotation group SO(3). Further applications of the proposed optimization framework are found due to the interesting connections between worst case quadrature errors, discrepancies and potential energies. Especially, discrepancies provide us with an intuitive notion for describing the uniformity of point distributions and are of particular importance for high dimensional integration in quasi-Monte Carlo methods. A generalized form of uniform point distributions arises in applications of image processing and computer graphics, where one is concerned with the problem of distributing points in an optimal way accordingly to a prescribed density function. We will show that such problems can be naturally described by the notion of discrepancy, and thus fit perfectly into the proposed framework. A typical application is halftoning of images, where nonuniform distributions of black dots create the illusion of gray toned images. We will see that the proposed optimization methods compete with state-of-the-art halftoning methods.

In der Dissertationsschrift wird ein neuartiges Konzept der Realisierung der Direkten Digitalen Frequenzsynthese (DDS) vorgestellt. Ausgehend von der analysierten Literatur werden das Wirkprinzip eines Standard-DDS-Synthesizer analysiert und Möglichkeiten zur Aufwandsreduktion untersucht. Ein neuartiger Ansatz zur Realisierung einer vollständig digitalen DDS ergibt sich in der Anwendung der Pulse-Output-DDS. Bei der Pulse-Output-DDS wird neben dem D/A-Wandler auch die Sinus-ROM-Tabelle aus dem prinzipiellen Aufbau der Standard-DDS entfernt. Ausgehend von einer derart modifizierten DDS-Struktur wird ein geeignetes DDS-Modell entwickelt, mit welchem alle auftretenden Synthesefehler systematisch erfaßt und bewertet werden können. Die gewonnenen Erkenntnisse über die prinzipbedingten Synthesefehler bilden die Grundlage für Erweiterungen der Pulse-Output-DDS mit deren Hilfe eine qualitative Verbesserung des synthetisierten Signals erreicht wird. Dabei steht vor allem die Anwendung von Verfahren der digitalen Signalverarbeitung im Vordergrund, die zu einer Verringerung bzw. Kompensation oder zu einer spektralen Veränderung des auftretenden DDS-Fehlersignals geeignet sind. Es werden die erreichbaren Verbesserungen, aber auch die theoretischen und praktischen Grenzen von folgenden Verfahren aufgezeigt: absolute Verringerung des DDS-Fehlersignals Dithering des DDS-Fehlersignals Rauschformung (Noise-Shaping) des Fehlersignalspektrums Insbesondere bei der Rauschformung werden unterschiedliche Ansätze untersucht und bewertet mit dem Ziel, ein optimales Verfahren für den Rauschformungsprozeß bei der Verwendung in einer Pulse-Output-DDS zu finden. Durch die echtzeitfähige Implementation eines erweiterten DDS-Systems in einem Standard-CMOS-Prozeß werden die gefundenen theoretischen Lösungen verifiziert.

In der Dissertationsschrift wird ein neuartiges Konzept der Realisierung der Direkten Digitalen Frequenzsynthese (DDS) vorgestellt. Ausgehend von der analysierten Literatur werden das Wirkprinzip eines Standard-DDS-Synthesizer analysiert und Möglichkeiten zur Aufwandsreduktion untersucht. Ein neuartiger Ansatz zur Realisierung einer vollständig digitalen DDS ergibt sich in der Anwendung der Pulse-Output-DDS. Bei der Pulse-Output-DDS wird neben dem D/A-Wandler auch die Sinus-ROM-Tabelle aus dem prinzipiellen Aufbau der Standard-DDS entfernt. Ausgehend von einer derart modifizierten DDS-Struktur wird ein geeignetes DDS-Modell entwickelt, mit welchem alle auftretenden Synthesefehler systematisch erfaßt und bewertet werden können. Die gewonnenen Erkenntnisse über die prinzipbedingten Synthesefehler bilden die Grundlage für Erweiterungen der Pulse-Output-DDS mit deren Hilfe eine qualitative Verbesserung des synthetisierten Signals erreicht wird. Dabei steht vor allem die Anwendung von Verfahren der digitalen Signalverarbeitung im Vordergrund, die zu einer Verringerung bzw. Kompensation oder zu einer spektralen Veränderung des auftretenden DDS-Fehlersignals geeignet sind. Es werden die erreichbaren Verbesserungen, aber auch die theoretischen und praktischen Grenzen von folgenden Verfahren aufgezeigt: absolute Verringerung des DDS-Fehlersignals Dithering des DDS-Fehlersignals Rauschformung (Noise-Shaping) des Fehlersignalspektrums Insbesondere bei der Rauschformung werden unterschiedliche Ansätze untersucht und bewertet mit dem Ziel, ein optimales Verfahren für den Rauschformungsprozeß bei der Verwendung in einer Pulse-Output-DDS zu finden. Durch die echtzeitfähige Implementation eines erweiterten DDS-Systems in einem Standard-CMOS-Prozeß werden die gefundenen theoretischen Lösungen verifiziert.

We consider the problem of numerical integration, where one aims to approximate an integral of a given continuous function from the function values at given sampling points, also known as quadrature points. A useful framework for such an approximation process is provided by the theory of reproducing kernel Hilbert spaces and the concept of the worst case quadrature error. However, the computation of optimal quadrature points, which minimize the worst case quadrature error, is in general a challenging task and requires efficient algorithms, in particular for large numbers of points. The focus of this thesis is on the efficient computation of optimal quadrature points on the torus T^d, the sphere S^d, and the rotation group SO(3). For that reason we present a general framework for the minimization of the worst case quadrature error on Riemannian manifolds, in order to construct numerically such quadrature points. Therefore, we consider, for N quadrature points on a manifold M, the worst case quadrature error as a function defined on the product manifold M^N. For the optimization on such high dimensional manifolds we make use of the method of steepest descent, the Newton method, and the conjugate gradient method, where we propose two efficient evaluation approaches for the worst case quadrature error and its derivatives. The first evaluation approach follows ideas from computational physics, where we interpret the quadrature error as a pairwise potential energy. These ideas allow us to reduce for certain instances the complexity of the evaluations from O(M^2) to O(M log(M)). For the second evaluation approach we express the worst case quadrature error in Fourier domain. This enables us to utilize the nonequispaced fast Fourier transforms for the torus T^d, the sphere S^2, and the rotation group SO(3), which reduce the computational complexity of the worst case quadrature error for polynomial spaces with degree N from O(N^k M) to O(N^k log^2(N) + M), where k is the dimension of the corresponding manifold. For the usual choice N^k ~ M we achieve the complexity O(M log^2(M)) instead of O(M^2). In conjunction with the proposed conjugate gradient method on Riemannian manifolds we arrive at a particular efficient optimization approach for the computation of optimal quadrature points on the torus T^d, the sphere S^d, and the rotation group SO(3). Finally, with the proposed optimization methods we are able to provide new lists with quadrature formulas for high polynomial degrees N on the sphere S^2, and the rotation group SO(3). Further applications of the proposed optimization framework are found due to the interesting connections between worst case quadrature errors, discrepancies and potential energies. Especially, discrepancies provide us with an intuitive notion for describing the uniformity of point distributions and are of particular importance for high dimensional integration in quasi-Monte Carlo methods. A generalized form of uniform point distributions arises in applications of image processing and computer graphics, where one is concerned with the problem of distributing points in an optimal way accordingly to a prescribed density function. We will show that such problems can be naturally described by the notion of discrepancy, and thus fit perfectly into the proposed framework. A typical application is halftoning of images, where nonuniform distributions of black dots create the illusion of gray toned images. We will see that the proposed optimization methods compete with state-of-the-art halftoning methods.