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¶