Residual polynomial sequence

A polynomial residue sequence is created by repeated division with remainder of two polynomials . If it is a matter of polynomials with coefficients from one field , the Euclidean algorithm , for example, delivers such a sequence. In the more general case of polynomials with coefficients from a factorial ring , however, the dividend must be multiplied by a suitable constant in order to be able to carry out the division with the remainder ( pseudodivision ).

Residual polynomial sequences are used in computer algebra to compute a greatest common divisor of two polynomials. The problem that arises there that the coefficients of the polynomials grow exponentially is solved by the sub-resultant method.

definition

For two polynomials , with coefficients from a factorial ring is there are always polynomials so that ${\displaystyle f,g\in R[x]}$ ${\displaystyle g\not =0}$ ${\displaystyle R}$ ${\displaystyle q,r\in R[x]}$

${\displaystyle \mathrm {lc} (g)^{\mathrm {deg} (f)-\mathrm {deg} (g)+1}f\,=\,qg+br}$ and ${\displaystyle \mathrm {deg} (r)\,<\,\mathrm {deg} (g)}$

applies; where denotes the leading coefficient of . It is referred to as a pseudo remainder and a pseudo quotient ( pseudo division , see Donald Knuth , Section 4.6.1), and we write ${\displaystyle \mathrm {lc} (g)}$ ${\displaystyle g}$ ${\displaystyle r}$ ${\displaystyle q}$

${\displaystyle r=\mathrm {prem} (f,g)}$.

Polynomials and have similar names , in characters if there are with ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle f\sim g}$ ${\displaystyle a,b\in R}$

${\displaystyle af=bg.}$

A sequence of polynomials is called a polynomial residue sequence if ${\displaystyle p_{0},p_{1},\ldots ,p_{n}}$

${\displaystyle p_{i+2}\ \sim \ \mathrm {prem} (p_{i},p_{i+1})}$

for as well ${\displaystyle k=0,\ldots ,n-2}$

${\displaystyle \mathrm {prem} (p_{n-1},p_{n})=0}$

be valid.

Special residual consequences

Pseudo-polynomial residue sequence

For polynomials supplies ${\displaystyle p_{0},p_{1}}$

${\displaystyle p_{k+2}:=\mathrm {prem} (p_{k},p_{k+1})}$

a polynomial residue sequence called a pseudo-polynomial residue sequence . In practice, it has the disadvantage that the coefficients of the polynomials grow exponentially. ${\displaystyle p_{k}}$

Primitive residual polynomial sequence

If you divide a polynomial by its content , you get a polynomial whose coefficients are prime (primitive part of the polynomial, ppart). This leads to the consequence

${\displaystyle p_{k+2}:=\mathrm {ppart} (\mathrm {prem} (p_{k},p_{k+1})),}$

called the primitive residue sequence of polynomials . In order to calculate this sequence, however, GCD calculations in the coefficient ring are required, which in practice take up a lot of computing time. ${\displaystyle R}$

Sub-result sequence

In practice, the

${\displaystyle p_{k+2}:={\frac {\mathrm {prem} (p_{k},p_{k+1})}{g_{k}\cdot h_{k}^{\delta _{k}}}}}$

defined sequence used. It is

${\displaystyle \delta _{k}:=\mathrm {deg} (p_{k})-\mathrm {deg} (p_{k+1})}$

and and are through ${\displaystyle g_{k}}$ ${\displaystyle h_{k}}$

${\displaystyle h_{0},g_{0}:=1}$

${\displaystyle g_{k+1}:=\mathrm {lc} (p_{k+1})}$

${\displaystyle h_{k+1}:=h_{k}^{1-\delta _{k}}g_{k+1}^{\delta _{k}}}$

Are defined. All the divisions that occur here open up, and the coefficients of the polynomials defined in this way grow much more slowly than with the pseudo-polynomial residue sequence.

properties

The last term of a polynomial residue sequence is similar to the greatest common divisor of the polynomials and : ${\displaystyle p_{n}}$ ${\displaystyle p_{0}}$ ${\displaystyle p_{1}}$

${\displaystyle p_{n}\ \sim \ \mathrm {ggT} (p_{0},p_{1}).}$

Residual polynomial sequences can therefore be used for calculating the GCD in polynomial rings .

literature

• WS Brown, Joseph F. Traub: On Euclid's Algorithm and the Theory of Subresultants . In: Journal of the ACM . tape 18-4 , October 1971, pp. 505-514 .
• Donald E. Knuth : The Art of Computer Programming . 3. Edition. Vol. II: Seminumerical Algorithms. Addison-Wesley, 1998.
• Rüdiger Loos: Generalized Polynomial Remainder Sequences . In: Bruno Buchberger , GE Collins, Rüdiger Loos (eds.): Computer Algebra . Springer, 1982.
• Attila Pethő: Algebraic Algorithms . Ed .: Michael Pohst . Vieweg, 1999, ISBN 978-3-528-06598-0 .
• Michael Kaplan: Computer Algebra . Springer, 2005, ISBN 3-540-21379-1 .