This file offers one function and one class: GraeffeN
and GraeffeSeq
.
Let f
be two RingElem
values representing univariate polynomials in a polynomial ring P
over ZZ
or QQ
.
Let n
and N
be positive integers.
GraeffeN(f, n)
-- returns a RingElem
representing the n
-th order Graeffe transformation of f
- its roots are the n
-th powers of the roots of f
.
GraeffeSeq(f, N)
-- constructs an instance of GraeffeSeq
- allowing for iteration over the Graeffe transformations of f
.
*GraeffeSeq
-- returns a RingElem
representing the current Graeffe iteration of internally stored f
. Not thread-safe!
++GraeffeSeq
-- advances the sequence by one - calculating Newton coefficients for the next Graeffe iteration internally. Not thread-safe!
GraeffeN
resultant approach is taken from Cipu et al. (DOI:10.1007/s00200-011-0150-8).
GraeffeSeq
approach is taken from Hatfield's Dissertation (Root-powering of Polynomial Equations).
GraeffeSeq
approach are 1-indexed since it is much easier to deal with them this way.
unsigned long
s could be used in some places instead.
GraeffeSeq
is not thread-safe!
2022