Trennkreisverfahren

Das Trennkreisverfahren (engl. splitting circle method) ist eine Methode zum numerischen Faktorisieren von Polynomen in einer Variablen mit komplexen Koeffizienten. Dieses Verfahren wurde 1982 von Arnold Schönhage in dem Artikel The fundamental theorem of algebra in terms of computational complexity (bisher nur im Netz veröffentlicht) vorgeschlagen und 1996 von Xavier Gourdon im Computeralgebrasystem PARI/GP und nachfolgend Magma implementiert. Seit der Mitte der 1990er Jahre wurden u.a. von V. Pan und G. Malajovich Verbesserungen des Algorithmus vorgeschlagen, die jedoch bisher nirgends implementiert wurden.

Durch fortgesetztes Zerlegen eines Polynoms in zwei nichttriviale Faktoren kann letztendlich eine Faktorisierung in Linearfaktoren erreicht werden. Dies ist gleichbedeutend zum Auffinden aller komplexen Nullstellen des Polynoms einschließlich der Angabe ihrer Vielfachheit.

Beim numerischen Rechnen mit einer fixierten endlichen Genauigkeit (s. Gleitkommazahl und Festkommazahl) ist es nicht möglich, zwischen einer mehrfach auftretenden Nullstelle und einer gleichmächtigen Gruppe nahe beieinander liegender Nullstellen zu unterscheiden. In diesem Fall ist das Ergebnis des Verfahrens eine Faktorisierung in

• Linearfaktoren für ausreichend isolierte Nullstelle und
• Faktoren höheren Grades für Gruppen von Nullstellen, die in der gewählten Genauigkeit nicht unterscheidbar sind.

Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Trennkreisverfahren aus der freien Enzyklοpädιe Wιkιpedιa und steht unter der Lizenz Creative Commons CC-BY-SA 3.0 Unported (Kurzfassung). Liste der Autoren

Anbieterkennzeichnung