linear solver which uses the sparse Cholesky solver from Eigen More...

#include <linear_solver_eigen.h>

Inheritance diagram for g2o::LinearSolverEigen< MatrixType >:

[legend]

Collaboration diagram for g2o::LinearSolverEigen< MatrixType >:

[legend]

Classes
class	CholeskyDecomposition
	Sub-classing Eigen's SimplicialLLT to perform ordering with a given ordering. More...

Public Types
typedef Eigen::SparseMatrix< double, Eigen::ColMajor >	SparseMatrix

typedef Eigen::Triplet< double >	Triplet

typedef Eigen::PermutationMatrix< Eigen::Dynamic, Eigen::Dynamic >	PermutationMatrix

using	CholeskyDecompositionBase = Eigen::SimplicialLLT< SparseMatrix, Eigen::Upper >

Public Member Functions
	LinearSolverEigen ()

virtual bool	init ()

bool	solve (const SparseBlockMatrix< MatrixType > &A, double x, double b)

Public Member Functions inherited from g2o::LinearSolverCCS< MatrixType >
	LinearSolverCCS ()

	~LinearSolverCCS ()

virtual bool	solveBlocks (double **&blocks, const SparseBlockMatrix< MatrixType > &A)

virtual bool	solvePattern (SparseBlockMatrix< MatrixX > &spinv, const std::vector< std::pair< int, int > > &blockIndices, const SparseBlockMatrix< MatrixType > &A)

bool	blockOrdering () const
	do the AMD ordering on the blocks or on the scalar matrix

void	setBlockOrdering (bool blockOrdering)

Public Member Functions inherited from g2o::LinearSolver< MatrixType >
	LinearSolver ()

virtual	~LinearSolver ()

bool	writeDebug () const
	write a debug dump of the system matrix if it is not PSD in solve

void	setWriteDebug (bool b)

Public Attributes
	EIGEN_MAKE_ALIGNED_OPERATOR_NEW

Protected Member Functions
bool	computeCholesky (const SparseBlockMatrix< MatrixType > &A, double &t)

void	computeSymbolicDecomposition (const SparseBlockMatrix< MatrixType > &A)

void	fillSparseMatrix (const SparseBlockMatrix< MatrixType > &A, bool onlyValues)

bool	solveBlocks_impl (const SparseBlockMatrix< MatrixType > &A, std::function< void(MarginalCovarianceCholesky &)> compute)

Protected Member Functions inherited from g2o::LinearSolverCCS< MatrixType >
void	initMatrixStructure (const SparseBlockMatrix< MatrixType > &A)

Protected Attributes
bool	_init

SparseMatrix	_sparseMatrix

CholeskyDecomposition	_cholesky

Protected Attributes inherited from g2o::LinearSolverCCS< MatrixType >
SparseBlockMatrixCCS< MatrixType > *	_ccsMatrix

bool	_blockOrdering

Protected Attributes inherited from g2o::LinearSolver< MatrixType >
bool	_writeDebug

Additional Inherited Members
Static Public Member Functions inherited from g2o::LinearSolver< MatrixType >
static void	allocateBlocks (const SparseBlockMatrix< MatrixType > &A, double **&blocks)
	allocate block memory structure

static void	deallocateBlocks (const SparseBlockMatrix< MatrixType > &A, double **&blocks)
	de-allocate the block structure

template<typename BlockDerived , typename ScalarDerived >
static void	blockToScalarPermutation (const SparseBlockMatrix< MatrixType > &A, const Eigen::MatrixBase< BlockDerived > &p, const Eigen::MatrixBase< ScalarDerived > &scalar)

Detailed Description

template<typename MatrixType>
class g2o::LinearSolverEigen< MatrixType >

linear solver which uses the sparse Cholesky solver from Eigen

Has no dependencies except Eigen. Hence, should compile almost everywhere without to much issues. Performance should be similar to CSparse.

Definition at line 51 of file linear_solver_eigen.h.

Member Typedef Documentation

◆ CholeskyDecompositionBase

template<typename MatrixType >

using g2o::LinearSolverEigen< MatrixType >::CholeskyDecompositionBase = Eigen::SimplicialLLT<SparseMatrix, Eigen::Upper>

Definition at line 58 of file linear_solver_eigen.h.

◆ PermutationMatrix

template<typename MatrixType >

typedef Eigen::PermutationMatrix<Eigen::Dynamic, Eigen::Dynamic> g2o::LinearSolverEigen< MatrixType >::PermutationMatrix

Definition at line 56 of file linear_solver_eigen.h.

