In this work, the fast evaluation and reconstruction of multivariate trigonometric polynomials with frequencies supported on arbitrary index sets of finite cardinality is considered, where rank-1 lattices are used as spatial discretizations. The approximation of multivariate smooth periodic functions by trigonometric polynomials is studied, based on a one-dimensional FFT applied to function samples. The smoothness of the functions is characterized via the decay of their Fourier coefficients, and various estimates for sampling errors are shown, complemented by numerical tests for up to 25 dimensions. In addition, the special case of perturbed rank-1 lattice nodes is considered, and a fast Taylor expansion based approximation method is developed. One main contribution is the transfer of the methods to the non-periodic case. Multivariate algebraic polynomials in Chebyshev form are used as ansatz functions and rank-1 Chebyshev lattices as spatial discretizations. This strategy allows for using fast algorithms based on a one-dimensional DCT. The smoothness of a function can be characterized via the decay of its Chebyshev coefficients. From this point of view, estimates for sampling errors are shown as well as numerical tests for up to 25 dimensions. A further main contribution is the development of a high-dimensional sparse FFT method based on rank-1 lattice sampling, which allows for determining unknown frequency locations belonging to the approximately largest Fourier or Chebyshev coefficients of a function. / In dieser Arbeit wird die schnelle Auswertung und Rekonstruktion multivariater trigonometrischer Polynome mit Frequenzen aus beliebigen Indexmengen endlicher Kardinalität betrachtet, wobei Rang-1-Gitter (rank-1 lattices) als Diskretisierung im Ortsbereich verwendet werden. Die Approximation multivariater glatter periodischer Funktionen durch trigonometrische Polynome wird untersucht, wobei Approximanten mittels einer eindimensionalen FFT (schnellen Fourier-Transformation) angewandt auf Funktionswerte ermittelt werden. Die Glattheit von Funktionen wird durch den Abfall ihrer Fourier-Koeffizienten charakterisiert und mehrere Abschätzungen für den Abtastfehler werden gezeigt, ergänzt durch numerische Tests für bis zu 25 Raumdimensionen. Zusätzlich wird der Spezialfall gestörter Rang-1-Gitter-Knoten betrachtet, und es wird eine schnelle Approximationsmethode basierend auf Taylorentwicklung vorgestellt. Ein wichtiger Beitrag dieser Arbeit ist die Übertragung der Methoden vom periodischen auf den nicht-periodischen Fall. Multivariate algebraische Polynome in Chebyshev-Form werden als Ansatzfunktionen verwendet und sogenannte Rang-1-Chebyshev-Gitter als Diskretisierungen im Ortsbereich. Diese Strategie ermöglicht die Verwendung schneller Algorithmen basierend auf einer eindimensionalen DCT (diskreten Kosinustransformation). Die Glattheit von Funktionen kann durch den Abfall ihrer Chebyshev-Koeffizienten charakterisiert werden. Unter diesem Gesichtspunkt werden Abschätzungen für Abtastfehler gezeigt sowie numerische Tests für bis zu 25 Raumdimensionen. Ein weiterer wichtiger Beitrag ist die Entwicklung einer Methode zur Berechnung einer hochdimensionalen dünnbesetzten FFT basierend auf Abtastwerten an Rang-1-Gittern, wobei diese Methode die Bestimmung unbekannter Frequenzen ermöglicht, welche zu den näherungsweise größten Fourier- oder Chebyshev-Koeffizienten einer Funktion gehören.

Die Hauptthemen dieser Arbeit sind einerseits eine tiefgehende Analyse von nichtlinearen differential-algebraischen Gleichungen (DAEs) vom Index 2, die aus der modifizierten Knotenanalyse (MNA) von elektrischen Schaltkreisen hervorgehen, und andererseits die Entwicklung von Konvergenzkriterien für Waveform Relaxationsmethoden zum Lösen gekoppelter Probleme. Ein Schwerpunkt in beiden genannten Themen ist die Beziehung zwischen der Topologie eines Schaltkreises und mathematischen Eigenschaften der zugehörigen DAE. Der Analyse-Teil umfasst eine detaillierte Beschreibung einer Normalform für Schaltkreis DAEs vom Index 2 und Abschätzungen, die für die Sensitivität des Schaltkreises bezüglich seiner Input-Quellen folgen. Es wird gezeigt, wie diese Abschätzungen wesentlich von der topologischen Position der Input-Quellen im Schaltkreis abhängen. Die zunehmend komplexen Schaltkreise in technologischen Geräten erfordern oftmals eine Modellierung als gekoppeltes System. Waveform relaxation (WR) empfiehlt sich zur Lösung solch gekoppelter Probleme, da sie auf die Subprobleme angepasste Lösungsmethoden und Schrittweiten ermöglicht. Es ist bekannt, dass WR zwar bei Anwendung auf gewöhnliche Differentialgleichungen konvergiert, falls diese eine Lipschitz-Bedingung erfüllen, selbiges jedoch bei DAEs nicht ohne Hinzunahme eines Kontraktivitätskriteriums sichergestellt werden kann. Wir beschreiben allgemeine Konvergenzkriterien für WR auf DAEs vom Index 2. Für den Fall von Schaltkreisen, die entweder mit anderen Schaltkreisen oder mit elektromagnetischen Feldern verkoppelt sind, leiten wir außerdem hinreichende topologische Konvergenzkriterien her, die anhand von Beispielen veranschaulicht werden. Weiterhin werden die Konvergenzraten des Jacobi WR Verfahrens und des Gauss-Seidel WR Verfahrens verglichen. Simulationen von einfachen Beispielsystemen zeigen drastische Unterschiede des WR-Konvergenzverhaltens, abhängig davon, ob die Konvergenzbedingungen erfüllt sind oder nicht. / The main topics of this thesis are firstly a thorough analysis of nonlinear differential-algebraic equations (DAEs) of index 2 which arise from the modified nodal analysis (MNA) for electrical circuits and secondly the derivation of convergence criteria for waveform relaxation (WR) methods on coupled problems. In both topics, a particular focus is put on the relations between a circuit's topology and the mathematical properties of the corresponding DAE. The analysis encompasses a detailed description of a normal form for circuit DAEs of index 2 and consequences for the sensitivity of the circuit with respect to its input source terms. More precisely, we provide bounds which describe how strongly changes in the input sources of the circuit affect its behaviour. Crucial constants in these bounds are determined in terms of the topological position of the input sources in the circuit. The increasingly complex electrical circuits in technological devices often call for coupled systems modelling. Allowing for each subsystem to be solved by dedicated numerical solvers and time scales, WR is an adequate method in this setting. It is well-known that while WR converges on ordinary differential equations if a Lipschitz condition is satisfied, an additional convergence criterion is required to guarantee convergence on DAEs. We present general convergence criteria for WR on higher index DAEs. Furthermore, based on our results of the analysis part, we derive topological convergence criteria for coupled circuit/circuit problems and field/circuit problems. Examples illustrate how to practically check if the criteria are satisfied. If a sufficient convergence criterion holds, we specify at which rate of convergence the Jacobi and Gauss-Seidel WR methods converge. Simulations of simple benchmark systems illustrate the drastically different convergence behaviour of WR depending on whether or not the circuit topological convergence conditions are satisfied.

