Personal tools

SC²S Colloquium - June 2, 2008

From Sccswiki

Jump to: navigation, search
Date: June 2
Room: 02.07.023
Time: 2 pm, s.t.

Contents

14:00 Uhr - Johannes Hölzl: Automatischer Korrektheisbeweis von Algorithmen zur Hierarchischen Basistransformation (IDP)

Bereits einfache Algorithmen, die auf dünnen Gittern arbeiten, sind sehr komplex und mehrfach rekursiv. Sie basieren meist auf Traversierungen des Baumes der hierarchischen Basisfunktionen. Ein typischer, komplexer Algorithmus ist das sogenannte Up-Down-Verfahren, das zur Berechnung des Laplace-Operators einer Dünngitterfunktion benötigt wird. Aufgrund der hohen Komplexität der verschachtelt rekursiven Algorithmen ist es sehr mühsam, fehleranfällig und zeitaufwändig, derartige Dünngitteralgorithmen erfolgreich zu implementieren.

Daher sollte im Rahmen dieses IDPs die Korrektheit eines ersten Dünngitteralgorithmus mithilfe des Isabelle Systems interaktiv bewiesen werden. Die gewonnenen Erkenntnisse und Theoreme können dann für verwandte Algorithmen meist mit relativ geringem Aufwand angepasst werden. Im Vortrag werden der Up-Down-Algorithmus und die Funktionsweise von Isabelle erklärt sowie der erfolgreiche Beweis des Up-Down Algorithmus vorgestellt.


14:45 Uhr - Benjamin Peherstorfer: Adaptive Sparse Grid Representation for Indicator Functions (BA)

Für carakteristische Funktionen achsparalleler Rechtecke wird die Genauigkeit der Bestapproximation in Dünngitterräumen untersucht. Hierfür wird die Menge der durch die approximierte Funktion falsch zugeordneten Punkte bestimmt. Der untersuchte Ansatz nutzt Eigenschaften der Dünngitter-Repräsentation aus, um eine möglichst gute Approximation der Höhenlinie, die der Rechtecksgrenze entspricht, zu errechnen. In diesem Zusammenhang wurden die beiden Verfahren "Marching Squares" und "Quad Squares" implementiert. Um den Fehler zu bestimmen, wird die Fläche zwischen Soll-Linie und approximierter Höhenlinie bestimmt. Dadurch ist schließlich eine Gegenüberstellung von Fehler und Level des benutzten Gitters, Aufwand des Verfahrens oder Verfeinerungsgrad des Gitters möglich.


15:15 Uhr - Marcin Salaterski: Storing Results of Parameterised CFD Simulations Using Sparse Grid Techniques (MA)

Applications and simulations that depend on results of other simulations have the disadvantage that each "function evaluation" equals a whole run of a simulation, which is usually costly in time and resources. For example, simulating the behaviour of a car may need simulations of the tyres which again depend on multiple parameters, like the condition of the roadbed, the diameter of the wheel, the tyre tread pattern and the current speed. It would be advantageous to simulate the tyres for many combinations of the parameters in advance (i.e. do many function evaluations), to store the results and to interpolate between the function evaluations, when a simulation result is needed.

The current Masters Thesis is a first prototype on how sparse grids can achieve this for a simple CFD simulation. The driven cavity, based on the CFD lab code, was simulated for different parameter settings at the LRZ Linux Cluster. The results of the sparse grid interpolation is shown.


15:40 Uhr - Deepak Pandey: Regression with Spatially Adaptive Sparse Grids in Financial Applications (MA)

The aim of Regression is to identify and model dependencies between a dependent variable and one or multiple independent variables in numerical data. Regression techniques compute a "best fit" to the data with regard to some metrik. Mostly, least squares or related measures are used to determine the quality of the fit. Given a function space, the function that best fits the data is to be identified.

Spatially adaptive sparse grids shall be examined for the estimation of "best fit" functions with respect to the least square measure. This is needed in financial applications, for example in path dependent options, such as the American option. Especially non-smoothness and extrapolation into areas with few points have to be dealt with.