剩餘序列

Question

我想計算GCD使用的兩個多項式的餘數序列。如果我的理解維基百科的文章約Pseudo-remainder sequence，計算它的一種方式是使用Euclid算法：

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

這意味着我將收集rem()部分。但是，如果係數是整數，則中間分數增長非常快，因此存在所謂的「僞餘數序列」，其嘗試將係數保持爲小整數。

我的問題是，如果我理解正確（我嗎？），上述兩個序列只有恆定因子不同，但是當我嘗試運行下面的例子時，我得到了不同的結果，爲什麼？第一個餘數序列相差-2，好吧，但爲什麼第二個序列如此不同？我假設subresultants()正常工作，但爲什麼g % (f % g)不起作用？

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) 

這導致

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

上面的兩個序列的差異僅在於常數因子

對於一個變量的多項式，他們做的。對於多元多項式，它們不會。

多元多項式的除法是somewhat tricky business：結果取決於所選擇的單項式的順序（默認情況下，sympy使用詞典順序）。當你要求它將2*x**2 - 12*x + 1除以x*y + 8*x - 1/2*y + 1/2時，它發現分母的主導單項是x*y，分子中沒有可被x*y整除的單項。所以商是零，一切都是餘數。

子結果的計算（如sympy中的實現）將x，y中的多項式當作x中的單變量多項式，其係數恰好來自y中的多項式環。可以肯定的是，產生一系列的子結果，其對x的度數一直保持下降直到達到0：序列的最後一個多項式不會有x。關於y的程度可能（並且確實）增加，因爲算法沒有問題將y中的任何多項式相乘以使x退出。

結果是兩個計算都能正常工作，他們只是做不同的事情。