Computer-Algebra

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

Die Computer-Algebra ist das Teilgebiet der Mathematik, das sich mit der symbolischen Manipulation algebraischer Ausdrücke beschäftigt. Hauptziel dieses Teilgebiets ist es, für alle denkbaren Aufgaben im Umfeld des exakten Rechnens mit algebraischen Ausdrücken möglichst effiziente Algorithmen zu finden sowie deren Komplexität zu ermitteln (über die Komplexitätstheorie sind hier die Disziplinen Mathematik und Informatik ganz eng miteinander verwoben). Einen Schwerpunkt bildet das exakte Rechnen mit ganzen, rationalen und algebraischen Zahlen sowie mit Polynomen über diesen Zahlenräumen.

Praktische Anwendung erfahren solche Ergebnisse durch den Einsatz effizienter Algorithmen bei der Entwicklung und Verbesserung von Computer-Algebra-Systemen, die die rechnergestützte Manipulation algebraischer Ausdrücke ermöglichen. Diese Systeme sind auch ein immer wichtiger werdendes Werkzeug für Mathematiker und Naturwissenschaftler verschiedenster Fachrichtungen. Damit mit Computer-Algebra-Systemen erzeugte Ergebnisse in der Mathematik als Beweis anerkannt werden können, muss allerdings erheblicher Entwicklungsaufwand betrieben werden, um sie 100 % zuverlässig machen zu können. Kommerziell erfolgreiche Computer-Algebra-Systeme erfüllen diese Zuverlässigkeit derzeit nur in stark eingeschränkten Teilbereichen.

Die Fülle an verfügbarem Wissen aus der Computer-Algebra ist in der Literatur überwiegend schwer auffindbar, da es meist in anderen Teilgebieten der Mathematik und noch mehr der Informatik veröffentlicht wird.

[Bearbeiten] Effiziente exakte Arithmetik mit ganzen Zahlen

Will man die Zeitkomplexität von Aufgaben und Algorithmen zur exakten Arithmetik mit ganzen Zahlen klassifizieren, so muss zunächst ein Rechnermodell zugrunde gelegt werden. Eine Diskussion diverser Rechnermodelle findet sich im Kapitel Komplexität. Ein relativ eingängiges Modell ist die Mehrband-Turingmaschine, eine Variante der klassischen Turingmaschine, die mehrere Bänder mit je einem Schreib-/Lesekopf besitzt. Für Komplexitätsabschätzungen mit der Landau-Notation wird bei Bedarf unter der Bezeichnung $\operatorname{log}$ ein Logarithmus zu einer nicht spezifizierten Basis $B > 1$ verwendet. Als Maß für die Zeit wird die Zahl der benötigten Bitoperationen gewählt, die in Landau-Notation von der Bitlänge des Inputs abhängig gemacht wird.

Die präzise mathematische Angabe von (Bit-)Komplexitäten für die exakte Arithmetik mit ganzen Zahlen muss zunächst mit der genauen Festlegung der Bitlänge einer ganzen Zahl starten: Ist die Zahl $a \in \mathbb Z$ nichtnull, so wird

$L(a) := \operatorname{floor}\left(log_2 |a|\right)$

gesetzt; zusätzlich wird $L (0): = 1$ definiert. Man beachte, dass für eine konkrete Abspeicherung einer ganzen Zahl zusätzlich mindestens noch ein Bit für das Vorzeichen der Zahl benötigt wird.

Eine - oft vernachlässigte - Aufgabe eines Algorithmus ist das Herausschreiben des Outputs; hier sind zunächst folgende Abschätzungen dienlich:

Für alle Zahlen $a, b \in \mathbb Z$ und $n\in\mathbb N_0$ gilt:

$L(a+b) \leq 1 + \max(L(a), L(b))$ ,

$L(a\cdot b) \leq L(a) + L(b)$ ,

$L(a^n) \leq n L(a)$ .

Die Aufgaben der Vorzeichenbestimmung $\operatorname{sgn}(a)$ , der Berechnung des Negativen $- a$ sowie der Betragsbildung $| a |$ sind alle in linearer Zeit $O (l)$ mit $l = L (a)$ durchführbar; die Addition $a + b$ sowie der Vergleich zweier Zahlen $a < b$ sind in linearer Zeit $O (l)$ mit $l = max(L (a), L (b))$ zu bewältigen. Der n-Shift $2^n\cdot a$ ist in $O (n + l)$ durchführbar.

