GaussianFactorGraph.cpp
Go to the documentation of this file.
1 /* ----------------------------------------------------------------------------
2 
3  * GTSAM Copyright 2010, Georgia Tech Research Corporation,
4  * Atlanta, Georgia 30332-0415
5  * All Rights Reserved
6  * Authors: Frank Dellaert, et al. (see THANKS for the full author list)
7 
8  * See LICENSE for the license information
9 
10  * -------------------------------------------------------------------------- */
11 
28 #include <gtsam/base/debug.h>
29 #include <gtsam/base/timing.h>
30 #include <gtsam/base/cholesky.h>
31 
32 using namespace std;
33 using namespace gtsam;
34 
35 namespace gtsam {
36 
37  // Instantiate base classes
38  template class FactorGraph<GaussianFactor>;
40 
41  /* ************************************************************************* */
42  bool GaussianFactorGraph::equals(const This& fg, double tol) const
43  {
44  return Base::equals(fg, tol);
45  }
46 
47  /* ************************************************************************* */
49  KeySet keys;
50  for (const sharedFactor& factor: *this)
51  if (factor)
52  keys.insert(factor->begin(), factor->end());
53  return keys;
54  }
55 
56  /* ************************************************************************* */
57  std::map<Key, size_t> GaussianFactorGraph::getKeyDimMap() const {
58  map<Key, size_t> spec;
59  for (const GaussianFactor::shared_ptr& gf : *this) {
60  for (GaussianFactor::const_iterator it = gf->begin(); it != gf->end(); it++) {
61  map<Key,size_t>::iterator it2 = spec.find(*it);
62  if ( it2 == spec.end() ) {
63  spec.emplace(*it, gf->getDim(it));
64  }
65  }
66  }
67  return spec;
68  }
69 
70  /* ************************************************************************* */
71  double GaussianFactorGraph::error(const VectorValues& x) const {
72  double total_error = 0.;
73  for(const sharedFactor& factor: *this){
74  if(factor)
75  total_error += factor->error(x);
76  }
77  return total_error;
78  }
79 
80  /* ************************************************************************* */
81  double GaussianFactorGraph::probPrime(const VectorValues& c) const {
82  // NOTE the 0.5 constant is handled by the factor error.
83  return exp(-error(c));
84  }
85 
86  /* ************************************************************************* */
87  GaussianFactorGraph::shared_ptr GaussianFactorGraph::cloneToPtr() const {
89  *result = *this;
90  return result;
91  }
92 
93  /* ************************************************************************* */
94  GaussianFactorGraph GaussianFactorGraph::clone() const {
96  for (const sharedFactor& f : *this) {
97  if (f)
98  result.push_back(f->clone());
99  else
100  result.push_back(sharedFactor()); // Passes on null factors so indices remain valid
101  }
102  return result;
103  }
104 
105  /* ************************************************************************* */
108  for (const sharedFactor& factor: *this) {
109  if (factor)
110  result.push_back(factor->negate());
111  else
112  result.push_back(sharedFactor()); // Passes on null factors so indices remain valid
113  }
114  return result;
115  }
116 
117  /* ************************************************************************* */
118  using SparseTriplets = std::vector<std::tuple<int, int, double> >;
119  SparseTriplets GaussianFactorGraph::sparseJacobian(const Ordering& ordering,
120  size_t& nrows,
121  size_t& ncols) const {
122  gttic_(GaussianFactorGraph_sparseJacobian);
123  // First find dimensions of each variable
124  typedef std::map<Key, size_t> KeySizeMap;
125  KeySizeMap dims;
126  for (const auto& factor : *this) {
127  if (!static_cast<bool>(factor)) continue;
128 
129  for (auto it = factor->begin(); it != factor->end(); ++it) {
130  dims[*it] = factor->getDim(it);
131  }
132  }
133 
134  // Compute first scalar column of each variable
135  ncols = 0;
136  KeySizeMap columnIndices = dims;
137  for (const auto key : ordering) {
138  columnIndices[key] = ncols;
139  ncols += dims[key];
140  }
141 
142  // Iterate over all factors, adding sparse scalar entries
143  SparseTriplets entries;
144  entries.reserve(30 * size());
145  nrows = 0;
146  for (const auto& factor : *this) {
147  if (!static_cast<bool>(factor)) continue;
148 
149  // Convert to JacobianFactor if necessary
150  JacobianFactor::shared_ptr jacobianFactor(
151  std::dynamic_pointer_cast<JacobianFactor>(factor));
152  if (!jacobianFactor) {
154  std::dynamic_pointer_cast<HessianFactor>(factor));
155  if (hessian)
156  jacobianFactor.reset(new JacobianFactor(*hessian));
157  else
158  throw std::invalid_argument(
159  "GaussianFactorGraph contains a factor that is neither a "
160  "JacobianFactor nor a HessianFactor.");
161  }
162 
163  // Whiten the factor and add entries for it
164  // iterate over all variables in the factor
165  const JacobianFactor whitened(jacobianFactor->whiten());
166  for (auto key = whitened.begin(); key < whitened.end(); ++key) {
167  JacobianFactor::constABlock whitenedA = whitened.getA(key);
168  // find first column index for this key
169  size_t column_start = columnIndices[*key];
170  for (size_t i = 0; i < (size_t)whitenedA.rows(); i++)
171  for (size_t j = 0; j < (size_t)whitenedA.cols(); j++) {
172  double s = whitenedA(i, j);
173  if (std::abs(s) > 1e-12)
174  entries.emplace_back(nrows + i, column_start + j, s);
175  }
176  }
177 
178  JacobianFactor::constBVector whitenedb(whitened.getb());
179  for (size_t i = 0; i < (size_t)whitenedb.size(); i++) {
180  double s = whitenedb(i);
181  if (std::abs(s) > 1e-12) entries.emplace_back(nrows + i, ncols, s);
182  }
183 
184  // Increment row index
185  nrows += jacobianFactor->rows();
186  }
187 
188  ncols++; // +1 for b-column
189  return entries;
190  }
191 
192  /* ************************************************************************* */
193  SparseTriplets GaussianFactorGraph::sparseJacobian() const {
194  size_t nrows, ncols;
195  return sparseJacobian(Ordering(this->keys()), nrows, ncols);
196  }
197 
198  /* ************************************************************************* */
199  Matrix GaussianFactorGraph::sparseJacobian_() const {
200  gttic_(GaussianFactorGraph_sparseJacobian_matrix);
201  // call sparseJacobian
202  auto result = sparseJacobian();
203 
204  // translate to base 1 matrix
205  size_t nzmax = result.size();
206  Matrix IJS(3, nzmax);
207  for (size_t k = 0; k < result.size(); k++) {
208  const auto& entry = result[k];
209  IJS(0, k) = double(std::get<0>(entry) + 1);
210  IJS(1, k) = double(std::get<1>(entry) + 1);
211  IJS(2, k) = std::get<2>(entry);
212  }
213  return IJS;
214  }
215 
216  /* ************************************************************************* */
217  Matrix GaussianFactorGraph::augmentedJacobian(
218  const Ordering& ordering) const {
219  // combine all factors
220  JacobianFactor combined(*this, ordering);
221  return combined.augmentedJacobian();
222  }
223 
224  /* ************************************************************************* */
225  Matrix GaussianFactorGraph::augmentedJacobian() const {
226  // combine all factors
227  JacobianFactor combined(*this);
228  return combined.augmentedJacobian();
229  }
230 
231  /* ************************************************************************* */
232  pair<Matrix, Vector> GaussianFactorGraph::jacobian(
233  const Ordering& ordering) const {
234  Matrix augmented = augmentedJacobian(ordering);
235  return make_pair(augmented.leftCols(augmented.cols() - 1),
236  augmented.col(augmented.cols() - 1));
237  }
238 
239  /* ************************************************************************* */
240  pair<Matrix, Vector> GaussianFactorGraph::jacobian() const {
241  Matrix augmented = augmentedJacobian();
242  return make_pair(augmented.leftCols(augmented.cols() - 1),
243  augmented.col(augmented.cols() - 1));
244  }
245 
246  /* ************************************************************************* */
247  Matrix GaussianFactorGraph::augmentedHessian(
248  const Ordering& ordering) const {
249  // combine all factors and get upper-triangular part of Hessian
250  Scatter scatter(*this, ordering);
251  HessianFactor combined(*this, scatter);
252  return combined.info().selfadjointView();
253  }
254 
255  /* ************************************************************************* */
256  Matrix GaussianFactorGraph::augmentedHessian() const {
257  // combine all factors and get upper-triangular part of Hessian
258  Scatter scatter(*this);
259  HessianFactor combined(*this, scatter);
260  return combined.info().selfadjointView();
261  }
262 
263  /* ************************************************************************* */
264  pair<Matrix, Vector> GaussianFactorGraph::hessian(
265  const Ordering& ordering) const {
266  Matrix augmented = augmentedHessian(ordering);
267  size_t n = augmented.rows() - 1;
268  return make_pair(augmented.topLeftCorner(n, n), augmented.topRightCorner(n, 1));
269  }
270 
271  /* ************************************************************************* */
272  pair<Matrix, Vector> GaussianFactorGraph::hessian() const {
273  Matrix augmented = augmentedHessian();
274  size_t n = augmented.rows() - 1;
275  return make_pair(augmented.topLeftCorner(n, n), augmented.topRightCorner(n, 1));
276  }
277 
278  /* ************************************************************************* */
279  VectorValues GaussianFactorGraph::hessianDiagonal() const {
280  VectorValues d;
281  for (const sharedFactor& factor : *this) {
282  if(factor){
283  factor->hessianDiagonalAdd(d);
284  }
285  }
286  return d;
287  }
288 
289  /* ************************************************************************* */
290  map<Key,Matrix> GaussianFactorGraph::hessianBlockDiagonal() const {
291  map<Key,Matrix> blocks;
292  for (const sharedFactor& factor : *this) {
293  if (!factor) continue;
294  map<Key,Matrix> BD = factor->hessianBlockDiagonal();
295  map<Key,Matrix>::const_iterator it = BD.begin();
296  for (;it!=BD.end();++it) {
297  Key j = it->first; // variable key for this block
298  const Matrix& Bj = it->second;
299  if (blocks.count(j))
300  blocks[j] += Bj;
301  else
302  blocks.emplace(j,Bj);
303  }
304  }
305  return blocks;
306  }
307 
308  /* ************************************************************************ */
309  VectorValues GaussianFactorGraph::optimize(const Eliminate& function) const {
310  gttic(GaussianFactorGraph_optimize);
311  return BaseEliminateable::eliminateMultifrontal(Ordering::COLAMD, function)
312  ->optimize();
313  }
314 
315  /* ************************************************************************* */
316  VectorValues GaussianFactorGraph::optimize(const Ordering& ordering, const Eliminate& function) const {
317  gttic(GaussianFactorGraph_optimize);
318  return BaseEliminateable::eliminateMultifrontal(ordering, function)->optimize();
319  }
320 
321  /* ************************************************************************* */
322  // TODO(frank): can we cache memory across invocations
323  VectorValues GaussianFactorGraph::optimizeDensely() const {
324  gttic(GaussianFactorGraph_optimizeDensely);
325 
326  // Combine all factors in a single HessianFactor (as done in augmentedHessian)
327  Scatter scatter(*this);
328  HessianFactor combined(*this, scatter);
329 
330  // TODO(frank): cast to large dynamic matrix :-(
331  // NOTE(frank): info only valid (I think) in upper triangle. No problem for LLT...
332  Matrix augmented = combined.info().selfadjointView();
333 
334  // Do Cholesky Factorization
335  size_t n = augmented.rows() - 1;
336  auto AtA = augmented.topLeftCorner(n, n);
337  auto eta = augmented.topRightCorner(n, 1);
339 
340  // Solve and convert, re-using scatter data structure
341  Vector solution = llt.solve(eta);
342  return VectorValues(solution, scatter);
343  }
344 
345  /* ************************************************************************* */
346  namespace {
347  JacobianFactor::shared_ptr convertToJacobianFactorPtr(const GaussianFactor::shared_ptr &gf) {
348  JacobianFactor::shared_ptr result = std::dynamic_pointer_cast<JacobianFactor>(gf);
349  if( !result )
350  // Convert any non-Jacobian factors to Jacobians (e.g. Hessian -> Jacobian with Cholesky)
351  result = std::make_shared<JacobianFactor>(*gf);
352  return result;
353  }
354  }
355 
356  /* ************************************************************************* */
357  VectorValues GaussianFactorGraph::gradient(const VectorValues& x0) const
358  {
359  VectorValues g = VectorValues::Zero(x0);
360  for (const sharedFactor& factor: *this) {
361  JacobianFactor::shared_ptr Ai = convertToJacobianFactorPtr(factor);
362  Vector e = Ai->error_vector(x0);
363  Ai->transposeMultiplyAdd(1.0, e, g);
364  }
365  return g;
366  }
367 
368  /* ************************************************************************* */
369  VectorValues GaussianFactorGraph::gradientAtZero() const {
370  // Zero-out the gradient
371  VectorValues g;
372  for (const sharedFactor& factor: *this) {
373  if (!factor) continue;
374  VectorValues gi = factor->gradientAtZero();
375  g.addInPlace_(gi);
376  }
377  return g;
378  }
379 
380  /* ************************************************************************* */
381  VectorValues GaussianFactorGraph::optimizeGradientSearch() const
382  {
383  gttic(GaussianFactorGraph_optimizeGradientSearch);
384 
385  gttic(Compute_Gradient);
386  // Compute gradient (call gradientAtZero function, which is defined for various linear systems)
387  VectorValues grad = gradientAtZero();
388  double gradientSqNorm = grad.dot(grad);
389  gttoc(Compute_Gradient);
390 
391  gttic(Compute_Rg);
392  // Compute R * g
393  Errors Rg = *this * grad;
394  gttoc(Compute_Rg);
395 
396  gttic(Compute_minimizing_step_size);
397  // Compute minimizing step size
398  double step = -gradientSqNorm / gtsam::dot(Rg, Rg);
399  gttoc(Compute_minimizing_step_size);
400 
401  gttic(Compute_point);
402  // Compute steepest descent point
403  grad *= step;
404  gttoc(Compute_point);
405 
406  return grad;
407  }
408 
409  /* ************************************************************************* */
411  Errors e;
412  for (const GaussianFactor::shared_ptr& factor: *this) {
413  JacobianFactor::shared_ptr Ai = convertToJacobianFactorPtr(factor);
414  e.push_back((*Ai) * x);
415  }
416  return e;
417  }
418 
419  /* ************************************************************************* */
420  void GaussianFactorGraph::multiplyHessianAdd(double alpha,
421  const VectorValues& x, VectorValues& y) const {
422  for (const GaussianFactor::shared_ptr& f: *this)
423  f->multiplyHessianAdd(alpha, x, y);
424  }
425 
426  /* ************************************************************************* */
427  void GaussianFactorGraph::multiplyInPlace(const VectorValues& x, Errors& e) const {
428  multiplyInPlace(x, e.begin());
429  }
430 
431  /* ************************************************************************* */
432  void GaussianFactorGraph::multiplyInPlace(const VectorValues& x, const Errors::iterator& e) const {
433  Errors::iterator ei = e;
434  for (const GaussianFactor::shared_ptr& factor: *this) {
435  JacobianFactor::shared_ptr Ai = convertToJacobianFactorPtr(factor);
436  *ei = (*Ai)*x;
437  ei++;
438  }
439  }
440 
441  /* ************************************************************************* */
443  typedef JacobianFactor J;
444  for (const GaussianFactor::shared_ptr& factor: factors) {
445  J::shared_ptr jacobian(std::dynamic_pointer_cast<J>(factor));
446  if (jacobian && jacobian->get_model() && jacobian->get_model()->isConstrained()) {
447  return true;
448  }
449  }
450  return false;
451  }
452 
453  /* ************************************************************************* */
454  // x += alpha*A'*e
455  void GaussianFactorGraph::transposeMultiplyAdd(double alpha, const Errors& e,
456  VectorValues& x) const {
457  // For each factor add the gradient contribution
458  Errors::const_iterator ei = e.begin();
459  for (const sharedFactor& factor: *this) {
460  JacobianFactor::shared_ptr Ai = convertToJacobianFactorPtr(factor);
461  Ai->transposeMultiplyAdd(alpha, *(ei++), x);
462  }
463  }
464 
466  //void residual(const GaussianFactorGraph& fg, const VectorValues &x, VectorValues &r) {
467  // Key i = 0 ;
468  // for (const GaussianFactor::shared_ptr& factor, fg) {
469  // JacobianFactor::shared_ptr Ai = convertToJacobianFactorPtr(factor);
470  // r[i] = Ai->getb();
471  // i++;
472  // }
473  // VectorValues Ax = VectorValues::SameStructure(r);
474  // multiply(fg,x,Ax);
475  // axpy(-1.0,Ax,r);
476  //}
477 
479  //void multiply(const GaussianFactorGraph& fg, const VectorValues &x, VectorValues &r) {
480  // r.setZero();
481  // Key i = 0;
482  // for (const GaussianFactor::shared_ptr& factor, fg) {
483  // JacobianFactor::shared_ptr Ai = convertToJacobianFactorPtr(factor);
484  // Vector &y = r[i];
485  // for (JacobianFactor::const_iterator j = Ai->begin(); j != Ai->end(); ++j) {
486  // y += Ai->getA(j) * x[*j];
487  // }
488  // ++i;
489  // }
490  //}
491 
492  /* ************************************************************************* */
493  VectorValues GaussianFactorGraph::transposeMultiply(const Errors& e) const
494  {
495  VectorValues x;
496  Errors::const_iterator ei = e.begin();
497  for (const sharedFactor& factor: *this) {
498  JacobianFactor::shared_ptr Ai = convertToJacobianFactorPtr(factor);
499  for (JacobianFactor::const_iterator j = Ai->begin(); j != Ai->end(); ++j) {
500  // Create the value as a zero vector if it does not exist.
501  pair<VectorValues::iterator, bool> xi = x.tryInsert(*j, Vector());
502  if(xi.second)
503  xi.first->second = Vector::Zero(Ai->getDim(j));
504  xi.first->second += Ai->getA(j).transpose() * *ei;
505  }
506  ++ ei;
507  }
508  return x;
509  }
510 
511  /* ************************************************************************* */
512  Errors GaussianFactorGraph::gaussianErrors(const VectorValues& x) const
513  {
514  Errors e;
515  for (const sharedFactor& factor: *this) {
516  JacobianFactor::shared_ptr Ai = convertToJacobianFactorPtr(factor);
517  e.push_back(Ai->error_vector(x));
518  }
519  return e;
520  }
521 
522  /* ************************************************************************* */
523  void GaussianFactorGraph::printErrors(
524  const VectorValues& values, const std::string& str,
525  const KeyFormatter& keyFormatter,
526  const std::function<bool(const Factor* /*factor*/,
527  double /*whitenedError*/, size_t /*index*/)>&
528  printCondition) const {
529  cout << str << "size: " << size() << endl << endl;
530  for (size_t i = 0; i < (*this).size(); i++) {
531  const sharedFactor& factor = (*this)[i];
532  const double errorValue =
533  (factor != nullptr ? (*this)[i]->error(values) : .0);
534  if (!printCondition(factor.get(), errorValue, i))
535  continue; // User-provided filter did not pass
536 
537  stringstream ss;
538  ss << "Factor " << i << ": ";
539  if (factor == nullptr) {
540  cout << "nullptr"
541  << "\n";
542  } else {
543  factor->print(ss.str(), keyFormatter);
544  cout << "error = " << errorValue << "\n";
545  }
546  cout << endl; // only one "endl" at end might be faster, \n for each
547  // factor
548  }
549  }
550 
551 } // namespace gtsam
const gtsam::Symbol key('X', 0)
Vector3_ operator*(const Double_ &s, const Vector3_ &v)
def step(data, isam, result, truth, currPoseIndex)
Definition: visual_isam.py:82
const Solve< LLT< _MatrixType, _UpLo >, Rhs > solve(const MatrixBase< Rhs > &b) const
Definition: SolverBase.h:106
Scalar * y
#define gttic_(label)
Definition: timing.h:245
double dot(const V1 &a, const V2 &b)
Definition: Vector.h:195
Global debugging flags.
std::shared_ptr< This > shared_ptr
A shared_ptr to this class.
IsDerived< DERIVEDFACTOR > push_back(std::shared_ptr< DERIVEDFACTOR > factor)
Add a factor directly using a shared_ptr.
Definition: FactorGraph.h:190
int n
Eigen::MatrixXd Matrix
Definition: base/Matrix.h:39
Scalar Scalar * c
Definition: benchVecAdd.cpp:17
leaf::MyValues values
const GaussianFactorGraph factors
Definition: BFloat16.h:88
VectorValues & addInPlace_(const VectorValues &c)
Matrix augmentedJacobian() const override
static enum @1107 ordering
void g(const string &key, int i)
Definition: testBTree.cpp:41
std::pair< iterator, bool > tryInsert(Key j, const Vector &value)
Definition: VectorValues.h:209
EIGEN_DEVICE_FUNC const ExpReturnType exp() const
Scalar Scalar int size
Definition: benchVecAdd.cpp:17
#define gttic(label)
Definition: timing.h:295
EIGEN_DONT_INLINE void llt(const Mat &A, const Mat &B, Mat &C)
Definition: llt.cpp:5
Eigen::SelfAdjointView< constBlock, Eigen::Upper > selfadjointView(DenseIndex I, DenseIndex J) const
Return the square sub-matrix that contains blocks(i:j, i:j).
Eigen::VectorXd Vector
Definition: Vector.h:38
Values result
constABlock::ConstColXpr constBVector
Definition: pytypes.h:1403
Standard Cholesky decomposition (LL^T) of a matrix and associated features.
Definition: LLT.h:66
Point2(* f)(const Point3 &, OptionalJacobian< 2, 3 >)
RealScalar alpha
Contains the HessianFactor class, a general quadratic factor.
Array< double, 1, 3 > e(1./3., 0.5, 2.)
RealScalar s
Linear Factor Graph where all factors are Gaussians.
size_t size() const
Definition: Values.h:178
JacobiRotation< float > J
std::shared_ptr< This > shared_ptr
shared_ptr to this class
std::shared_ptr< This > shared_ptr
shared_ptr to this class
std::function< std::string(Key)> KeyFormatter
Typedef for a function to format a key, i.e. to convert it to a string.
Definition: Key.h:35
std::shared_ptr< This > shared_ptr
shared_ptr to this class
static std::stringstream ss
Definition: testBTree.cpp:31
Vector xi
Definition: testPose2.cpp:148
traits
Definition: chartTesting.h:28
static Symbol x0('x', 0)
std::vector< std::tuple< int, int, double > > SparseTriplets
double dot(const VectorValues &v) const
Expression of a fixed-size or dynamic-size block.
Definition: Block.h:103
#define gttoc(label)
Definition: timing.h:296
int optimize(const SfmData &db, const NonlinearFactorGraph &graph, const Values &initial, bool separateCalibration=false)
Definition: timeSFMBAL.h:64
A Gaussian factor using the canonical parameters (information form)
static double error
Definition: testRot3.cpp:37
const G double tol
Definition: Group.h:86
std::shared_ptr< GaussianFactor > sharedFactor
Shared pointer to a factor.
Definition: FactorGraph.h:105
KeyVector::const_iterator const_iterator
Const iterator over keys.
Definition: Factor.h:82
const KeyVector keys
Factor Graph Base Class.
set noclip points set clip one set noclip two set bar set border lt lw set xdata set ydata set zdata set x2data set y2data set boxwidth set dummy x
#define abs(x)
Definition: datatypes.h:17
Eigen::Matrix< double, Eigen::Dynamic, 1 > Vector
const SymmetricBlockMatrix & info() const
Return underlying information matrix.
bool hasConstraints(const GaussianFactorGraph &factors)
Gaussian Bayes Tree, the result of eliminating a GaussianJunctionTree.
std::uint64_t Key
Integer nonlinear key type.
Definition: types.h:102
std::ptrdiff_t j
Timing utilities.
Efficient incomplete Cholesky on rank-deficient matrices, todo: constrained Cholesky.


gtsam
Author(s):
autogenerated on Tue Jul 4 2023 02:34:15