# ComplexRootFindingPackage(R, UP)¶

crfp.spad line 1 [edit on github]

R: Join(Field, OrderedRing)

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.