www.wikidata.de-de.nina.az

Computeralgebra Die ist das Teilgebiet der Mathematik und Informatik das sich mit der automatisierten symbolischen Manip

Computeralgebra

Die Computeralgebra ist das Teilgebiet der Mathematik und Informatik, das sich mit der automatisierten symbolischen Manipulation algebraischer Ausdrücke beschäftigt.

Überblick Bearbeiten

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 ganzen, rationalen und algebraischen Zahlen sowie mit Polynomen über diesen Zahlenräumen. Eine weitere Anwendung ist das symbolische Lösen von Gleichungen aller Arten, das symbolische Summieren von Reihen, die symbolische Berechnung von 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 Computeralgebrasystemen, 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.

Zugrundeliegende Strukturen Bearbeiten

Anders als in der Numerik, wo mit 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 Gruppen, Ringe oder Körper) zu spezifizieren.

Gruppen Bearbeiten

Alle endlichen Gruppen lassen sich im Computer darstellen, für unendliche Gruppen gibt es unter bestimmten Voraussetzungen Algorithmen, etwa für polyzyklische Gruppen.

Berechenbare Ringe Bearbeiten

Ein 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,
  • Gleichheit zwischen zwei Elementen kann in endlicher Zeit entschieden werden,
  • es gibt Algorithmen, mit denen die Ringoperationen „+“ und „·“ durchgeführt werden können.

Beispiele Bearbeiten

Berechenbar sind etwa:

Aus einem berechenbaren Ring lassen sich weitere berechenbare Ringe konstruieren:

Formale Objekte Bearbeiten

In der Computeralgebra werden neben den Elementen der zugrundeliegenden Bereiche noch weitere „formale“ Objekte betrachtet wie etwa

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

Anwendungen Bearbeiten

Bei den Anwendungen mathematischer Methoden in Naturwissenschaft und Technik stehen traditionell 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); Integration und Lösung von Differentialgleichungen in geschlossener Form; symbolische Berechnungen in den Algebren der Quantenmechanik; Klassifikation höherdimensionaler kristallographischer 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 Isomeren; Lösung großer Gleichungssysteme 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; kryptographische Kodierung von vertraulichen Nachrichten durch Public-Key-Verfahren mit Methoden der Zahlentheorie und der algebraischen Gruppen; Verifikation von Sicherheitsmechanismen (Protokollen).
  • In der Robotik: Bewegungsplanung und Regulierung autonomer Roboter z. B. in der Raumfahrt; zylindrisch algebraische Zellenzerlegung des ; geometrische Bildverarbeitung beim Maschinensehen.
  • Im 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 Bearbeiten

Effiziente exakte Arithmetik mit ganzen Zahlen Bearbeiten

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 ein Logarithmus zu einer nicht spezifizierten Basis 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 nicht null, so wird

gesetzt; zusätzlich wird definiert. Für die konkrete Speicherung einer ganzen Zahl wird zusätzlich mindestens noch ein Bit für das Vorzeichen benötigt.

Die Aufgaben der Vorzeichenbestimmung der Berechnung des Negativen sowie der Betragsbildung sind alle in linearer Zeit mit durchführbar; die Addition sowie der Vergleich zweier Zahlen sind in linearer Zeit mit zu bewältigen. Der n-Shift ist in durchführbar.

Ein nicht-triviales Ergebnis der Computeralgebra ist die Erkenntnis, dass die Multiplikation wesentlich schneller als in (was dem naiven Multiplikationsalgorithmus entspricht) lösbar ist. Eine Beschleunigung erreichte zunächst 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

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

eingeführt. Ausgestattet mit dieser „schnellen“ Integer-Multiplikation kann nun der Katalog der Grundrechenarten für die Arithmetik in wie folgt vervollständigt werden: Die Aufgabe der Berechnung von ist in durchführbar; für die (simultane) Berechnung der Binomialkoeffizienten wird benötigt. Die ganzzahlige Division (mit Quotient und Rest als Ergebnis) benötigt

