Documentation of 'org.spaceroots.rkcheck.DerivationTree' Java class
DerivationTree
Skip navigation links
org.spaceroots.rkcheck

Class 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).

    • 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.
        Overrides:
        equals in class java.lang.Object
        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.
        Overrides:
        hashCode in class java.lang.Object
        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)))
        Overrides:
        toString in class java.lang.Object
        Returns:
        a string representation of the tree.
Skip navigation links

DataMelt 3.0 © DataMelt by jWork.ORG

Ads help maintain this website.