Progress Variable

Tabulation methods depend on finding the closest configuration as efficiently as possible. The purpose and philosophy of the tabulation is to provide full kinetic data with computational efficiency. However, it is impractical, both for the tabulation and for the transport complexity within a CFD calculation, to use the full set of species and conditions of the full mechanism. For this reason, a reduced set of progress variables is chosen to represent the position in configuration space of the calculation.

The progress variables are used to find the closest configuration. In the design of this tabulation method, this is done in two stages:

· Hypercube: Using a tree structure (see Section \ref{sec:treesearch}), a set of configurations bounded by a hypercube of progress variable values is isolated.

· Nearest: All configurations collected are compared and the closest (currently

· using the normed euclidean distance) is found. Two types of comparisons are possible:

o Progress Variables: If the calculation only involves the progress variables, then only these are used. This situation occurs when the tabulated database is used by an external calculation.

o Full: If the full set of variables are available, then all are used. This situation occurs when setting up the database.

Tree Search for Hypercube

As explained in the last section, a primary task of tabulation is to find, as efficiently as possible, the nearest configuration. A practical intermediate step, in lieu of linearly searching through all configurations in the database, is to narrow the search with a decision tree structure to a hypercube region encompassing a 'reasonable' set of configurations close to the target. From those configurations in the hypercube, a linear search is performed.

In this implementation, the search data structure chosen is a fixed leveled, one level per progress variable, multiple branched tree. Each non-leaf node corresponds to a progress variable. The nth progress variable is represented by the nth level in the tree, with the root node being the first level. The branches to the next node correspond to fixed intervals from a minimum to a maximum. Which branch to follow is a direct computation of which interval the value of the corresponding progress variable belongs to.

The tree is built dynamically, as needed. Corresponding to the configuration, the search traverses down the levels of the tree until a leaf node is found. When a leaf node is reached, then the list of indices of the corresponding tabulations are returned.

Non-Leaf Search

At the ith, non-leaf level, the search proceeds as follows:

· Value: Isolate the ith progress variable from the target configuration.

· Interval: From the minimum, maximum and number of branches, compute which branch position, b, the value corresponds to.

· Branch: The index at the bth value within the node, corresponds to the node, representing the (n+1)th level, to branch to. If a node does not exist, the create an empty node of the (n+1)th level.

The computational complexity of the search with n progress variables corresponds basically to the retrieval of the n+1 nodes of the tree and then the retrieval of the set of configurations listed in the leaves. The number of nodes in the tree can be quite large, usually exceeding the number of data configurations to be indexed. Therefore, the set of nodes, are also stored in a vector that can reside both in memory and on disc.

If no configurations are found, then an expanded search is made (and, of course, the complexity increases correspondingly). The expanded search entails eliminating the constraint of the lowest progress variable. The effect is using a reduced number of progress variables. The configurations within all the leaf nodes of the sub-tree of the last considered progress variable (level of the tree) are considered as candidates to find the closest configuration. Progress variables, i.e. tree levels, are eliminated until a non-empty set of candidates is found. Using this strategy places some weight on the ordering of the progress variables used. The 'least significant' variables should be at the lower levels.