Umfangreichere Programmieraufgabe:
Berechnung von Elementen der kristallinen Basis
der Quantengruppe Uq+(sln)
| Dirk Dudek |
Jens Bender |
| BUGH Wuppertal |
BUGH Wuppertal |
| dudek@rz.uni-wuppertal.de |
bender@rz.uni-wuppertal.de |
März 1998 bis April 1998
Inhaltsverzeichnis
Diese Beschreibung stellt eine kurze Dokumentation der umfangreicheren
Programmieraufgabe dar. Es handelt sich dabei um ein Programm, dessen Aufgabe
es ist, Basiswechselkoeffizienten zwischen der kristallinen Basis und der
PBW-Basis der Gruppe Uq+ (sln) zu berechnen.
Der zugrundeliegende Algorithmus wird von der Theorie der Quantengruppen
geliefert.
Die kristalline Basis B sieht sehr unscheinbar aus. Ihre
Existenz hat allerdings enorme Konsequenzen! So lassen sich mit B
zum Beispiel alle Fragen zur endlich-dimensionalen Darstellungstheorie der
Lie-Algebra sln auf kombinatorische Probleme reduzieren.
Eines der Hauptprobleme in der Theorie der kristallinen Basis B
ist, daß ihre Kombinatorik zwar gut verstanden ist, ihre einzelnen
Elemente aber unbekannt sind (außer für n=2 und n=3).
Man ist besonders an den Basiswechselkoeffizienten zwischen B
und der PBW-Basis B interessiert, da man die PBW-Basis B als "verstanden"
annimmt.
Der Algorithmus ist in vier Hauptabschnitte gegliedert, welche es rekursiv
erlauben mittels einiger Übergangskoeffizienten die gesuchten
Basiswechselkoeffizienten zu berechnen. Die Aufteilung im einzelnen lautet:
- Reduktion von zeta nach omega.
- Reduktion von omega nach gamma.
- Reduktion von gamma nach c.
- Berechnung der c.
Liest man die vier Schritte des Algorithmus umgekehrt, so lassen sich die
Basiswechsel-Polynome zetaMN durch iteriertes Anwenden
des dritten Schrittes auf den Null-Modul und zweimaliges Auflösen einer
Rekursion über die Entartungsordnung explizit berechnen.
Als Eingabe sollte das Programm die folgenden Parameter akzeptieren:
- Die Länge n des Köchers An.
- Koeffizienten, durch welche ein beliebiger kQ-Modul als Zerlegung in
Unzerlegbare eindeutig festliegt.
Für die so spezifizierte Köcherlänge n und den Modul M
soll dann eine Liste von Paaren der Form
N mit M <=deg N, zetaMN
ausgegeben werden, d.h. jeder Modul N mit M<=degN und der
zugehörige Basiswechselkoeffizient zetaMN.
Realistische Schranken für die Eingabewerte liegen bei
n<9 und dimkM<20.
Ferner kann die Rechenzeit für Eingaben nahe diesen Schranken im
mehrstündigen Bereich liegen, denn bereits für n > 4 sind so
gut wie keine nicht-trivialen Beispiele bekannt.
Sowohl die Eingabe der Parameter als auch die Ausgabe der Liste von Paaren
dürfen schlicht gehalten werden.
Die Wahl der Programmiersprache C begründet sich hauptsächlich
durch die große Portabilität und der besseren Rechengeschwindigkeit
von C gegenüber Mathematica, die durch wenige
Zusatzprozeduren (Arithmetik mit Polynomen) nicht gemindert wird.
Als Compiler wurde der GNU-C-Compiler gewählt, der auf praktisch
allen Plattformen zur Verfügung steht. Das Programm nutzt einige
Besonderheiten dieses Compilers ([0]-Arrays, inline-Funktionen), was aber die
Portabilität nicht einschränkt.
Die Aufrufschablone des Programms lautet
kristallin [-test] [-all] [-verbose] [-debug] [-logmem]
Dabei bedeuten die einzelnen Optionen:
- -test
- Die in Abschnitt Tests der ausführlichen
Dokumentation aufgeführten Tests werden durchgeführt.
Schlägt einer der Tests fehl, wird der Text "Programm buggy" auf
stderr ausgegeben und das Programm wechselt in den
-debug-Modus. Natürlich verlangsamt diese Option den
Programmlauf etwas.
- -all
- Nach Start des Programms wird als erstes die Länge des zu
behandelnden Köchers erfragt, danach der zu betrachtende
Dimensionsvektor. Wird diese Option nicht angegeben, wird anschließend
der zu betrachtende Modul gegeben durch seine Zerlegung in Unzerlegbare
eingegeben. Wird diese Option aber angegeben, werden nacheinander alle
Moduln, die zum gegebenen Dimensionsvektor passen, behandelt. Diese
Option eignet sich besonders, um einen gewissen Überblick zu
bekommen und um die Testläufe ökonomischer durchführen
zu können.
- -verbose
- Zusätzlich zu den zetaMN werden auch alle
benötigten omegaMN und
gammaMN ausgegeben. Weiterhin werden vor der
Eingabe des Moduls alle Unzerlegbaren und alle Moduln zum gegebenen
Dimensionsvektor ausgegeben. Die Moduln werden dabei durch eine
Kurzschreibweise dargestellt, und zwar werden die Multiplizitäten
der Unzerlegbaren in der Reihenfolge E1,n,
E1,n-1, E2,n, E1,n-2,
..., E11, ..., Enn ausgegeben (n
ist die Länge des Köchers).
- -debug
- Zusätzlich zu -verbose wird die Berechnung der
M[M] ausführlich angezeigt, einschließlich
aller cri (M,Ma).
- -logmem
- Der maximal benutzte Speicher für diesen Programmlauf wird
angezeigt. Ebenso wie -test wird das Programm etwas verlangsamt,
außerdem wird der Speicherverbrauch etwas erhöht. Dieser
zusätzliche Speicherverbrauch wird aber nicht mitgerechnet, ebenso
bleibt der durch malloc eingebrachte Overhead
unberücksichtigt.
Bei der Eingabe der Moduln als direkte Summe der Unzerlegbaren ist zu beachten,
daß nur die Multiplitzitäten der Unzerlegbaren abgefragt werden,
die noch nicht eindeutig durch vorhergehende Eingaben und den Dimensionsvektor
festgelegt sind. Die Eingaben müssen im bei der Eingabeaufforderung
angegebenen Bereich liegen, damit sie akzeptiert werden.
Der Algorithmus wurde wie im Theorieteil (der ausführlichen
Dokumentation) geschildert umgesetzt. Dabei sind dem Programm einige
erklärende Kommentare als Programmtext hinzugefügt worden, um
wichtige Programmdetails zu beleuchten.
Das Programm besitzt keine Schranken für die Eingabeparameter,
wie sie im obigen Abschnitt angegeben sind. Praktisch sind beliebig hohe Werte
für Köcherlänge und Modul-Dimension möglich. Doch die
protokollierten Testläufe machen deutlich, daß große
Eingabewerte hohen Speicherplatzbedarf fordern und die Geduld des
Programmnutzers auf die Probe stellen.
Die genaue Programmdokumentation ist mit Hilfe von LaTeX2e erstellt worden
und kann entweder als dvi-Datei oder als PostScript-Datei heruntergeladen
werden.
Download der LaTeX2e-Dokumetation (im dvi-Format):
kristallin.dvi
Download der LaTeX2e-Dokumetation (im ps-Format):
kristallin.ps
Das Programm selbst liegt als binäre Datei für verschiedene
Plattformen vorkompiliert vor:
Für weitere Informationen zum Programm und ausführbare Dateien für
andere Systeme ist Rücksprache via E-Mail
möglich:
Letzte Änderung: 10.Juli 1998
© 1998 by D2 & J.B.
dudek@rz.uni-wuppertal.de