PD. Dr. Martin Kreuzer WS 2001/2002 Fakultät für Mathematik Universität Regensburg

Übungen zur Vorlesung “Computeralgebra für Naturwissenschaftler”

Tutorium 6: Integer Programming

Das Ziel dieses Tutoriums ist es, die in Abschnitt 17 der Vorlesung vorgestellten Algorithmen zu implementieren, an konkreten Beispielen auszuprobieren, und zu optimieren. Gegeben seien eine Matrix A = (a_{ij}) ∈ Mat_{m,n}(ℕ) und ein Vektor b ∈ ℕ^{n}. Ferner sei K ein Körper, sei P = K[x_{1}, …, x_{n}], sei Q = K[x_{1}, …, x_{n}, y_{1}, …, y_{m}], und sei J ⊆ Q das von {x_{1} − t_{1}, …, x_{n} − t_{n}} mit t_{i} = y_{1}^{a_{1i}} ⋯ y_{m}^{a_{mi}} erzeugte Ideal.

a) Schreiben Sie eine CoCoA-Funktion DioSysSolve(…), die als Eingabe die Matrix A und den Vektor b erwartet. Die Funktion soll zuerst prüfen, ob das Diophantische Gleichungssystem S : A · (z_{1}, …, z_{n})^{transp.} = b lösbar ist und in diesem Fall dann eine Lösung von S berechnen.

b) Wenden Sie Ihre Funktion DioSysSolve(…) in den folgenden Fällen an:

1) ( \begin{matrix}3 & 1 & 11 & 2 & 3 \\ 4 & 5 & 0 & 1 & 7 \\ 5 & 6 & 1 & 9 & 2 \end{matrix} ) ( z_{1} ; ⋮ ; z_{5} ) = ( \begin{matrix}20 \\ 17 \\ 23 \end{matrix} )

2) ( \begin{matrix}3 & 1 & 11 & 2 & 3 \\ 4 & 5 & 0 & 1 & 7 \\ 5 & 6 & 1 & 9 & 2 \end{matrix} ) ( z_{1} ; ⋮ ; z_{5} ) = ( \begin{matrix}20 \\ 17 \\ 21 \end{matrix} )

3) ( \begin{matrix}3 & 1 & 11 & 2 & 3 & 5 & 3 \\ 4 & 5 & 0 & 1 & 7 & 4 & 6 \\ 5 & 6 & 1 & 9 & 2 & 3 & 3 \end{matrix} ) ( z_{1} ; ⋮ ; z_{7} ) = ( \begin{matrix}31 \\ 27 \\ 38 \end{matrix} )

c) Berechnen Sie das Eliminationsideal J ∩ P in den folgenden Fällen mit Hilfe des eingebauten Befehls Elim(…).

1) A_{1} = ( \begin{matrix}3 & 1 & 11 & 2 & 3 & 5 & 3 & 5 \\ 4 & 5 & 0 & 1 & 7 & 4 & 6 & 2 \\ 5 & 6 & 1 & 9 & 2 & 3 & 3 & 1 \end{matrix} )

2) A_{2} = ( \begin{matrix}1 & 4 & 9 & 5 & 8 & 7 & 3 & 3 & 6 & 7 \\ 1 & 6 & 2 & 4 & 4 & 1 & 2 & 4 & 0 & 4 \\ 4 & 3 & 4 & 4 & 3 & 6 & 6 & 5 & 2 & 9 \\ 3 & 1 & 9 & 6 & 9 & 7 & 1 & 9 & 2 & 9 \\ 9 & 7 & 0 & 6 & 3 & 9 & 2 & 0 & 8 & 4 \end{matrix} )

3) A_{3} = ( \begin{matrix}4 & 3 & 3 & 3 & 2 & 2 & 2 & 2 & 2 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 2 & 1 & 1 & 0 & 0 & 0 & 3 & 2 & 2 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 2 & 1 & 0 & 0 & 1 & 0 & 2 & 1 & 0 & 3 & 2 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 2 & 0 & 0 & 1 & 0 & 1 & 2 & 0 & 1 & 2 & 3 \end{matrix}

\begin{matrix}0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 4 & 3 & 3 & 2 & 2 & 2 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 2 & 0 & 1 & 3 & 2 & 1 & 0 & 4 & 3 & 2 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 2 & 0 & 1 & 2 & 3 & 0 & 1 & 2 & 3 & 4 \end{matrix} )

d) Verwenden Sie die in CoCoA eingebaute Funktion LinKer(…) sowie die Beschreibung von J ∩ P als I_{L} : (x_{1} ⋯ x_{n})^{∞}, um eine CoCoA-Funktion Toric(…) zu schreiben, die das Ideal J ∩ P effizient berechnet. Wenden Sie Ihre Funktion in den Fällen von c) an und vergleichen Sie die Timings. Hinweis: Die Funktion LinKer(…) ist nicht deterministisch. Wenden Sie sie mindestens achtmal an, um verschiedene ℤ-Basen von L zu erzeugen.

e) Seien f_{1}, …, f_{s} ∈ P. Zeigen Sie, dass für jedes Ideal I ⊆ P gilt

I : (f_{1} ⋯ f_{s})^{∞} = (⋯ ((I : (f_{1})^{∞}) : (f_{2})^{∞}) ⋯) : (f_{s})^{∞}

f) Seien f_{1}, …, f_{s}, g_{1}, …, g_{t} ∈ P. Ferner sei I ⊆ P ein Ideal, das das Polynom f_{1} ⋯ f_{s} − g_{1} ⋯ g_{t} enthalte. Beweisen Sie die Formel

I : (f_{1} ⋯ f_{s} · g_{1} ⋯ g_{t})^{∞} = I : (f_{1} ⋯ f_{s})^{∞}

g) Optimieren Sie ihre Funktion Toric(…), indem Sie die Resultate der beiden vorhergehenden Aufgaben anwenden. Vergleichen Sie die Timings der neuen Funktion ToricOpt(…) wieder in den Fällen von c).