In dieser Dissertation werden algorithmische Verbesserungen und Varianten für Simulationen der zwei-Flavor Gitter QCD mit dynamischen Fermionen studiert. Der O(a)-verbesserte Dirac-Wilson-Operator wird im Schrödinger Funktional mit einem Update des Hybrid Monte Carlo (HMC)-Typs verwendet. Sowohl der Hermitische als auch der nicht-Hermitische Operator werden betrachtet. Für den Hermitischen Dirac-Wilson-Operator untersuchen wir die Vorteile des symmetrischen gegenüber dem asymmetrischen Gerade-Ungerade-Präkonditionierens, wie man von einem mehr Zeitskalen-Integrator profitieren kann, sowie die Auswirkungen der kleinsten Eigenwerte auf die Stabilität des HMC Algorithmus. Im Fall des nicht-Hermitischen Operators leiten wir eine (semi)-analytische Schranke für das Spektrum her und zeigen eine Methode, um Informationen über den spektralen Rand zu gewinnen, indem wir komplexe Eigenwerte mit dem Lanczos-Algorithmus abschätzen. Diese spektralen Ränder erlauben es, Vorzüge des symmetrischen Gerade-Ungerade-Präkonditionierens oder den Effekt des Sheikholeslami-Wohlert-Terms für das Spektrum des nicht-Hermitischen Operators zu zeigen. Unter Verwendung der Informationen des spektralen Randes konstruieren wir angepasste, komplexe, skalierte und verschobene Tschebyschow Polynome zur Approximation des inversen Dirac-Wilson-Operators. Basierend auf diesen Polynomen entwickeln wir eine neue HMC-Variante, genannt nicht-Hermitischer polynomialer Hybrid Monte Carlo (NPHMC). Sie erlaubt, vom Importance Sampling unter Kompensation mit einem Gewichtungsfaktor abzuweichen. Zudem wird eine Erweiterung durch Anwendung des Hasenbusch-Tricks abgeleitet. Erste Größen der Leistungsfähigkeit, die die Abhängingkeit von den Eingabeparametern als auch einen Vergleich mit unserem Standard-HMC zeigen, werden präsentiert. Im Vergleich der beiden ein-Pseudofermion-Varianten ist der neue NPHMC etwas besser; eine eindeutige Aussage im Fall der zwei-Pseudofermion-Variante ist noch nicht möglich. / In this thesis algorithmic improvements and variants for two-flavor lattice QCD simulations with dynamical fermions are studied using the O(a)-improved Dirac-Wilson operator in the Schrödinger functional setup and employing a hybrid Monte Carlo-type (HMC) update. Both, the Hermitian and the Non-Hermitian operator are considered. For the Hermitian Dirac-Wilson operator we investigate the advantages of symmetric over asymmetric even-odd preconditioning, how to gain from multiple time scale integration as well as how the smallest eigenvalues affect the stability of the HMC algorithm. In case of the non-Hermitian operator we first derive (semi-)analytical bounds on the spectrum before demonstrating a method to obtain information on the spectral boundary by estimating complex eigenvalues with the Lanzcos algorithm. These spectral boundaries allow to visualize the advantage of symmetric even-odd preconditioning or the effect of the Sheikholeslami-Wohlert term on the spectrum of the non-Hermitian Dirac-Wilson operator. Taking advantage of the information of the spectral boundary we design best-suited, complex, scaled and translated Chebyshev polynomials to approximate the inverse Dirac-Wilson operator. Based on these polynomials we derive a new HMC variant, named non-Hermitian polynomial Hybrid Monte Carlo (NPHMC), which allows to deviate from importance sampling by compensation with a reweighting factor. Furthermore an extension employing the Hasenbusch-trick is derived. First performance figures showing the dependence on the input parameters as well as a comparison to our standard HMC are given. Comparing both algorithms with one pseudo-fermion, we find the new NPHMC to be slightly superior, whereas a clear statement for the two pseudo-fermion variants is yet not possible.