Sind zwei „ungleich“ große Zahlen a und b zu addieren, so definieren wir mit

$l_m := {\rm min}(L(a),\, L(b))$

die kleinere der beiden Bitlängen des Inputs. Es wird immer wieder behauptet, dass die Addition in $O\left(l_m \right)$ durchführbar sei. Dies ist allerdings aufgrund der Möglichkeit eines Übertrages bis zum höchstwertigen Bit der größeren Zahl (englisch „carry propagation“) falsch.

Ein erstes schönes, echt nicht-triviales Ergebnis der Computer-Algebra ist die Erkenntnis, dass die Multiplikation $a\cdot b$ wesentlich schneller als in $O\left(l^2\right)$ (was dem naiven Multiplikationsalgorithmus entspricht) lösbar ist. Eine Beschleunigung erreichte zunächst Karatsuba mit dem Karatsuba-Algorithmus; dieser wurde dann als ein Spezialfall einer noch allgemeineren Algorithmenfamilie erkannt, die unter den Begriff Toom-Cook-Algorithmus subsumiert werden. Bahnbrechend war dann der von Arnold Schönhage und Volker Strassen 1971 vorgestellte auf diskreten Fourier-Transformationen basierende Schönhage-Strassen-Algorithmus, für den die Autoren selbst eine Komplexität von

$O(l \cdot \log\, l \cdot \log\,\log\, l )$

nachwiesen. Bedenkt man, wie aufwendig der „naive“ Multiplikationsalgorithmus ist, so erscheint diese Komplexität unglaublich „schnell“. Da der Algorithmus allerdings ziemlich komplex und schwierig programmierbar ist, haben Scharen von Programmierern einen Bogen um ihn gemacht; er wartet bis heute auf eine effiziente Implementierung in einem Computer-Algebra-System. Eine Teilimplementierung des Algorithmus von Schönhage und Strassen wurde von Daniel J. Bernstein verwirklicht.

Da diese Komplexität der Integer-Multiplikation in der gesamten Computer-Algebra von absolut tragender Bedeutung ist, wurde hierfür eine Kurznotation

$\psi(l) := O(l \cdot \log\, l \cdot \log\,\log\, l)$

eingeführt.

Sind zwei „ungleich“ große Zahlen a und b zu multiplizieren, so kann man eine für Folgeabschätzungen sehr wichtige Verfeinerung der Komplexitätsabschätzung vornehmen: Dann ist die Multiplikation sogar in

$O\left(\frac{l}{l_m} \cdot\psi(l_m)\right)$

durchführbar. Der Beweis hierfür ist durchaus schon etwas aufwändiger.

Ausgestattet mit dieser „schnellen“ Integer-Multiplikation kann nun der Katalog der Grundrechenarten für die Arithmetik in $\mathbb Z$ wie folgt vervollständigt werden:

Die Aufgabe der Berechnung von $a n$ ist in $O\left(\psi(n l)\right)$ durchführbar; für die (simultane) Berechnung der Binomialkoeffizienten ${n\choose 0}\cdots{n\choose n}$ wird $O\left(n\cdot\psi(n)\right)$ benötigt. Die ganzzahlige Division $a / b$ (mit Quotient und Rest als Ergebnis) benötigt

$O\left(\frac{l}{l_m} \cdot\psi(l_m)\right)$ .

Die Berechnung des größten gemeinsamen Teilers $gcd(a, b)$ benötigt

$O\left(\left(\frac{l}{l_m} + {\rm log}\, l_m\right)\cdot\psi(l_m)\right)$ .

In gleicher Komplexität ist auch $gcdex(a, b)$ berechenbar, d. h. die Kofaktoren $u, v$ mit $gcd(a, b) = u a + v b$ werden mitberechnet.

[Bearbeiten] Effiziente exakte Arithmetik mit rationalen Zahlen

