Block sparsity-aware LDLT factorization algorithm. More...

#include <proxsuite-nlp/linalg/block-ldlt.hpp>

Inheritance diagram for proxsuite::nlp::linalg::BlockLDLT< _Scalar >:

Collaboration diagram for proxsuite::nlp::linalg::BlockLDLT< _Scalar >:

Public Types
using	Scalar = _Scalar

using	Base = ldlt_base<Scalar>

using	DView = typename Base::DView

using	Traits = LDLT_Traits<MatrixXs, Eigen::Lower>

using	PermutationType

using	PermIdxType = Eigen::Matrix<isize, Eigen::Dynamic, 1>

using	BlockTriL = TriangularBlockMatrix<const MatrixXs, Eigen::UnitLower>

using	BlockTriU

Public Types inherited from proxsuite::nlp::linalg::ldlt_base< _Scalar >
using	DView

Public Member Functions
	BlockLDLT (isize size, SymbolicBlockMatrix const &structure)
	The constructor copies the input matrix.

	BlockLDLT (BlockLDLT const &other)

void	computeStartIndices (const SymbolicBlockMatrix &in)
	Compute indices indicating where blocks start.

const SymbolicBlockMatrix &	structure () const

void	print_sparsity () const

bool	analyzePattern ()
	Analyze and factorize the block structure, if not done already.

usize	nblocks () const

void	setBlockPermutation (isize const *new_perm=nullptr)
	Calls updateBlockPermutationMatrix.

auto	blockPermIndices () -> std::vector< isize > &

BlockLDLT &	findSparsifyingPermutation ()
	Find a sparsity-maximizing permutation of the blocks. This will also compute the symbolic factorization.

const PermutationType &	permutationP () const

MatrixXs	reconstructedMatrix () const override

Traits::MatrixL	matrixL () const

Traits::MatrixU	matrixU () const

DView	vectorD () const override

template<typename Derived>
bool	solveInPlace (Eigen::MatrixBase< Derived > &b) const
	Solve for the right-hand side in-place.

template<typename Rhs>
Rhs::PlainObject	solve (const Eigen::MatrixBase< Rhs > &rhs) const

const MatrixXs &	matrixLDLT () const override

void	compute ()

BlockLDLT &	compute (const ConstMatrixRef &mat) override

Public Member Functions inherited from proxsuite::nlp::linalg::ldlt_base< _Scalar >
bool	solveInPlace (MatrixRef) const

Eigen::ComputationInfo	info () const

SignMatrix	sign () const

Public Attributes
	Scalar

Public Attributes inherited from proxsuite::nlp::linalg::ldlt_base< _Scalar >
	Scalar

Protected Member Functions
BlockLDLT &	updateBlockPermutationMatrix (SymbolicBlockMatrix const &in)

Protected Attributes
MatrixXs	m_matrix

SymbolicBlockMatrix	m_structure

SymbolicBlockMatrix	m_struct_tr

PermutationType	m_permutation

std::vector< isize >	m_perm

std::vector< isize >	m_perm_inv

std::vector< isize >	m_iwork

std::vector< isize >	m_start_idx

Eigen::ComputationInfo	m_info

SignMatrix	m_sign

Protected Attributes inherited from proxsuite::nlp::linalg::ldlt_base< _Scalar >
Eigen::ComputationInfo	m_info

SignMatrix	m_sign

Additional Inherited Members
Static Public Member Functions inherited from proxsuite::nlp::linalg::ldlt_base< _Scalar >
static DView	diag_view_impl (Mat &&mat)

Detailed Description

template<typename _Scalar>
struct proxsuite::nlp::linalg::BlockLDLT< _Scalar >

Block sparsity-aware LDLT factorization algorithm.

This struct owns the data of the SymbolicBlockMatrix given as input. The member function findSparsifyingPermutation() uses a heuristic (for now a brute-force search) to find a sparsity-maximizing permutation of the blocks in the input matrix. updateBlockPermutationMatrix() updates the permutation matrix according to the stored block-wise permutation indices.

Warning: The underlying block-wise structure is assumed to be invariant over the lifetime of this object when calling compute(). A change of structure should lead to recalculating the expected sparsity pattern of the factorization, and even recomputing the sparsity-optimal permutation.