Am Beispiel verschiedener Strömungstypen wird die Stabilität von Strömungen unter Einfluß eines Temperaturfeldes untersucht. Eine reguläre Störungs- rechnung wird durchgeführt, um die Effekte temperatur- abhängiger Stoffwerte systematisch und allgemein- gültig erfassen zu können. Die Ergebnisse werden in Form asymptotischer Reihen für die kritischen Kenn- zahlen der jeweiligen Probleme angegeben. Sowohl die Orr-Sommerfeld-Gleichungen als auch die PSE-Gleichungen, jeweils mit variablen Stoffwerten, kommen bei der Untersuchung von Grenzschicht- strömungen zum Einsatz. Von besonderem Interesse sind hier die Unterschiede in den Lösungen beider mathematischer Modelle bezüglich der Effekte variabler Stoffwerte. Es zeigt sich, dass die Differenzen in den Lösungen beider Theorien für den Fall konstanter und für den Fall variabler Stoffwerte gleich groß sind. Für die Grenzschichtströmung bei natürlicher Kon- vektion an einer beheizten vertikalen Wand werden die vollständigen PSE-Gleichungen gelöst. Hier zeigen sich starke Abweichungen zur lokalen paral- lelen Theorie (Orr--Sommerfeld--Gleichungen).

Markov-type inequalities provide upper bounds on the norm of the (higher order) derivative of an algebraic polynomial in terms of the norm of the polynomial itself. The present thesis considers the cases in which the norms are of the Laguerre, Gegenbauer, or Hermite type, with respective weights chosen differently on both sides of the inequality. An answer is given to the question on the best constant so that such an inequality is valid for every polynomial of degree at most n. The demanded best constant turns out to be the operator norm of the differential operator. The latter conicides with the tractable spectral norm of its matrix representation in an appropriate set of orthonormal bases. The methods to determine these norms vary tremendously, depending on the difference of the parameters accompanying the weights. Up to a very small gap in the parameter range, asymptotics for the best constant in each of the aforementioned cases are given. / Markovungleichungen liefern obere Schranken an die Norm einer (höheren) Ableitung eines algebraischen Polynoms in Bezug auf die Norm des Polynoms selbst. Diese vorliegende Arbeit betrachtet den Fall, dass die Normen vom Laguerre-, Gegenbauer- oder Hermitetyp sind, wobei die entsprechenden Gewichte auf beiden Seiten unterschiedlich gewählt werden. Es wird die kleinste Konstante bestimmt, sodass diese Ungleichung für jedes Polynom vom Grad höchstens n erfüllt ist. Die gesuchte kleinste Konstante kann als die Operatornorm des Differentialoperators dargestellt werden. Diese fällt aber mit der Spektralnorm der Matrixdarstellung in einem Paar geeignet gewählter Orthonormalbasen zusammen und kann daher gut behandelt werden. Zur Abschätzung dieser Normen kommen verschiedene Methoden zum Einsatz, die durch die Differenz der in den Gewichten auftretenden Parameter bestimmt werden. Bis auch eine kleine Lücke im Parameterbereich wird das asymptotische Verhalten der kleinsten Konstanten in jedem der betrachteten Fälle ermittelt.

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.

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.