In this work, the fast evaluation and reconstruction of multivariate trigonometric polynomials with frequencies supported on arbitrary index sets of finite cardinality is considered, where rank-1 lattices are used as spatial discretizations. The approximation of multivariate smooth periodic functions by trigonometric polynomials is studied, based on a one-dimensional FFT applied to function samples. The smoothness of the functions is characterized via the decay of their Fourier coefficients, and various estimates for sampling errors are shown, complemented by numerical tests for up to 25 dimensions. In addition, the special case of perturbed rank-1 lattice nodes is considered, and a fast Taylor expansion based approximation method is developed. One main contribution is the transfer of the methods to the non-periodic case. Multivariate algebraic polynomials in Chebyshev form are used as ansatz functions and rank-1 Chebyshev lattices as spatial discretizations. This strategy allows for using fast algorithms based on a one-dimensional DCT. The smoothness of a function can be characterized via the decay of its Chebyshev coefficients. From this point of view, estimates for sampling errors are shown as well as numerical tests for up to 25 dimensions. A further main contribution is the development of a high-dimensional sparse FFT method based on rank-1 lattice sampling, which allows for determining unknown frequency locations belonging to the approximately largest Fourier or Chebyshev coefficients of a function. / In dieser Arbeit wird die schnelle Auswertung und Rekonstruktion multivariater trigonometrischer Polynome mit Frequenzen aus beliebigen Indexmengen endlicher Kardinalität betrachtet, wobei Rang-1-Gitter (rank-1 lattices) als Diskretisierung im Ortsbereich verwendet werden. Die Approximation multivariater glatter periodischer Funktionen durch trigonometrische Polynome wird untersucht, wobei Approximanten mittels einer eindimensionalen FFT (schnellen Fourier-Transformation) angewandt auf Funktionswerte ermittelt werden. Die Glattheit von Funktionen wird durch den Abfall ihrer Fourier-Koeffizienten charakterisiert und mehrere Abschätzungen für den Abtastfehler werden gezeigt, ergänzt durch numerische Tests für bis zu 25 Raumdimensionen. Zusätzlich wird der Spezialfall gestörter Rang-1-Gitter-Knoten betrachtet, und es wird eine schnelle Approximationsmethode basierend auf Taylorentwicklung vorgestellt. Ein wichtiger Beitrag dieser Arbeit ist die Übertragung der Methoden vom periodischen auf den nicht-periodischen Fall. Multivariate algebraische Polynome in Chebyshev-Form werden als Ansatzfunktionen verwendet und sogenannte Rang-1-Chebyshev-Gitter als Diskretisierungen im Ortsbereich. Diese Strategie ermöglicht die Verwendung schneller Algorithmen basierend auf einer eindimensionalen DCT (diskreten Kosinustransformation). Die Glattheit von Funktionen kann durch den Abfall ihrer Chebyshev-Koeffizienten charakterisiert werden. Unter diesem Gesichtspunkt werden Abschätzungen für Abtastfehler gezeigt sowie numerische Tests für bis zu 25 Raumdimensionen. Ein weiterer wichtiger Beitrag ist die Entwicklung einer Methode zur Berechnung einer hochdimensionalen dünnbesetzten FFT basierend auf Abtastwerten an Rang-1-Gittern, wobei diese Methode die Bestimmung unbekannter Frequenzen ermöglicht, welche zu den näherungsweise größten Fourier- oder Chebyshev-Koeffizienten einer Funktion gehören.

No description available.