Use of computer algebra in the calculation of Feynman diagrams

The increasing precision of current and future experiments in high-energy physics requires a likewise increase in the accuracy of the calculation of theoretical predictions, in order to find evidence for possible deviations of the generally accepted Standard Model of elementary particles and interactions. Calculating the experimentally measurable cross sections of scattering and decay processes to a higher accuracy directly translates into including higher order radiative corrections in the calculation. The large number of particles and interactions in the full Standard Model results in an exponentially growing number of Feynman diagrams contributing to any given process in higher orders. Additionally, the appearance of multiple independent mass scales makes even the calculation of single diagrams non-trivial. For over two decades now, the only way to cope with these issues has been to rely on the assistance of computers. The aim of the xloops project is to provide the necessary tools to automate the calculation procedures as far as possible, including the generation of the contributing diagrams and the evaluation of the resulting Feynman integrals. The latter is based on the techniques developed in Mainz for solving one- and two-loop diagrams in a general and systematic way using parallel/orthogonal space methods. These techniques involve a considerable amount of symbolic computations. During the development of xloops it was found that conventional computer algebra systems were not a suitable implementation environment. For this reason, a new system called GiNaC has been created, which allows the development of large-scale symbolic applications in an object-oriented fashion within the C++ programming language. This system, which is now also in use for other projects besides xloops, is the main focus of this thesis. The implementation of GiNaC as a C++ library sets it apart from other algebraic systems. Our results prove that a highly efficient symbolic manipulator can be designed in an object-oriented way, and that having a very fine granularity of objects is also feasible. The xloops-related parts of this work consist of a new implementation, based on GiNaC, of functions for calculating one-loop Feynman integrals that already existed in the original xloops program, as well as the addition of supplementary modules belonging to the interface between the library of integral functions and the diagram generator.

Theoretical studies of fluid membrane mechanics

Biologische Membranen sind Fettmolekül-Doppelschichten, die sich wie zweidimensionale Flüssigkeiten verhalten. Die Energie einer solchen fluiden Oberfläche kann häufig mit Hilfe eines Hamiltonians beschrieben werden, der invariant unter Reparametrisierungen der Oberfläche ist und nur von ihrer Geometrie abhängt. Beiträge innerer Freiheitsgrade und der Umgebung können in den Formalismus mit einbezogen werden. Dieser Ansatz wird in der vorliegenden Arbeit dazu verwendet, die Mechanik fluider Membranen und ähnlicher Oberflächen zu untersuchen. Spannungen und Drehmomente in der Oberfläche lassen sich durch kovariante Tensoren ausdrücken. Diese können dann z. B. dazu verwendet werden, die Gleichgewichtsposition der Kontaktlinie zu bestimmen, an der sich zwei aneinander haftende Oberflächen voneinander trennen. Mit Ausnahme von Kapillarphänomenen ist die Oberflächenenergie nicht nur abhängig von Translationen der Kontaktlinie, sondern auch von Änderungen in der Steigung oder sogar Krümmung. Die sich ergebenden Randbedingungen entsprechen den Gleichgewichtsbedingungen an Kräfte und Drehmomente, falls sich die Kontaktlinie frei bewegen kann. Wenn eine der Oberflächen starr ist, muss die Variation lokal dieser Fläche folgen. Spannungen und Drehmomente tragen dann zu einer einzigen Gleichgewichtsbedingung bei; ihre Beiträge können nicht mehr einzeln identifiziert werden. Um quantitative Aussagen über das Verhalten einer fluiden Oberfläche zu machen, müssen ihre elastischen Eigenschaften bekannt sein. Der "Nanotrommel"-Versuchsaufbau ermöglicht es, Membraneigenschaften lokal zu untersuchen: Er besteht aus einer porenüberspannenden Membran, die während des Experiments durch die Spitze eines Rasterkraftmikroskops in die Pore gedrückt wird. Der lineare Verlauf der resultierenden Kraft-Abstands-Kurven kann mit Hilfe der in dieser Arbeit entwickelten Theorie reproduziert werden, wenn der Einfluss von Adhäsion zwischen Spitze und Membran vernachlässigt wird. Bezieht man diesen Effekt in die Rechnungen mit ein, ändert sich das Resultat erheblich: Kraft-Abstands-Kurven sind nicht länger linear, Hysterese und nichtverschwindende Trennkräfte treten auf. Die Voraussagen der Rechnungen könnten in zukünftigen Experimenten dazu verwendet werden, Parameter wie die Biegesteifigkeit der Membran mit einer Auflösung im Nanometerbereich zu bestimmen. Wenn die Materialeigenschaften bekannt sind, können Probleme der Membranmechanik genauer betrachtet werden. Oberflächenvermittelte Wechselwirkungen sind in diesem Zusammenhang ein interessantes Beispiel. Mit Hilfe des oben erwähnten Spannungstensors können analytische Ausdrücke für die krümmungsvermittelte Kraft zwischen zwei Teilchen, die z. B. Proteine repräsentieren, hergeleitet werden. Zusätzlich wird das Gleichgewicht der Kräfte und Drehmomente genutzt, um mehrere Bedingungen an die Geometrie der Membran abzuleiten. Für den Fall zweier unendlich langer Zylinder auf der Membran werden diese Bedingungen zusammen mit Profilberechnungen kombiniert, um quantitative Aussagen über die Wechselwirkung zu treffen. Theorie und Experiment stoßen an ihre Grenzen, wenn es darum geht, die Relevanz von krümmungsvermittelten Wechselwirkungen in der biologischen Zelle korrekt zu beurteilen. In einem solchen Fall bieten Computersimulationen einen alternativen Ansatz: Die hier präsentierten Simulationen sagen voraus, dass Proteine zusammenfinden und Membranbläschen (Vesikel) bilden können, sobald jedes der Proteine eine Mindestkrümmung in der Membran induziert. Der Radius der Vesikel hängt dabei stark von der lokal aufgeprägten Krümmung ab. Das Resultat der Simulationen wird in dieser Arbeit durch ein approximatives theoretisches Modell qualitativ bestätigt.

