Industrielle Anwendungen der Computeralgebra

1. Statistik: “Design of Experiments”

In dem Teilbereich “Design of Experiments” der Statistik geht es um folgendes Problem. Zur vollständigen Beantwortung einer Frage ist es notwendig, eine sehr große Zahl von Datenpunkten (“full factorial design”) zu kennen. Dies ist aber in der Praxis entweder unmöglich oder zu teuer. Darum soll eine Teilmenge so bestimmt werden, daß aus der Kenntnis der Teildaten die gesuchten Erkenntnisse über die Gesamtmenge erschlossen werden können.

Erstes Beispiel: (Marketing) Ein neues Handy soll am Markt eingeführt werden. Für die von den Kunden gewünschten Eigenschaften wird ein mathematisches Modell aufgestellt.

\begin{matrix}Eigenschaft & W erte & Modell \\ Farbe & blau, gelb, rot & 0, 1, 2 \\ Gewicht & 100 Gramm Schritte & 0, 1, 2, 3, 4 \\ Kanten & eckig, rund, abgeflacht & 0, 1, 2 \\ Preis & 5 P reisbereiche & 0, 1, 2, 3, 4 \end{matrix}

Die Menge aller möglichen Tupel (F, G, K, P) ∈ ℚ^{4} bildet das “full design” 𝔻. Die (gesuchten) Kundenpräferenzen entsprechen einer (unbekannten) Funktion f : 𝔻 ⟶ ℚ, die man das Modell nennt.

Bemerkung: Die Funktion f : 𝔻 ⟶ ℚ ist auf einer endlichen Menge definiert. Dann gibt es ein Polynom in ℚ[x_{1}, x_{2}, x_{3}, x_{4}], das auf 𝔻 die gleichen Werte annimmt wie f.

Problem: Wir können bei einer Kundenumfrage nicht verlangen, daß die Testpersonen eine Rangfolge für alle 225 möglichen Kombinationen der Eigenschaften aufstellen.

Lösungsansatz:

• Finde eine geeignete “kleine” Teilmenge 𝔽 ⊂ 𝔻 (“fraction”).

• Erfrage die Bewertung der Elemente von 𝔽 durch die Testpersonen.

• Versuche die Funktion f : 𝔻 ⟶ ℚ aus diesen Daten zu rekonstruieren (“identify the model”).

Mathematische Durchführung: Sie I(𝔻) die Menge aller Polynome in P = ℚ[x_{1}, x_{2}, x_{3}, x_{4}], die auf 𝔻 verschwinden. Dies ist ein Ideal in P. Es wird erzeugt von den Polynomen {x_{1}(x_{1} − 1)(x_{1} − 2), x_{2}(x_{2} − 1) ⋯ (x_{2} − 4), x_{3}(x_{3} − 1)(x_{3} − 2), x_{4}(x_{4} − 1) ⋯ (x_{4} − 4)}. Wir müssen das Ideal I(𝔽) aller Polynome, die auf 𝔽 verschwinden, berechnen und die Menge der “confounding polynomials” I(𝔽) \ I(𝔻).

Wenn wir dann etwas über die Monome wissen, die in dem gesuchten Polynom f wirklich vorkommen (z.B. “der Einfluß von Farbe und Preis auf f ist unkorrelliert”), dann können wir versuchen 𝔽 so zu wählen, dass f|_{𝔽} bereits das Polynom f ∈ P bestimmt. Allerdings können wir f stets um Elemente aus I(𝔻) abändern, ohne seine Werte auf 𝔻 zu beeinflussen.

Zweites Beispiel: (Umzug einer Chemiefabrik) Eine Chemiefabrik zog in ein neues Gebäude in einer anderen Gegend um. Plötzlich funktionierte einer der Filtrierschritte nicht mehr. Für die möglichen Ursachen gab es eine Reihe von Kandidaten:

• Die Lufttemperatur in der neuen Fabrikhalle war anders.

