Definition

The concept SparseMatrix describes the requirements for sparse matrices optimized for topological computations. Traditionally, sparse matrices data structures encode non zero coefficients of (sparse) matrices in order to optimize either matrices memory footprint, or linear algebra operations (which usually comes to optimize iterators over non zero coefficients and access to coefficients). However, topological operations require slightly different features:

- fast access to row or columns of matrices (which are actually the images under the application encoded by the matrix)

fast block operations (especially along row or columns)

The SparseMatrix concept describes requirements for such sparse matrix. It relies on the model of SparseChain which encodes sparse row or column vectors. Matrices are either column major or row major (hence they either store column sparse chains or row sparse chains).

The following constants, called ChainTypeFlag, encode the major direction of both sparse chains and sparse matrices.

OSM::COLUMN for column-major chains and matrices (which is the default),
OSM::ROW for row-major chains and matrices.

For instance, given the \(5\times 4\) matrix:

\[ A = \left(\begin{array}{cccc} 1 & \cdot & \cdot & \cdot \\ -1 & \cdot & 2 & \cdot\\ \cdot & \cdot & 1 & \cdot \\ \cdot & \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot & \cdot \\ \end{array}\right) \]

where \(\cdot\) means \(0\).

A column-major representation of \(A\) is: \([0\mapsto c_0, 2\mapsto c_2]\) with the column-chains: \(c_0 = [0\mapsto 1, 1\mapsto -1]\) and \(c_2 = [1\mapsto 2, 2\mapsto 1]\).
A row-major representation of \(A\) is: \([0\mapsto c_0, 1\mapsto c_1, 2\mapsto c_2]\) with the row-chains: \(c_0 = [0\mapsto 1]\) and \(c_1 = [0\mapsto -1, 2\mapsto 2]\) and \(c_2 = [2\mapsto 1]\).

Has models
: CGAL::OSM::Sparse_matrix<Ring, ChainTypeFlag>

See also: Ring; SparseChain

Types
typedef Ring	CoefficientType
	Type of coefficients stored in the matrix (a model of `Ring`).

typedef int	ChainTypeFlag
	Matrix and chain type (either `OSM::ROW` or `OSM::COLUMN`).

typedef unspecified_type	NonZeroChainIndices
	A data structure storing indices of non empty chains.

typedef unspecified_type	MatrixChain
	Type of the chains stored in the matrix.

Creation, filling
	SparseMatrix ()
	Creates an empty new sparse matrix object.

	SparseMatrix (const size_t rowCount, const size_t columnCount)
	Creates a new sparse matrix object with given rows/columns sizes.

	SparseMatrix (const SparseMatrix &otherToCopy)
	Creates a new sparse matrix from another sparse matrix object (with possibly a different `ChainTypeFlag`).

SparseMatrix &	operator= (const SparseMatrix &_otherToCopy)
	Assigns to other matrix.

void	nullify ()
	Cleans a sparse matrix (set all coefficients to zero).

Matrix informations and iterators
bool	is_null ()
	Tests if a sparse matrix is null.

std::pair< size_t, size_t >	dimensions () const
	Gets the matrix size.

NonZeroChainIndices::iterator	begin () const noexcept
	Iterator to the beginning of the chains indices (visited by increasing indices).

NonZeroChainIndices::iterator	end () const noexcept
	Iterator to the ending of the chains indices (visited by increasing indices).

NonZeroChainIndices::iterator	reverse_begin () const noexcept
	Reverse iterator to the beginning of the chains indices (visited by decreasing indices).

NonZeroChainIndices::iterator	reverse_end () const noexcept
	Reverse iterator to the ending of the chains indices (visited by decreasing indices).

Linear algebra operators
SparseMatrix &	operator-= (SparseMatrix &matrix, const SparseMatrix &other)
	Substracts a matrix and assign.

SparseMatrix &	operator*= (const CoefficientType &lambda)
	Applies factor on each coefficient and assign.

SparseMatrix	transpose ()
	Transposes a matrix.

SparseMatrix &	operator+= (SparseMatrix &matrix, const SparseMatrix &other)
	Adds a matrix and assign.

