gtsam
Loading...
Searching...
No Matches
gtsam::MultifrontalSolver Class Reference

Detailed Description

Imperative-style multifrontal solver for Gaussian factor graphs.

This class precomputes the elimination tree, allocates fixed solve storage, and provides efficient methods for loading new factors, eliminating the graph, and solving for the update vector. Each clique lazily allocates its packed Jacobian fallback rows on the first compatible load and reuses that storage thereafter.

Note
Only JacobianFactor and BatchJacobianFactor inputs are supported. Other Gaussian factor types will throw during construction/precompute or load.
Clique merging has two symbolic phases. First, leafMergeDimCap merges compatible multi-factor leaf siblings with identical separators into bounded algebraic cliques; one-factor leaves remain separate so direct batch factors can use the fused leaf path. Then mergeDimCap can merge remaining small children into their parents. Afterward, leaf task aggregation can schedule independent leaves together, with LeafMode::SameSeparator also accumulating compatible Cholesky updates in separator-local matrices.
Inheritance diagram for gtsam::MultifrontalSolver:

Public Member Functions

 MultifrontalSolver (const GaussianFactorGraph &graph, const Ordering &ordering, const Parameters &params=Parameters{})
 Construct the solver from a factor graph and an ordering.
 MultifrontalSolver (const GaussianFactorGraph &graph, const Ordering &ordering, size_t firstPhaseSize, const Parameters &params=Parameters{})
 Construct a solver configured for partial multifrontal elimination.
 MultifrontalSolver (PrecomputedData data, const Ordering &ordering, const Parameters &params=Parameters{})
 Construct the solver from precomputed symbolic data.
 MultifrontalSolver (PrecomputedData data, const Ordering &ordering, size_t firstPhaseSize, const Parameters &params=Parameters{})
 Construct a partial solver from precomputed symbolic data.
void load (const GaussianFactorGraph &graph)
 Load new numerical values from the factor graph.
void eliminateInPlace ()
 Eliminate the graph using Cholesky factorization.
void eliminateInPlace (const GaussianFactorGraph &graph)
 Load and eliminate the graph in a single traversal.
void eliminatePartialInPlace ()
 Eliminate the configured ordering prefix and assemble the retained clique factors without factorizing the retained variables.
void eliminatePartialInPlace (const GaussianFactorGraph &graph)
 Load a graph and partially eliminate it in one bottom-up traversal.
GaussianFactorGraph remainingFactorGraph () const
 Materialize one Hessian factor per retained clique after partial elimination.
GaussianBayesTree computeBayesTree () const
 Compute a Bayes tree from the in-place Cholesky factorization.
const VectorValues & updateSolution ()
 Solve for the update vector.
const VectorValues & updateSolution (const VectorValues &retainedSolution)
 Seed retained variables and back-substitute through eliminated cliques.
double deltaError (double *oldError=nullptr, double *newError=nullptr) const
 Return the linearized delta error from the last updateSolution() call.
const std::vector< CliquePtr > & roots () const
 Accessor for the roots of the elimination tree.
size_t cliqueCount () const
 Get the total number of cliques in the solver.
void print (const std::string &s="", const KeyFormatter &keyFormatter=DefaultKeyFormatter) const
 Print the solver state.
Public Member Functions inherited from gtsam::ForestTraversal< MultifrontalSolver, MultifrontalClique >
 ForestTraversal (size_t numThreads=std::thread::hardware_concurrency())
 Construct a helper with a fixed thread budget (used by TBB when enabled).
void runTopDown (Fn fn, int parallelThreshold=10)
 Scheduler-based top-down traversal.
void runBottomUp (Fn fn, int parallelThreshold=10, size_t leafAggregationProblemSize=0)
 Scheduler-based bottom-up traversal.

Static Public Member Functions

static PrecomputedData Precompute (const GaussianFactorGraph &graph, const Ordering &ordering)
 Precompute symbolic structure and sizing data from a factor graph.

Public Types

using Parameters = MultifrontalParameters
 Tuning parameters for traversal and reporting.
using CliquePtr = std::shared_ptr<MultifrontalClique>
 Shared pointer to a MultifrontalClique.
using Node = MultifrontalClique
 Node type for tree traversal utilities.

Classes

struct  PrecomputedData
 Precomputed symbolic and sizing data for multifrontal solver construction. More...

Protected Attributes

std::vector< CliquePtr > roots_
 Roots of the elimination tree.
std::vector< CliquePtr > cliques_
 All cliques in the solver.
std::map< Key, size_t > dims_
 Map from variable key to dimension.
VectorValues solution_
 Cached solution vector.
std::unordered_set< Key > fixedKeys_
 Keys fixed by constrained factors.
bool loaded_ = false
 Whether load() has been called.
bool eliminated_ = false
 Whether eliminateInPlace() ran.