◆ SparseMatrix

template<typename MatrixType >

typedef Eigen::SparseMatrix<double, Eigen::ColMajor> g2o::LinearSolverEigen< MatrixType >::SparseMatrix

Definition at line 53 of file linear_solver_eigen.h.

◆ Triplet

template<typename MatrixType >

typedef Eigen::Triplet<double> g2o::LinearSolverEigen< MatrixType >::Triplet

Definition at line 54 of file linear_solver_eigen.h.

Constructor & Destructor Documentation

◆ LinearSolverEigen()

template<typename MatrixType >

g2o::LinearSolverEigen< MatrixType >::LinearSolverEigen ( )

inline

Definition at line 87 of file linear_solver_eigen.h.

87: LinearSolverCCS<MatrixType>(), _init(true) {}

g2o::LinearSolverEigen::_init

bool _init

Definition linear_solver_eigen.h:113

Member Function Documentation

◆ computeCholesky()

template<typename MatrixType >

bool g2o::LinearSolverEigen< MatrixType >::computeCholesky	(	const SparseBlockMatrix< MatrixType > &	A,
		double &	t
	)

inlineprotected

Definition at line 118 of file linear_solver_eigen.h.

                                                                          {
    // perform some operations only once upon init
    if (_init) _sparseMatrix.resize(A.rows(), A.cols());
    fillSparseMatrix(A, !_init);
    if (_init) computeSymbolicDecomposition(A);
    _init = false;
 
    t = get_monotonic_time();
    _cholesky.factorize(_sparseMatrix);
    if (_cholesky.info() !=
        Eigen::Success) {  // the matrix is not positive definite
      if (this->writeDebug()) {
        G2O_ERROR(
            "Cholesky failure, writing debug.txt (Hessian loadable by Octave)");
        A.writeOctave("debug.txt");
      } else {
        G2O_DEBUG("Cholesky failure");
      }
      return false;
    }
    return true;
  }

References g2o::LinearSolverEigen< MatrixType >::_cholesky, g2o::LinearSolverEigen< MatrixType >::_init, g2o::LinearSolverEigen< MatrixType >::_sparseMatrix, g2o::SparseBlockMatrix< MatrixType >::cols(), g2o::LinearSolverEigen< MatrixType >::computeSymbolicDecomposition(), g2o::LinearSolverEigen< MatrixType >::fillSparseMatrix(), G2O_DEBUG, G2O_ERROR, g2o::get_monotonic_time(), g2o::SparseBlockMatrix< MatrixType >::rows(), g2o::LinearSolver< MatrixType >::writeDebug(), and g2o::SparseBlockMatrix< MatrixType >::writeOctave().

Referenced by g2o::LinearSolverEigen< MatrixType >::solve(), and g2o::LinearSolverEigen< MatrixType >::solveBlocks_impl().

◆ computeSymbolicDecomposition()

template<typename MatrixType >

void g2o::LinearSolverEigen< MatrixType >::computeSymbolicDecomposition ( const SparseBlockMatrix< MatrixType > & A )

inlineprotected

compute the symbolic decomposition of the matrix only once. Since A has the same pattern in all the iterations, we only compute the fill-in reducing ordering once and re-use for all the following iterations.

Definition at line 147 of file linear_solver_eigen.h.

                                                                            {
    double t = get_monotonic_time();
    if (!this->blockOrdering()) {
      _cholesky.analyzePattern(_sparseMatrix);
    } else {
      assert(A.rows() == A.cols() && "Matrix A is not square");
      // block ordering with the Eigen Interface
      Eigen::PermutationMatrix<Eigen::Dynamic, Eigen::Dynamic> blockP;
      {
        SparseMatrix auxBlockMatrix(A.blockCols().size(), A.blockCols().size());
        auxBlockMatrix.resizeNonZeros(A.nonZeroBlocks());
        // fill the CCS structure of the Eigen SparseMatrix
        A.fillBlockStructure(auxBlockMatrix.outerIndexPtr(),
                             auxBlockMatrix.innerIndexPtr());
        // determine ordering by AMD
        using Ordering = Eigen::AMDOrdering<SparseMatrix::StorageIndex>;
        Ordering ordering;
        ordering(auxBlockMatrix, blockP);
      }
 
      // Adapt the block permutation to the scalar matrix
      PermutationMatrix scalarP(A.rows());
      this->blockToScalarPermutation(A, blockP.indices(), scalarP.indices());
      // analyze with the scalar permutation
      _cholesky.analyzePatternWithPermutation(_sparseMatrix, scalarP);
    }
    G2OBatchStatistics* globalStats = G2OBatchStatistics::globalStats();
    if (globalStats)
      globalStats->timeSymbolicDecomposition = get_monotonic_time() - t;
  }

