org.spaceroots.rkcheck
Class DerivationTree

java.lang.Object
  org.spaceroots.rkcheck.DerivationTree

All Implemented Interfaces:

java.lang.Comparable

public class DerivationTree

extends java.lang.Object

implements java.lang.Comparable

This class implements rooted trees for determining order conditions in Runge-Kutta integrators.

The determination of order conditions for Runge-Kutta integrators involves identifying all the terms of two developments:

• the Taylor serie of the continuous flow (the theoretical solution)
• the Taylor serie of the discrete flow (the Runge-Kutta process)

According to a theorem from Butcher (1963), this identification can be done using rooted trees representing the multilinear derivations of the Runge-Kutta process. This class implements this computation process for one term, as explained in the paper Runge-Kutta Methods, Trees, and Maple by Folkmar Bornemann, Center of Mathematical Sciences, Munich University of Technology, February 9, 2001.

The nodes in such trees are either leaf nodes without any subtree or nodes with subtrees. Leaf nodes represent the basic function f by itself. Nodes with subtrees represent an elementary differential written for example f'''(f'(f), f'(f), f), which means we compute the third order derivative according to three arguments which themselves represent other elementary differentials.

Only the derivation structure is considered, there is no reference to the base function f which should be differentiated according to this structure (it remains an unknown througout the order conditions determination process). This means the nodes do not contain data per se, so these trees should not be confused with trees used as containers (such as AVL trees or red-black trees).

Version:

$Id: DerivationTree.java,v 1.4 2003/11/07 21:51:27 luc Exp $

Author:

L. Maisonobe

Constructor Summary

DerivationTree()
Simple constructor.

DerivationTree(DerivationTree tree)
Copy constructor.

DerivationTree(DerivationTree[] trees)
Build a derivation tree from an array of sub-trees.

Method Summary

int	compareTo(java.lang.Object o) Compares this tree with the specified object for order.
boolean	equals(java.lang.Object o) Check if the instance is equal to another tree.
QuadraticSurd	getAlpha() Get the alpha factor of the tree.
int	getDepth() Get the depth of the tree.
long	getFactorial() Get the factorial of the tree.
int	getOrder() Get the order of the tree.
int	hashCode() Returns the hash code value for this tree.
boolean	isLeaf() Check if a tree is a leaf.
java.util.Vector	listUpperTrees() List one order upper trees.
java.lang.String	orderConditionAsMaximaString(boolean interpolatorCondition) Get a Maxima string representation of the order condition of this derivation tree.
java.lang.String	orderConditionAsTeXString(boolean interpolatorCondition) Get a TeX string representation of the order condition of this derivation tree.
QuadraticSurd	orderConditionResidual(QuadraticSurd[] c, QuadraticSurd[][] a, QuadraticSurd[] b) Compute the residual on an order condition
java.lang.String	toString() Get a string representation of this tree.

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Constructor Detail

DerivationTree

public DerivationTree()

Simple constructor. Build a derivation tree of order 0 (i.e. no derivation at all).

DerivationTree

public DerivationTree(DerivationTree tree)

Copy constructor. Build a derivation tree from another one. This is a deep copy, no data is shared between the original tree and the instance.

Parameters:

tree - derivation tree to copy

DerivationTree

public DerivationTree(DerivationTree[] trees)

Build a derivation tree from an array of sub-trees.

Parameters:

trees - array of sub-trees (null elements will be skipped)

Method Detail

listUpperTrees

public java.util.Vector listUpperTrees()

List one order upper trees. This method lists all the derivation trees which have an order exactly one unit larger than the order of this tree.

Returns:

a vector of derivation trees

isLeaf

public boolean isLeaf()

Check if a tree is a leaf. A tree is a leaf if it is an order 1 tree (i.e. it represents the base function f itself, not any of its derivatives).

Returns:

true if the tree is a leaf

equals

public boolean equals(java.lang.Object o)

Check if the instance is equal to another tree. Two different trees are considered equals if the same derivations are performed in a similar structure. As an example f'''(f'(f), f'(f), f) is the same as f'''(f'(f), f, f'(f)) due to the multilinearity.

Parameters:

o - object against which we want to check equality

Returns:

true if o is a derivation tree having the same structure as the instance

hashCode

public int hashCode()

Returns the hash code value for this tree.

Returns:

the hash code value for this tree.

compareTo

public int compareTo(java.lang.Object o)

Compares this tree with the specified object for order. Comparison is done with respect to the order first, then to the number of subtrees, then using lexicographic order of subtrees.

Specified by:

compareTo in interface java.lang.Comparable

Parameters:

o - the Object to be compared.

Returns:

a negative integer, zero, or a positive integer as this object is less than, equal to, or greater than the specified object.

Throws:

java.lang.ClassCastException - if the specified object's type prevents it from being compared to this Object.

getDepth

public int getDepth()

Get the depth of the tree. The depth is recursively computed as one plus the maximum of the depths of all subtrees. The depth of a leaf tree is 0.

Returns:

order of the tree

getOrder

public int getOrder()

Get the order of the tree. The order of the tree is the parameter #beta in Folkmar Bornemann's paper. It is recursively computed as one plus the sum of the orders of all subtrees. The order of a leaf tree is 1.

Returns:

order of the tree

getFactorial

public long getFactorial()

Get the factorial of the tree. The factorial of the tree is the parameter beta! in Folkmar Bornemann's paper. It is recursively computed as the order of the tree times the factorial of all subtrees. The factorial of a leaf tree is 1.

Returns:

factorial of the tree

getAlpha

public QuadraticSurd getAlpha()

Get the alpha factor of the tree. The alpha factor of the tree is the parameter alpha_beta in Folkmar Bornemann's paper (note that it is not used for the computation of order conditions, it has been added in the paper and in this class only for completeness). It is recursively computed as delta_beta/n! times the alpha factor of all subtrees. The alpha factor of a leaf tree is 1. Quoting the paper of Folkmar Bornemann, by delta_beta we denote the number of different ordered tuples (beta_1, ..., beta_n) which correspond to the same unordered list beta= [beta_1, ... beta_n].

Returns:

alpha factor of the tree

orderConditionResidual

public QuadraticSurd orderConditionResidual(QuadraticSurd[] c,
                                            QuadraticSurd[][] a,
                                            QuadraticSurd[] b)

Compute the residual on an order condition

Parameters:

c - time steps array

a - internal weights array

b - estimation weights array

Returns:

order condition residual (should be null if condition is fulfilled)

orderConditionAsTeXString

public java.lang.String orderConditionAsTeXString(boolean interpolatorCondition)

Get a TeX string representation of the order condition of this derivation tree.

Parameters:

interpolatorCondition - indicator if the condition should be displayed for an interpolator (using a theta parameter between 0 and 1) or for an integrator (with the constant 1)

Returns:

a string representation (using TeX) of the order condition of the instance

orderConditionAsMaximaString

public java.lang.String orderConditionAsMaximaString(boolean interpolatorCondition)

Get a Maxima string representation of the order condition of this derivation tree.

Parameters:

interpolatorCondition - indicator if the condition should be displayed for an interpolator (using a theta parameter between 0 and 1) or for an integrator (with the constant 1)

Returns:

a string representation (using Maxima) of the order condition of the instance

toString

public java.lang.String toString()

Get a string representation of this tree. The string representation is a parenthesized expression including the derivation order at the tree level with primes charaters and the arguments like this : f'''(f, f''(f, f'(f)), f''(f, f'(f)))

Returns:

a string representation of the tree.