• Das Wasser in der neuen Gegend war anders.

• Eine der Maschinen hatte beim Transport einen Schaden erlitten.

• Die verwendeten Chemikalien hatten eine etwas andere Zusammensetzung (neue Zulieferer).

• Die Prozedur der Vorbehandlung hatte sich geändert (neue Angestellte).

Es war zu teuer, alle Kombinationen aller Werte dieser Faktoren in Testläufen durchzuspielen. Daher mußten einige wenige Testläufe so konfiguriert werden, daß sich aus ihnen der entscheidende Faktor ablesen ließ.

Wieder ist ein wichtiger Schritt in der Lösung die Berechnung des Ideals I(𝔽) ⊂ P aller Polynome in ℚ[x_{1}, …, x_{n}] die auf der (geplanten) Teilmenge 𝔽 ⊂ 𝔻 verschwinden. Sei 𝔽 = {P_{1}, …, P_{s}} mit P_{i} = (p_{i1}, …, p_{in}) ∈ ℚ^{n}. Das Ideal aller Polynome, die in P_{i} verschwinden, heiße I(P_{i}). Zu berechnen ist

I(𝔽) = ⋂_{i=1}^{s} I(P_{i}) = ⋂_{i=1}^{s}(x_{1} − p_{i1}, …, x_{n} − p_{in}).

Der effektivste Algorithmus in dieser Situation ist der Buchberger-Möller-Algorithmus.

Der Buchberger-Möller Algorithmus

Sei K ein Körper, σ eine Termordnung auf den Termen von K[x_{1}, …, x_{n}], und seien P_{1}, …, P_{s} ∈ K^{n}. Betrachte die folgenden Instruktionen:

1) Starte mit Listen G = [ ], Q = [ ], S = [ ], L = [1] und einer Matrix M = (m_{ij}) über K mit s Spalten und anfangs 0 Zeilen.

2) Ist L = [ ] so gib [G, Q] aus und stoppe. Andernfalls wähle t = min_{σ}(L) und streiche es aus L.

3) Berechne (t(P_{1}), …, t(P_{s})) ∈ K^{s}. Reduziere diesen Vektor gegen die Zeilen von M und erhalte

(v_{1}, …, v_{s}) = (t(P_{1}), …, t(P_{s})) − ∑_{i} a_{i} (m_{i1}, …, m_{is})

mit a_{i} ∈ K.

4) Ist (v_{1}, …, v_{s}) = 0, so füge das Polynom t − ∑_{i} a_{i}s_{i} zu G hinzu, wobei s_{i} das i-te Element von S ist. Streiche aus L alle Vielfachen von t und fahre mit 2) fort.

5) Ist (v_{1}, …, v_{s}) ≠ 0, so füge (v_{1}, …, v_{s}) als neue Zeile zu M hinzu, t−∑_{i} a_{i}s_{i} als neues Element zu S, t zur Liste Q, und zu L alle Terme in {x_{1}t, …, x_{n}t}, die weder Vielfaches eines Elements von L noch von {LT_{σ}(g) | g ∈ G} sind. Fahre dann mit 2) fort.

Dies ist ein Algorithmus, der die reduzierte σ-Gröbner Basis G des Ideals I = I(P_{1}) ∩ ⋯ ∩ I(P_{s}) berechnet sowie die Liste Q derjenigen Terme, die nicht in LT_{σ}(I) liegen.

Über K = ℚ stellt sich das Problem des Wachstums der Koeffizienten der Polynome. Man braucht eine modulare Version des Algorithmus.

Beispiel: Gegeben seien 100 Punkte in ℚ^{10} mit Koordinaten in {0, 1, 2, …, 9}^{10}. Wir suchen ein Erzeugendensystem für das Verschwindungsideal dieser Punkte.

