Umfang:

€ 440,– pro Monat (netto)

Dauer:

maximal 12 Monate

Wofür bekomme ich ein SFB-Stipendium?

Zur Unterstützung beim Bearbeiten eines SFB-nahen Themas. (Betreuer der Master-Arbeit muss ein SFB-Projektleiter sein.)

Vergabe von SFB-Stipendien:

Schriftliche Bewerbung inklusive Lebenslauf und Beschreibung des Master-Projekts bis spätestens
    31. Dezember 2006
an den Institutsvorstand Prof. Peter Paule schicken.

Adresse:
SpezialForschungsBereich F013
an der Johannes Kepler Universität Linz
zH. Herr Prof. Peter Paule

Altenbergerstr. 69
4040 Linz

Stand: Oktober 2006

F1301, F1302, F1303, F1304, F1305, F1306, F1309, F1315,

F1301 / F1305

Integraldarstellungen zur Berechnung von kombinatorischen Summen in Mathematica
(P. Paule)

G.P. Egorychev hat eine Methode vorgestellt, welche kombinatorische Summen (z.B. Summationen ueber Binomialkoeffizienten) in Integrale transformiert. Diese Integrale koennen dann mittels Substitution bzw. Residuen-Kalkuel vereinfacht werden. Das Ziel der Diplomarbeit ist es, diese Methode zur Vereinfachung von Summen auf den Computer zu bringen. Entsprechende Algorithmen sollen in Mathematica implementiert werden.
Zitat: Egorychev, G. P.: Integral Representation and the Computation of Combinatorial Sums, vol. 59 of Translations of Mathematical Monographs. American Mathematical Society, Providence, Rhode Island, 1984.

Nullstellenberechnung mittels Mellin-Reihen
(P. Paule)

Nullstellen von algebraischen Gleichungen koennen durch multivariate Potenzreihen (sog. Mellin-Reihen) in Potenzprodukten der Koeffizienten ausgedrueckt werden. Solche Darstellungen gehen auf Lagrange zurueck und wurden vor einigen Jahren "wiederentdeckt". Im Rahmen der Diplomarbeit sollen solche Darstellungen genauer untersucht werden, insbesondere auf ihre numerische Anwendbarkeit.

Symbolisches Lösen von Differentialgleichungen a la Frobenius
(P. Paule)

Lineare Differentialgleichungen mit polynomiellen Koeffizienten lassen sich im allgemeinen nicht in "geschlossener Form" loesen, weshalb man an alternativen Loesungsdarstellungen interessiert ist. Eine moegliche Alternative bietet die Methode von Frobenius, mit der sich Potenzreihenloesungen von Differentialgleichungen finden lassen. In einer Diplomarbeit soll untersucht werden, ob und wie sich auf der Grundlage der Frobeniusmethode ein automatisierbares Verfahren zur exakten Loesung von Differentialgleichungen in Potenzreihen gewinnen laesst.

Euler-Maclaurin Expansion von Symbolischen Summen
(P. Paule)

Die Formel von Euler-Maclaurin bietet eine Moeglichkeit, das asymptotische Verhalten von Folgen zu bestimmen, die durch Summenausdruecke definiert sind. Eines der Ziele der Diplomarbeit koennte sein, eine Klasse von Summen zu finden, fuer die sich auf der Grundlage dieser Formel ein algorithmisches Verfahren angeben laesst, mit dem die Asymptotik einer Folge automatisch bestimmt werden kann.

Exaktes Lösen von voll besetzten linearen Gleichungssystemen
(P. Paule)

Man interessiert sich aus verschiedenen Gruenden fuer die Loesungsraeume von linearen Gleichungssystemen mit rationalen Zahlen (oder rationalen Funktionen) als Koeffizienten. Fuer den Fall duenn besetzter Systeme stehen verschiedene Loesungsmethoden zur Verfuegung, mit denen Loesungsraeume effizient bestimmt werden koennen. Eine Diplomarbeit koennte sich mit der Behandlung von Systemen befassen, die nicht duenn besetzt sind. Einige Loesungsmethoden, die aktuell in der Diskussion stehen, waeren hinsichtlich ihrer effektiven Effizienz miteinander zu vergleichen.

