imported>MrBenjo: +Normdaten

2025-10-30T21:06:22Z

+Normdaten

Neue Seite

Die '''Computeralgebra''' ist das Teilgebiet der [[Mathematik]] und [[Informatik]], das sich mit der automatisierten [[Symbolische Mathematik|symbolischen Manipulation]] [[algebra]]ischer Ausdrücke beschäftigt.

== Überblick ==

Hauptziel der Computeralgebra ist es, durch konservative Rechnungen algebraische Ausdrücke umzuformen und eine möglichst kompakte Darstellung zu erzielen. Die Wertigkeit und Präzision der Gleichung wird dabei nicht angetastet. Rundungen oder Näherungen werden nicht zugelassen. Eine Nebenbedingung ist hierbei, die verwendeten Algorithmen und Methoden effizient zu gestalten.

Die Disziplinen Mathematik und [[Informatik]] sind in der Computeralgebra eng miteinander verwoben, einerseits über die [[Komplexitätstheorie]] für die Analyse, andererseits über die [[Softwaretechnik]] für die praktische Umsetzung computeralgebraischer Algorithmen.

Einen Schwerpunkt bildet das exakte Rechnen mit [[Ganze Zahl|ganzen]], [[Rationale Zahl|rationalen]] und [[Algebraische Zahl|algebraischen Zahlen]] sowie mit [[Polynom]]en über diesen Zahlenräumen. Eine weitere Anwendung ist das symbolische [[Lösen von Gleichungen]] aller Arten, das symbolische Summieren von [[Reihe (Mathematik)|Reihen]], die symbolische Berechnung von [[Grenzwert (Folge)|Grenzwerten]] und das symbolische Differenzieren und Integrieren (auch [[Algebraische Integration]] genannt).

Praktische Anwendung erfahren solche Ergebnisse durch den Einsatz effizienter Algorithmen bei der Entwicklung und Verbesserung von [[Computeralgebrasystem]]en, die die rechnergestützte Manipulation algebraischer Ausdrücke ermöglichen. Diese Systeme sind auch ein immer wichtiger werdendes Werkzeug für Mathematiker und Naturwissenschaftler verschiedener Fachrichtungen.

== Zugrundeliegende Strukturen ==

Anders als in der [[Numerik]], wo mit [[Gleitkommazahl|Gleitkomma-Approximationen]] der auftretenden Zahlen gerechnet wird, hat die Computeralgebra den Anspruch, stets exakt zu rechnen. Entsprechend ist es grundsätzlich notwendig, Anforderungen an die zugrundeliegenden Strukturen (in der Regel [[Gruppe (Mathematik)|Gruppen]], [[Ring (Algebra)|Ringe]] oder [[Körper (Algebra)|Körper]]) zu spezifizieren.

=== Gruppen ===

Alle [[Endliche Gruppe|endlichen Gruppen]] lassen sich im Computer darstellen, für [[unendliche Gruppe]]n gibt es unter bestimmten Voraussetzungen Algorithmen, etwa für [[polyzyklische Gruppe]]n.

=== Berechenbare Ringe ===

Ein [[Ring (Algebra)|Ring]] heißt ''berechenbar'' (oder „effektiv“), wenn folgende Bedingungen gelten:
* Die Elemente des Rings können auf einem Computer dargestellt werden, insbesondere muss die Darstellung der Elemente endlich sein,
* [[Identitätsgleichung|Gleichheit]] zwischen zwei Elementen kann in endlicher Zeit entschieden werden,
* es gibt [[Algorithmus|Algorithmen]], mit denen die Ringoperationen „+“ und „·“ durchgeführt werden können.

=== Beispiele ===

Berechenbar sind etwa:
* die [[Natürliche Zahlen|natürlichen Zahlen]] <math>\N</math>
* die [[Ganze Zahlen|ganzen Zahlen]] <math>\Z</math>
* die [[Rationale Zahlen|rationalen Zahlen]] <math>\Q</math>
* alle Formen von [[Endlicher Körper|endlichen Körpern]].

Aus einem berechenbaren Ring <math>R</math> lassen sich weitere berechenbare Ringe konstruieren:

* [[Polynomring]]e über <math>R</math>
* [[Rationale Funktion]]en über <math>R</math>
* [[Matrix (Mathematik)|Matrizen]] über <math>R</math>
* Alle endlichen [[Algebraische Erweiterung|algebraischen Erweiterungen]] der obigen Körper,
* Alle endlichen [[Transzendente Erweiterung|transzendenten Erweiterungen]] der obigen Körper.

=== Formale Objekte ===