Definition at line 197 of file block-ldlt.hpp.

Member Typedef Documentation

◆ Scalar

template<typename _Scalar>

using proxsuite::nlp::linalg::BlockLDLT< _Scalar >::Scalar = _Scalar

Definition at line 198 of file block-ldlt.hpp.

◆ Base

template<typename _Scalar>

using proxsuite::nlp::linalg::BlockLDLT< _Scalar >::Base = ldlt_base<Scalar>

Definition at line 200 of file block-ldlt.hpp.

◆ DView

template<typename _Scalar>

using proxsuite::nlp::linalg::BlockLDLT< _Scalar >::DView = typename Base::DView

Definition at line 201 of file block-ldlt.hpp.

◆ Traits

template<typename _Scalar>

using proxsuite::nlp::linalg::BlockLDLT< _Scalar >::Traits = LDLT_Traits<MatrixXs, Eigen::Lower>

Definition at line 202 of file block-ldlt.hpp.

◆ PermutationType

template<typename _Scalar>

using proxsuite::nlp::linalg::BlockLDLT< _Scalar >::PermutationType

Initial value:

Eigen::PermutationMatrix<Eigen::Dynamic, Eigen::Dynamic, isize>

Definition at line 203 of file block-ldlt.hpp.

◆ PermIdxType

template<typename _Scalar>

using proxsuite::nlp::linalg::BlockLDLT< _Scalar >::PermIdxType = Eigen::Matrix<isize, Eigen::Dynamic, 1>

Definition at line 205 of file block-ldlt.hpp.

◆ BlockTriL

template<typename _Scalar>

using proxsuite::nlp::linalg::BlockLDLT< _Scalar >::BlockTriL = TriangularBlockMatrix<const MatrixXs, Eigen::UnitLower>

Definition at line 206 of file block-ldlt.hpp.

◆ BlockTriU

template<typename _Scalar>

using proxsuite::nlp::linalg::BlockLDLT< _Scalar >::BlockTriU

Initial value:

 
      TriangularBlockMatrix<const typename MatrixXs::AdjointReturnType,
                            Eigen::UnitUpper>

Definition at line 207 of file block-ldlt.hpp.

Constructor & Destructor Documentation

◆ BlockLDLT() [1/2]

template<typename _Scalar>

proxsuite::nlp::linalg::BlockLDLT< _Scalar >::BlockLDLT	(	isize	size,
		SymbolicBlockMatrix const &	structure )

inline

The constructor copies the input matrix.

Parameters

mat	and symbolic block pattern
structure.

Definition at line 228 of file block-ldlt.hpp.

◆ BlockLDLT() [2/2]

template<typename _Scalar>

proxsuite::nlp::linalg::BlockLDLT< _Scalar >::BlockLDLT ( BlockLDLT< _Scalar > const & other )

inline

Definition at line 237 of file block-ldlt.hpp.

◆ ~BlockLDLT()

template<typename _Scalar>

proxsuite::nlp::linalg::BlockLDLT< _Scalar >::~BlockLDLT ( )

inline

Definition at line 256 of file block-ldlt.hpp.

Member Function Documentation

◆ updateBlockPermutationMatrix()

template<typename Scalar>

BlockLDLT< Scalar > & proxsuite::nlp::linalg::BlockLDLT< Scalar >::updateBlockPermutationMatrix ( SymbolicBlockMatrix const & in )

protected

Definition at line 44 of file block-ldlt.hxx.

◆ computeStartIndices()

template<typename _Scalar>

void proxsuite::nlp::linalg::BlockLDLT< _Scalar >::computeStartIndices ( const SymbolicBlockMatrix & in )

inline

Compute indices indicating where blocks start.

Definition at line 249 of file block-ldlt.hpp.

◆ structure()

template<typename _Scalar>

const SymbolicBlockMatrix & proxsuite::nlp::linalg::BlockLDLT< _Scalar >::structure ( ) const

inline

Returns: a reference to the symbolic representation of the block-matrix.

Definition at line 266 of file block-ldlt.hpp.

◆ print_sparsity()

template<typename _Scalar>

void proxsuite::nlp::linalg::BlockLDLT< _Scalar >::print_sparsity ( ) const

