CGAL::OSM::Full_lu< CoefficientRing, StorageFormat, SparseMatrix > Class Template Reference

#include <CGAL/OSM/Full_lu.h>

Definition

template<typename CoefficientRing, int StorageFormat, typename SparseMatrix>
class CGAL::OSM::Full_lu< CoefficientRing, StorageFormat, SparseMatrix >

The class Full_lu implements LU decomposition via full pivoting for an OSM::Sparse_matrix.

This decomposition is performed with coefficients in an IntegralDomainWithoutDivision. Hence, at each step, the algorithm identifies an invertible pivot. The algorithm factors a matrix \(A\) as:

\[PAQ = L\cdot U\]

where \(P\) and \(Q\) are permutation matrices (for rows and columns respectively), \(L\) is a lower matrix and \(U\) a upper matrix.

In order to take advantage of the sparse structure of matrices, internal computations are carried out over ROW matrices. Hence, given a COLUMN matrix \(A\), the algorithm actually factors \(A^t\) and performs further computations (inverse(), solve() ...) based on the decomposition of \(A^t\). As a consequence, in order to optimise searches, pivots are visited row-wise (which is unusual).

Template Parameters

SparseMatrix

Type of the argument Sparse_matrix.

Public Types
typedef CoefficientRing	Coefficient_ring
	Type of underlying coefficient ring.
typedef SparseMatrix::template Sparse_matrix_type< Coefficient_ring, StorageFormat >	Sparse_matrix_arg
	Type of input matrix.

Public Member Functions
	Full_lu (const typename SparseMatrix::template Sparse_matrix_type< CoefficientRing, StorageFormat > &A)
	Constructor from a sparse matrix.
size_t	compute ()
	Performs a full LU decomposition over an IntegralDomainWithoutDivision coefficient ring.
Sparse_matrix_arg	solve (const Sparse_matrix_arg &B)
	Solves the linear system \(AX=B\) where \(A\) is the underlying matrix of the Full_lu object.
Coefficient_ring	determinant ()
	Computes the determinant of the matrix.
bool	is_invertible ()
	Tests is the matrix is invertible (ie.
Sparse_matrix_arg	inverse ()
	Computes the inverse of the matrix.
std::conditional_t< _storage_format==ROW, const Sparse_matrix_arg &, Sparse_matrix_arg >	matrix_L ()
	Returns L.
std::conditional_t< _storage_format==ROW, const Sparse_matrix_arg &, Sparse_matrix_arg >	matrix_U ()
	Returns U.
std::conditional_t< _storage_format==ROW, const Sparse_matrix_arg &, Sparse_matrix_arg >	matrix_P ()
	Returns P.
std::conditional_t< _storage_format==ROW, const Sparse_matrix_arg &, Sparse_matrix_arg >	matrix_Q ()
	Returns Q.

Protected Types
using	Row_matrix = typename SparseMatrix::template Sparse_matrix_type< Coefficient_ring, OSM::ROW >
using	Row_chain = typename SparseMatrix::template Sparse_chain_type< Coefficient_ring, ROW >

Protected Member Functions
Sparse_matrix_arg	backward_substitution_U (const Row_matrix &U, const Sparse_matrix_arg &B)
Sparse_matrix_arg	forward_substitution_L (const Row_matrix &L, const Sparse_matrix_arg &B)

Protected Attributes
Row_matrix	_P
Row_matrix	_Q
Row_matrix	_L
Row_matrix	_U
size_t	_n
size_t	_rank
bool	_computed

Static Protected Attributes
static constexpr int	_storage_format = StorageFormat

Friends
template<typename CR , int SF, typename SM >
std::ostream &	operator<< (std::ostream &out, const Full_lu< CR, SF, SM > &lu)
	Output L, U, P, Q matrices to a stream.

Constructor & Destructor Documentation

Full_lu()

template<typename CoefficientRing , int StorageFormat, typename SparseMatrix >

CGAL::OSM::Full_lu< CoefficientRing, StorageFormat, SparseMatrix >::Full_lu

(

const typename SparseMatrix::template Sparse_matrix_type< CoefficientRing, StorageFormat > &

A

)

Constructor from a sparse matrix.

Parameters

A	sparse matrix to decompose.

Exceptions

Invalid_matrix

If the matrix `A`is not square, raises a `std::invalid_argument`.

Member Function Documentation

compute()

template<typename CoefficientRing , int StorageFormat, typename SparseMatrix >

size_t CGAL::OSM::Full_lu< CoefficientRing, StorageFormat, SparseMatrix >::compute

Performs a full LU decomposition over an IntegralDomainWithoutDivision coefficient ring.

Returns

The rank of the matrix.

inverse()

template<typename CoefficientRing , int StorageFormat, typename SparseMatrix >

Sparse_matrix_arg CGAL::OSM::Full_lu< CoefficientRing, StorageFormat, SparseMatrix >::inverse

(

)

Computes the inverse of the matrix.

Warning

For solving linear systems \(AX=B\), please use Full_lu<Matrix_type>(A).solve(B) (which is more efficient than computing \(A^{-1}\times B\)).

is_invertible()

template<typename CoefficientRing , int StorageFormat, typename SparseMatrix >

bool CGAL::OSM::Full_lu< CoefficientRing, StorageFormat, SparseMatrix >::is_invertible

(

)

Tests is the matrix is invertible (ie.

full rank and determinant invertible).

solve()

template<typename CoefficientRing , int StorageFormat, typename SparseMatrix >

Sparse_matrix_arg CGAL::OSM::Full_lu< CoefficientRing, StorageFormat, SparseMatrix >::solve

(

const Sparse_matrix_arg &

B

)

Solves the linear system \(AX=B\) where \(A\) is the underlying matrix of the Full_lu object.

Parameters

B	Right-hand side matrix of the system.