In der Computeralgebra werden neben den Elementen der zugrundeliegenden Bereiche noch weitere „formale“ Objekte betrachtet wie etwa
* [[Integralrechnung|Integrale]],
* [[Unendliche Reihe|Reihen]],
* ([[Formale Potenzreihe|formale]]) [[Potenzreihe]]n,
* [[Differenzialgleichung|Differential-]] und [[Differenzengleichung]]en (bzw. -operatoren).

Hierbei geht es in der Regel nicht um die Berechnung von Zahlwerten, sondern beispielsweise um die Bestimmung von „geschlossenen Formeln“ als Lösungen.

== Anwendungen ==

Bei den Anwendungen mathematischer Methoden in Naturwissenschaft und Technik stehen traditionell [[Numerik|numerische]] Methoden im Vordergrund. Mit den symbolischen Methoden der Computeralgebra haben sich neue Anwendungsgebiete eröffnet, bei denen es auf exakte Lösungen ankommt und bei denen strukturmathematische Überlegungen, z. B. zur Beschreibung von Symmetrien, eingehen; ferner die Behandlung von Problemen, die von unbestimmten Parametern abhängen.

Dazu gehören etwa:
* In der [[Physik]] und ihren technologischen Anwendungen: Gemischt symbolisch-numerische Berechnungen komplexer Probleme in der [[Himmelsmechanik]], der [[Hochenergiephysik]] ([[Feynman-Integrale]]) und der [[Relativitätstheorie]] ([[Differentialgeometrie]]); [[Integralrechnung|Integration]] und Lösung von [[Differentialgleichungen]] in geschlossener Form; symbolische Berechnungen in den Algebren der [[Quantenmechanik]]; Klassifikation höherdimensionaler kristallographischer [[Gruppentheorie|Gruppen]] zur Beschreibung von inkommensurabel modulierten Strukturen, Quasikristallen und magnetischen Strukturen.
* In der [[Chemie]]: Anwendungen der Darstellungstheorie auf die Klassifikation von Graphen chemischer Verbindungen, insbesondere von [[Isomer]]en; Lösung großer [[Gleichungssystem]]e zur Bestimmung chemischer Reaktionsgleichgewichte bei variablen Reaktionsbedingungen, z. B. bei Verbrennungsprozessen und der Abgasregulierung.
* In der [[Informationssicherheit]]: Algebraische Methoden der Fehlererkennung und -korrektur bei der Nachrichtenübertragung; [[Kryptographie|kryptographische]] Kodierung von vertraulichen Nachrichten durch [[Public-Key-Verfahren]] mit Methoden der [[Zahlentheorie]] und der [[Algebraische Gruppe|algebraischen Gruppen]]; Verifikation von Sicherheitsmechanismen (Protokollen).
* In der [[Robotik]]: Bewegungsplanung und Regulierung autonomer Roboter z. B. in der [[Raumfahrt]]; zylindrisch algebraische Zellenzerlegung des <math>\R^n</math>; geometrische [[Bildverarbeitung]] beim [[Maschinelles Sehen|Maschinensehen]].
* Im [[Computer-aided design|computergestützten Entwurf (CAD)]]: Flexible Inferenzsysteme für die geometrische Modellierung parametrisierter Probleme; Konstruktion von Übergangsflächen.
* In der [[Kontrolltheorie]]: Untersuchung der Stabilität und Sicherheit von Kontrollsystemen mit Rückkopplung.
* In der [[Genforschung]]: Klassifikation von DNA-Strukturen.
* In der [[Ausbildung]]: Computeralgebrasysteme versprechen eine Verbesserung des Mathematikunterrichts, da es durch ihren Einsatz möglich wird, sich mehr auf die Unterrichtsinhalte zu konzentrieren. Ferner ist die Behandlung realistischerer anwendungsbezogener Aufgaben möglich.

Die Methoden der Computeralgebra erlauben in diesen Anwendungsbereichen eine automatische Behandlung von Problemen, die sonst nur mühsam mit Ad-hoc-Ansätzen angegangen werden konnten. Das große Potential dieser Methoden ist dabei noch lange nicht ausgeschöpft. Kontinuierliche Förderung dieser Anwendungen und der zugrundeliegenden Algorithmen kombiniert mit immer leistungsstärkerer Hardware werden dem Gebiet Computeralgebra weitere Entwicklungsmöglichkeiten geben.

== Komplexitätsbetrachtungen ==
=== Effiziente exakte Arithmetik mit ganzen Zahlen ===