SparseMatrix	operator+ (const SparseMatrix &first, const SparseMatrix &second)
	Adds two matrices together.

SparseMatrix	operator- (const SparseMatrix &first, const SparseMatrix &second)
	Substracts two matrices together.

SparseMatrix	operator- (const SparseMatrix &matrix)
	Computes the negative of a matrix (unary operator).

SparseMatrix	operator* (const CoefficientType &lambda, const SparseMatrix &matrix)
	Applies factor on each coefficients into a new matrix.

SparseMatrix	operator* (const SparseMatrix &matrix, const CoefficientType &lambda)
	Applies factor on each coefficients into a new matrix.

SparseMatrix &	operator*= (SparseMatrix &matrix, const SparseMatrix &other)
	Multiplies a matrix and assign.

SparseMatrix	operator* (const SparseMatrix &first, const SparseMatrix &second)
	Performs multiplication between matrices and returns a new column-major matrix.

SparseMatrix	operator% (const SparseMatrix &first, const SparseMatrix &second)
	Performs multiplication between matrices and returns a new row-major matrix.

Sparse_chain< CoefficientType, COLUMN >	operator* (const SparseMatrix &first, const Sparse_chain< CoefficientType, COLUMN > &second)
	Performs multiplication between a matrix and a column-based chain.

Sparse_chain< CoefficientType, ROW >	operator* (const Sparse_chain< CoefficientType, ROW > &first, const SparseMatrix &second)
	Performs multiplication between a row-based chain and a matrix.

Access and blocks operations
MatrixChain	operator[] (size_t index) const
	Gets a chain from a const matrix.

const Sparse_chain< CoefficientType, COLUMN > &	cget_column (const SparseMatrix< CoefficientType, COLUMN > &matrix, size_t i)
	Gets a constant reference over the column of index`i` from a column matrix.

const Sparse_chain< CoefficientType, ROW > &	cget_row (const SparseMatrix< CoefficientType, ROW > &matrix, size_t i)
	Gets a constant reference over the row of index`i` from a row matrix.

void	set_column (SparseMatrix &matrix, size_t i, const Sparse_chain< CoefficientType, COLUMN > &chain)
	Sets a column in the matrix (whatever the `ChainTypeFlag` of the matrix).

void	set_row (SparseMatrix &matrix, size_t i, const Sparse_chain< CoefficientType, ROW > &chain)
	Sets a row in `matrix` (whatever the `ChainTypeFlag` of the matrix).

SparseMatrix &	operator/= (const std::vector< size_t > &indexes)
	Gets a submatrix from the matrix and assign.

SparseMatrix &	operator/= (size_t i)
	Gets a submatrix from the matrix and assign.

void	set_coef (SparseMatrix &matrix, size_t i, size_t j, const CoefficientType d)
	Sets a given coefficient.

CoefficientType	get_coef (const SparseMatrix &matrix, size_t i, size_t j)
	Gets a given coefficient.

Sparse_chain< CoefficientType, COLUMN >	get_column (const SparseMatrix &matrix, size_t index)
	Gets the value of the column at a given `index` from the matrix (whatever the `ChainTypeFlag` of the matrix).

Sparse_chain< CoefficientType, ROW >	get_row (const SparseMatrix &matrix, size_t index)
	Gets the value of the row at a given `index` from the matrix (whatever the `ChainTypeFlag` of the matrix).

SparseMatrix	operator/ (const SparseMatrix &matrix, size_t i)
	Gets a submatrix from the matrix.

SparseMatrix &	del_column (SparseMatrix &matrix, size_t index)
	Nullifies a column from the matrix.

SparseMatrix &	del_row (SparseMatrix &matrix, size_t index)
	Nullifies a row from the matrix.

SparseMatrix &	del_coef (SparseMatrix &matrix, size_t i, size_t j)
	Nullifies a coefficient of the matrix.

Output
std::ostream &	operator<< (std::ostream &_stream, const SparseMatrix &matrix)
	Inserts `matrix` in the output stream.

std::ostream &	write_matrix (const SparseMatrix &matrix, std::ostream &out)
	Inserts `matrix` in an output stream.

template<typename _CT >
std::istream &	read_matrix (SparseMatrix &matrix, std::istream &in)
	Extracts a sparse matrix from an input stream.