F1302

Natural style proving in predicate logic
(T. Jebelean)

Development and implementation of methods for proving in first order and in higher-order predicate logic, which are similar to human proving methods.

Special proving methods for problems arising in program verification
(T. Jebelean)

Development, refinement and implementation of special proving methods for proof problems which arise in the context of verification of functional and imperative programs.

Integration of automated reasoning with algebraic algorithms
(T. Jebelean)

Development, refinement, and implementation of proof methods which use special algebraic algorithms (Groebner Bases, Cylindrical Algebraic Decomposition, combinatorial techniques, etc.).

Logical based synthesis of algorithms
(T. Jebelean)

Development and implementation of systematic methods for the automatic synthesis of algorithms and programs starting from the logical specification of their behaviour.

Proof carrying code
(T. Jebelean)

Development and implementation of specific techniques for the representation in a hierarchical manner of proofs (including special inference rules) which can be communicated together with programs in order to certify their correct behaviour.

Interactive proving
(T. Jebelean)

Design and implementation of generic techniques for interactive proving using special inference engines.

Programmtransformation von Praedikatenlogik nach Java: Logische Funktoren in der Algebra
(B. Buchberger, M. Rosenkranz)

Das Theorema-System - koordiniert von Prof. Buchberger am RISC ? ist ein integriertes Framework zum Beweisen, Rechnen und Loesen in allen Bereichen der Mathematik, verbunden durch die universelle Sprache der Praedikatenlogik. Von besonderer Wichtigkeit ist die Angabe ("Programmierung") und Durchfuehrung ("Exekution") von generischen Rechnungen in der Algebra mit Hilfe von sogenannten Funktoren. Um dabei eine hohe Effizienz sicherzustellen, sollen relevante Teile der praedikatenlogischen Programme in aequivalenten Java-Code uebersetzt werden.

Generische Implementierung diverser Polynombegriffe in Theorema
(B. Buchberger, M. Rosenkranz)

Es gibt in der Algebra diverse Varianten von Polynombegriffen - kommutative sowie allerlei nichtkommutative. Es handelt sich bei diesem Projekt darum, relevante Polynom-Manipulationen in generischer Weise im Rahmen des Theorema-Systems - koordiniert von Prof. Buchberger ? zu implementieren. Dabei ist die logisch einwandfreie Fundierung ebenso wichtig wie Effizienzfragen; letztere sind im Zusammenhang mit dem bereits laufenden Projekt eines Java-Uebersetzers zu behandeln.

Zwischen Groebnerbasen und Knuth-Bendix: Konfluente Reduktionen fuer generische Polynombereiche
(B. Buchberger, M. Rosenkranz)

Der Buchberger-Algorithmus zum Auffinden von Groebnerbasen und der Knuth-Bendix-Algorithmus zum Saettigen von Gleichungstheorien sind wohl die bedeutendsten Vertreter der Familie von CPC-Algorithmen (CPC = critical pair / completion); eventuell - obwohl von etwas anderer Natur - mag man hier auch noch Robinsons Resolutionsalgorithmus nennen. Zwischen dem Buchberger- und dem Knuth-Bendix-Algorithmus liegt ein weites Spektrum an Kompletierungsalgorithmen fuer allerlei "verallgemeinerte Polynome", auf denen eine einheitliche Systematik und Implementierung von grosser praktischer Wichtigkeit ist. Der zentrale Gedanke ist hier stets, die vorgegebene "Reduktion" (= Vereinfachung von polynomialen Gleichungen durch Einsetzen anderer solcher Gleichungen) "konfluent" zu machen (= es ist letztlich egal was man wo einsetzt).

F1303

Berechnung des Geschlechts einer Algebraischen Kurve mit Numerischen Koeffizienten
(J. Schicho)

Gegeben sei ein Polynom in zwei Variablen über dem Körper der komplexen Zahlen. Gesucht ist das Geschlecht der Kurve. Für dieses Problem gibt es bereits exakte Algorithmen, die auf der Analyse der Singularitäten beruhen. Die Lösung des numerischen Problems könnte auf einer Diplomarbeit von S. Kusper (Univ. Linz) aufbauen, die eine numerische Methode zur Analyse der Singularitäten enthält.

