Polynomial gcd computations over towers of algebraic extensions (Q4352810)

A technique for computing univariate polynomial gcd over algebraic extensions of a field is presented. It combines ideas from \textit{G. E. Collins}' 1967 subresultant algorithm [J. Assoc. Comput. Machin. 14, 128--142 (1967; Zbl 0152.35403), or Am. Math. Mon. 73, 708--712 (1966; Zbl 0147.29505)], see also \textit{R. Loos} [Computer algebra, symbolic computation, Comput. Suppl. 4, 115--137 (1982; Zbl 0577.13001)] and \textit{H. Lueneburg} [On the rational normal form endomorphisms, B.I.-Wissenschaftsverlag (1987; Zbl 0635.12012)], with D5 like-processes due to Delladora, Dicrescenzo and \textit{D. Duval} [Semin. Theor. Nombres, Univ. Bordeaux I 1986/1987, Exp. No. 17 (1987; Zbl 0644.12001) and Eurocal' 85 (B. F. Caviness, Ed.), Lect. Notes Comput. Sci. 204, p. 289 (1985) (for the entire collection, see Zbl 0568.00019)]. Collin's work connects the theory of pseudo remainder sequences useful for gcd computations with the theory of subresultants, while the D5-procedure goes back to a remark of D. Lazard: For any \(P(X)\) and \(A(X)\) in \(\mathbb Q[X]\) with \(P(X)\) squarefree, \(A(X)\) is zero modulo \(\gcd(P,A)\) and invertible modulo \(P/\gcd(P,A)\). The advantage of the author's approach over currently implemented ones is to keep the intermediate polynomials of the computations permanently in the base field instead of computing with generic univariate polynomial gcds and post-specialization. This way they limit coefficient swelling. In the final section complete algorithms are presented, up to a few modifications AXIOM programs; see \textit{R. Jenks} and \textit{R. Sutor} [AXIOM. The scientific computation system, Springer-Verlag (1992; Zbl 0758.68010)]. Among these algorithms one finds implementations of ones due to \textit{D. Lazard} [Discrete Appl. Math. 33, 147--160 (1991; Zbl 0753.13013) and J. Symb. Comput. 13, 117--131 (1992; Zbl 0753.13012)], the reviews of which by Nishimura are recommended since many of the notions in the paper under consideration are also found there. The methods permit the authors to solve the cyclic 7 system -- see \textit{G. Björck} and \textit{R. Fröberg} [J. Symb. Comput. 12, No. 3, 329--336 (1991; Zbl 0751.12001)] completely automatically. For the entire collection see [Zbl 0847.00060].