CGAL 6.3-dev - Homological Discrete Vector Fields
Loading...
Searching...
No Matches
CGAL::OSM::Full_lu< CoefficientRing, StorageFormat, SparseMatrixStructure > Class Template Reference

#include <CGAL/OSM/Full_lu.h>

Definition

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

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
CoefficientRinga model of the IntegralDomainWithoutDivision concept.
SparseMatrixStructurea model of the SparseMatrixStrctureconcept, type of the sparse matrix considered for LU decomposition.

Public Types

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

Public Member Functions

 Full_lu (const typename SparseMatrixStructure::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.

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 SparseMatrixStructure>
CGAL::OSM::Full_lu< CoefficientRing, StorageFormat, SparseMatrixStructure >::Full_lu ( const typename SparseMatrixStructure::template Sparse_matrix_type< CoefficientRing, StorageFormat > & A)

Constructor from a sparse matrix.

Parameters
Asparse matrix to decompose.
Exceptions
Invalid_matrixIf the matrix `A`is not square, raises a `std::invalid_argument`.

Member Function Documentation

◆ compute()

template<typename CoefficientRing, int StorageFormat, typename SparseMatrixStructure>
size_t CGAL::OSM::Full_lu< CoefficientRing, StorageFormat, SparseMatrixStructure >::compute ( )

Performs a full LU decomposition over an IntegralDomainWithoutDivision coefficient ring.

Returns
The rank of the matrix.

◆ inverse()

template<typename CoefficientRing, int StorageFormat, typename SparseMatrixStructure>
Sparse_matrix_arg CGAL::OSM::Full_lu< CoefficientRing, StorageFormat, SparseMatrixStructure >::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 SparseMatrixStructure>
bool CGAL::OSM::Full_lu< CoefficientRing, StorageFormat, SparseMatrixStructure >::is_invertible ( )

Tests is the matrix is invertible (ie.

full rank and determinant invertible).

◆ solve()

template<typename CoefficientRing, int StorageFormat, typename SparseMatrixStructure>
Sparse_matrix_arg CGAL::OSM::Full_lu< CoefficientRing, StorageFormat, SparseMatrixStructure >::solve ( const Sparse_matrix_arg & B)

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

Parameters
BRight-hand side matrix of the system.