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.


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#