Restsequenzen

Question

Ich möchte die Restsequenz von zwei Polynomen wie von GCD verwendet berechnen. Wenn ich den Wikipedia-Artikel über Pseudo-remainder sequence verstanden, eine Möglichkeit, es zu berechnen ist Euklids Algorithmus zu verwenden:

gcd(a, b) := if b = 0 then a else gcd(b, rem(a, b)) 

Sinn will ich, dass rem() Teile sammeln. Wenn jedoch die Koeffizienten ganze Zahlen sind, wachsen die Zwischenfraktionen sehr schnell, und dann gibt es die sogenannten "Pseudorestsequenzen", die versuchen, die Koeffizienten in kleinen ganzen Zahlen zu halten.

Meine Frage ist, wenn ich richtig verstanden habe (habe ich?), Die beiden obigen Sequenzen unterscheiden sich nur durch konstanten Faktor, aber wenn ich versuche, das folgende Beispiel auszuführen, bekomme ich unterschiedliche Ergebnisse, warum? Die erste Restsequenz unterscheidet sich um -2, ok, aber warum ist die zweite Sequenz so anders? Ich nehme an, subresultants() funktioniert richtig, aber warum funktioniert das g % (f % g) nicht?

f = Poly(x**2*y + x**2 - 5*x*y + 2*x + 1, x, y) 
g = Poly(2*x**2 - 12*x + 1, x) 
print 
print subresultants(f, g)[2] 
print subresultants(f, g)[3] 
print 
print f % g 
print g % (f % g) 

die

Poly(-2*x*y - 16*x + y - 1, x, y, domain='ZZ') 
Poly(-9*y**2 - 54*y + 225, x, y, domain='ZZ') 

Poly(x*y + 8*x - 1/2*y + 1/2, x, y, domain='QQ') 
Poly(2*x**2 - 12*x + 1, x, y, domain='QQ') 

Answer 1

in resultiert die beiden obigen Sequenzen

für Polynome von einer variable nur durch konstanten Faktor unterscheiden, sie tun. Für multivariate Polynome nicht.

Die Division von multivariablen Polynomen ist ein somewhat tricky business: Ergebnis hängt von der gewählten Reihenfolge der Monome (standardmäßig verwendet Sympy lexikographische Reihenfolge). Wenn Sie es bitten, 2*x**2 - 12*x + 1 durch x*y + 8*x - 1/2*y + 1/2 zu teilen, stellt es fest, dass das führende Monom des Nenners x*y ist, und es gibt kein monomial in dem Zähler, der durch x*y teilbar ist. Also ist der Quotient Null, und alles ist ein Rest.

Die Berechnung von subresultants (wie es in sympy implementiert ist) behandelt Polynome in x, y als single-variable Polynome in x, deren Koeffizienten zufällig aus dem Ring der Polynome in y kommen. Es ist sicher, eine Folge von Unterresultaten zu erzeugen, deren Grad in Bezug auf x weiter abnimmt, bis sie 0 erreicht: das letzte Polynom der Sequenz wird kein x enthalten. Der Grad in Bezug auf y kann (und geht) nach oben, da der Algorithmus kein Problem hat, die Terme mit irgendwelchen Polynomen in y zu multiplizieren, um x zum Ausfallen zu bringen.

Das Ergebnis ist, dass beide Berechnungen korrekt funktionieren, sie nur verschiedene Dinge tun.