Das minimale Erzeugendensystem hat 286 Polynome mit je ca. 100 Termen. Jeder Koeffizient hat ca. 160 stellige Zähler und Nenner. Das Erzeugendensystem füllt ca. 4000 Bildschirmseiten.

Die modulare Version des BM-Algorithmus In obiger Situation betrachte folgende Instruktionen:

1) Setze Q = [ ], G = [ ], m = 1 und G_{m} = [ ].

2) Wähle eine neue Primzahl p, so daß die Reduktionen \overline{P}_{1}, …, \overline{P}_{s} paarweise verschieden sind.

3) Wende den BM-Algorithmus mit K = 𝔽_{p} auf die Punktmenge \{\overline{P}_{1}, …, \overline{P}_{s}\} an und erhalte [G_{p}, Q_{p}].

4) Vergleiche Q_{p} = [q′_{1}, q′_{2}, …] mit Q = [q_{1}, q_{2}, …] wie folgt: Q ist besser als Q_{p} wenn es ein j gibt mit q_{1} = q′_{1}, …, q_{j−1} = q′_{j−1}, q_{j} <_{σ} q′_{j}. Ist Q besser als Q_{p} so fahre mit 2) fort. Ist Q_{p} besser als Q, so ersetze Q durch Q_{p}, m durch p, G_{m} durch G_{p} und fahre mit 2) fort.

5) Jetzt gilt Q = Q_{p}. Ersetze m durch mp und kombiniere G_{m} mit G_{p} mit Hilfe des Chinesischen Restsatz Algorithmus. Nenne das Ergebnis G′.

6) Ist G′ ≠ G, so ersetze G durch G′. Fahre mit 2) fort.

7) Nun gilt G′ = G. Prüfe, ob alle Polynome aus G an den Punkten P_{1}, …, P_{s} verschwinden. Wenn nicht, fahre mit 2) fort. Wenn ja, gib [G, Q] aus und stoppe.

Dies ist ein Algorithmus, der die reduzierte σ-Gröbner Basis G von I = I(P_{1})∩⋯∩I(P_{s}) und die Liste Q der Terme außerhalb LT_{σ}(I) berechnet.

Weitere Fragen:

1) Sei eine Teilmenge 𝔽 ⊂ 𝔻 vorgegeben. Welche Modelle f : 𝔽 ⟶ 𝔻 können mit Hilfe von f|_{𝔽} identifiziert werden?

2) Die Koeffizienten von {1, x_{1}, …, x_{n}} in f heißen die Haupteffekte, diejenigen von {x_{i}x_{j} | i, j = 1, …, n} heißen die Interaktionen. Welche Teilmengen 𝔽 von 𝔻 sind zu wählen, wenn man nur die Haupteffekte identifizieren will?

3) Welche Teilmengen 𝔽 von s Punkten aus 𝔻 identifizieren die größte Anzahl linearer polynomialer Modelle?

Literatur:

1) L. Robbiano, Gröbner bases and statistics, in: B. Buchberger und F. Winkler (Hrsg.), Gröbner Bases and Applications, Proc. Conf. Linz 1998, London Math. Soc. Lect. Notes 251, Cambridge University Press, S. 179–204

2) J. Abbott, A. Bigatti, M. Kreuzer und L. Robbiano, Computing ideals of points, J. Symb. Comput. 30 (2000), S. 341– 356

3) J. Abbott, M. Kreuzer und L. Robbiano, Computing zerodimensional schemes, Preprint 2000 2. Computeralgebra in der Warteschlangentheorie

in Zusammenarbeit mit Dr. H. Gold (Infineon Technologies)

Bei der Ablaufplanung in der Chipfertigung spielen Warteschlangen mit Kontrolle eine große Rolle. Hat man eine Anzahl von verschiedenen Maschinen (z.B. Stepper, Plasmaätzer, etc.) und Lots (d.h. Fertigungsgruppen) unterschiedlicher Priorität und Größe, so ist die Durchlaufzeit eines einzelnen Lots durch die Maschinengruppe annähernd Poissonverteilt. Ferner nehmen wir an, daß die Rohmaterialanlieferung und die Chipnachfrage durch Poisson-Prozesse gegeben sind. Wir erhalten folgende Situation.