bool partiallyEliminated_ = false
 Whether partial elimination ran.
Ordering ordering_
 Complete variable ordering.
size_t firstPhaseSize_ = 0
 Prefix eliminated in partial mode.
Parameters params_
 Tunable solver parameters.
double lastOldError_ = 0.0
 Cached old linearized error.
double lastNewError_ = 0.0
 Cached new linearized error.
bool hasDeltaError_ = false
 Whether updateSolution computed it.

Friends

std::ostream & operator<< (std::ostream &os, const MultifrontalSolver &solver)
 Output stream operator for MultifrontalSolver.

Constructor & Destructor Documentation

◆ MultifrontalSolver() [1/3]

gtsam::MultifrontalSolver::MultifrontalSolver ( const GaussianFactorGraph & graph,
const Ordering & ordering,
const Parameters & params = Parameters{} )

Construct the solver from a factor graph and an ordering.

This builds the indexed junction tree and allocates fixed solve matrices. Packed Jacobian fallback storage is allocated lazily during the first load. Call load() before eliminating to populate numerical values.

Parameters
graphThe factor graph to solve. Must contain only JacobianFactor or BatchJacobianFactor instances.
orderingThe variable ordering to use for elimination.
paramsTunable parameters for traversal and reporting.

◆ MultifrontalSolver() [2/3]

gtsam::MultifrontalSolver::MultifrontalSolver ( const GaussianFactorGraph & graph,
const Ordering & ordering,
size_t firstPhaseSize,
const Parameters & params = Parameters{} )

Construct a solver configured for partial multifrontal elimination.

The leading firstPhaseSize keys in ordering are eliminated, while the remaining keys stay assembled in retained clique factors.

◆ MultifrontalSolver() [3/3]

gtsam::MultifrontalSolver::MultifrontalSolver ( PrecomputedData data,
const Ordering & ordering,
const Parameters & params = Parameters{} )

Construct the solver from precomputed symbolic data.

Call load() before eliminating to populate numerical values.

Parameters
dataPrecomputed symbolic structure and sizing data.
orderingThe variable ordering to use for seeding solution storage.
paramsTunable parameters for traversal and reporting.

Member Function Documentation

◆ computeBayesTree()

GaussianBayesTree gtsam::MultifrontalSolver::computeBayesTree ( ) const

Compute a Bayes tree from the in-place Cholesky factorization.

Requires eliminateInPlace() to have been called beforehand.

Returns
A GaussianBayesTree representing the eliminated factor graph encoded by the current multifrontal factorization.

◆ deltaError()

double gtsam::MultifrontalSolver::deltaError ( double * oldError = nullptr,
double * newError = nullptr ) const

Return the linearized delta error from the last updateSolution() call.

Optionally returns the old and new linearized errors.

◆ eliminateInPlace() [1/2]

void gtsam::MultifrontalSolver::eliminateInPlace ( )

Eliminate the graph using Cholesky factorization.

This operates in-place on the clique's reusable numerical storage.

◆ eliminateInPlace() [2/2]

void gtsam::MultifrontalSolver::eliminateInPlace ( const GaussianFactorGraph & graph)

Load and eliminate the graph in a single traversal.

This calls fillAb() and eliminateInPlace() per clique in post-order.

◆ load()

void gtsam::MultifrontalSolver::load ( const GaussianFactorGraph & graph)

Load new numerical values from the factor graph.

The first load builds cached factor load plans and allocates only the Jacobian rows needed by the selected numerical path. Later compatible loads overwrite and reuse that packed storage.

Parameters
graphThe factor graph with updated values (structure must match the graph used to construct/precompute this solver, apart from updated numerical values).

◆ Precompute()

MultifrontalSolver::PrecomputedData gtsam::MultifrontalSolver::Precompute ( const GaussianFactorGraph & graph,
const Ordering & ordering )
static

Precompute symbolic structure and sizing data from a factor graph.

This builds an IndexedJunctionTree that can be reused across multiple solver instances when the graph structure and ordering remain unchanged. Only JacobianFactor and BatchJacobianFactor inputs are supported.

Parameters
graphThe factor graph (must contain only supported Jacobian-style factor instances)
orderingThe variable elimination ordering
Returns
PrecomputedData containing the indexed junction tree and sizing info

◆ remainingFactorGraph()

GaussianFactorGraph gtsam::MultifrontalSolver::remainingFactorGraph ( ) const

Materialize one Hessian factor per retained clique after partial elimination.

Each returned factor owns a compact copy of its active upper-triangular information block because it may outlive the clique.

◆ updateSolution()

const VectorValues & gtsam::MultifrontalSolver::updateSolution ( )

Solve for the update vector.

Returns
Reference to the internally cached solution vector.
The documentation for this class was generated from the following files: