Computeralgebra

Kernidee und Ziel

Computeralgebra ist ein Teilgebiet von Mathematik und Informatik. Sie beschäftigt sich mit der automatisierten symbolischen Manipulation algebraischer Ausdrücke. Symbolisch bedeutet: Es wird mit Zeichen, Variablen und exakten Ausdrücken gerechnet, nicht nur mit Zahlenwerten.

Das Hauptziel ist, algebraische Ausdrücke durch konservative Rechnungen umzuformen und möglichst kompakt darzustellen. Dabei bleiben Wertigkeit und Präzision der Gleichung erhalten. Rundungen oder Näherungen sind nicht zugelassen. Zugleich sollen die verwendeten Algorithmen effizient sein, also mit möglichst geringem Rechenaufwand arbeiten.

Mathematik und Informatik sind in der Computeralgebra eng verbunden. Die Komplexitätstheorie hilft bei der Analyse, wie aufwendig Algorithmen sind. Die Softwaretechnik ist wichtig, um solche Algorithmen praktisch in Computeralgebrasystemen umzusetzen.

Ein Schwerpunkt liegt auf exaktem Rechnen mit ganzen Zahlen, rationalen Zahlen, algebraischen Zahlen und Polynomen über diesen Zahlenräumen. Weitere wichtige Aufgaben sind das symbolische Lösen von Gleichungen, das symbolische Summieren von Reihen, die symbolische Berechnung von Grenzwerten sowie symbolisches Differenzieren und Integrieren. Symbolisches Integrieren wird auch algebraische Integration genannt.

Praktisch werden die Ergebnisse in Computeralgebrasystemen genutzt. Solche Systeme ermöglichen die rechnergestützte Manipulation algebraischer Ausdrücke und sind ein wichtiges Werkzeug für Mathematiker und Naturwissenschaftler verschiedener Fachrichtungen.

Mathematische Grundlagen

Computeralgebra unterscheidet sich von der Numerik dadurch, dass sie exakt rechnen will. In der Numerik wird häufig mit Gleitkomma-Approximationen gearbeitet, also mit Näherungswerten. Für exaktes Rechnen muss man genau festlegen, in welchen mathematischen Strukturen gerechnet wird. Typische zugrundeliegende Strukturen sind Gruppen, Ringe und Körper.

Eine Gruppe ist eine algebraische Struktur, in der eine Verknüpfung bestimmten Regeln folgt. Alle endlichen Gruppen lassen sich im Computer darstellen. Für bestimmte unendliche Gruppen gibt es ebenfalls Algorithmen, zum Beispiel für polyzyklische Gruppen.

Ein Ring heißt berechenbar oder effektiv, wenn drei Bedingungen erfüllt sind: Erstens können seine Elemente auf einem Computer dargestellt werden, insbesondere mit endlicher Darstellung. Zweitens kann in endlicher Zeit entschieden werden, ob zwei Elemente gleich sind. Drittens gibt es Algorithmen für die Ringoperationen „+“ und „·“.

Beispiele für berechenbare Ringe sind die natürlichen Zahlen \mathbb{N}, die ganzen Zahlen \mathbb{Z}, die rationalen Zahlen \mathbb{Q} und alle Formen von endlichen Körpern. Aus einem berechenbaren Ring R lassen sich weitere berechenbare Ringe konstruieren, etwa Polynomringe über R, rationale Funktionen über R, Matrizen über R, alle endlichen algebraischen Erweiterungen der genannten Körper und alle endlichen transzendenten Erweiterungen der genannten Körper.

Neben den Elementen solcher Bereiche betrachtet die Computeralgebra auch formale Objekte. Dazu gehören Integrale, Reihen, formale Potenzreihen sowie Differential- und Differenzengleichungen beziehungsweise entsprechende Operatoren. Dabei geht es meist nicht um die Berechnung einzelner Zahlenwerte, sondern zum Beispiel um geschlossene Formeln als Lösungen.

Anwendungsgebiete

In Naturwissenschaft und Technik standen traditionell numerische Methoden im Vordergrund. Durch symbolische Methoden der Computeralgebra entstanden neue Anwendungsgebiete, besonders dort, wo exakte Lösungen wichtig sind, wo mathematische Strukturen wie Symmetrien beschrieben werden sollen oder wo Probleme von unbestimmten Parametern abhängen.

In der Physik und ihren technologischen Anwendungen werden symbolisch-numerische Berechnungen komplexer Probleme genutzt, unter anderem in der Himmelsmechanik, der Hochenergiephysik mit Feynman-Integralen und der Relativitätstheorie mit Differentialgeometrie. Dazu kommen Integration und Lösung von Differentialgleichungen in geschlossener Form, symbolische Berechnungen in den Algebren der Quantenmechanik und die Klassifikation höherdimensionaler kristallographischer Gruppen zur Beschreibung von inkommensurabel modulierten Strukturen, Quasikristallen und magnetischen Strukturen.

In der Chemie werden Methoden der Darstellungstheorie zur Klassifikation von Graphen chemischer Verbindungen eingesetzt, besonders bei Isomeren. Außerdem können große Gleichungssysteme gelöst werden, um chemische Reaktionsgleichgewichte bei variablen Reaktionsbedingungen zu bestimmen, etwa bei Verbrennungsprozessen und der Abgasregulierung.

In der Informationssicherheit nutzt man algebraische Methoden zur Fehlererkennung und Fehlerkorrektur bei der Nachrichtenübertragung. Auch kryptographische Kodierung vertraulicher Nachrichten durch Public-Key-Verfahren verwendet Methoden der Zahlentheorie und algebraischer Gruppen. Außerdem können Sicherheitsmechanismen und Protokolle verifiziert werden.

Weitere Anwendungen liegen in der Robotik, etwa bei Bewegungsplanung und Regulierung autonomer Roboter in der Raumfahrt, bei zylindrisch algebraischer Zellenzerlegung des \mathbb{R}^n und bei geometrischer Bildverarbeitung im Maschinensehen. Im computergestützten Entwurf, also CAD, werden flexible Inferenzsysteme für geometrische Modellierung parametrisierter Probleme und die Konstruktion von Übergangsflächen genannt. In der Kontrolltheorie geht es um Stabilität und Sicherheit von Kontrollsystemen mit Rückkopplung. In der Genforschung dient Computeralgebra zur Klassifikation von DNA-Strukturen.

Auch in der Ausbildung spielen Computeralgebrasysteme eine Rolle. Sie versprechen eine Verbesserung des Mathematikunterrichts, weil man sich stärker auf Unterrichtsinhalte konzentrieren kann. Außerdem werden realistischere anwendungsbezogene Aufgaben möglich.

Komplexität bei ganzen Zahlen

Für exakte Arithmetik mit ganzen Zahlen muss die Zeitkomplexität von Aufgaben und Algorithmen klassifiziert werden. Dafür braucht man zuerst ein Rechnermodell. Ein anschauliches Modell ist die Mehrband-Turingmaschine, eine Variante der klassischen Turingmaschine mit mehreren Bändern und je einem Schreib-/Lesekopf. Für Abschätzungen wird die Landau-Notation verwendet. Unter \operatorname{log} versteht man bei Bedarf einen Logarithmus zu einer nicht spezifizierten Basis B>1. Als Zeitmaß dient die Zahl der benötigten Bitoperationen, abhängig von der Bitlänge des Inputs.

Für eine ganze Zahl a\in\mathbb{Z}, die nicht null ist, wird die Bitlänge als L(a):=\lfloor \log_2 |a|\rfloor definiert. Zusätzlich gilt L(0):=1. Zur konkreten Speicherung einer ganzen Zahl braucht man außerdem mindestens ein Bit für das Vorzeichen.

Einfache Operationen sind vergleichsweise günstig. Die Vorzeichenbestimmung \operatorname{sgn}(a), die Berechnung von -a und die Betragsbildung |a| sind in linearer Zeit O(l) mit l=L(a) durchführbar. Addition a+b und Vergleich a<b sind ebenfalls in linearer Zeit O(l) möglich, wobei l=\max(L(a),L(b)) gilt. Der n-Shift 2^n\cdot a ist in O(n+l) durchführbar.