Die Berechnung des größten gemeinsamen Teilers benötigt

In gleicher Komplexität ist auch berechenbar, d. h. die Kofaktoren mit werden mitberechnet.

Effiziente exakte Arithmetik mit rationalen Zahlen Bearbeiten

Bevor exakte Arithmetik in 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 und 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

repräsentierbar. Ist diese Festlegung einmal getroffen, so beinhaltet jede elementare Operation in 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 sind damit die Operationen alle in der Komplexität

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.

Effiziente exakte Arithmetik mit Polynomen in ℚ[x] Bearbeiten

Es genügt hierbei, die Arithmetik in 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 definiert man die (Koeffizienten-)Länge als das Maximum der Längen der einzelnen Koeffizienten.

Für die folgende Laufzeitentabelle wichtiger Berechnungsprobleme in setzen wir folgendes voraus:

  • vom Grad bzw. ferner ,
  • von der Länge bzw. ferner und ,
  • daneben sei mit Bitlänge .

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

Operation Komplexität als bei ungleichen Eingabegrößen
Division mit Rest
Skalierung
Skalierung
Skalierung
Skalierung

Siehe auch Bearbeiten

Literatur Bearbeiten

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, Mohammad Amin Shokrollahi: Algebraic Complexity Theory (= Die Grundlehren der mathematischen Wissenschaften in Einzeldarstellungen. 315). Springer, Berlin u. a. 1997, ISBN 3-540-60582-7 (Rezension).
  • 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 Cox, 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 Bearbeiten

  • Fachgruppe Computeralgebra, gemeinsame Fachgruppe von GI, DMV und GAMM
  • Sieveking: (PDF; 666 kB) Skript, Goethe-Universität Frankfurt a. M., Archivlink, abgerufen am 26. Februar 2022
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Die Computeralgebra ist das Teilgebiet der Mathematik und Informatik das sich mit der automatisierten symbolischen Manipulation algebraischer Ausdrucke beschaftigt Inhaltsverzeichnis 1 Uberblick 2 Zugrundeliegende Strukturen 2 1 Gruppen 2 2 Berechenbare Ringe 2 3 Beispiele 2 4 Formale Objekte 3 Anwendungen 4 Komplexitatsbetrachtungen 4 1 Effiziente exakte Arithmetik mit ganzen Zahlen 4 2 Effiziente exakte Arithmetik mit rationalen Zahlen 4 3 Effiziente exakte Arithmetik mit Polynomen in ℚ x 5 Siehe auch 6 Literatur 7 WeblinksUberblick BearbeitenHauptziel der Computeralgebra ist es durch konservative Rechnungen algebraische Ausdrucke umzuformen und eine moglichst kompakte Darstellung zu erzielen Die Wertigkeit und Prazision der Gleichung wird dabei nicht angetastet Rundungen oder Naherungen 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 uber die Komplexitatstheorie fur die Analyse andererseits uber die Softwaretechnik fur die praktische Umsetzung computeralgebraischer Algorithmen Einen Schwerpunkt bildet das exakte Rechnen mit ganzen rationalen und algebraischen Zahlen sowie mit Polynomen uber diesen Zahlenraumen Eine weitere Anwendung ist das symbolische Losen von Gleichungen aller Arten das symbolische Summieren von Reihen die symbolische Berechnung von 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 Computeralgebrasystemen die die rechnergestutzte Manipulation algebraischer Ausdrucke ermoglichen Diese Systeme sind auch ein immer wichtiger werdendes Werkzeug fur Mathematiker und Naturwissenschaftler verschiedenster Fachrichtungen Zugrundeliegende Strukturen BearbeitenAnders als in der Numerik wo mit Gleitkomma Approximationen der auftretenden Zahlen gerechnet wird hat die Computeralgebra den Anspruch stets exakt zu rechnen Entsprechend ist es grundsatzlich notwendig Anforderungen an die zugrundeliegenden Strukturen in der Regel Gruppen Ringe oder Korper zu spezifizieren Gruppen Bearbeiten Alle endlichen Gruppen lassen sich im Computer darstellen fur unendliche Gruppen gibt es unter bestimmten Voraussetzungen Algorithmen etwa fur polyzyklische Gruppen Berechenbare Ringe Bearbeiten Ein Ring heisst berechenbar oder effektiv wenn folgende Bedingungen gelten Die Elemente des Rings konnen auf einem Computer dargestellt werden insbesondere muss die Darstellung der Elemente endlich sein Gleichheit zwischen zwei Elementen kann in endlicher Zeit entschieden werden es gibt Algorithmen mit denen die Ringoperationen und durchgefuhrt werden konnen Beispiele Bearbeiten Berechenbar sind etwa die naturlichen Zahlen N displaystyle mathbb N nbsp die ganzen Zahlen Z displaystyle mathbb Z nbsp die rationalen Zahlen Q displaystyle mathbb Q nbsp alle Formen von endlichen Korpern Aus einem berechenbaren Ring R displaystyle R nbsp lassen sich weitere berechenbare Ringe konstruieren Polynomringe uber R displaystyle R nbsp Rationale Funktionen uber R displaystyle R nbsp Matrizen uber R displaystyle R nbsp Alle endlichen algebraischen Erweiterungen der obigen Korper Alle endlichen transzendenten Erweiterungen der obigen Korper Formale Objekte Bearbeiten In der Computeralgebra werden neben den Elementen der zugrundeliegenden Bereiche noch weitere formale Objekte betrachtet wie etwa Integrale Reihen formale Potenzreihen Differential und Differenzengleichungen bzw operatoren Hierbei geht es in der Regel nicht um die Berechnung von Zahlwerten sondern beispielsweise um die Bestimmung von geschlossenen Formeln als Losungen Anwendungen BearbeitenBei den Anwendungen mathematischer Methoden in Naturwissenschaft und Technik stehen traditionell numerische Methoden im Vordergrund Mit den symbolischen Methoden der Computeralgebra haben sich neue Anwendungsgebiete eroffnet bei denen es auf exakte Losungen ankommt und bei denen strukturmathematische Uberlegungen z B zur Beschreibung von Symmetrien eingehen ferner die Behandlung von Problemen die von unbestimmten Parametern abhangen Dazu gehoren etwa In der Physik und ihren technologischen Anwendungen Gemischt symbolisch numerische Berechnungen komplexer Probleme in der Himmelsmechanik der Hochenergiephysik Feynman Integrale und der Relativitatstheorie Differentialgeometrie Integration und Losung von Differentialgleichungen in geschlossener Form symbolische Berechnungen in den Algebren der Quantenmechanik Klassifikation hoherdimensionaler kristallographischer 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 Isomeren Losung grosser Gleichungssysteme 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 Nachrichtenubertragung kryptographische Kodierung von vertraulichen Nachrichten durch Public Key Verfahren mit Methoden der Zahlentheorie und der algebraischen Gruppen Verifikation von Sicherheitsmechanismen Protokollen In der Robotik Bewegungsplanung und Regulierung autonomer Roboter z B in der Raumfahrt zylindrisch algebraische Zellenzerlegung des R n displaystyle mathbb R n nbsp geometrische Bildverarbeitung beim Maschinensehen Im computergestutzten Entwurf CAD Flexible Inferenzsysteme fur die geometrische Modellierung parametrisierter Probleme Konstruktion von Ubergangsflachen In der Kontrolltheorie Untersuchung der Stabilitat und Sicherheit von Kontrollsystemen mit Ruckkopplung In der Genforschung Klassifikation von DNA Strukturen In der Ausbildung Computeralgebrasysteme versprechen eine Verbesserung des Mathematikunterrichts da es durch ihren Einsatz moglich wird sich mehr auf die Unterrichtsinhalte zu konzentrieren Ferner ist die Behandlung realistischerer anwendungsbezogener Aufgaben moglich Die Methoden der Computeralgebra erlauben in diesen Anwendungsbereichen eine automatische Behandlung von Problemen die sonst nur muhsam mit Ad hoc Ansatzen angegangen werden konnten Das grosse Potential dieser Methoden ist dabei noch lange nicht ausgeschopft Kontinuierliche Forderung dieser Anwendungen und der zugrundeliegenden Algorithmen kombiniert mit immer leistungsstarkerer Hardware werden dem Gebiet Computeralgebra weitere Entwicklungsmoglichkeiten geben Komplexitatsbetrachtungen BearbeitenEffiziente exakte Arithmetik mit ganzen Zahlen Bearbeiten Will man die Zeitkomplexitat von Aufgaben und Algorithmen zur exakten Arithmetik mit ganzen Zahlen klassifizieren so muss zunachst ein Rechnermodell zugrunde gelegt werden Eine Diskussion diverser Rechnermodelle findet sich im Kapitel Komplexitat Ein relativ eingangiges Modell ist die Mehrband Turingmaschine eine Variante der klassischen Turingmaschine die mehrere Bander mit je einem Schreib Lesekopf besitzt Fur Komplexitatsabschatzungen mit der Landau Notation wird bei Bedarf unter der Bezeichnung log displaystyle operatorname log nbsp ein Logarithmus zu einer nicht spezifizierten Basis B gt 1 displaystyle B gt 1 nbsp verwendet Als Mass fur die Zeit wird die Zahl der benotigten Bitoperationen gewahlt die in Landau Notation von der Bitlange des Inputs abhangig gemacht wird Die prazise mathematische Angabe von Bit Komplexitaten fur die exakte Arithmetik mit ganzen Zahlen muss zunachst mit der genauen Festlegung der Bitlange einer ganzen Zahl starten Ist die Zahl a Z displaystyle a in mathbb Z nbsp nicht null so wird L a log 2 a displaystyle L a lfloor log 2 a rfloor nbsp gesetzt zusatzlich wird L 0 1 displaystyle L 0 1 nbsp definiert Fur die konkrete Speicherung einer ganzen Zahl wird zusatzlich mindestens noch ein Bit fur das Vorzeichen benotigt Die Aufgaben der Vorzeichenbestimmung sgn a displaystyle operatorname sgn a nbsp der Berechnung des Negativen a displaystyle a nbsp sowie der Betragsbildung a displaystyle a nbsp sind alle in linearer Zeit O l displaystyle O l nbsp mit l L a displaystyle l L a nbsp durchfuhrbar die Addition a b displaystyle a b nbsp sowie der Vergleich zweier Zahlen a lt b displaystyle a lt b nbsp sind in linearer Zeit O l displaystyle O l nbsp mit l m a x L a L b displaystyle l rm max L a L b nbsp zu bewaltigen Der n Shift 2 n a displaystyle 2 n cdot a nbsp ist in O n l displaystyle O n l nbsp durchfuhrbar Ein nicht triviales Ergebnis der Computeralgebra ist die Erkenntnis dass die Multiplikation a b displaystyle a cdot b nbsp wesentlich schneller als in O l 2 displaystyle O left l 2 right nbsp was dem naiven Multiplikationsalgorithmus entspricht losbar ist Eine Beschleunigung erreichte zunachst 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 Schonhage und Volker Strassen 1971 vorgestellte auf diskreten Fourier Transformationen basierende Schonhage Strassen Algorithmus fur den die Autoren selbst eine Komplexitat von O l log l log log l displaystyle O l cdot log l cdot log log l nbsp nachwiesen Bedenkt man wie aufwendig der naive Multiplikationsalgorithmus ist so erscheint diese Komplexitat unglaublich schnell Da der Algorithmus allerdings ziemlich komplex und schwierig programmierbar ist gibt es bis heute keine effiziente Implementierung in einem Computeralgebrasystem Da die Komplexitat der Integer Multiplikation in der gesamten Computeralgebra von absolut tragender Bedeutung ist wurde hierfur eine Kurznotation ps l O l log l log log l displaystyle psi l O l cdot log l cdot log log l nbsp eingefuhrt Ausgestattet mit dieser schnellen Integer Multiplikation kann nun der Katalog der Grundrechenarten fur die Arithmetik in Z displaystyle mathbb Z nbsp wie folgt vervollstandigt werden Die Aufgabe der Berechnung von a n displaystyle a n nbsp ist in O ps n l displaystyle O left psi nl right nbsp durchfuhrbar fur die simultane Berechnung der Binomialkoeffizienten n 0 n n displaystyle n choose 0 cdots n choose n nbsp wird O n ps n displaystyle O left n cdot psi n right nbsp benotigt Die ganzzahlige Division a b displaystyle a b nbsp mit Quotient und Rest als Ergebnis benotigt O l l m ps l m displaystyle O left frac l l m cdot psi l m right nbsp Die Berechnung des grossten gemeinsamen Teilers g c d a b displaystyle rm gcd a b nbsp benotigt O l l m l o g l m ps l m displaystyle O left left frac l l m rm log l m right cdot psi l m right nbsp In gleicher Komplexitat ist auch g c d e x a b displaystyle rm gcdex a b nbsp berechenbar d h die Kofaktoren u v displaystyle u v nbsp mit g c d a b u a v b displaystyle rm gcd a b ua vb nbsp werden mitberechnet Effiziente exakte Arithmetik mit rationalen Zahlen Bearbeiten Bevor exakte Arithmetik in Q displaystyle mathbb Q nbsp konkret durchgefuhrt werden kann muss erst eine kanonische Darstellung Reprasentation rationaler Zahlen gefunden werden dieses Problem tauchte bei der exakten Arithmetik der ganzen Zahlen noch nicht auf Rationale Zahlen sind Aquivalenzklassen bedeutungsgleicher Bruche aus ganzen Zahlen zum Beispiel sind 1 2 displaystyle frac 1 2 nbsp und 2 4 displaystyle frac 2 4 nbsp unterschiedliche Reprasentanten der gleichen rationalen Zahl Die gangigste kanonische Darstellung rationaler Zahlen wird festgelegt indem alle gemeinsamen Teiler aus Zahler und Nenner herausgekurzt werden Jede rationale Zahl ist dann eindeutig durch einen gekurzten Bruch p q displaystyle frac p q nbsp mit p Z displaystyle p in mathbb Z nbsp q N displaystyle q in mathbb N nbsp und g g T p q 1 displaystyle rm ggT p q 1 nbsp reprasentierbar Ist diese Festlegung einmal getroffen so beinhaltet jede elementare Operation in Q displaystyle mathbb Q nbsp wie Addition und Multiplikation auch notwendigerweise die Aufgabe des Herauskurzens des grossten gemeinsamen Teilers aus Zahler und Nenner des Ergebnisbruches Dank der Resultate der exakten Arithmetik in Z displaystyle mathbb Z nbsp sind damit die Operationen a b a b a b a b displaystyle a b quad a b quad a cdot b quad a b nbsp alle in der Komplexitat O ps l l o g l displaystyle O left psi l cdot rm log l right nbsp durchfuhrbar Von der Hoffnung die Addition rationaler Zahlen in linearer Komplexitat bewerkstelligen zu konnen muss man hierbei Abschied nehmen Glucklicherweise kann die Berechnung des grossten 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 Effiziente exakte Arithmetik mit Polynomen in ℚ x Bearbeiten Es genugt hierbei die Arithmetik in Z x displaystyle mathbb Z left x right nbsp zu betrachten da Operationen mit rationalen Polynomen in naheliegender Weise durch jeweiliges Ausklammern der Hauptnenner auf Operationen mit ganzzahligen Polynomen zuruckgefuhrt werden konnen Fur Polynome f Z x displaystyle f in mathbb Z x nbsp definiert man die Koeffizienten Lange L f displaystyle L f nbsp als das Maximum der Langen der einzelnen Koeffizienten Fur die folgende Laufzeitentabelle wichtiger Berechnungsprobleme in Z x displaystyle mathbb Z x nbsp setzen wir folgendes voraus f g Z x displaystyle f g in mathbb Z left x right nbsp vom Grad d f deg f displaystyle d f deg f nbsp bzw d g deg g displaystyle d g deg g nbsp ferner d max d f d g d m min d f d g displaystyle d max d f d g d m min d f d g nbsp von der Lange l f L f displaystyle l f L f nbsp bzw l g L g displaystyle l g L g nbsp ferner l max l f l g displaystyle l max l f l g nbsp und l m min l f l g displaystyle l m min l f l g nbsp daneben sei a Z displaystyle a in mathbb Z nbsp mit Bitlange l a L a displaystyle l a L a nbsp Dann fuhren die gemass Bitkomplexitat schnellsten bislang bekannten Algorithmen zu folgender Laufzeittabelle Operation Komplexitat als O displaystyle O dots nbsp bei ungleichen Eingabegrossenf g displaystyle f g nbsp d l displaystyle d l nbsp d m l displaystyle d m l nbsp f g displaystyle f cdot g nbsp ps d l log d displaystyle psi d l log d nbsp d d m ps d m d d m 1 l log d displaystyle frac d d m psi d m d d m 1 l log d nbsp f g displaystyle f g nbsp Division mit Rest ps d l log d displaystyle psi d l log d nbsp d l d m l m ps d m l m log d m displaystyle frac dl d m l m psi d m l m log d m nbsp prem f g displaystyle operatorname prem f g nbsp displaystyle nbsp d d m ps d m d d m 1 l log d displaystyle frac d d m psi d m d d m 1 l log d nbsp f k displaystyle f k nbsp ps k d l log d displaystyle psi kd l log d nbsp displaystyle nbsp f a x displaystyle f ax nbsp Skalierung d ps l d l a displaystyle d psi l dl a nbsp displaystyle nbsp a d f x a displaystyle a d f left frac x a right nbsp Skalierung d ps l d l a displaystyle d psi l dl a nbsp displaystyle nbsp f 2 x displaystyle f 2x nbsp Skalierung d l d displaystyle d l d nbsp displaystyle nbsp 2 d f x 2 displaystyle 2 d f left frac x 2 right nbsp Skalierung d l d displaystyle d l d nbsp displaystyle nbsp Siehe auch BearbeitenSymbolische MathematikLiteratur BearbeitenDeutschsprachige Literatur Michael Kaplan Computeralgebra Springer Berlin u a 2005 ISBN 3 540 21379 1 Wolfram Koepf Computeralgebra Eine algorithmisch orientierte Einfuhrung Springer Berlin u a 2006 ISBN 3 540 29894 0 Attila Petho Algebraische Algorithmen Herausgegeben von Michael Pohst Vieweg Braunschweig u a 1999 ISBN 3 528 06598 2 Englischsprachige Literatur Peter Burgisser Michael Clausen Mohammad Amin Shokrollahi Algebraic Complexity Theory Die Grundlehren der mathematischen Wissenschaften in Einzeldarstellungen 315 Springer Berlin u a 1997 ISBN 3 540 60582 7 Rezension 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 Cox 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 Jurgen 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 BearbeitenFachgruppe Computeralgebra gemeinsame Fachgruppe von GI DMV und GAMM Sieveking Algorithmen der Computeralgebra PDF 666 kB Skript Goethe Universitat Frankfurt a M Archivlink abgerufen am 26 Februar 2022 Abgerufen von https de wikipedia org w index php title Computeralgebra amp oldid 224411677