↓^{λ_{2}}
Schlange Q_{2}
↓
⟶^{λ_{1}} Schlange Q_{1} ⟶^{μ} Schlange Q_{3} ⟶ Output

Hierbei ist ⟶^{λ_{1}} der Anlieferungsprozeß, ⟶^{μ} der Fertigungsprozeß, ⟶^{λ_{2}} der Chipnachfrageprozeß, Schlange Q_{1} enthält die noch nicht abgearbeiteten Lots, Schlange Q_{2} enthält die noch nicht befriedigte Nachfrage, und Schlange Q_{3} ist das Lager.

Alle drei Warteschlangen sollen eine endliche Kapazität haben. Wir nehmen außerdem an, daß Q_{2} oder Q_{3} stets leer ist, d.h. daß alle Aufträge sofort erledigt werden, solange Chips im Lager sind.

Für i = 1, 2, 3 sei s_{i} die Kapazität der Warteschlange Q_{i}. Wir können voraussetzen, daß das System so dimensioniert ist, daß s_{1} = s_{2}+s_{3} gilt, und diese Zahl nennen wir ab jetzt s. Wir setzen

i = \{ \begin{matrix}1 + Jobs in Q_{1} & falls gerade gefertigt wird, \\ 0 & sonst, und \end{matrix}

j = \{ \begin{matrix}s_{3} + Jobs in Q_{2} & falls Q_{2} nichtleer ist, \\ freie Plätze in Q_{3} & sonst \end{matrix}

Dann erfüllen die Wahrscheinlichkeiten p_{ij} dafür, daß sich das System im Zustand (i, j) befindet, die folgenden Rekursionsgleichungen:

p_{i+1 j+1} χ_{i<s, j<s} μ = p_{ij}[χ_{i<s}λ_{1} + χ_{j<s}λ_{2} + χ_{i>0, j>0}μ] − p_{i−1 j} χ_{i>0} λ_{1} − p_{i j−1} χ_{j>0} λ_{2}

1) Für spezielle Werte von λ_{1}, λ_{2} und μ kann man diese Rekursionsgleichungen mit Hilfe eines expliziten Algorithmus lösen, vgl.

H. Gold, A Markovian single server with upstream job and downstream demand arrival system, Queuing Systems 30 (1998), 435 – 455

2) Eigentlich möchte man die Lösungen in Abhängigkeit von λ_{1}, λ_{2} und μ studieren.

Dazu betrachten wir die Rekursionsgleichungen als ein algebraisches Gleichungssystem über dem Funktionenkörper ℚ(λ_{1}, λ_{2}, μ). Wir versuchen es mit Mitteln der Computeralgebra symbolisch zu lösen. Im Fall s = 3 ergibt sich nach der Substitution x_{ij} := p_{ij}, y := \frac{λ_{1}}{μ}, z := \frac{λ_{2}}{μ} zum Beispiel

(1) x_{00}(y + z) − x_{11} = 0

(2) x_{01}(y + z) − x_{12} − x_{00}z = 0

(3) x_{02}(y + z) − x_{13} − x_{01}z = 0

(4) x_{03}y − x_{02}z = 0

(5) x_{10}(y + z) − x_{21} − x_{00}y = 0

(6) x_{11}(y + z + 1) − x_{22} − x_{01}y − x_{10}z = 0

(7) x_{12}(y + z + 1) − x_{23} − x_{02}y − x_{11}z = 0

(8) x_{13}(y + 1) − x_{03}y − x_{12}z = 0

(9) x_{20}(y + z) − x_{31} − x_{10}y = 0

(10) x_{21}(y + z + 1) − x_{32} − x_{11}y − x_{20}z = 0