References g2o::LinearSolverEigen< MatrixType >::_cholesky, g2o::LinearSolverEigen< MatrixType >::_sparseMatrix, g2o::LinearSolverEigen< MatrixType >::CholeskyDecomposition::analyzePatternWithPermutation(), g2o::SparseBlockMatrix< MatrixType >::blockCols(), g2o::LinearSolverCCS< MatrixType >::blockOrdering(), g2o::LinearSolver< MatrixType >::blockToScalarPermutation(), g2o::SparseBlockMatrix< MatrixType >::cols(), g2o::SparseBlockMatrix< MatrixType >::fillBlockStructure(), g2o::get_monotonic_time(), g2o::G2OBatchStatistics::globalStats(), g2o::SparseBlockMatrix< MatrixType >::nonZeroBlocks(), g2o::SparseBlockMatrix< MatrixType >::rows(), and g2o::G2OBatchStatistics::timeSymbolicDecomposition.

Referenced by g2o::LinearSolverEigen< MatrixType >::computeCholesky().

◆ fillSparseMatrix()

template<typename MatrixType >

void g2o::LinearSolverEigen< MatrixType >::fillSparseMatrix	(	const SparseBlockMatrix< MatrixType > &	A,
		bool	onlyValues
	)

inlineprotected

Definition at line 178 of file linear_solver_eigen.h.

                                         {
    if (onlyValues) {
      this->_ccsMatrix->fillCCS(_sparseMatrix.valuePtr(), true);
      return;
    }
    this->initMatrixStructure(A);
    _sparseMatrix.resizeNonZeros(A.nonZeros());
    int nz = this->_ccsMatrix->fillCCS(_sparseMatrix.outerIndexPtr(),
                                       _sparseMatrix.innerIndexPtr(),
                                       _sparseMatrix.valuePtr(), true);
    (void)nz;
    assert(nz <= static_cast<int>(_sparseMatrix.data().size()));
  }

References g2o::LinearSolverCCS< MatrixType >::_ccsMatrix, g2o::LinearSolverEigen< MatrixType >::_sparseMatrix, g2o::LinearSolverCCS< MatrixType >::initMatrixStructure(), and g2o::SparseBlockMatrix< MatrixType >::nonZeros().

Referenced by g2o::LinearSolverEigen< MatrixType >::computeCholesky().

◆ init()

template<typename MatrixType >

virtual bool g2o::LinearSolverEigen< MatrixType >::init ( )

inlinevirtual

init for operating on matrices with a different non-zero pattern like before

Implements g2o::LinearSolver< MatrixType >.

Definition at line 89 of file linear_solver_eigen.h.

                      {
    _init = true;
    return true;
  }

References g2o::LinearSolverEigen< MatrixType >::_init.

Referenced by g2o::SolverSLAM2DLinear::solveOrientation().

◆ solve()

template<typename MatrixType >

bool g2o::LinearSolverEigen< MatrixType >::solve	(	const SparseBlockMatrix< MatrixType > &	A,
		double *	x,
		double *	b
	)

inlinevirtual

Assumes that A is the same matrix for several calls. Among other assumptions, the non-zero pattern does not change! If the matrix changes call init() before. solve system Ax = b, x and b have to allocated beforehand!!

Implements g2o::LinearSolver< MatrixType >.

Definition at line 94 of file linear_solver_eigen.h.

                                                                           {
    double t;
    bool cholState = computeCholesky(A, t);
    if (!cholState) return false;
 
    // Solving the system
    VectorX::MapType xx(x, _sparseMatrix.cols());
    VectorX::ConstMapType bb(b, _sparseMatrix.cols());
    xx = _cholesky.solve(bb);
    G2OBatchStatistics* globalStats = G2OBatchStatistics::globalStats();
    if (globalStats) {
      globalStats->timeNumericDecomposition = get_monotonic_time() - t;
      globalStats->choleskyNNZ =
          _cholesky.matrixL().nestedExpression().nonZeros();
    }
    return true;
  }

References g2o::LinearSolverEigen< MatrixType >::_cholesky, g2o::LinearSolverEigen< MatrixType >::_sparseMatrix, g2o::G2OBatchStatistics::choleskyNNZ, g2o::LinearSolverEigen< MatrixType >::computeCholesky(), g2o::get_monotonic_time(), g2o::G2OBatchStatistics::globalStats(), and g2o::G2OBatchStatistics::timeNumericDecomposition.

