ComplexRootFindingPackage(R, UP)

crfp.spad line 1 [edit on github]

ComplexRootFindingPackage provides functions to find all roots of a polynomial p over the complex number by using Plesken's idea to calculate in the polynomial ring modulo f and employing the Chinese Remainder Theorem. In this first version, the precision (see digits) is not increased when this is necessary to avoid rounding errors. Hence it is the user's responsibility to increase the precision if necessary. Note also, if this package is called with e.g. Fraction Integer, the precise calculations could require a lot of time. Also note that evaluating the zeros is not necessarily a good check whether the result is correct: already evaluation can cause rounding errors.

complexZeros: (UP, R) -> List Complex R

complexZeros(p, eps) tries to determine all complex zeros of the polynomial p with accuracy given by eps.

complexZeros: UP -> List Complex R

complexZeros(p) tries to determine all complex zeros of the polynomial p with accuracy given by the package constant globalEps which you may change by setErrorBound.

divisorCascade: (UP, UP) -> List Record(factors: List UP, error: R)

divisorCascade(p, tp) assumes that degree of polynomial tp is smaller than degree of polynomial p, both monic. A sequence of divisions is calculated using the remainder, made monic, as divisor for the the next division. The result contains also the error of the factorizations, i.e. the norm of the remainder polynomial.

divisorCascade: (UP, UP, Boolean) -> List Record(factors: List UP, error: R)

divisorCascade(p, tp) assumes that degree of polynomial tp is smaller than degree of polynomial p, both monic. A sequence of divisions are calculated using the remainder, made monic, as divisor for the next division. The result contains also the error of the factorizations, i.e. the norm of the remainder polynomial. If info is true, then information messages are issued.

factor: (UP, R) -> Factored UP

factor(p, eps) tries to factor p into linear factors with error at most eps. An overall error bound eps0 is determined and iterated tree-like calls to pleskenSplit are used to get the factorization.

factor: (UP, R, Boolean) -> Factored UP

factor(p, eps, info) tries to factor p into linear factors with error at most eps. An overall error bound eps0 is determined and iterated tree-like calls to pleskenSplit are used to get the factorization. If info is true, then information messages are given.

factor: UP -> Factored UP

factor(p) tries to factor p into linear factors with error at most globalEps, the internal error bound, which can be set by setErrorBound. An overall error bound eps0 is determined and iterated tree-like calls to pleskenSplit are used to get the factorization.

graeffe: UP -> UP

graeffe p determines q such that q(-z^2) = p(z)*p(-z). Note that the roots of q are the squares of the roots of p.

norm: UP -> R

norm(p) determines sum of absolute values of coefficients Note: this function depends on abs.

pleskenSplit: (UP, R) -> Factored UP

pleskenSplit(poly, eps) determines a start polynomial start\ by using “startPolynomial then it increases the exponent n of start ^ n mod poly to get an approximate factor of poly, in general of degree “degree poly -1". Then a divisor cascade is calculated and the best splitting is chosen, as soon as the error is small enough.

pleskenSplit: (UP, R, Boolean) -> Factored UP

pleskenSplit(poly, eps, info) determines a start polynomial start by using “startPolynomial then it increases the exponent n of start ^ n mod poly to get an approximate factor of poly, in general of degree “degree poly -1". Then a divisor cascade is calculated and the best splitting is chosen, as soon as the error is small enough. If info is true, then information messages are issued.

reciprocalPolynomial: UP -> UP

reciprocalPolynomial(p) calulates a polynomial which has exactly the inverses of the non-zero roots of p as roots, and the same number of 0-roots.

rootRadius: (UP, R) -> R

rootRadius(p, errQuot) calculates the root radius of p with a maximal error quotient of errQuot.

rootRadius: UP -> R

rootRadius(p) calculates the root radius of p with a maximal error quotient of 1+globalEps, where globalEps is the internal error bound, which can be set by setErrorBound.

schwerpunkt: UP -> Complex R

schwerpunkt(p) determines the ‘Schwerpunkt’ of the roots of the polynomial p of degree n, i.e. the center of gravity, which is *coefficient of x^(n-1)* divided by *n times coefficient of x^n*.

setErrorBound: R -> R

setErrorBound(eps) changes the internal error bound, by default being 10 ^ (-3) to eps, if R is a member in the category QuotientFieldCategory Integer. The internal globalDigits is set to ceiling(1/r)^2*10 being 10^7 by default.

startPolynomial: UP -> Record(start: UP, factors: Factored UP)

startPolynomial(p) uses the ideas of Schoenhage's variant of Graeffe's method to construct circles which separate roots to get a good start polynomial, i.e. one whose image under the Chinese Remainder Isomorphism has both entries of norm smaller and greater or equal to 1. In case the roots are found during internal calculations. The corresponding factors are in factors which are otherwise 1.