(11) x_{22}(y + z + 1) − x_{33} − x_{12}y − x_{21}z = 0

(12) x_{23}(y + 1) − x_{13}y − x_{22}z = 0

(13) x_{30}z − x_{20}y = 0

(14) x_{31}(z + 1) − x_{21}y − x_{30}z = 0

(15) x_{32}(z + 1) − x_{22}y − x_{31}z = 0

(16) x_{33} − x_{23}y − x_{32}z = 0

Man hat also ein lineares Gleichungssystem von (s + 1)^{2} Gleichungen in (s + 1)^{2} Unbestimmten x_{ij} über dem Körper ℚ(y, z).

Man kann die Koeffizientenmatrix M_{s} aufstellen und die Cramersche Regel anwenden. Es gibt einen 1-dimensionalen Lösungsraum, in dem die korrekte Lösung die Normierungsgleichung

∑_{i,j} x_{ij} = 1

erfüllen muß.

Der Lösungsvektorraum von M_{s} wird also von einem Tupel von Polynomen (f_{00}, …, f_{ss}) aufgespannt, die bis auf einen Normierungsfaktor eindeutig bestimmt sind. Folglich können wir annehmen, daß sie keinen gemeinsamen Faktor haben.

Die folgenden Fragen sind für die Anwendungen interessant: 1) Welche Grade haben die Polynome f_{ij} ?

2) Was ist ihr Leitterm (bzgl. der gradkompatiblen Termordnung σ mit y > z) ?

3) Bis zu welchem s kann man die f_{ij} effektiv berechnen? (Praktisch relevant ist s ≤ 25.)

Einige Antworten: Um die Matrix M_{s} zu lösen, führt man zuerst einige Vereinfachungsschritte durch.

1) Wende die Substitution v = \frac{z}{y}, w = \frac{1}{y} an und beseitige alle Nenner. Aus der (−y)-Diagonalen wird dadurch eine (−1)-Diagonale.

2) Verwende die (−1)-Diagonale, um die Matrix M_{s} auszuräumen. Erhalte in der rechten unteren Ecke eine (s + 1) × (s + 1)-Matrix N_{s}, die jedoch jetzt dicht mit Polynomen höheren Grades besetzt ist.

Algorithmus 1: Wende eine geeignete Version des Bareiss-Algorithmus oder des Malashonok-Algorithmus auf N_{s} an.

Satz 2.1. a) Die Matrix N_{s} hat den linearen Anteil

N_{s}^{lin} = ( \begin{matrix}−v & w & 0 & ⋯ & ⋯ & 0 \\ v & −v − w & w & 0 & ⋯ & 0 \\ 0 & ... & ... & ... & ... & ⋮ \\ ⋮ & ... & ... & ... & ... & 0 \\ ⋮ & & ... & ... & −v − w & w \\ 0 & ⋯ & ⋯ & 0 & v & −w \end{matrix} )

b) Die Matrix N_{s}^{lin} hat den (bis auf einen Faktor eindeutigen) Lösungsvektor (w^{s}, vw^{s−1}, …, v^{s}).

c) Die Matrix N_{s} hat einen (bis auf einen Faktor eindeutigen) Lösungsvektor (g_{0}, …, g_{s}) mit

g_{i} = v^{i}w^{s−i} + (Terme höheren Grades)

Korollar 2.2. Für die Leitterme der Polynome f_{s0}, …, f_{ss} gilt

LT_{σ}(f_{si}) = y^{s^{2}+s}z^{i}  für i = 0, …, s.

Insbesondere gilt deg(f_{si}) = s^{2} + s + i für i = 0, …, s.

Vermutung: Der Leitterm von f_{0i} ist y^{s^{2}−i}z^{s+i} für i = 0, …, s. Ist die Vermutung richtig, so gilt

deg(f_{ij}) = s^{2} + s + min{i, j}  für i, j = 0, …, s.