Efficient parallel proximity queries and an application to highly complex motion planning problems with many narrow passages

In vielen Bereichen der industriellen Fertigung, wie zum Beispiel in der Automobilindustrie, wer- den digitale Versuchsmodelle (sog. digital mock-ups) eingesetzt, um die Entwicklung komplexer Maschinen m ̈oglichst gut durch Computersysteme unterstu ̈tzen zu k ̈onnen. Hierbei spielen Be- wegungsplanungsalgorithmen eine wichtige Rolle, um zu gew ̈ahrleisten, dass diese digitalen Pro- totypen auch kollisionsfrei zusammengesetzt werden k ̈onnen. In den letzten Jahrzehnten haben sich hier sampling-basierte Verfahren besonders bew ̈ahrt. Diese erzeugen eine große Anzahl von zuf ̈alligen Lagen fu ̈r das ein-/auszubauende Objekt und verwenden einen Kollisionserken- nungsmechanismus, um die einzelnen Lagen auf Gu ̈ltigkeit zu u ̈berpru ̈fen. Daher spielt die Kollisionserkennung eine wesentliche Rolle beim Design effizienter Bewegungsplanungsalgorith- men. Eine Schwierigkeit fu ̈r diese Klasse von Planern stellen sogenannte “narrow passages” dar, schmale Passagen also, die immer dort auftreten, wo die Bewegungsfreiheit der zu planenden Objekte stark eingeschr ̈ankt ist. An solchen Stellen kann es schwierig sein, eine ausreichende Anzahl von kollisionsfreien Samples zu finden. Es ist dann m ̈oglicherweise n ̈otig, ausgeklu ̈geltere Techniken einzusetzen, um eine gute Performance der Algorithmen zu erreichen.rnDie vorliegende Arbeit gliedert sich in zwei Teile: Im ersten Teil untersuchen wir parallele Kollisionserkennungsalgorithmen. Da wir auf eine Anwendung bei sampling-basierten Bewe- gungsplanern abzielen, w ̈ahlen wir hier eine Problemstellung, bei der wir stets die selben zwei Objekte, aber in einer großen Anzahl von unterschiedlichen Lagen auf Kollision testen. Wir im- plementieren und vergleichen verschiedene Verfahren, die auf Hu ̈llk ̈operhierarchien (BVHs) und hierarchische Grids als Beschleunigungsstrukturen zuru ̈ckgreifen. Alle beschriebenen Verfahren wurden auf mehreren CPU-Kernen parallelisiert. Daru ̈ber hinaus vergleichen wir verschiedene CUDA Kernels zur Durchfu ̈hrung BVH-basierter Kollisionstests auf der GPU. Neben einer un- terschiedlichen Verteilung der Arbeit auf die parallelen GPU Threads untersuchen wir hier die Auswirkung verschiedener Speicherzugriffsmuster auf die Performance der resultierenden Algo- rithmen. Weiter stellen wir eine Reihe von approximativen Kollisionstests vor, die auf den beschriebenen Verfahren basieren. Wenn eine geringere Genauigkeit der Tests tolerierbar ist, kann so eine weitere Verbesserung der Performance erzielt werden.rnIm zweiten Teil der Arbeit beschreiben wir einen von uns entworfenen parallelen, sampling- basierten Bewegungsplaner zur Behandlung hochkomplexer Probleme mit mehreren “narrow passages”. Das Verfahren arbeitet in zwei Phasen. Die grundlegende Idee ist hierbei, in der er- sten Planungsphase konzeptionell kleinere Fehler zuzulassen, um die Planungseffizienz zu erh ̈ohen und den resultierenden Pfad dann in einer zweiten Phase zu reparieren. Der hierzu in Phase I eingesetzte Planer basiert auf sogenannten Expansive Space Trees. Zus ̈atzlich haben wir den Planer mit einer Freidru ̈ckoperation ausgestattet, die es erlaubt, kleinere Kollisionen aufzul ̈osen und so die Effizienz in Bereichen mit eingeschr ̈ankter Bewegungsfreiheit zu erh ̈ohen. Optional erlaubt unsere Implementierung den Einsatz von approximativen Kollisionstests. Dies setzt die Genauigkeit der ersten Planungsphase weiter herab, fu ̈hrt aber auch zu einer weiteren Perfor- mancesteigerung. Die aus Phase I resultierenden Bewegungspfade sind dann unter Umst ̈anden nicht komplett kollisionsfrei. Um diese Pfade zu reparieren, haben wir einen neuartigen Pla- nungsalgorithmus entworfen, der lokal beschr ̈ankt auf eine kleine Umgebung um den bestehenden Pfad einen neuen, kollisionsfreien Bewegungspfad plant.rnWir haben den beschriebenen Algorithmus mit einer Klasse von neuen, schwierigen Metall- Puzzlen getestet, die zum Teil mehrere “narrow passages” aufweisen. Unseres Wissens nach ist eine Sammlung vergleichbar komplexer Benchmarks nicht ̈offentlich zug ̈anglich und wir fan- den auch keine Beschreibung von vergleichbar komplexen Benchmarks in der Motion-Planning Literatur.