Klassifikation der mehrfachen Kreisflächen in Räumen beliebiger Dimension
(J. Schicho)

Eine Fläche - mit Ausnahme der Ebene und der Kugel - besitzt höchstens 6 erzeugende Scharen von Kreisen. In Räumen höherer Dimension lassen sich allerdings Flächen finden, die mehr solche Scharen besitzen. Aufbauend auf einer Arbeit aus dem Jahr 2001, die die Klassifikation von mehr-fachen Kegelschnittflächen in beliebiger Dimension enthält, sollen die mehrfachen Kreisflächen unter diesen herausgesucht und dargestellt werden.

Kurvenparametrisierung unter Ausnutzung des Newton-Polygons
(J. Schicho)

In einer Zusammenarbeit von T. Beck und J. Schicho sind kürzlich Algorithmen zur Parametrisierung ebener algebraischer Kurven entwickelt worden, die die Struktur der gegebenen Gleichung ausnützen. Thema dieser Arbeit ist es, diese Algorithmen zu implementieren und vergleichende Experimente anzustellen.

F1304

Moving algebraic curves in geometric design
(F. Winkler)

Implicitization and parametrization are central topics in computer aided geometric design. They can be solved by plain methods in elimination theory, but usually at a high cost. The concept of "moving" algebraic curves has been suggested by Sederberg et al. as an alternative method for implicitizing rational curves. The method of Sederberg should be investigated, programmed, and tested for practical examples.
T.Sederberg, R.Goldman, H.Du, "Implicitizing rational curves by the method of moving algebraic curves", J. Symbolic Computation 23/2&3, 153-175 (1997)

Blending of algebraic surfaces
(F. Winkler)

In geometric design, objects are usually modelled as a collection of surfaces. However, in many cases one wants to form a composite object whose surface is smooth. This question leads to the blending problem. In fact, a blending surface is a surface that provides a smooth transition between distinct geometric features of an object. In such a thesis, problems and existing methods should be explained and selected algorithms implemented in a computer algebra system.
S.Perez-Diaz, J.R.Sendra, "Computing all parametric solutions for blending surfaces", J. Symbolic Computation 36/6, 925-964 (2003)

Diophantine equation solving via parametrization
(F. Winkler)

In Diophantine equation solving we are looking for points on algebraic curves (and surfaces) with coordinates in the integers Z. Such problems can be solved if a parametric representation of the curve can be determined. The method of Poulakis based on the parametrization algorithm of Sendra and Winkler should be closely analyzed and implemented.
D.Poulakis, E.Vokos, "On the practical solution of genus zero diophantine equations", J. Symbolic Computation 30/5, 573-582 (2000) and an accompanying paper of 2002

Solving algebraic ordinary differential equations via parametrization
(F. Winkler)

An algebraic ODE can be written as F(y0,y1,...,yn)=0, where F is a polynomial and yi denotes the i-th derivation of y. Recently Feng and Gao gave necessary and sufficient conditions for an algebraic ODE to have a rational type general solution. Solution algorithms can be constructed based on the relation between rational solutions of a first order ODE and rational parametrizations of the plane algebraic curve defined by this ODE. Mathematical analysis and implementation of the solution algorithm is the goal.
R.Feng, X.-S.Gao, "Rational general solutions of algebraic ODEs", Proceedings ISSAC 2004, 155-162 (2004)

Algorithmic factorization of linear PDEs
(F. Winkler)

If we can factor the operator L= L1*L2 defining a linear partial differential equation, then we can facilitate the solution of the corresponding PDE. Recently Grigoriev and Schwarz have described a completely algebraic algorithm for deciding the factorization of such an operator, and for actually finding a factorization if it exists. In my research group we have been improving and generalizing this algorithm. The algorithm of Grigoriev and Schwarz should be explained and implemented in a computer algebra system.
D.Grigoriev, F.Schwarz, "Factoring and solving linear PDEs", Computing 73/2, 179-197 (2004)