Bevor exakte Arithmetik in $\mathbb Q$ konkret durchgeführt werden kann, muss erst eine kanonische Darstellung (Repräsentation) rationaler Zahlen gefunden werden; dieses Problem tauchte bei der exakten Arithmetik der ganzen Zahlen noch nicht auf. Rationale Zahlen sind Äquivalenzklassen „bedeutungsgleicher“ Brüche aus ganzen Zahlen; zum Beispiel sind $\frac{1}{2}$ und $\frac{2}{4}$ unterschiedliche Repräsentanten der gleichen rationalen Zahl.

Die gängigste kanonische Darstellung rationaler Zahlen wird festgelegt, indem alle gemeinsamen Teiler aus Zähler und Nenner herausgekürzt werden: Jede rationale Zahl ist dann eindeutig durch einen gekürzten Bruch

$\frac{p}{q}$ mit $p\in \mathbb Z$ , $q\in\mathbb N$ und

ggT(p, q) = 1

repräsentierbar. Ist diese Festlegung einmal getroffen, so beinhaltet jede elementare Operation in $\mathbb Q$ wie Addition und Multiplikation auch notwendigerweise die Aufgabe des Herauskürzens des größten gemeinsamen Teilers aus Zähler und Nenner des Ergebnisbruches.

Dank der Resultate der exakten Arithmetik in $\mathbb Z$ sind damit die Operationen $a+b,\quad a-b, \quad a\cdot b, \quad a/b$ alle in der Komplexität

$O\left( \psi(l)\cdot {\rm log}\, l \right)$

durchführbar. Von der Hoffnung, die Addition rationaler Zahlen in linearer Komplexität bewerkstelligen zu können, muss man hierbei Abschied nehmen.

Glücklicherweise kann die Berechnung des größten gemeinsamen Teilers sehr effizient mit Hilfe des Euklidischen Algorithmus berechnet werden. Der Euklidische Algorithmus spielt an vielen Stellen in der Computeralgebra in wechselnden Varianten eine tragende Rolle.

[Bearbeiten] Effiziente exakte Arithmetik mit rationalen Polynomen in $\mathbb Q\left[x\right]$

Es genügt hierbei, die Arithmetik in $\mathbb Z\left[x\right]$ zu betrachten, da Operationen mit rationalen Polynomen in naheliegender Weise durch jeweiliges Ausklammern der Hauptnenner auf Operationen mit ganzzahligen Polynomen zurückgeführt werden können. Für Polynome $f\in \mathbb Z[x]$ definiert man die (Koeffizienten-) Länge $L (f)$ als das Maximum der Längen der einzelnen Koeffizienten.

Für die folgende Laufzeitentabelle wichtiger Berechnungsprobleme in $\Z[x]$ setzen wir folgendes voraus:

$f, g\in\Z\left[x\right]$
vom Grad $d f = deg f$ bzw. $d g = deg g,$ ferner $d = \max(d_f,d_g),\, d_m = \min(d_f,d_g)$ ,
von der Länge $l f = L (f)$ bzw. $l g = L (g),$ ferner $l = max(l f, l g)$ und $l m = min(l f, l g)$ ,
daneben sei $a\in\Z$ mit Bitlänge $l a = L (a)$ .

Dann führen die (gemäß Bitkomplexität) schnellsten bislang bekannten Algorithmen zu folgender Laufzeittabelle:

Operation	Komplexität als $O(\dots)$	bei ungleichen Eingabegrößen
$f + g$	$d\, l$	$d_m\, l$
$f\cdot g$	$ψ(d (l + log d))$	$\frac{d}{d_m}\,\psi(d_m((d-d_m+1)l+\log d))$
$f / g$ Division mit Rest	$ψ(d (l + log d))$	$\frac{dl}{d_m l_m}\,\psi(d_m(l_m+\log d_m))$
$\operatorname{prem}(f,g)$	$-$	$\frac{d}{d_m}\,\psi(d_m((d-d_m+1)l+\log d))$
$f k$	$ψ(k d (l + log d))$	$-$
$f (a x)$ Skalierung	$d\,\psi(l+d l_a)$	$-$
$a^d f(\frac{x}{a})$ Skalierung	$d\,\psi(l+d l_a)$	$-$
$f (2 x)$ Skalierung	$d (l + d)$	$-$
$2^d f(\frac{x}{2})$ Skalierung	$d (l + d)$	$-$