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 StorageFormat, encode the major direction of both sparse chains and sparse matrices.

CGAL::OSM::COLUMN for column-major chains and matrices (which is the default),
CGAL::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<IntegralDomainWithoutDivision, StorageFormat>

See also: IntegralDomainWithoutDivision; SparseChain

Types
typedef unspecified_type	Coefficient_ring
	Type of coefficients stored in the matrix (a model of `IntegralDomainWithoutDivision`).

typedef int	Storage_format
	Matrix and chain storage format (either `ROW` or `COLUMN`).

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

typedef unspecified_type	Matrix_chain
	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 `StorageFormat`).

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.

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

Non_zero_chain_indices::iterator	end () const noexcept
	Past-the-end iterator of the chain indices (visited by increasing indices).

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

Non_zero_chain_indices::iterator	reverse_end () const noexcept
	Past-the-end reverse iterator of the chain indices (visited by decreasing indices).

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

SparseMatrix &	operator*= (const Coefficient_ring &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)
	Subtracts two matrices together.

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

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

SparseMatrix	operator* (const SparseMatrix &matrix, const Coefficient_ring &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.

SparseChain	operator* (const SparseMatrix &matrix, const SparseChain &column)
	Performs multiplication between a matrix and a column-based chain.

SparseChain	operator* (const SparseChain &row, const SparseMatrix &matrix)
	Performs multiplication between a row-based chain and a matrix.

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

const SparseChain &	cget_column (const SparseMatrix &matrix, size_t i)
	Gets a constant reference over the column of index`i` from a column matrix.

const SparseChain &	cget_row (const SparseMatrix &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 SparseChain &column)
	Sets a column in the matrix (whatever the `StorageFormat` of the matrix).

void	set_row (SparseMatrix &matrix, size_t i, const Sparse_chain &row)
	Sets a row in `matrix` (whatever the `StorageFormat` of the matrix).

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

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

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

Coefficient_ring	get_coefficient (const SparseMatrix &matrix, size_t i, size_t j)
	Gets a given coefficient.

SparseChain	get_column (const SparseMatrix &matrix, size_t index)
	Gets the value of the column at a given `index` from the matrix (whatever the `StorageFormat` of the matrix).

SparseChain	get_row (const SparseMatrix &matrix, size_t index)
	Gets the value of the row at a given `index` from the matrix (whatever the `StorageFormat` of the matrix).

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

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

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

SparseMatrix &	remove_coefficient (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 StorageFormat with coefficients of type Coefficient_ring. 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 StorageFormat with coefficients of type Coefficient_ring 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 StorageFormat).

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

Member Function Documentation

◆ begin()

Non_zero_chain_indices::iterator SparseMatrix::begin ( ) const

noexcept

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

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

◆ cget_column()

const SparseChain & SparseMatrix::cget_column	(	const SparseMatrix &	matrix,
		size_t	i
	)

Gets a constant reference over the column of indexi from a column matrix.

Precondition: matrix.is_column() must be true.

Returns: a constant reference to a column chain.

◆ cget_row()

const SparseChain & SparseMatrix::cget_row	(	const SparseMatrix &	matrix,
		size_t	i
	)

Gets a constant reference over the row of indexi from a row matrix.

Precondition: matrix.is_row() must be true.

Returns: a constant reference to a row chain.

◆ dimensions()

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

Gets the matrix size.

The matrix size as a row/column pair.

◆ end()

Non_zero_chain_indices::iterator SparseMatrix::end ( ) const

noexcept

Past-the-end iterator of the chain indices (visited by increasing indices).

The function returns an iterator past the end of the chain 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 Coefficient_ring & 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
	)

Subtracts a matrix and assign.

Subtracts each coefficient of the matrix together and stores the result in matrix. Matrices must have the same Coefficient_ring but can have different StorageFormat.

◆ operator/=() [1/2]

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

Gets a submatrix from the matrix and assign.

Removes (along the major dimension) all indices provided in the vector indices 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[]()

Matrix_chain 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()

Non_zero_chain_indices::iterator SparseMatrix::reverse_begin ( ) const

noexcept

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

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

◆ reverse_end()

Non_zero_chain_indices::iterator SparseMatrix::reverse_end ( ) const

noexcept

Past-the-end reverse iterator of the chain indices (visited by decreasing indices).

The function returns a past-the-end reverse iterator of the chain indices.

◆ set_column()

void SparseMatrix::set_column	(	SparseMatrix &	matrix,
		size_t	i,
		const SparseChain &	column
	)

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

Set the ith column of matrix to column. 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)\)).

Precondition: column.is_column() must be true

◆ set_row()

void SparseMatrix::set_row	(	SparseMatrix &	matrix,
		size_t	i,
		const Sparse_chain &	row
	)

Sets a row in matrix (whatever the StorageFormat 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)\)).

Precondition: row.is_row() must be true

◆ transpose()

SparseMatrix SparseMatrix::transpose ( )

Transposes a matrix.

The function returns a new matrix where the StorageFormat is changed.

Friends And Related Function Documentation

◆ get_coefficient

Coefficient_ring get_coefficient	(	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

SparseChain get_column	(	const SparseMatrix &	matrix,
		size_t	index
	)

friend

Gets the value of the column at a given index from the matrix (whatever the StorageFormat 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)\)).

Returns: a column chain.

◆ get_row

SparseChain get_row	(	const SparseMatrix &	matrix,
		size_t	index
	)

friend

Gets the value of the row at a given index from the matrix (whatever the StorageFormat 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)\)).

Returns: a row chain.

◆ 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 Coefficient_ring but can have different StorageFormat. Efficiency of the product depends of StorageFormat.

◆ operator* [1/5]

SparseMatrix operator*	(	const Coefficient_ring &	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]

SparseChain operator*	(	const SparseChain &	row,
		const SparseMatrix &	matrix
	)

friend

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

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

Precondition: the matrix and the chain must have the same Coefficient_ring.; row.is_row() must be true

◆ operator* [3/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 Coefficient_ring but can have different StorageFormat. Efficiency of the product depends of StorageFormat (when possible, prefer row-major by column-major products).

◆ operator* [4/5]

SparseMatrix operator*	(	const SparseMatrix &	matrix,
		const Coefficient_ring &	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* [5/5]

SparseChain operator*	(	const SparseMatrix &	matrix,
		const SparseChain &	column
	)

friend

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

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

Precondition: the matrix and the chain must have the same Coefficient_ring.; column.is_column() must be true

◆ 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 Coefficient_ring but can have different StorageFormat.

◆ 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 Coefficient_ring but can have different StorageFormat.

◆ 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 Coefficient_ring but can have different StorageFormat.

◆ operator- [1/2]

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

friend

Subtracts two matrices together.

Subtracts 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 Coefficient_ring but can have different StorageFormat.

◆ 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.

◆ remove_coefficient

SparseMatrix & remove_coefficient	(	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.

◆ remove_column

SparseMatrix & remove_column	(	SparseMatrix &	matrix,
		size_t	index
	)

friend

Nullifies a column from the matrix.

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

◆ remove_row

SparseMatrix & remove_row	(	SparseMatrix &	matrix,
		size_t	index
	)

friend

Nullifies a row from the matrix.

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

◆ set_coefficient

void set_coefficient	(	SparseMatrix &	matrix,
		size_t	i,
		size_t	j,
		const Coefficient_ring	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()

◆ cget_column()

◆ cget_row()

◆ 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

◆ get_coefficient

◆ 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/

◆ remove_coefficient

◆ remove_column

◆ remove_row

◆ set_coefficient