Satz 2.3. Die Polynome des Lösungsvektors (g_{0}, …, g_{s}) von N_{s} sind von der Form g_{i} = v^{i}w^{s−i}h_{i} mit Polynomen h_{i} vom Grad deg(h_{i}) = s^{2} − 2s + i und h_{i}(0, 0) ≠ 0 für i = 0, …, s.

Man kann eine weitere Matrix L_{s} aufstellen, deren Lösungsvektor gerade (h_{0}, …, h_{s}) ist.

Algorithmus 2: Man kann die Matrix L_{s} wie folgt effizient lösen:

1) Für verschiedene Primzahlen p betrachte die Reduktion L_{s}(mod p) der Matrix L_{s} modulo p, d.h. das Bild von L_{s} in ℤ/(p)[v, w].

2) Löse L_{s}(mod p) mit Hilfe des Malashonok-Verfahrens.

3) Rekombiniere die modularen Lösungen mit Hilfe des Chinesichen Restsatzes.

4) Ist das Produkt der verwendeten Primzahlen groß genug, erhält man die korrekte Lösung über ℚ. Dies kann man durch Einsetzen leicht bestätigen.

In der Praxis erhalten wir folgende Ergebnisse:

1) Cramer’s Regel funktioniert für s ≤ 4.

2) Das Malashonok-Verfahren löst N_{s} für s ≤ 8.

3) Algorithmus 2 löst L_{s} für s ≤ 12.

Die Größe der Lösung von N_{s} für s = 7 (d.h. die 8 Polynome g_{0}, …, g_{7}) ist ca. 400 kB.

Literatur:

1) H. Gold, A Markovian single server with upstream job and downstream demand arrival system, Queuing Systems 30 (1998), 435 – 455

2) H. Gold, Performance evaluation of and decision making tools for semiconductor wafer probing facilities, in: Proc. Conf. MASM 2000 (erscheint)

3) B. Krammer, Effektive lineare Algebra für Polynommatrizen, Diplomarbeit, Universität Regensburg 2000

4) G.I. Malashonok, Solution methods for linear equation systems in a commutative ring, Proc. Conf. MEGA ’90 (Castiglioncello 1990), Progress in Math. 94, Birkhäuser, Basel 1992

5) A. Wills, Algebraische Probleme in der Warteschlangentheorie, Diplomarbeit, Universität Regensburg (in Vorbereitung)

3. Computeralgebra in der Codierungstheorie

Sei p eine Primzahl, sei e > 0, sei q = p^{e}, und sei 𝔽_{q} der Körper mit q Elementen. Ein linearer Code C ist ein 𝔽_{q}-Untervektorraum von 𝔽_{q}^{s}. Dabei heißt s die Länge von c, die Zahl d = dim_{𝔽_{q}}(C) heißt die Dimension von C, und

m(C) = min{#{i | c_{i} ≠ 0} | (c_{1}, …, c_{s}) ∈ C \ {0}}

heißt der Minimalabstand von C.

Ein guter linearer Code hat einen großen Minimalabstand bei kleiner Länge und großer Dimension. Es gilt die

Singleton-Schranke: m ≤ s − d + 1

Ziele: 1) Konstruiere gute lineare Codes, also Codes, die der Singleton-Schranke nahe kommen.

2) Ist ein linearer Code C ⊆ 𝔽_{q}^{s} gegeben, so berechne seinen Minimalabstand.

Hanson’s Konstruktion: Gegeben sei eine endliche Punktmenge 𝕏 = {P_{1}, …, P_{s}} in ℙ^{n}(𝔽_{q}). Ihr homogenes Verschwindungsideal in 𝔽_{q}[x_{0}, …, x_{n}] werde mit I_{𝕏} bezeichnet. Ferner sei R = 𝔽_{q}[x_{0}, …, x_{n}]/I_{𝕏} der homogene Koordinatenring von 𝕏 und H_{𝕏} : ℕ ⟶ ℕ (i ↦ dim_{𝔽_{q}}(R_{i})) die Hilbert-Funktion von 𝕏.