F1306

Nested iteration strategies for 2D elastic-plastic problems
(U. Langer)

Nested iteration strategies allow an elegant incorporation of extrapolation techniques, adaptivity and fast solvers into the solution process for the corresponding variational inequality describing the quasistatic elastic-plastic deformation process.

Boundary Element based Finite Element Approximation to non-linear problems
(U. Langer)

The boundary element method allows the efficient construction of finite element Galerkin schemes with harmonic basis functions on very general meshes. The efficient construction of such finite element equations and the investigation of the convergence properties are some topics which can be studied in the diploma thesis.

F1309

Preconditioners and Krylov Subspace Methods for KKT Systems
(W. Zulehner)

Solution of optimization problems with equality constraints have to satisfy a system of equations, the so-called Karush-Kuhn-Tucker (KKT) system. Here we are interested in large scale sparse KKT systems. Such systems typically result from the discretization of optimization problem which involves partial differential equations. A specific property of a KKT system is that it is an indefinite block-structured system. An efficient solver requires a good preconditioner in combination with an appropriate acceleration technique (Krylov subspace methods). Several classes of methods have been proposed in literature. The task in the thesis is to describe and analyze these methods in a common framework and to compare their numerical behavior for typical applications.
If required this topic can easily and quite naturally be distributed to several master theses.

F1315

Wavelets für implizit definierte Kurven
(B. Jüttler, M. Kapl)

Zur hierarchischen Darstellung implizit definierter Kurven und Flächen wurde eine neue Klasse von Wavelet-artigen Spline-Basen entwickelt. Diese erlauben es, die Verteilung des Fehlers bei der Vergröberung der Darstellung besser an die Geometrie anzupassen. Dazu werden L2-Räume mit einem inneren Produkt betrachtet, bei dem die Gewichtsfunktion nicht konstant ist. In der zu bearbeitenden Diplomarbeit soll diese Wavelet-artige Darstellung für konkrete Anwendungen, wie beispielsweise Kompression, hierarchischem Editieren usw., eingesetzt werden, um so die Möglichkeiten und Grenzen dieses neuen Werkzeuges zu untersuchen.
Literatur: Manuskript zu den Wavelet-artigen Spline-Basen (bei Herrn Kapl erhältlich)

Einsatz von effizienten geometrischen Lösern für polynomiale Gleichungssysteme in der numerischen Simulation
(B. Jüttler, U. Langer)

Im Rahmen des Teilprojektes 15 wurden effiziente geometrische Lösungsverfahren entwickelt, mit denen sich alle Lösungen eines polynomialen Gleichungsystems aus d Gleichungen im d-dimensionalen Einheitswürfel finden lassen. Im Rahmen eines numerischen Simulationsproblems im Bereich der direkten Probleme besteht das Bedürfnis, durch ein effizientes Verfahren alle positiven Lösungen eines Systems zweier Gleichungen zu ermitteln. In der zu bearbeitenden Diplomarbeit soll der geometrische Lösungsalgorithmus auf diesen Fall übertragen und in den Algorithmus zur numerischen Simulation eingebunden werden.
Literatur: M. Barton und B. Juettler, SFB Report (2006), Computing roots of polynomials by quadratic clipping, www.sfb013.uni-linz.ac.at

Approximation mittels Evolution für geometrische Grundobjekte
(B. Jüttler, M. Aigner)

Für Freiformkurven und -flächen läßt sich die Approximation von Punktwolken als ein Evolutionsprozeß formulieren, bei dem die Normalgeschwindigkeit der Datenfußpunkte von deren Entfernung zu den gegebenen Punkten bestimmt ist. Die approximierende Kurve bzw. Fläche "schwimmt" gewissermaßen im Distanzfeld der gegebenen Meßpunkte. Dieses Verfahren wurden bereits eingehend untersucht und sollen nun auf geometrische Grundobjekte, wie natürliche Quadriken (Kugeln, Kreiskegel und -zylinder) übertragen werden.
Literatur: Hybrid curve fitting, bei Herrn Aigner erhältlich