Will man die Zeitkomplexität von Aufgaben und Algorithmen zur exakten Arithmetik mit [[Ganze Zahlen|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 <math>\operatorname{log}</math> ein [[Logarithmus]] zu einer nicht spezifizierten Basis <math>B>1</math> 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 <math> a \in \mathbb Z</math> nicht null, so wird
:<math> L(a) := \lfloor \log_2 |a|\rfloor </math>
gesetzt; zusätzlich wird <math> L(0):=1 </math> definiert. Für die konkrete Speicherung einer ganzen Zahl wird zusätzlich mindestens noch ein Bit für das [[Vorzeichen (Zahl)|Vorzeichen]] benötigt.

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

Ein nicht-triviales Ergebnis der Computeralgebra ist die Erkenntnis, dass die Multiplikation <math> a\cdot b</math> wesentlich schneller als in <math>O\left(l^2\right)</math> (was dem naiven Multiplikationsalgorithmus entspricht) lösbar ist. Eine Beschleunigung erreichte zunächst [[Anatoli Alexejewitsch Karazuba|Anatoli Karazuba]] mit dem [[Karazuba-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
: <math>O(l \cdot \log\, l \cdot \log\,\log\, l )</math>
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, gibt es bis heute keine effiziente Implementierung in einem Computeralgebrasystem.

Da die Komplexität der Integer-Multiplikation in der gesamten Computeralgebra von absolut tragender Bedeutung ist, wurde hierfür eine Kurznotation
: <math> \psi(l) := O(l \cdot \log\, l \cdot \log\,\log\, l)</math>
eingeführt. Ausgestattet mit dieser „schnellen“ Integer-Multiplikation kann nun der Katalog der [[Grundrechenart]]en für die Arithmetik in <math>\mathbb Z</math> wie folgt vervollständigt werden: Die Aufgabe der Berechnung von <math>a^n</math> ist in <math>O\left(\psi(n l)\right)</math> durchführbar; für die (simultane) Berechnung der Binomialkoeffizienten <math>{n\choose 0}\cdots{n\choose n}</math> wird <math> O\left(n\cdot\psi(n)\right)</math> benötigt. Die ganzzahlige Division <math> a/b </math> (mit Quotient und Rest als Ergebnis) benötigt
: <math> O\left(\frac{l}{l_m} \cdot\psi(l_m)\right) </math>.
Die Berechnung des größten gemeinsamen Teilers <math> \operatorname{gcd}(a,b)</math> benötigt
: <math> O\left(\left(\frac{l}{l_m} + \log l_m\right)\cdot\psi(l_m)\right) </math>.
In gleicher Komplexität ist auch <math> \operatorname{gcdex}(a,b)</math> berechenbar, d. h. die Kofaktoren <math> u, v</math> mit <math> \operatorname{gcd}(a,b) = ua+vb</math> werden mitberechnet.

=== Effiziente exakte Arithmetik mit rationalen Zahlen ===

Bevor exakte Arithmetik in <math>\mathbb Q</math> 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
<math>\tfrac{1}{2}</math> und <math>\tfrac{2}{4}</math> 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ürzter Bruch|gekürzten Bruch]]
:<math>\frac{p}{q}\quad</math> mit <math>\quad p\in \mathbb Z,</math> <math>q\in\mathbb N</math> und <math>\operatorname{ggT}(p,q) = 1</math>
repräsentierbar. Ist diese Festlegung einmal getroffen, so beinhaltet jede elementare Operation in <math>\mathbb Q</math> wie Addition und Multiplikation auch notwendigerweise die Aufgabe des Herauskürzens des [[größter gemeinsamer Teiler|größten gemeinsamen Teilers]] aus Zähler und Nenner des Ergebnisbruches.

Dank der Resultate der exakten Arithmetik in <math>\mathbb Z</math> sind damit die Operationen
<math>a+b,\ a-b,\ a \cdot b,\ a/b</math> alle in der Komplexität
: <math> O\left( \psi(l)\cdot \log l \right) </math>
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 [[Euklidischer Algorithmus|Euklidischen Algorithmus]] berechnet werden. Der Euklidische Algorithmus spielt an vielen Stellen in der Computeralgebra in wechselnden Varianten eine tragende Rolle.

=== {{Anker|Polynome}}Effiziente exakte Arithmetik mit Polynomen in ℚ[x] ===

Es genügt hierbei, die Arithmetik in <math>\mathbb Z\left[x\right]</math> 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 <math> f\in \mathbb Z[x]</math> definiert man die (Koeffizienten-)Länge <math>L(f)</math> als das Maximum der Längen der einzelnen Koeffizienten.

Für die folgende Laufzeitentabelle wichtiger Berechnungsprobleme in <math>\Z[x]</math> setzen wir folgendes voraus:
* <math>f, g\in\Z\left[x\right]</math>
* vom Grad <math>d_f=\deg f</math> bzw. <math>d_g=\deg g,</math> ferner <math>d = \max(d_f,d_g),\, d_m = \min(d_f,d_g)</math>,
* von der Länge <math>l_f = L(f)</math> bzw. <math>l_g = L(g),</math> ferner <math>l = \max(l_f,l_g)</math> und <math>l_m = \min(l_f, l_g)</math>,
* daneben sei <math>a\in\Z</math> mit Bitlänge <math>l_a = L(a)</math>.

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

{| class="wikitable"
|-
|Operation
||Komplexität als <math>O(\dots)</math>||bei ungleichen Eingabegrößen
|-
|<math>f+g</math>||<math>d\, l</math>||<math>d_m\, l</math>
|-
|<math>f\cdot g</math>||<math>\psi(d(l+\log d))</math>||<math>\frac{d}{d_m}\,\psi(d_m((d-d_m+1)l+\log d))</math>
|-
|<math>f/g</math> Division mit Rest||<math>\psi(d(l+\log d))</math>||<math>\frac{dl}{d_m l_m}\,\psi(d_m(l_m+\log d_m))</math>
|-
|<math>\operatorname{prem}(f,g)</math>||<math>-</math>||<math>\frac{d}{d_m}\,\psi(d_m((d-d_m+1)l+\log d))</math>
|-
|<math>f^k</math>||<math>\psi(k d (l+\log d))</math>||<math>-</math>
|-
|<math>f(ax)</math> Skalierung||<math>d\,\psi(l+d l_a)</math>||<math>-</math>
|-
|<math>a^d f\left(\frac{x}{a}\right)</math> Skalierung||<math>d\,\psi(l+d l_a)</math>||<math>-</math>
|-
|<math>f(2x)</math> Skalierung||<math>d(l+d)</math>||<math>-</math>
|-
|<math>2^d f\left(\frac{x}{2}\right)</math> Skalierung||<math>d(l+d)</math>||<math>-</math>
|}

== Siehe auch ==
* [[Symbolische Mathematik]]

== Literatur ==
Deutschsprachige Literatur:
* Michael Kaplan: ''Computeralgebra.'' Springer, Berlin u. a. 2005, ISBN 3-540-21379-1.
* Wolfram Koepf: ''Computeralgebra. Eine algorithmisch orientierte Einführung.'' Springer, Berlin u. a. 2006, ISBN 3-540-29894-0.
* [[Attila Pethö]]: ''Algebraische Algorithmen.'' Herausgegeben von [[Michael Pohst]]. Vieweg, Braunschweig u. a. 1999, ISBN 3-528-06598-2.

Englischsprachige Literatur:
* [[Peter Bürgisser]], [[Michael Clausen]], [[Amin Shokrollahi|Mohammad Amin Shokrollahi]]: ''Algebraic Complexity Theory'' (= ''Die Grundlehren der mathematischen Wissenschaften in Einzeldarstellungen.'' 315). Springer, Berlin u. a. 1997, ISBN 3-540-60582-7 ([http://www.mathematik.de/ger/rezensionen/algebraic_complexity_theory.html Rezension]).
* [[Arjeh Cohen|Arjeh M. Cohen]], Hans Cuypers, Hans Sterk: ''Some Tapas of Computer Algebra'' (= ''Algorithms and Computation in Mathematics.'' 4). Springer, Berlin u. a. 1999, ISBN 3-540-63480-0.
* [[David A. Cox|David Cox]], [[John B. Little|John Little]], [[Donal O’Shea]]: ''Ideals, varieties, and algorithms.'' 2nd Edition. Springer, New York NY ua. a. 1997, ISBN 0-387-94680-2.
* [[Joachim von zur Gathen]], Jürgen Gerhard: ''Modern Computer Algebra.'' 2nd Edition. Cambridge University Press, Cambridge u. a. 2003, ISBN 0-521-82646-2.
* Keith O. Geddes, Stephen R. Czapor, George Labahn: ''Algorithms for Computer Algebra.'' Kluwer, Boston MA u. a. 1992, ISBN 0-7923-9259-0.

== Weblinks ==
* [http://www.fachgruppe-computeralgebra.de/ Fachgruppe Computeralgebra], gemeinsame Fachgruppe von [[Gesellschaft für Informatik|GI]], [[Deutsche Mathematiker-Vereinigung|DMV]] und [[Gesellschaft für Angewandte Mathematik und Mechanik|GAMM]]
* Sieveking: [https://web.archive.org/web/20170129104802/http://www.math.uni-frankfurt.de/~ismi/sieveking/lecturenotes/Algorithmen.pdf ''Algorithmen der Computeralgebra''.] (PDF; 666 kB) Skript, Goethe-Universität Frankfurt a. M., Archivlink, abgerufen am 26. Februar 2022

{{Normdaten|TYP=s|GND=4010449-7}}

[[Kategorie:Algebra]]
[[Kategorie:Teilgebiet der Mathematik]]

Computeralgebra - Versionsgeschichte

imported>MrBenjo: +Normdaten