Ein wichtiges Ergebnis ist, dass Multiplikation a\cdot b schneller möglich ist als mit dem naiven Algorithmus der Ordnung O(l^2). Der Karazuba-Algorithmus von Anatoli Karazuba brachte eine Beschleunigung. Später wurde er als Spezialfall der allgemeineren Toom-Cook-Algorithmen erkannt. Besonders wichtig war der 1971 von Arnold Schönhage und Volker Strassen vorgestellte Schönhage-Strassen-Algorithmus auf Basis diskreter Fourier-Transformationen. Für ihn wurde die Komplexität O(l\cdot \log l\cdot \log\log l) nachgewiesen. Der Artikel weist zugleich darauf hin, dass dieser Algorithmus komplex und schwierig programmierbar ist und es bis heute keine effiziente Implementierung in einem Computeralgebrasystem gebe.

Da Integer-Multiplikation für die Computeralgebra grundlegend ist, wird die Kurznotation \psi(l):=O(l\cdot \log l\cdot \log\log l) eingeführt. Mit schneller Integer-Multiplikation lassen sich weitere Operationen beschreiben: Die Berechnung von a^n ist in O(\psi(nl)) möglich. Die simultane Berechnung der Binomialkoeffizienten {n\choose 0}\cdots {n\choose n} benötigt O(n\cdot\psi(n)). Ganzzahlige Division a/b mit Quotient und Rest benötigt O((l/l_m)\cdot\psi(l_m)). Die Berechnung des größten gemeinsamen Teilers \operatorname{gcd}(a,b) benötigt O(((l/l_m)+\log l_m)\cdot\psi(l_m)). In gleicher Komplexität ist auch \operatorname{gcdex}(a,b) berechenbar, also die Mitberechnung von Kofaktoren u,v mit \operatorname{gcd}(a,b)=ua+vb.

Rationale Zahlen und Polynome

Bei rationalen Zahlen \mathbb{Q} entsteht ein Darstellungsproblem, das es bei ganzen Zahlen nicht in gleicher Weise gibt. Rationale Zahlen sind Äquivalenzklassen bedeutungsgleicher Brüche aus ganzen Zahlen. Zum Beispiel sind \tfrac{1}{2} und \tfrac{2}{4} verschiedene Repräsentanten derselben rationalen Zahl.

Die übliche kanonische Darstellung rationaler Zahlen ist der vollständig gekürzte Bruch. Jede rationale Zahl wird eindeutig als \frac{p}{q} mit p\in\mathbb{Z}, q\in\mathbb{N} und \operatorname{ggT}(p,q)=1 dargestellt. Dadurch gehört zu jeder elementaren Operation in \mathbb{Q}, etwa Addition oder Multiplikation, auch das Kürzen des Ergebnisbruches mit dem größten gemeinsamen Teiler. Für a+b, a-b, a\cdot b und a/b ergibt sich mit den Resultaten für \mathbb{Z} die Komplexität O(\psi(l)\cdot\log l). Die Addition rationaler Zahlen ist daher nicht in linearer Komplexität zu erwarten. Wichtig ist hier der Euklidische Algorithmus, mit dem der größte gemeinsame Teiler sehr effizient berechnet werden kann; er spielt in vielen Varianten eine tragende Rolle in der Computeralgebra.

Für Polynome in \mathbb{Q}[x] genügt es, die Arithmetik in \mathbb{Z}[x] zu betrachten. Operationen mit rationalen Polynomen können durch Ausklammern der Hauptnenner auf Operationen mit ganzzahligen Polynomen zurückgeführt werden. Für ein Polynom f\in\mathbb{Z}[x] wird die Koeffizientenlänge L(f) als Maximum der Längen seiner Koeffizienten definiert.

Für zwei Polynome f,g\in\mathbb{Z}[x] betrachtet man ihre Grade d_f=\deg f, d_g=\deg g, außerdem d=\max(d_f,d_g) und d_m=\min(d_f,d_g). Für die Längen gelten l_f=L(f), l_g=L(g), l=\max(l_f,l_g) und l_m=\min(l_f,l_g). Für a\in\mathbb{Z} gilt zusätzlich l_a=L(a).

Die schnellsten bekannten Algorithmen gemäß Bitkomplexität führen zu Laufzeiten wie O(dl) für f+g, O(\psi(d(l+\log d))) für f\cdot g sowie ebenfalls O(\psi(d(l+\log d))) für Division mit Rest f/g. Für Potenzen gilt f^k in O(\psi(kd(l+\log d))). Skalierungen wie f(ax) und a^d f(x/a) haben die Komplexität O(d\,\psi(l+dl_a)), während spezielle Skalierungen mit 2, also f(2x) und 2^d f(x/2), mit O(d(l+d)) angegeben werden.