Graeffe

• Examples
• User documentation
  • Operations
• Maintainer documentation
• Bugs, shortcomings and other ideas
• Main changes

Examples

• ex-Graeffe.C

User documentation

This file offers one function and one class: GraeffeN and GraeffeSeq.

Operations

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!

Maintainer documentation

• The GraeffeN resultant approach is taken from Cipu et al. (DOI:10.1007/s00200-011-0150-8).
• The GraeffeSeq approach is taken from Hatfield's Dissertation (Root-powering of Polynomial Equations).
• The indices of the various arrays in the GraeffeSeq approach are 1-indexed since it is much easier to deal with them this way.

Bugs, shortcomings and other ideas

• unsigned longs could be used in some places instead.
• The vector for the Newton coefficients should be resized dynamically, not allocated once in the beginning.
• GraeffeSeq is not thread-safe!

Main changes

2022

• August (v0.99802): first release