Constructor & Destructor Documentation

◆ SparseMatrix() [1/3]

SparseMatrix::SparseMatrix ( )

Creates an empty new sparse matrix object.

Default constructor, initialize an empty matrix of type ChainTypeFlag with coefficients of type CoefficientType. The default matrix size is 0x0.

◆ SparseMatrix() [2/3]

SparseMatrix::SparseMatrix	(	const size_t	rowCount,
		const size_t	columnCount
	)

Creates a new sparse matrix object with given rows/columns sizes.

Constructor with sizes, initialize an empty matrix of type ChainTypeFlag with coefficients of type CoefficientType and a given size along rows/columns.

◆ SparseMatrix() [3/3]

SparseMatrix::SparseMatrix ( const SparseMatrix & otherToCopy )

Creates a new sparse matrix from another sparse matrix object (with possibly a different ChainTypeFlag).

Copy constructor, initialize a sparse matrix of same sizes, containing the same coefficients (but not necessarly of the same ChainTypeFlag). If types are different, the constructor performs conversion.

Member Function Documentation

◆ begin()

NonZeroChainIndices::iterator SparseMatrix::begin ( ) const

noexcept

Iterator to the beginning of the chains indices (visited by increasing indices).

The function returns an iterator to the beginning of the (non zero) chains indices.

◆ dimensions()

std::pair< size_t, size_t > SparseMatrix::dimensions ( ) const

Gets the matrix size.

The matrix size as a row/column pair.

◆ end()

NonZeroChainIndices::iterator SparseMatrix::end ( ) const

noexcept

Iterator to the ending of the chains indices (visited by increasing indices).

The function returns an iterator to the ending of the chains indices.

◆ is_null()

bool SparseMatrix::is_null ( )

Tests if a sparse matrix is null.

The function returns true if the sparse matrix is null (that is, empty) and false otherwise.

◆ nullify()

void SparseMatrix::nullify ( )

Cleans a sparse matrix (set all coefficients to zero).

Empty all structures of the sparse matrix.

◆ operator*=()

SparseMatrix & SparseMatrix::operator*= ( const CoefficientType & lambda )

Applies factor on each coefficient and assign.

This method multiplies the matrix by a scalar factor lambda.

◆ operator-=()

SparseMatrix & SparseMatrix::operator-=	(	SparseMatrix &	matrix,
		const SparseMatrix &	other
	)

Substracts a matrix and assign.

Substracts each coefficient of the matrix together and stores the result in matrix. Matrices must have the same CoefficientType but can have different ChainTypeFlag.

◆ operator/=() [1/2]

SparseMatrix & SparseMatrix::operator/= ( const std::vector< size_t > & indexes )

Gets a submatrix from the matrix and assign.

Removes (along the major dimension) all indexes provided in the vector indexes from the matrix and returns it.

◆ operator/=() [2/2]

SparseMatrix & SparseMatrix::operator/= ( size_t i )

Gets a submatrix from the matrix and assign.

Removes (along the major dimension) the chain of index i from the matrix and returns it.

◆ operator=()

SparseMatrix & SparseMatrix::operator= ( const SparseMatrix & _otherToCopy )

Assigns to other matrix.

Assign to other matrix coefficient-wise, equivalent to copying it.

Matrices must have the same type.

◆ operator[]()

MatrixChain SparseMatrix::operator[] ( size_t index ) const

Gets a chain from a const matrix.

If the matrix is column-major, returns the ith column, and if the matrix is row-major, returns the ith row.

◆ reverse_begin()

NonZeroChainIndices::iterator SparseMatrix::reverse_begin ( ) const

noexcept

Reverse iterator to the beginning of the chains indices (visited by decreasing indices).

The function returns a reverse iterator to the beginning of the (non zero) chains indices.

◆ reverse_end()

NonZeroChainIndices::iterator SparseMatrix::reverse_end ( ) const

noexcept

Reverse iterator to the ending of the chains indices (visited by decreasing indices).

The function returns a reverse iterator to the ending of the chains indices.

◆ set_column()

void SparseMatrix::set_column	(	SparseMatrix &	matrix,
		size_t	i,
		const Sparse_chain< CoefficientType, COLUMN > &	chain
	)

