An extended polynomial GCD algorithm using Hankel matrices (Q1186699): Difference between revisions

For \(F\) a field consider univariate polynomials \(f=f_ nx^ n+\dots,\) and \(g\in F[x]\), with \(\deg(g)\leq\deg(f)=n\). The sequence \((d_ i)_{i\geq 0}\) defined by \(g(x)/f(x)=\sum_{i\geq 0}d_ ix^{-i}\) gives rise to a Hankel matrix \(H_ \infty=(d_{i+j-1})_{i,j\geq 1}\) with \(r\times r\) left upper pricipal submatrices \(H_ r\). If \(H_ m\), say, is nonsingular one finds a vector \(\omega^ m=(a_ 1,\dots,a_ m)\) such that \(\omega^ m\cdot H_ m=(d_{m+1},\dots,d_{2m})\), and an associated polynomial \(p_ m(x)=x^ m-a_ mx^{m-1}-\cdots-a_ 1\). Let \(\{H_{n_ 0},H_{n_ 1},\dots,H_{n_ s}\}\) be the sequence of all such nonsingular principal submatrices of \(H_ \infty\) and consider the assocaited \(\{\omega^{n_ 0},\omega^{n_ 1},\dots,\omega^{n_ s}\}\) and polynomial Hankel sequences (PHS) \(p_{n_ 0},\dots,p_{n_ s}\). Here \(n_ 0=0\), \(1\leq n_ 1<n_ 2<\cdots<n_ s\leq n\), and the conventions \(p_ 0=1\), \(H_ 0\) empty but nonsingular, \(\omega^ 0\) empty are used. Let \(a=-f_ n(\omega^{n_{s-1}},-1)\cdot(d_{n_ s},\dots,d_{n_ s+n_{s- 1}})^ T\) and define a \((1+n_{s-1})\)-square matrix \(D\) by \(D_{ij}=(d_{i+j-n-1})\), where \(d\)'s with negative indices are to be interpreted as zeroes. The main result is that the polynomials defined by \(v(x)=(1/a)p_{n_{s-1}}(x)\) and \(u(x)=-(1/a)(\omega^{n_{s-1}},- 1)\cdot D\cdot (x^{n_{s-1}},\dots,x,1)^ T\) satisfy the Hankel extended greatest common (HEGCD) divisor equation \(u\cdot f+v\cdot g=\text{gcd}(f,g)\). Pseudo codes for \(\text{PHS}(f,g)\) and \(\text{HEGCD}(f,g)=[\text{gcd}(f,g),u,v]\) are given. The maximum computing time for HEGCD is \(O(n^ 9l^ 2)\) where \(l=\max\{\log(\text{norm}(f)),\log(\text{norm}(g))\}\); the number of operation is \(O(n^ 2)\). The latter number compares favorably with a modular algorithm by \textit{W. S. Brown} [J. ACM 18, 478-504 (1971; Zbl 0226.65040)]. For related work by the authors see Lect. Notes Comput. Sci. 356, 321-333 (1989; Zbl 0682.15020).