Seminarleitung: Dr. Martin Kreuzer, Zi. M 003, Tel. 943 -3036

Anmeldung per E-Mail: <Martin Kreuzer@mathematik.uni-regensburg.de>

Termin, Ort: Mi, 8:30 - 10:00, Raum M 101

Nr. im Vorlesungsverzeichnus:  51078

Inhalt:  Die Vorträge behandeln Anwendungen der Computeralgebra in der Industrie und der Technik. Zuerst wird ein konkretes Problem vorgestellt. Dann wird gezeigt, wie man es mathematisch beschreibt. Die mathematische Aufgabe wird auf ein Problem der Computeralgebra zurückgeführt, das mit Hilfe der Theorie der Gröbner-Basen gelöst werden kann. Neben einer elementaren Einführung sollen jeweils Lösungsansätze mittels CoCoA programmiert werden.

Voraussetzung: Grundkenntnisse in Computeralgebra und CoCoAL.

Vorträge

1. 9.6.99: Computeralgebra in der 2-stufigen stochastischen Programmierung (A. Zellner)

Literatur: a) F.V. Louveaux und M.H.v.d. Vlerk, Sochastic programming with simple integer recourse, Math. Programming 61A (1993), S. 301-325
b) R. Schultz, L. Stougie und M.H.v.d. Vlerk, Solving stochastic programming with integer recourse by enumeration: A framework using Gröbner basis reductions, Math. Programming 83A (1998), S. 229-252
c) S. Vajda, Probabilistic Programming, Academic Press, New York 1972
Inhalt: Die 2-stufige stochstische Programmierung befaßt sich mit folgender Aufgabe: Manche Daten eines Problems sind noch mit Unsicherheiten behaftet. Dennoch muß man gewisse Entscheidungen ("first-stage decisions") treffen. Wenn die gesuchten Informationen später eintreffen, hat man die Möglichkeit zu Korrekturmaßnahmen ("second-stage or recourse actions"), die jedoch mit Defizitstrafen oder Überschüssen behaftet sein können. Bei der ganzzahligen stochastischen Programmierung treten dabei Systeme auf, deren Zielfunktionen mit Hilfe von Gröbner-Basen ausgewertet werden können.

Ausführliche Vortragsbeschreibung: <casemi.ps>
Zugehörige CoCoA-Programme:     <casemi.coc>
 

2. 16.6.99: Computeralgebra in der Analyse komplexer Informationssysteme (T. Eisenmann)

Literatur: X.H. Kramer und R.C. Laubenbacher, Combinatorial Homotopy of Simplicial Complexes and Complex Information Systems, in: D.A. Cox und B. Sturmfels (Hrsg.), Applications of Computational Algebraic Geometry, Proc. Symp. Applied Math. 53, Amer. Math. Soc., Providence 1998, S. 91-118
Inhalt: Ein komplexes Informationssystem besteht aus einer großen Anzahl von "Agenten", die mit nahegelegenen anderen Agenten auf Grund lokaler Informationen kommunizieren. Das dynamische Verhalten des Gesamtsystems hängt von strukturellen Beschränkungen des Informationsflusses ab (z.B. bei der Planung von Verkehrsflüssen). Solche globalen Beschränkungen kann man mit der sogenannten Q-Analyse studieren, und ebenso mit Hilfe der kombinatorischen Homotopie. Letztere kann mit Hilfe von Gröbner-Basen in freien assoziativen Algebren berechnet werden.

Ausführliche Vortragsbeschreibung: <compl_is.htm>
 

3. 23.6.99, 30.6.99: Computeralgebra in der Ablaufplanung (C. Jung)