inline

Definition at line 267 of file block-ldlt.hpp.

◆ analyzePattern()

template<typename Scalar>

bool proxsuite::nlp::linalg::BlockLDLT< Scalar >::analyzePattern ( )

inline

Analyze and factorize the block structure, if not done already.

Definition at line 35 of file block-ldlt.hxx.

◆ nblocks()

template<typename _Scalar>

usize proxsuite::nlp::linalg::BlockLDLT< _Scalar >::nblocks ( ) const

inline

Definition at line 272 of file block-ldlt.hpp.

◆ setBlockPermutation()

template<typename Scalar>

void proxsuite::nlp::linalg::BlockLDLT< Scalar >::setBlockPermutation ( isize const * new_perm = nullptr )

Calls updateBlockPermutationMatrix.

Definition at line 14 of file block-ldlt.hxx.

◆ blockPermIndices()

template<typename _Scalar>

auto proxsuite::nlp::linalg::BlockLDLT< _Scalar >::blockPermIndices ( ) -> std::vector<isize> &

inline

Definition at line 277 of file block-ldlt.hpp.

◆ findSparsifyingPermutation()

template<typename Scalar>

BlockLDLT< Scalar > & proxsuite::nlp::linalg::BlockLDLT< Scalar >::findSparsifyingPermutation ( )

Find a sparsity-maximizing permutation of the blocks. This will also compute the symbolic factorization.

Definition at line 26 of file block-ldlt.hxx.

◆ permutationP()

template<typename _Scalar>

const PermutationType & proxsuite::nlp::linalg::BlockLDLT< _Scalar >::permutationP ( ) const

inline

Definition at line 283 of file block-ldlt.hpp.

◆ reconstructedMatrix()

template<typename Scalar>

BlockLDLT< Scalar >::MatrixXs proxsuite::nlp::linalg::BlockLDLT< Scalar >::reconstructedMatrix ( ) const

overridevirtual

Implements proxsuite::nlp::linalg::ldlt_base< _Scalar >.

Definition at line 62 of file block-ldlt.hxx.

◆ matrixL()

template<typename _Scalar>

Traits::MatrixL proxsuite::nlp::linalg::BlockLDLT< _Scalar >::matrixL ( ) const

inline

Definition at line 287 of file block-ldlt.hpp.

◆ matrixU()

template<typename _Scalar>

Traits::MatrixU proxsuite::nlp::linalg::BlockLDLT< _Scalar >::matrixU ( ) const

inline

Definition at line 291 of file block-ldlt.hpp.

◆ vectorD()

template<typename _Scalar>

DView proxsuite::nlp::linalg::BlockLDLT< _Scalar >::vectorD ( ) const

inlineoverridevirtual

Implements proxsuite::nlp::linalg::ldlt_base< _Scalar >.

Definition at line 295 of file block-ldlt.hpp.

◆ solveInPlace()

template<typename Scalar>

template<typename Derived>

bool proxsuite::nlp::linalg::BlockLDLT< Scalar >::solveInPlace ( Eigen::MatrixBase< Derived > & b ) const

Solve for the right-hand side in-place.

TODO: fixcaching this variable somewhere w/ update to m_structure

Definition at line 74 of file block-ldlt.hxx.

◆ solve()

template<typename _Scalar>

template<typename Rhs>

Rhs::PlainObject proxsuite::nlp::linalg::BlockLDLT< _Scalar >::solve ( const Eigen::MatrixBase< Rhs > & rhs ) const

inline

Definition at line 304 of file block-ldlt.hpp.

◆ matrixLDLT()

template<typename _Scalar>

const MatrixXs & proxsuite::nlp::linalg::BlockLDLT< _Scalar >::matrixLDLT ( ) const

inlineoverridevirtual

Reimplemented from proxsuite::nlp::linalg::ldlt_base< _Scalar >.

Definition at line 310 of file block-ldlt.hpp.

◆ compute() [1/2]

template<typename _Scalar>

void proxsuite::nlp::linalg::BlockLDLT< _Scalar >::compute ( )

inline

Definition at line 312 of file block-ldlt.hpp.

◆ compute() [2/2]

template<typename _Scalar>