◆ solveBlocks_impl()

template<typename MatrixType >

bool g2o::LinearSolverEigen< MatrixType >::solveBlocks_impl	(	const SparseBlockMatrix< MatrixType > &	A,
		std::function< void(MarginalCovarianceCholesky &)>	compute
	)

inlineprotectedvirtual

Implementation of the general parts for computing the inverse blocks of the linear system matrix. Here we call a function to do the underlying computation.

Implements g2o::LinearSolverCCS< MatrixType >.

Definition at line 198 of file linear_solver_eigen.h.

                                                              {
    // compute the cholesky factor
    double t;
    bool cholState = computeCholesky(A, t);
    if (!cholState) return false;
    // compute the inverse blocks
    MarginalCovarianceCholesky mcc;
    mcc.setCholeskyFactor(
        _cholesky.matrixL().rows(),
        const_cast<int*>(
            _cholesky.matrixL().nestedExpression().outerIndexPtr()),
        const_cast<int*>(
            _cholesky.matrixL().nestedExpression().innerIndexPtr()),
        const_cast<double*>(_cholesky.matrixL().nestedExpression().valuePtr()),
        const_cast<int*>(_cholesky.permutationP().indices().data()));
    compute(mcc);  // call the desired computation on the mcc object
    // book keeping statistics
    G2OBatchStatistics* globalStats = G2OBatchStatistics::globalStats();
    if (globalStats) {
      globalStats->choleskyNNZ =
          _cholesky.matrixL().nestedExpression().nonZeros();
    }
    return true;
  }

References g2o::LinearSolverEigen< MatrixType >::_cholesky, g2o::G2OBatchStatistics::choleskyNNZ, g2o::LinearSolverEigen< MatrixType >::computeCholesky(), g2o::G2OBatchStatistics::globalStats(), and g2o::MarginalCovarianceCholesky::setCholeskyFactor().

Member Data Documentation

◆ _cholesky

template<typename MatrixType >

CholeskyDecomposition g2o::LinearSolverEigen< MatrixType >::_cholesky

protected

Definition at line 115 of file linear_solver_eigen.h.

Referenced by g2o::LinearSolverEigen< MatrixType >::computeCholesky(), g2o::LinearSolverEigen< MatrixType >::computeSymbolicDecomposition(), g2o::LinearSolverEigen< MatrixType >::solve(), and g2o::LinearSolverEigen< MatrixType >::solveBlocks_impl().

◆ _init

template<typename MatrixType >

bool g2o::LinearSolverEigen< MatrixType >::_init

protected

Definition at line 113 of file linear_solver_eigen.h.

Referenced by g2o::LinearSolverEigen< MatrixType >::computeCholesky(), and g2o::LinearSolverEigen< MatrixType >::init().

◆ _sparseMatrix

template<typename MatrixType >

SparseMatrix g2o::LinearSolverEigen< MatrixType >::_sparseMatrix

protected

Definition at line 114 of file linear_solver_eigen.h.

Referenced by g2o::LinearSolverEigen< MatrixType >::computeCholesky(), g2o::LinearSolverEigen< MatrixType >::computeSymbolicDecomposition(), g2o::LinearSolverEigen< MatrixType >::fillSparseMatrix(), and g2o::LinearSolverEigen< MatrixType >::solve().

◆ EIGEN_MAKE_ALIGNED_OPERATOR_NEW

template<typename MatrixType >

g2o::LinearSolverEigen< MatrixType >::EIGEN_MAKE_ALIGNED_OPERATOR_NEW

Definition at line 86 of file linear_solver_eigen.h.

The documentation for this class was generated from the following file:

/build/reproducible-path/g2o-0~20230806/g2o/solvers/eigen/linear_solver_eigen.h

Classes

Public Types

Public Member Functions

Public Attributes

Protected Member Functions

Protected Attributes

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ CholeskyDecompositionBase

◆ PermutationMatrix

◆ SparseMatrix

◆ Triplet

Constructor & Destructor Documentation

◆ LinearSolverEigen()

Member Function Documentation

◆ computeCholesky()

◆ computeSymbolicDecomposition()

◆ fillSparseMatrix()

◆ init()

◆ solve()

◆ solveBlocks_impl()

Member Data Documentation

◆ _cholesky

◆ _init

◆ _sparseMatrix

◆ EIGEN_MAKE_ALIGNED_OPERATOR_NEW