Representations of lattice point sets [Elektronische Ressource] : theory, algorithms, applications / von Raymond Hemmecke

Sujets

• Mathematics

Informations

• Publié par: otto-von-guericke-universitat_magdeburg
• Publié le: 01 janvier 2006
• Nombre de lectures: 30
• Langue: Deutsch
• Poids de l'ouvrage: 1 Mo

Extrait

Representations of lattice point sets
Theory, Algorithms, Applications
Habilitationsschrift
zur Erlangung des akademischen Grades
doctor rerum naturalium habilitatus (Dr. rer. nat. habil.)
genehmigt
durch die Fakult¨at f¨ur Mathematik
der Otto-von-Guericke-Universit¨at Magdeburg
von Dr. Raymond Hemmecke
geb. am 16.07.1972 in Ko¨lleda, Thu¨ringen
Gutachter: Prof. Dr. Robert Weismantel Universit¨at Magdeburg
Prof. Dr. Peter Kleinschmidt Universit¨at Passau
Prof. Dr. Bernd Sturmfels University of California, Berkeley
Magdeburg, den 4. Oktober 2006Zusammenfassung
In der vorliegendenArbeit bescha¨ftigen wir uns mit Systemen linearer diophantischerGleichungen
und Ungleichungen der Form
⊺
a z = α , i= 1,...,m ,i 1i
⊺
b z ≤ β , j = 1,...,m ,j 2j
⊺c z ≡ γ (mod p ), k =1,...,m .k k 3k
Solche Systeme treten in vielen interessanten Anwendungen auf, z.B.:
• lineare und nichtlineare ganzzahlige Optimierung [2],
• Sampling auf Kontingenztabellen in der Statistik [50],
• Za¨hlen von Gitterpunkten in der Kombinatorik und der Statistik [44],
• Dekomposition chemischer Reaktionen in Elementarreaktionen [89],
• Erreichbarkeit in Petri-Netzen [22],
• Fundamentalkurven und -fl¨achen in der Topologie [124].
Abh¨angig vom Problem ergeben sich unterschiedliche mathematische Fragestellungen, z.B.:
• Lo¨sbarkeit des linearen Systems u¨berZ,
• Finden einer ganzzahligen Lo¨sung,
• Effiziente Kodierung aller ganzzahlige Lo¨sungen,
• Za¨hlen aller ganzzahligen Lo¨sungen,
• Finden einer Kosten-optimalen ganzzahligen Lo¨sung.
DabeibildetdieeffizienteKodierungaller,m¨oglicherweiseunendlichvielen,ganzzahligenLo¨sungen
eines linearen Systems eines der grundlegenden Probleme. Wir betrachten im folgenden drei Mo¨g-
lichkeiten:
iii
• Darstellung u¨ber ganzzahlige Basen,
• Darstellung u¨ber Hilbertbasen,
• Darstellung u¨ber kurze rationale Erzeugendenfunktionen.
Darstellungen von Gitterpunktmengen
Darstellung u¨ber ganzzahlige Basen. Wir nennen T ⊆S eine ganzzahlige Erzeugendenmenge
nvon S ⊆Z , falls fu¨r alle s∈S endliche viele Elemente t ∈T und nichtnegative ganze Zahlen αi i
mit X
s= α ti i
existieren. Eine inklusions-minimale ganzzahlige Erzeugendenmenge nennt man auch ganzzahlige
Basis. Mit Hilfe einer ganzzahligen Basis lassen sich also alle Elemente einer, m¨oglicherweise un-
endlichen, Gitterpunktmenge S ganzzahlig erzeugen. Obwohl diese Basen in einem primalen Algo-
rithmus zur Lo¨sung linearer ganzzahliger Optimierungsprobleme Einsatz finden [69], haben sie fu¨r
viele andereAnwendungenzweiwichtige Nachteile.Zumeinenexistiertnicht fu¨r jede Gitterpunkt-
menge S eine endliche ganzzahlige Basis, selbst dann nicht, wenn S die Gitterpunktmenge eines
Polyeders ist. Zum anderen werden durch T meist auch Elemente erzeugt, die nicht zu S geh¨oren,
d.h., im allgmeinen ist n oX
S( α t :t ∈T,α ∈Z .i i i i +
Es sei noch bemerkt, daß fu¨r die Gitterpunktmenge in rationalen polyedrischen Kegeln stets eine
endliche ganzzahlige Erzeugendenmenge, eine sogenannte Hilbertbasis, existiert.
Darstellung u¨ber Hilbertbasen. Die beiden Nachteile von ganzzahligen Basen lassen sich zu-
mindest fu¨r Polyederdadurch beheben, daß wir eine ganzzahlige Version von Weyls Theorem u¨ber
die Zerlegung von Polyedern in die Summe eines Polytops und eines Kegels verwenden:
nGiles & Pulleyblank [64]: Fu¨r jedes nichtleere Polyeder P ⊆ R existiert ein rationales Polytop
n n n n nQ⊆R und ein rationaler Kegel C ⊆R mit P ∩Z = (Q∩Z )+(C∩Z ).
Mit anderen Worten, jeder Gitterpunkt aus P ist die Summe einer inhomogenen ganzzahligen
Lo¨sung aus Q und einer nichtnegativen ganzzahligen Linearkombination der homogenen Elemente
einer Hilbertbasis von C.
DieVorteiledieserendlichenDarstellungliegenaufderHand:Fu¨rjedesnichtleerePolyederexistiert
eine solche Darstellung seiner Gitterpunkte und diese Darstellung kodiert wirklich nur die Gitter-
punkte des Polyeders. Als Nachteil erweist sich jedoch die Gr¨oße der beteiligten Mengen. Sowohl
nQ∩Z alsauchdieHilbertbasisvonC k¨onnenselbstinfesterDimensionexponentiellvieleElemente
besitzen.
Darstellung u¨ber kurze rationale Erzeugendenfunktionen. Eine weitere Kodierungsm¨og-
lichkeit ist die implizite Kodierung der Gitterpunkte einer MengeS in einer Erzeugendenfunktion:X
αf (z)= z ,S
α∈Siii
αα 1 αnwobei z =z ...z . Wenn S unendlich ist, so ist f (z) eine (Laurent-) Reihe und fu¨r endlichesS1 n
S istf (z)ein(Laurent-)Polynom.Desweiterenhatf (z)diescho¨neEigenschaft,daß|S|=f (1).S S S
Allerdings besitzt f (z) auch |S| Summanden. Interessanterweise kann man aber im Fall, daß SS
die Gitterpunktmenge eines Polyeders ist, f (z) auch a¨quivalent als Summe rationaler FunktionenS
uX iz
f (z)= ES iQd vij(1−z )i∈I j=1
mit endlicher Indexmenge I und mit E ∈ {0,1} schreiben, wobei die Kodierungsl¨ange dieseri
Repra¨sentation in fester Dimension polynomiell in der Kodierungsl¨ange der Ungleichungsbeschrei-
bung fu¨r P ist [13]. Dies rechtfertigt die Bezeichnung “kurze rationale Erzeugendenfunktion”. Wie
schon oben angedeutet, erm¨oglicht diese Darstellung das effiziente Za¨hlen von Gitterpunkten in
Polytopen fester Dimension.
Obwohl diese Darstellung in fester Dimension scho¨ne Komplexita¨tsaussagen erlaubt, hat auch sie
einen Nachteil. Ist S lediglich u¨ber f (z), d.h. als rationale Erzeugendenfunktion gegeben, erweistS
sich bereits die Angabe eines einzigen Punktes aus S als praktisch schwierig, obwohl sich dies in
fester Dimension theoretisch natu¨rlich in polynomieller Zeit bewerkstelligen l¨aßt.
Themen der vorliegenden Arbeit
Ganzzahlige Basen, Hilbertbasen, Graverbasen
In Kapitel 1 zeigen wir, daß eine Gitterpunktmenge S genau dann eine endliche ganzzahlige Basis
besitzt, wenn cone(S) ein rationaler polyedrischer Kegel ist.
In Kapitel 2 betrachten wir spezielle ganzzahlige Basen, na¨mlich Hilbertbasen und Graverbasen.
Wir setzen die Ausfu¨hrungen aus [71] u¨ber die positive Summeneigenschaft fort, kombinieren sie
aber mit einem Project-and-Lift Ansatz, der zuerst Hilbert- und Graverbasen in Projektionen
berechnet und diese dann in den Originalraum liftet. Dieser Algorithmus zur Berechnung von
Hilbertbasen und Graverbasen scheint das ganzzahlige Pendant zur Double-Description Methode
zur Berechnung von Extremstrahlen von Kegeln und von Zirkuiten von Matrizen [60, 74] zu sein.
Kapitel 3 enth¨alt keine eigenen neuen Resultate, sondern erkla¨rt Schritt fu¨r Schritt, wie Graver-
basen sich als universelle Testmengen in einem primalen Augmentierungsalgorithmus zur Lo¨sung
von linearen ganzzahligen Optimierungsproblemen einsetzen lassen. Hierbei liefert die Graverba-
sis Richtungen, in die nichtoptimale ganzzahlige Lo¨sungen verbessert werden k¨onnen. Schulz und
Weismantel [108] haben gezeigt, daß man sogar die verbessernden Richtungen so geschickt w¨ahlen
kann, daß der Augmentierungsalgorithmus in polynomieller Zeit in der Kodierungsgro¨ße des Pro-
blems und der Kodierungsgro¨ße der Graverbasis l¨auft.
In Kapitel4 wenden wir diese Komplexita¨tsaussageauf lineare ganzzahligeOptimierungsprobleme
an, deren Struktur eine polynomiell große Kodierung der Graverbasis zula¨ßt und damit zu einem
polynomiellen Algorithmus zur Lo¨sung dieser Problemklasse fu¨hrt.iv
In Kapitel 5 pr¨asentieren wir dann einen Algorithmus zur effizienteren Berechnung von Graver-
basen im Fall, daß der gegebenen Matrix eine gewisse symmetrische Struktur zugrundeliegt. Dies
erm¨oglicht zum Beispiel die Berechnung von Graverbasen fu¨r gro¨ßere Kontingenztabellen in der
Statistik.
In Kapitel 6 zeigen wir die Existenz endlicher Testmengen fu¨r gewisse ganzzahlige konvexe Opti-
mierungsprobleme u¨ber Polyedern. Unser Ansatz u¨ber Graverbasen fu¨hrt zur gleichen endlichen
Testmenge wie in [97] durch Verfeinerung von Kegeln und Vereinigung ihrer inklusions-minimalen
Hilbertbasen.
Am Ende des ersten Teil, in Kapitel 7, pr¨asentieren wir Malkins Project-and-Lift Algorithmus
zur Berechnung von Erzeugendenmengen und Gr¨obnerbasen von Gitteridealen [75]. Diese Mengen
finden zum Beispiel beim Sampling in der Statistik, als Testmengen in der ganzzahligen Opti-
mierung (fu¨r feste Kostfunktion) Kapitel 3 oder beim Za¨hlen von Gitterpunkten in Polytopen
(Kapitel 8) Anwendung. Interessanterweise ist Malkins Algorithmus angewandt auf die Berech-
nung von Graverbasen mit Hilfe von Gr¨obnerbasen a¨quivalent zum Project-and-Lift Algorithmus
aus Kapitel 2 zur direkten Berechnung von Graverbasen, [114, Kapitel 14].
Kurze rationale Erzeugendenfunktionen
Nachdem wir in Kapitel 8 zeigen, wie man Gitterpunkte in Polytopen mit Hilfe von Hilbert-
basen und Gr¨obnerbasentorischer Ideale berechnen kann, gehen wir in Kapitel 9 auf die einzelnen
Schritte von Barvinoks Algorithmus [13] und dessen Implementierung in der Software LattE [41]
ein. Obwohl diese Implementierung bereits recht erfolgreich neue Za¨hlformeln berechnen konnte,
konnte erst unsere vorgeschlagene Homogenisierung des Polyt