BlockLDLT & proxsuite::nlp::linalg::BlockLDLT< _Scalar >::compute ( const ConstMatrixRef & mat )

inlineoverridevirtual

Sets the input matrix to mat, performs the permutation and runs the algorithm.

Implements proxsuite::nlp::linalg::ldlt_base< _Scalar >.

Definition at line 322 of file block-ldlt.hpp.

Member Data Documentation

◆ Scalar

template<typename _Scalar>

proxsuite::nlp::linalg::BlockLDLT< _Scalar >::Scalar

Definition at line 199 of file block-ldlt.hpp.

◆ m_matrix

template<typename _Scalar>

MatrixXs proxsuite::nlp::linalg::BlockLDLT< _Scalar >::m_matrix

protected

Definition at line 212 of file block-ldlt.hpp.

◆ m_structure

template<typename _Scalar>

SymbolicBlockMatrix proxsuite::nlp::linalg::BlockLDLT< _Scalar >::m_structure

protected

Definition at line 213 of file block-ldlt.hpp.

◆ m_struct_tr

template<typename _Scalar>

SymbolicBlockMatrix proxsuite::nlp::linalg::BlockLDLT< _Scalar >::m_struct_tr

protected

Definition at line 214 of file block-ldlt.hpp.

◆ m_permutation

template<typename _Scalar>

PermutationType proxsuite::nlp::linalg::BlockLDLT< _Scalar >::m_permutation

protected

Definition at line 215 of file block-ldlt.hpp.

◆ m_perm

template<typename _Scalar>

std::vector<isize> proxsuite::nlp::linalg::BlockLDLT< _Scalar >::m_perm

protected

Definition at line 218 of file block-ldlt.hpp.

◆ m_perm_inv

template<typename _Scalar>

std::vector<isize> proxsuite::nlp::linalg::BlockLDLT< _Scalar >::m_perm_inv

protected

Definition at line 219 of file block-ldlt.hpp.

◆ m_iwork

template<typename _Scalar>

std::vector<isize> proxsuite::nlp::linalg::BlockLDLT< _Scalar >::m_iwork

protected

Definition at line 220 of file block-ldlt.hpp.

◆ m_start_idx

template<typename _Scalar>

std::vector<isize> proxsuite::nlp::linalg::BlockLDLT< _Scalar >::m_start_idx

protected

Definition at line 221 of file block-ldlt.hpp.

◆ m_info

template<typename _Scalar>

Eigen::ComputationInfo proxsuite::nlp::linalg::ldlt_base< Scalar >::m_info

protected

Definition at line 48 of file ldlt-base.hpp.

◆ m_sign

template<typename _Scalar>

SignMatrix proxsuite::nlp::linalg::ldlt_base< Scalar >::m_sign

protected

Definition at line 49 of file ldlt-base.hpp.

The documentation for this struct was generated from the following files:

include/proxsuite-nlp/linalg/block-ldlt.hpp
include/proxsuite-nlp/linalg/block-ldlt.hxx

Public Types

Public Member Functions

Public Attributes

Protected Member Functions

Protected Attributes

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ Scalar

◆ Base

◆ DView

◆ Traits

◆ PermutationType

◆ PermIdxType

◆ BlockTriL

◆ BlockTriU

Constructor & Destructor Documentation

◆ BlockLDLT() [1/2]

◆ BlockLDLT() [2/2]

◆ ~BlockLDLT()

Member Function Documentation

◆ updateBlockPermutationMatrix()

◆ computeStartIndices()

◆ structure()

◆ print_sparsity()

◆ analyzePattern()

◆ nblocks()

◆ setBlockPermutation()

◆ blockPermIndices()

◆ findSparsifyingPermutation()

◆ permutationP()

◆ reconstructedMatrix()

◆ matrixL()

◆ matrixU()

◆ vectorD()

◆ solveInPlace()

◆ solve()

◆ matrixLDLT()

◆ compute() [1/2]

◆ compute() [2/2]

Member Data Documentation

◆ Scalar

◆ m_matrix

◆ m_structure

◆ m_struct_tr

◆ m_permutation

◆ m_perm

◆ m_perm_inv

◆ m_iwork

◆ m_start_idx

◆ m_info

◆ m_sign