We consider multivariate trigonometric polynomials with frequencies supported on a fixed but arbitrary frequency index set I, which is a finite set of integer vectors of length d. Naturally, one is interested in spatial discretizations in the d-dimensional torus such that - the sampling values of the trigonometric polynomial at the nodes of this spatial discretization uniquely determines the trigonometric polynomial, - the corresponding discrete Fourier transform is fast realizable, and - the corresponding fast Fourier transform is stable. An algorithm that computes the discrete Fourier transform and that needs a computational complexity that is bounded from above by terms that are linear in the maximum of the number of input and output data up to some logarithmic factors is called fast Fourier transform. We call the fast Fourier transform stable if the Fourier matrix of the discrete Fourier transform has a condition number near one and the fast algorithm does not corrupt this theoretical stability. We suggest to use rank-1 lattices and a generalization as spatial discretizations in order to sample multivariate trigonometric polynomials and we develop construction methods in order to determine reconstructing sampling sets, i.e., sets of sampling nodes that allow for the unique, fast, and stable reconstruction of trigonometric polynomials. The methods for determining reconstructing rank-1 lattices are component{by{component constructions, similar to the seminal methods that are developed in the field of numerical integration. During this thesis we identify a component{by{component construction of reconstructing rank-1 lattices that allows for an estimate of the number of sampling nodes M |I|\le M\le \max\left(\frac{2}{3}|I|^2,\max\{3\|\mathbf{k}\|_\infty\colon\mathbf{k}\in I\}\right) that is sufficient in order to uniquely reconstruct each multivariate trigonometric polynomial with frequencies supported on the frequency index set I. We observe that the bounds on the number M only depends on the number of frequency indices contained in I and the expansion of I, but not on the spatial dimension d. Hence, rank-1 lattices are suitable spatial discretizations in arbitrarily high dimensional problems. Furthermore, we consider a generalization of the concept of rank-1 lattices, which we call generated sets. We use a quite different approach in order to determine suitable reconstructing generated sets. The corresponding construction method is based on a continuous optimization method. Besides the theoretical considerations, we focus on the practicability of the presented algorithms and illustrate the theoretical findings by means of several examples. In addition, we investigate the approximation properties of the considered sampling schemes. We apply the results to the most important structures of frequency indices in higher dimensions, so-called hyperbolic crosses and demonstrate the approximation properties by the means of several examples that include the solution of Poisson's equation as one representative of partial differential equations.

We consider multivariate trigonometric polynomials with frequencies supported on a fixed but arbitrary frequency index set I, which is a finite set of integer vectors of length d. Naturally, one is interested in spatial discretizations in the d-dimensional torus such that - the sampling values of the trigonometric polynomial at the nodes of this spatial discretization uniquely determines the trigonometric polynomial, - the corresponding discrete Fourier transform is fast realizable, and - the corresponding fast Fourier transform is stable. An algorithm that computes the discrete Fourier transform and that needs a computational complexity that is bounded from above by terms that are linear in the maximum of the number of input and output data up to some logarithmic factors is called fast Fourier transform. We call the fast Fourier transform stable if the Fourier matrix of the discrete Fourier transform has a condition number near one and the fast algorithm does not corrupt this theoretical stability. We suggest to use rank-1 lattices and a generalization as spatial discretizations in order to sample multivariate trigonometric polynomials and we develop construction methods in order to determine reconstructing sampling sets, i.e., sets of sampling nodes that allow for the unique, fast, and stable reconstruction of trigonometric polynomials. The methods for determining reconstructing rank-1 lattices are component{by{component constructions, similar to the seminal methods that are developed in the field of numerical integration. During this thesis we identify a component{by{component construction of reconstructing rank-1 lattices that allows for an estimate of the number of sampling nodes M |I|\le M\le \max\left(\frac{2}{3}|I|^2,\max\{3\|\mathbf{k}\|_\infty\colon\mathbf{k}\in I\}\right) that is sufficient in order to uniquely reconstruct each multivariate trigonometric polynomial with frequencies supported on the frequency index set I. We observe that the bounds on the number M only depends on the number of frequency indices contained in I and the expansion of I, but not on the spatial dimension d. Hence, rank-1 lattices are suitable spatial discretizations in arbitrarily high dimensional problems. Furthermore, we consider a generalization of the concept of rank-1 lattices, which we call generated sets. We use a quite different approach in order to determine suitable reconstructing generated sets. The corresponding construction method is based on a continuous optimization method. Besides the theoretical considerations, we focus on the practicability of the presented algorithms and illustrate the theoretical findings by means of several examples. In addition, we investigate the approximation properties of the considered sampling schemes. We apply the results to the most important structures of frequency indices in higher dimensions, so-called hyperbolic crosses and demonstrate the approximation properties by the means of several examples that include the solution of Poisson's equation as one representative of partial differential equations.