´

Ganzzahlige Optimierungsmodelle für Subspace Codes und endliche Geometrie
KU 2430/3-1, WA 1666/9-1

Fano_plane.svg

Beschreibung

Fehlerkorrigierende Codes werden heute in nahezu jeder Form der Informationsübertragung und -speicherung eingesetzt. Prominente Beispiele sind Kommunikation mit Weltraumsonden, Digitales Fernsehen (DVB), ADSL, verteilte Speichersysteme (Windows Azure) und CD-Player.

Vielfältige Anwendungen in Kommunikationsnetzen wie dem Internet, mobilen Endgeräten wie Smartphones und Cloud Computing, mit ihren schnell wechselnden technischen Standards, erfordern eine mathematische Theorie, die unabhängig von der genauen Netzwerktopologie ist. Bislang werden in Kommunkiationsnetzen wie dem Internet die Durchsatzraten durch ausgeklügelte Routing-Strategien optimiert. Erst vor wenigen Jahren wurde erkannt, dass die Durchsatzraten in bestimmten Situationen noch deutlich verbessert werden können, indem Datenpakete überlagert werden, d. h. über einem geeigneten endlichen Körper linear kombiniert werden. Wenn in diesem Kommunikationsmodell auch Fehler korrigiert werden sollen, also Codierungstheorie betrieben werden soll, bietet es sich ganz natürlich an, als Alphabet die Menge aller Teilräume eines endlichen Vektorraumes zu betrachten, da Teilräume invariant gegenüber Linearkombination ihrer Vektoren sind. Ein subspace code ist dann eine Menge geeigneter Teilräume.

Eine Hauptforschungsrichtung ist die Existenzfrage und die Konstruktion von guten bzw. optimalen subspace codes. Dieses Problem ist zur Zeit hochaktuell und ist zum Beispiel Thema der EU COST Action IC1104 "Random Network Coding and Designs over GF(q)". Eine umfassende Suche nach guten subspace codes wird erschwert durch die Tatsache, dass die Anzahl aller Teilräume eines endlichen Vektorraumes schon für kleine Parameter sehr groß wird. Die auf diesen Objekten operierende Symmetriegruppe ist in der Regel ebenfalls riesig und verursacht weitere algorithmische Herausforderungen.

In Bayreuth wurden in den letzten Jahren computerunterstützte Konstruktionsverfahren in verschiedenen Gebieten der diskreten Mathematik sehr erfolgreich eingesetzt. Die zugrunde liegende Idee hierbei ist, den Suchraum mit Methoden der Gruppentheorie zu verkleinern. Entweder sucht man nur Lösungen mit vorgegebenen Symmetrien oder nutzt die Isomorphie zwischen unterschiedlichen Lösungen aus. Die Suche nach Inzidenzstrukturen lässt sich auf die Lösung eines ganzzahligen linearen Gleichungssystems zurückführen. Die erzielten Resultate sollen dann dabei unterstützen, die Theorie besser zu erklären.

Im Rahmen dieses Projektes wird ein derartiger Ansatz auf die vorliegende Fragestellung angepasst. Als Innovation sollen mit Hilfe theoretischer Resultate aus der endlichen Geometrie und durch Betrachtung von Schnittzahlen schärfere ganzzahlige Formulierungen gefunden werden. Grundidee hierbei ist, geeignete geometrische Teilstrukturen zu modellieren und zu klassifizieren. Dem ursprünglichen Problem werden nun Restriktionen hinzugefügt, indem jeweils ein Isomorphietyp als Teilstruktur vorgeschrieben wird. Die resultierenden Teilprobleme werden dann unter Verwendung von Methoden der ganzzahligen linearen Optimierung gelöst.

Dieses Projekt wird finanziell durch die Deutsche Forschungsgemeinschaft gefördert. Details hierzu können auf den Seiten der DFG eingesehen werden.

Gefördert durch

dfg_logo

Projektleiter

Projektlaufzeit

April 2015 bis März 2018

Mitarbeiter:

Veranstaltungen / Lehre

Literatur

2019

2018

2017

2016

2015

2014

2013

2012

Homepage

Eine Tabelle der Subspace Codes: http://subspacecodes.uni-bayreuth.de.

Universität Bayreuth -