Sets a column in the matrix (whatever the ChainTypeFlag of the matrix).

Set the ith column of matrix to chain. For column-matrices, it should be equivalent to an assignment, however, for row-matrices, a traversal of the matrix is required (in \(\mathcal O(n)\)).

◆ set_row()

void SparseMatrix::set_row	(	SparseMatrix &	matrix,
		size_t	i,
		const Sparse_chain< CoefficientType, ROW > &	chain
	)

Sets a row in matrix (whatever the ChainTypeFlag of the matrix).

Set the ith row of matrix to chain. For row-matrices, it should be equivalent to an assignment, however, for column-matrices, a traversal of the matrix is required (in \(\mathcal O(n)\)).

◆ transpose()

SparseMatrix SparseMatrix::transpose ( )

Transposes a matrix.

The function returns a new matrix where the chain type flag is changed.

Friends And Related Function Documentation

◆ del_coef

SparseMatrix & del_coef	(	SparseMatrix &	matrix,
		size_t	i,
		size_t	j
	)

friend

Nullifies a coefficient of the matrix.

Removes coefficient on row i / column j of the matrix.

◆ del_column

SparseMatrix & del_column	(	SparseMatrix &	matrix,
		size_t	index
	)

friend

Nullifies a column from the matrix.

Removes column of index i whatever the ChainTypeFlag of the matrix. For column matrices, it just comes to the \= operator and for row matrices, it entails a traversal of the matrix.

◆ del_row

SparseMatrix & del_row	(	SparseMatrix &	matrix,
		size_t	index
	)

friend

Nullifies a row from the matrix.

Removes row of index i whatever the ChainTypeFlag of the matrix. For row matrices, it just comes to the \= operator and for column matrices, it entails a traversal of the matrix.

◆ get_coef

CoefficientType get_coef	(	const SparseMatrix &	matrix,
		size_t	i,
		size_t	j
	)

friend

Gets a given coefficient.

Returns the coefficient on row i and column j of the matrix.

◆ get_column

Sparse_chain< CoefficientType, COLUMN > get_column	(	const SparseMatrix &	matrix,
		size_t	index
	)

friend

Gets the value of the column at a given index from the matrix (whatever the ChainTypeFlag of the matrix).

For column-matrices, it is equivalent to operator[], for row-matrices a traversal of the matrix is required (in \(\mathcal O(n)\)).

◆ get_row

Sparse_chain< CoefficientType, ROW > get_row	(	const SparseMatrix &	matrix,
		size_t	index
	)

friend

Gets the value of the row at a given index from the matrix (whatever the ChainTypeFlag of the matrix).

For row-matrices, it is equivalent to operator[], for column-matrices a traversal of the matrix is required (in \(\mathcal O(n)\)).

◆ operator%

SparseMatrix operator%	(	const SparseMatrix &	first,
		const SparseMatrix &	second
	)

friend

Performs multiplication between matrices and returns a new row-major matrix.

Perform standard linear algebra product between matrices and returns a new row-major matrix (when possible, prefer *= for efficiency). Matrices must have the same CoefficientType but can have different ChainTypeFlag. Efficiency of the product depends of ChainTypeFlag.

◆ operator* [1/5]

SparseMatrix operator*	(	const CoefficientType &	lambda,
		const SparseMatrix &	matrix
	)

friend

Applies factor on each coefficients into a new matrix.

This method creates a new matrix obtained by multiplying the matrix by a scalar factor lambda. If lambda is zero, the function comes to nullify the matrix (when possible, prefer *= for efficiency).

◆ operator* [2/5]

Sparse_chain< CoefficientType, ROW > operator*	(	const Sparse_chain< CoefficientType, ROW > &	first,
		const SparseMatrix &	second
	)

friend

Performs multiplication between a row-based chain and a matrix.

Generates a row-based chain from the matrix multiplication and returns it.

The matrix and the chain must have the same coefficient type.

◆ operator* [3/5]

Sparse_chain< CoefficientType, COLUMN > operator*	(	const SparseMatrix &	first,
		const Sparse_chain< CoefficientType, COLUMN > &	second
	)