Literatur: a) N.R.Natraj, S.R.Tayur und R.R.Thomas, An algebraic geometry algorithm for scheduling in the presence of setups and correlated demands, Math. Programming 69A, S. 369-401
b) G.M. Ziegler, Gröbner Bases and Integer Programming, in: A.M. Cohen, H. Cuypers und H. Sterk (Hrsg.), Some Tapas of Computer Algebra, Algorithms and Computation in Mathematics 4, Springer, Berlin 1999, S. 168-183
c) B. Sturmfels, Algorithms in Invariant Theory, Springer, Wien 1993, S. 19-23
Inhalt: In der Ablaufplanung (engl. "scheduling") soll eine Menge von Aufgaben auf Maschinen verschiedener Typen zeitlich geplant werden, wobei die Nachfrage durch unkorrellierte Zufallsvariable beschrieben werde. Dabei ist der Zeit- und Kapazitätsverlust durch Maschinenumstellungen minimal zu halten. Das Problem wird formuliert als eine Aufgabe der ganzzahligen Programmierung (engl. "integer programming"), d.h. für eine Menge linearer Gleichungen und Ungleichungen sind diejenigen ganzzahligen Lösungen zu finden, die ein bestimmtes lineares Funktional minimieren. Die Lösung erfolgt mit Hilfe einer geeigneten Version von Buchberger's Algorithmus unter Berechnung einer reduzierten Gröbner-Basis.

Ausführliche Vortragsbeschreibung: <ablaufpl.htm>
Zugehörige CoCoA-Programme:     <ablaufpl.coc>
 

4. 7.7.99: Computeralgebra im Computer Aided Geometric Design (CAGD) (A. Wills)

Literatur: a) T.W. Sederberg, Applications to Computer Aided Geometric design, in: D.A. Cox und B. Sturmfels (Hrsg.), Applications of Computational Algebraic Geometry, Proc. Symp. Applied Math. 53, Amer. Math. Soc., Providence 1998, S. 69-89
b) F. Winkler, Polynomial Algorithms in Computer Algebra, Springer, Wien 1996, S. 224-236
Inhalt: Will man Kurven und Flächen im CAGD darstellen, so verwendet man fast ausschließlich durch rationale polynomiale Parametrisierungen gegebene Objekte. Allerdings besteht dabei das Problem, daß es zwischen den Polynomen der Parametrisierung und dem geometrischen Aussehen der Objekte keine offensichtlichen Beziehungen gibt. Dieses Problem kann mit Bezier-Kurven (und -Flächen) gelöst werden. Um das Verschwindungsideal der Kurven zu finden, ist ein Implizitisierungsprozeß nötig, der mit Hilfe von Eliminationen durchgeführt wird. Auch der umgekehrte Vorgang - die Parametrisierung - wird besprochen.
 
5. 14.7.99: Computeralgebra in der Robotik (L. Görlitz)

Literatur: a) D. Cox, J. Little und D. O'Shea, Ideals, Varieties, and Algorithms, Springer Undergraduate Texts in Mathematics, New York 1992, Chapter 6, § 1 - 3
b) M.J. Gonzalez-Lopez und L. Gonzalez-Vega, The Inverse Kinematics Problem in Robotics, in: A.M. Cohen, H. Cuypers und H. Sterk (Hrsg.), Some Tapas of Computer Algebra, Algorithms and Computation in Mathematics 4, Springer, Berlin 1999, S. 305-310
Inhalt: Beim inversen kinematischen Problem geht es darum, zu einem explizit beschriebenen Roboterarm und einer Position festzustellen, ob der Roboterarm diese Position erreichen kann, ob die Lösung eindeutig ist, und wie man sie berechnen kann. Es ergibt sich ein Gleichungssystem, das die Sinus bzw. Cosinus der Winkel der Roboterarme enthält und durch eine rationale Parametrisierung in ein polynomiales Gleichungssystem umgewandelt werden kann. Es werden auch kinematische Singularitäten und Bewegungsplanung besprochen.

Ausführliche Vortragsbeschreibung: <robotik.htm>
 

6. 21.7.99, 28.7.99: Computeralgebra in der Computergraphik (J. Schmidbauer)

Literatur: a) B.A. Barksy, Computer Graphics and Geometric Modeling Using Beta-Splines, Springer, Berlin 1988
b) H. Späth, Spline-Algorithmen zur Konstruktion glatter Kurven und Flächen, R. Oldenburg Verlag, München 1973
c) D. Cox, J. Little und D. O'Shea, Using Algebraic Geometry, Graduate Texts in Math. 185, Springer, New York 1998, S. 385-406
Inhalt: Möchte man kompizierte Kurven oder Flächen graphisch veranschaulichen, so werden sie zuerst mit Hilfe sogenannter Splines approximiert, und dann werden diese gezeichnet. Dabei unterscheidet man zwischen interpolierenden und approximierenden Splines. Bei den interpolierenden Splines besteht ein Trade-Off zwischen dem Grad der Splines und der Güte der Approximation. Die Untersuchung des Moduls aller Splines erfolgt unter Anwendung der Computeralgebra.

