SymbolicEliminationTree

Authors: Frank Dellaert, et al. (see THANKS for the full author list)

See LICENSE for the license information

A SymbolicEliminationTree represents the computational structure used in variable elimination, particularly in sparse Cholesky or QR factorization. Each node in the tree corresponds to the elimination of a single variable.

The tree structure reveals dependencies: the elimination of a variable (node) depends on the results from its children in the tree. The root of the tree corresponds to the last variable eliminated. This structure is closely related to the resulting Bayes net or Bayes tree.

%pip install --quiet gtsam-develop

from gtsam import SymbolicEliminationTree, SymbolicFactorGraph, Ordering
from gtsam.symbol_shorthand import X, L

Creating a SymbolicEliminationTree¶

An elimination tree is constructed from a SymbolicFactorGraph and an Ordering.

# Create a factor graph
graph = SymbolicFactorGraph()
graph.push_factor(X(0))
graph.push_factor(X(0), X(1))
graph.push_factor(X(1), X(2))
graph.push_factor(X(0), L(1))
graph.push_factor(X(1), L(2))

# Define an elimination ordering
ordering = Ordering([L(1), L(2), X(0), X(1), X(2)])  # Eliminate L(1) first, then X(0), X(1), X(2) last

# Construct the elimination tree
elimination_tree = SymbolicEliminationTree(graph, ordering)

# Print the tree structure (text representation)
elimination_tree.print("Symbolic Elimination Tree:\n")

Symbolic Elimination Tree:
-(x2)
Symbolic Elimination Tree:
| -(x1)
Symbolic Elimination Tree:
| -  x1 x2
Symbolic Elimination Tree:
| | -(x0)
Symbolic Elimination Tree:
| | -  x0
Symbolic Elimination Tree:
| | -  x0 x1
Symbolic Elimination Tree:
| | | -(l1)
Symbolic Elimination Tree:
| | | -  x0 l1
Symbolic Elimination Tree:
| | -(l2)
Symbolic Elimination Tree:
| | -  x1 l2

(Note: Direct visualization of the elimination tree structure isn’t available via a simple .dot() method like factor graphs or Bayes nets/trees in the Python wrapper, but the print output shows the parent-child relationships.)