Bekanntlich steigt die Funktion H_{𝕏} streng monoton an, bis sie die Punktezahl s erreicht. Dann bleibt sie konstant gleich s. Wir setzen σ_{𝕏} = max{i ∈ ℕ | H_{𝕏}(i) < s}. Im folgenden nehmen wir an, daß die erste Koordinate aller Punkte in 𝕏 von Null verschieden ist, d.h. daß 𝕏 im affinen Raum D_{+}(x_{0}) liegt.

Für j = 1, …, σ_{𝕏} betrachte die Abbildung

\begin{matrix}Φ_{j} : R_{j} & ⟶ & 𝔽_{q}^{s} \\ f & ⟼ & (f(P_{1}), …, f(P_{s})) \end{matrix}

wobei die Funktionswerte in D_{+}(x_{0}) zu bilden sind.

Satz 3.1. (Hansen)

a) Für jedes j ∈ {1, …, σ_{𝕏}} ist die Abbildung Φ_{j} injektiv. Ihr Bild ist ein linearer Code C_{j}(𝕏) der Länge s und der Dimension H_{𝕏}(j).

b) Sei i ≥ 1 und j ∈ {1, …, σ_{𝕏}}. Genau dann gilt m(C_{j}(𝕏)) ≥ s − i + 1, wenn für jede Teilmenge 𝕐 ⊆ 𝕏 bestehend aus i Punkten gilt, daß H_{𝕐}(j) = H_{𝕏}(j) ist.

In diesem Fall sagen wir, 𝕏 sei (s − i, j)-uniform.

Wie man leicht sieht, kann jeder lineare Code durch Hansen’s Konstruktion erhalten werden. Um gute lineare Codes zu konstruieren, braucht man also möglichst große, uniforme Teilmengen 𝕏 ⊆ ℙ^{n}(𝔽_{q}).

Algorithmen zur Uniformitätsberechnung

1) Die (1, σ_{𝕏})-Uniformität von 𝕏 heißt klassisch auch die Cayley-Bacharach Eigenschaft. Man kann sie mit Hilfe einer Liaison-Technik effizient prüfen.

2) Für jedes j ∈ {1, …, σ_{𝕏}} ist die (s − H_{𝕏}(j), j)-Uni-formität die maximal mögliche. Um sie zu prüfen, muß man zuerst den kanonischen Modul ω_{R} des Rings R mit Hilfe der Adjunktionsformel

ω_{R} ≅ \underline{Hom}_{K[x_{0}]}(R, K[x_{0}])(−1)

berechnen und dann gewisse Multiplikationsabbildungen in diesem Modul auf Biinjektivität testen.

3) Um die (i, σ_{𝕏})-Uniformität für i ∈ {1, …, s−H_{𝕏}(σ_{𝕏})} zu prüfen, kann man mit Hilfe einer Variante des Buchberger-Möller Algorithmus die Separatoren von 𝕏 bestimmen. Dies sind homogene Polynome f_{1}, …, f_{s} vom Grad σ_{𝕏} + 1 mit f_{i}(P_{j}) = δ_{ij} für i, j = 1, …, s. An diesen Separatoren kann man die gewünschte Uniformität erkennen.

Literatur:

1) S. Beck und M. Kreuzer, How to compute the canonical module of a set of points, in: Proc. Conf. MEGA ’94 (Santander 1994), Progress in Math. 143, Birkhäuser, Basel 1996

2) J.P. Hansen, Points in uniform position and maximum distance separable codes, in: Proc. Conf. Zero-Dimensional Schemes (Ravello 1992), de Gruyter, Berlin 1994

3) M. Kreuzer, On the canonical module of a set of points, Boll. Un. Mat. Ital. (8) 1-B (2000), 221 – 261