Ausführliche Vortragsbeschreibung: <compgraf.html>
Zugehörige CoCoA-Programme:     <splines.coc>
 
7. Computeralgebra in der statistischen Designtheorie

Literatur: Robbiano, Gröbner Bases and Statistics, in: B. Buchberger und F. Winkler (Hrsg.), Gröbner Bases and Applications, London Math. Soc. Lecture Notes 251, Cambridge Univ. Press 1998, S. 179ff
Inhalt: Beim Design von Experimenten versucht man, aus möglichst wenigen experimentellen Daten gewisse Informationen herauszuholen. Da man typischerweise nicht alle möglichen Konstellationen der entscheidenden Faktoren durchspielen kann, gilt es einige Fälle so zu konstruieren, daß die entsprechenden Versuchsergebnisse bereits die gewünschten Schüsse zulassen. Algebraisch gesehen läuft das Problem darauf hinaus, aus einer endlichen Punktmenge eine Teilmenge so auszuwählen, daß die Ideale aller Polynome, die auf der Teilmenge verschwinden, bestimmte Eigenschaften haben.
 
8. Computeralgebra im Triebwerksdesign

Literatur: Grabmeier, An application of a symbolic version of the Raleigh-Ritz method to the design of aircraft turbines, Preprint 1995
Inhalt: Während des Erhärtungsprozesses bei der Herstellung von Flugzeugtriebwerken treten Temperaturdifferenzen auf, die zu Materialspannungen führen und Verbiegungen auslösen können. Das Problem kann mit Differentialgleichungen beschrieben werden, die numerisch lösbar sind. Es soll jedoch schon beim Design des Triebwerks eine optimale Form gefunden werden, d.h. die Gleichungen sind symbolisch (mit unbestimmten Koeffizienten) zu lösen. Dazu wird die Raleigh-Ritz Methode angewandt, bei der ein Energiefunktional minimiert werden muß. Das entstehende System polynomialer Gleichungen wird mit Gröbner-Basen gelöst.
 
9. Computeralgebra in der Festigkeitslehre

Literatur: a) W. Törnig, M. Gipsen und B. Kasper, Numerische Lösung von partiellen Differentialgleichungen der Technik, B.G. Teubner, Stuttgart 1985
b) D. Cox, J. Little und D. O'Shea, Using Algebraic Geometry, Graduate Texts in Math. 185, Springer, New York 1998, S. 385-406
Inhalt: Viele Probleme der Festigkeitslehre werden durch (elliptische) Differentialgleichungen beschrieben. Will man diese mit der Methode der finiten Elemente lösen, so zerlegt man das Definitionsgebiet zuerst in Dreiecke, setzt die gesuchte physikalische Größe als polynomiale Funktion über jedem Dreieck an, und fügt diese lokalen Ansätze zu einer globalen Ansatzfunktion (einem "Spline") zusammen. Die Zuordnung von Werten zu den Ecken ("Knoten") der Dreiecke liefert Gleichungen, deren Lösungsmenge ("Freiheitsgrade") bestimmt werden soll. Möglichst viele der verwendeten Schritte sollen symbolisch, d.h. mit unbestimmten Koeffizienten, ausgeführt werden.
 
10. Computeralgebra in der Analyse zyklischer Moleküle

Literatur: I.Z. Emiris, Sparse Elimination and Applications in Kinematics, Doctoral Dissertation, Univ. of California at Berkeley, Berkeley 1994 (erhältlich via www.inria.fr/saga)
Inhalt: Möchte man die geometrische Struktur komplexer zyklische Moleküle herausfinden, so stößt man auf das "Docking Problem", d.h. auf die Frage wie sich ein Molekül an einen Rezeptor anlagern kann. Die Berechnung aller energetisch günstigen Konfigurationen zyklische Moleküle zeigt sich als äquivalent zum inversen kinematischen Problem und wird mit Hilfe der Technik der "Sparse Elimination" (Elimination im dünnbesetzten Fall) gelöst. Im Fall sechsatomiger Moleküle wird die Aufgabe explizit ausgearbeitet.