Последовательности остатков

Question

Я хотел бы вычислить последовательность остатков двух многочленов, используемых GCD. Если я понял статью Википедии о Pseudo-remainder sequence, один из способов вычислить его заключается в использовании алгоритма Евклида:

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. Несомненно, будет создана последовательность субрезультатов, степень которых по х продолжает уменьшаться до тех пор, пока не достигнет 0: последний многочлен последовательности не будет иметь x в нем. Степень по y может (и действительно) возрастать, так как алгоритм не имеет проблем с умножением членов на любые полиномы от y, чтобы вывести x.

Результат состоит в том, что оба вычисления работают правильно, они просто делают разные вещи.