File sparse_schur_solver.h#

namespace sym

template<typename _MatrixType> class SparseSchurSolver#

#include <sparse_schur_solver.h>

A solver for factorizing and solving positive definite matrices with a large block-diagonal component

This includes matrices typically encountered in SfM, where the landmarks-to-landmarks block of the Hessian is block diagonal (there are no cross-terms between different landmarks)

We should have a matrix A of structure

A = ( B    E )
    ( E^T  C )

with C in R^{C_dim x C_dim} block diagonal.

The full problem is A x = b, which we can break down the same way as

( B    E ) ( y ) = ( v )
( E^T  C ) ( z )   ( w )

We then have two equations:

B y + E z = v
E^T y + C z = w

C is block diagonal and therefore easy to invert, so we can write

z = C^{-1} (w - E^T y)

Plugging this into the first equation, we can eliminate z:

B y + E C^{-1} (w - E^T y) = v
=> B y + E C^{-1} w - E C^{-1} E^T y = v
=> (B - E C^{-1} E^T) y = v - E C^{-1} w

Defining the Schur complement S = B - E C^{-1} E^T, we have

S y = v - E C^{-1} w

So, we can form S and use the above equation to solve for y. Once we have y, we can use the equation for z above to solve for z, and we’re done.

See http://ceres-solver.org/nnls_solving.html#dense-schur-sparse-schur

Public Types

using MatrixType = _MatrixType #

using Scalar = typename MatrixType::Scalar#

using SMatrixSolverType = SparseCholeskySolver<MatrixType, Eigen::Lower>#

using MatrixX = Eigen::Matrix<Scalar, Eigen::Dynamic, Eigen::Dynamic>#

using VectorX = Eigen::Matrix<Scalar, Eigen::Dynamic, 1>#

Public Functions

inline SparseSchurSolver(const typename SMatrixSolverType::Ordering &ordering = Eigen::MetisOrdering<typename SMatrixSolverType::StorageIndex>())#

inline bool IsInitialized() const#

void ComputeSymbolicSparsity(const MatrixType &A, int C_dim)#

void Factorize(const MatrixType &A)#

template<typename RhsType> Eigen::Matrix<Scalar, Eigen::Dynamic, Eigen::Dynamic> Solve(const Eigen::MatrixBase<RhsType> &rhs) const#

void SInvInPlace(Eigen::Matrix<Scalar, Eigen::Dynamic, Eigen::Dynamic> &x_and_rhs) const#

Private Members

bool is_initialized_#

SparsityInformation sparsity_information_#

FactorizationData factorization_data_#

SMatrixSolverType S_solver_#

struct FactorizationData#

Public Members

Eigen::SparseMatrix<Scalar> C_inv_lower#

Eigen::SparseMatrix<Scalar> E_transpose#

Eigen::SparseMatrix<Scalar> S_lower#

struct SparsityInformation#

Public Members

int total_dim_#

int B_dim_#

int C_dim_#

std::vector<CBlock> C_blocks_#

struct CBlock#

Public Members

int start_idx#

int dim#

std::vector<int> col_starts_in_C_inv#