friend

Performs multiplication between a matrix and a column-based chain.

Generates a column-based chain from the matrix multiplication and returns it.

The matrix and the chain must have the same coefficient type.

◆ operator* [4/5]

SparseMatrix operator*	(	const SparseMatrix &	first,
		const SparseMatrix &	second
	)

friend

Performs multiplication between matrices and returns a new column-major matrix.

Perform standard linear algebra product between matrices and returns a new column-major matrix (when possible, prefer *= for efficiency). Matrices must have the same CoefficientType but can have different ChainTypeFlag. Efficiency of the product depends of ChainTypeFlag (when possible, prefer row-major by column-major products).

◆ operator* [5/5]

SparseMatrix operator*	(	const SparseMatrix &	matrix,
		const CoefficientType &	lambda
	)

friend

Applies factor on each coefficients into a new matrix.

This method creates a new matrix obtained by multiplying the matrix by a scalar factor lambda. If lambda is zero, the function comes to nullify the matrix (when possible, prefer *= for efficiency).

◆ operator*=

SparseMatrix & operator*=	(	SparseMatrix &	matrix,
		const SparseMatrix &	other
	)

friend

Multiplies a matrix and assign.

Multiply each coefficient of the matrix together and stores the result in matrix. Matrices must have the same CoefficientType but can have different ChainTypeFlag.

◆ operator+

SparseMatrix operator+	(	const SparseMatrix &	first,
		const SparseMatrix &	second
	)

friend

Adds two matrices together.

Adds each coefficient of the matrices together and returns a new matrix (of the same type as first) representing the result (when possible, prefer += for efficiency). Matrices must have the same CoefficientType but can have different ChainTypeFlag.

◆ operator+=

SparseMatrix & operator+=	(	SparseMatrix &	matrix,
		const SparseMatrix &	other
	)

friend

Adds a matrix and assign.

Adds each coefficient of the matrix together and stores the result in this. Matrices must have the same CoefficientType but can have different ChainTypeFlag.

◆ operator- [1/2]

SparseMatrix operator-	(	const SparseMatrix &	first,
		const SparseMatrix &	second
	)

friend

Substracts two matrices together.

Substracts each coefficient of the matrix together and returns a new matrix (of the same type as first) representing the result (when possible, prefer -= for efficiency). Matrices must have the same CoefficientType but can have different ChainTypeFlag.

◆ operator- [2/2]

SparseMatrix operator- ( const SparseMatrix & matrix )

friend

Computes the negative of a matrix (unary operator).

Returns: The resulting matrix.

◆ operator/

SparseMatrix operator/	(	const SparseMatrix &	matrix,
		size_t	i
	)

friend

Gets a submatrix from the matrix.

Nullifies the chain of index i along the major direction of a copy of the matrix amd returns it.

◆ set_coef

void set_coef	(	SparseMatrix &	matrix,
		size_t	i,
		size_t	j,
		const CoefficientType	d
	)

friend

Sets a given coefficient.

Assign the scalar d to the coefficient on row i and column j.

Definition

Types

Creation, filling

Matrix informations and iterators

Linear algebra operators

Access and blocks operations

Output

Constructor & Destructor Documentation

◆ SparseMatrix() [1/3]

◆ SparseMatrix() [2/3]

◆ SparseMatrix() [3/3]

Member Function Documentation

◆ begin()

◆ dimensions()

◆ end()

◆ is_null()

◆ nullify()

◆ operator*=()

◆ operator-=()

◆ operator/=() [1/2]

◆ operator/=() [2/2]

◆ operator=()

◆ operator[]()

◆ reverse_begin()

◆ reverse_end()

◆ set_column()

◆ set_row()

◆ transpose()

Friends And Related Function Documentation

◆ del_coef

◆ del_column

◆ del_row

◆ get_coef

◆ get_column

◆ get_row

◆ operator%

◆ operator* [1/5]

◆ operator* [2/5]

◆ operator* [3/5]

◆ operator* [4/5]

◆ operator* [5/5]

◆ operator*=

◆ operator+

◆ operator+=

◆ operator- [1/2]

◆ operator- [2/2]

◆ operator/

◆ set_coef