Sequential reduction algorithm. More...

#include <graph_transform.hpp>

Public Member Functions
void	merge (Index i)
	Merge all cliques that contain a given independent variable. More...

void	reorder_random ()
	Re-order random effects. More...

	sequential_reduction (global &glob, std::vector< Index > random, std::vector< sr_grid > grid=std::vector< sr_grid >(1, sr_grid(-20, 20, 200)), std::vector< Index > random2grid=std::vector< Index >(0), bool perm=true)
	CTOR of sequential reduction object. More...

std::vector< ad_aug >	tabulate (std::vector< Index > inv_index, Index dep_index)
	tabulate each combination of variables of a subgraph More...

void	update (Index i)
	Integrate independent variable number i, (`inv_index[i]`). More...

Detailed Description

Sequential reduction algorithm.

Integrated terms are functions of cliques.
There can be arbitrarily many active cliques.
A clique must be represented by a sorted index vector (the variables) and a 'logsum' vector of the same length as length(grid)^length(clique) (can be very long !).
Everytime we process a summation we look right for all the cliques. We must find all the cliques that contain the variable we are currently integrating. All matching cliques must be updated: we remove the current integration variable and add it's parents. It may be that no more terms depend on the current integration variable (the forward/backward graph has no dep variables). In this case we simply sum out the variable and remove it from all the cliques. Eventually all cliques will become empty.
If at anytime two cliques have the same index vector they can be merged into one. However, this optimization is not necessary for the method to work.
The final node xend to be integrated will in general belong to a number of identical cliques {xend}, {xend},... The sum of all those cliques is our end result.

Example: Consider the circular graph

+-x1-x2-x3-x4-x5-x6-x7-+

|______________________|

Each edge is a logspace term. Assume we integrate in some random order:

x1, x5, x7, x6, ...

When integrating wrt x1 we generate the clique {2, 7}.
When integrating wrt x5 we generate the clique {4, 6}.
When integrating wrt x7 we notice that 7 is already in a clique. There is only one term (edge) left that depends on x7: f(x6,x7).
This term is tabulated and log-integrated versus {2, 7} to produce a new clique {2, 6}.
When integrating wrt x6 we notice that 6 is already in two cliques. There are no terms (edges) left that depend on x6.
Therefore x6 is summed out of the two cliques. The updated cliques are {4} and {2}.

Definition at line 581 of file graph_transform.hpp.

Constructor & Destructor Documentation

§ sequential_reduction()

TMBad::sequential_reduction::sequential_reduction	(	global &	glob,
		std::vector< Index >	random,
		std::vector< sr_grid >	grid = `std::vector<sr_grid>(1, sr_grid(-20, 20, 200))`,
		std::vector< Index >	random2grid = `std::vector<Index>(0)`,
		bool	perm = `true`
	)

CTOR of sequential reduction object.

The optimal order is not found by this routine. In general a good choice is the fill-reducing permutation of the sparse Cholesky factorization. For hierarchical models the optimal ordering is the opposite of the 'natural simulation order'.

Parameters

glob	Output from `accumulation_tree_split()`.
random	Which independent variables to integrate out and in what order (if `perm=false`). To be specific, the order of integration is `inv_index[random[0]]`, `inv_index[random[1]]`, ...
grid	Vector of grids to be used by individual random effects - see `random2grid`.
random2grid	Factor determining the grid to be used for each random effect. To be specific, the i'th random effect `random[i]` uses the grid `grid[random2grid[i]]`.
perm	Apply a permutation of `random` based on a simple heuristic (see `reorder_random()`).

Definition at line 3843 of file TMBad.cpp.

Member Function Documentation

§ merge()

void TMBad::sequential_reduction::merge ( Index i )

Merge all cliques that contain a given independent variable.

Parameters

i	Index to remove

Example:

 Assume i=2 and the current state contains cliques
 (1) (1 2 3) (2 4) (1 3)
 We start by finding all cliques that contain 2, in this case:
 (1 2 3) (2 4)
 The 'super' clique becomes
 (1 2 3 4)
 Rather than expanding this as a 4D array we figure out how to
 access the 4D information from the existing lower dimensional
 arrays (1 2 3) and (2 4), i.e. 'offsets' and 'strides'.
 We integrate 'i' out of the 4D array without constructing the 4D
 array. The resulting clique is
 (1 3 4)
 This new (merged) clique is added to the list and the updated list now
looks like: (1) (1 3 4) (1 3)

Definition at line 3966 of file TMBad.cpp.

§ reorder_random()

void TMBad::sequential_reduction::reorder_random ( )

Re-order random effects.

Two random effects are connected if they both affect the same term. This function finds a fill-reducing permutation of the corresponding un-directed graph.

Definition at line 3885 of file TMBad.cpp.

Referenced by sequential_reduction().

§ tabulate()

std::vector< ad_aug > TMBad::sequential_reduction::tabulate	(	std::vector< Index >	inv_index,
		Index	dep_index
	)

tabulate each combination of variables of a subgraph

It is assumed that a subgraph has been made. The subgraph has a certain number of inputs and outputs. This function tabulates a given output dep_index for all combinations of inputs inv_index. To avoid tabulating identical functions many times, we a use caching based on term hash codes.

Note: If multiple grids are in play we have to include the grid ids in the hash codes! (although it is hard to imagine a case where one would wish to tabulate identical functions using different grids).

Definition at line 3936 of file TMBad.cpp.

§ update()

void TMBad::sequential_reduction::update ( Index i )

Integrate independent variable number i, (inv_index[i]).

The algorithm works as follows:

Identify all factors (terms in logspace) that depend on x_i and have not yet been integrated.
Identify all variables V that affect these terms (for now assume all variables are random effects) by determining a reverse sub-graph.
Based on the sub-graph tabulate a new clique C consisting of V indices.
In the set S of all existing cliques locate those containing i. Merge them with C while removing them from S.
Integrate variable i out of C and add C to S.

Definition at line 4020 of file TMBad.cpp.

The documentation for this struct was generated from the following files:

Public Member Functions