Math.Combinatorics.Species.NewtonRaphson

The Newton-Raphson iterative method for computing with recursive species. Any species T which can be written in the form T = X*R(T) (the species of "R-enriched rooted trees") may be computed by a quadratically converging iterative process. In fact we may also compute species of the form T = N + X*R(T) for any integer species N, by iteratively computing T' = X*R(T' + N) and then adding N.

Documentation

newtonRaphsonIter :: Species s => s -> Integer -> s -> s

A single iteration of the Newton-Raphson method. newtonRaphsonIter r k a assumes that a is a species having contact of order k with species t = x * (r ``o`` t) (that is, a and t agree on all label sets of size up to and including k), and returns a new species with contact of order 2k+2 with t.

See BLL section 3.3.

newtonRaphson :: Species s => s -> Integer -> s

Given a species r and a desired accuracy k, newtonRaphson r k computes a species which has contact at least k with the species t = x * (r ``o`` t).

newtonRaphsonRec :: (ASTFunctor f, Species s) => f -> Integer -> Maybe s

newtonRaphsonRec f k tries to compute the recursive species represented by the code f up to order at least k, using Newton-Raphson iteration. Returns Nothing if f cannot be written in the form f = X*R(f) for some species R.

solveForR :: (ASTFunctor f, Species s) => f -> Maybe (s, s)

Given a code f representing a recursive species, try to find an integer species N and species R such that f = N + X*R(f). If such species can be found, return Just (N,R); otherwise return Nothing.