|
CGAL 6.3-dev - Homological Discrete Vector Fields
|
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:
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 integer constants, called Storage_format, encode the major direction of both sparse chains and sparse 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\).
Types | |
| typedef unspecified_type | Coefficient_ring |
| Type of coefficients stored in the matrix (a model of IntegralDomainWithoutDivision). | |
| typedef unspecified_type | Sparse_chain_type |
| Type of SparseChain used for storage. | |
| typedef unspecified_type | Non_zero_chain_indices |
| A range of indices of non empty chains. | |
| typedef unspecified_type | Matrix_chain |
| Type of the chains stored in the matrix. | |
Member data | |
| int | Storage_format |
| Matrix storage format (either CGAL::OSM::ROW or CGAL::OSM::COLUMN). | |
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. | |
| void | nullify () |
| Cleans a sparse matrix (set all coefficients to zero). | |
| void | eye (size_t nrows, size_t ncols) |
| Sets an identity matrix. | |
| void | eye (std::pair< size_t, size_t > dimensions) |
| Sets an identity matrix. | |
Matrix informations and iterators | |
| bool | is_null () |
| Tests if a sparse matrix is null. | |
| bool | is_empty () |
| Tests if a Sparse_matrix is empty. | |
| int | storage_format () |
| Returns the storage format of the matrix. | |
| std::pair< size_t, size_t > | dimensions () const |
| Gets the matrix size. | |
| Non_zero_chain_indices::iterator | begin () const noexcept |
| Iterator to the index of the first non null chain. | |
| Non_zero_chain_indices::iterator | end () const noexcept |
| Iterator past-the-end of chain indices. | |
| Non_zero_chain_indices::iterator | reverse_begin () const noexcept |
| Reverse iterator to the index of the last non null chain. | |
| Non_zero_chain_indices::iterator | reverse_end () const noexcept |
| Reverse iterator past-the-end of chain indices. | |
Linear algebra operators | |
| SparseMatrix & | operator-= (SparseMatrix &matrix, const SparseMatrix &other) |
| Subtracts two matrices into a new matrix. | |
| 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) |
| Perform addition of matrices and assign the result to matrix. | |
| SparseMatrix | operator+ (const SparseMatrix &first, const SparseMatrix &second) |
| Perform addition of matrices and assign the result to matrix. | |
| SparseMatrix | operator- (const SparseMatrix &first, const SparseMatrix &second) |
| Subtracts two matrices into a new matrix. | |
| 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) |
| Perform multiplication of matrices and assign the result to matrix. | |
| SparseMatrix | operator* (const SparseMatrix &first, const SparseMatrix &second) |
| Perform multiplication of matrices and return a new column-major matrix. | |
| SparseMatrix | operator% (const SparseMatrix &first, const SparseMatrix &second) |
| Perform multiplication of matrices and return a new row-major matrix. | |
| SparseChain | operator* (const SparseMatrix &matrix, const SparseChain &column) |
| Perform multiplication of a sparse matrix (column or row major) and a column-chain. | |
| SparseChain | operator* (const SparseChain &row, const SparseMatrix &matrix) |
| Perform multiplication of a row-chain and a sparse matrix (column or row major). | |
Access and blocks operations | |
| Matrix_chain | operator[] (size_t index) const |
| Gets the value of a chain from a const matrix. | |
| const SparseChain & | cget_column (const SparseMatrix &matrix, size_t index) |
| Gets a const reference over a column from a column matrix. | |
| const SparseChain & | cget_row (const SparseMatrix &matrix, size_t index) |
| Gets a constant reference over a row from a row matrix. | |
| void | set_column (SparseMatrix &matrix, size_t index, const SparseChain &column) |
| Set the value of the column at a given index from the matrix to column (whatever the Storage_format of the matrix). | |
| void | set_row (SparseMatrix &matrix, size_t index, const SparseChain &row) |
| Set the value of the row at a given index from the matrix to chain (whatever the StorageFormat of the matrix). | |
| SparseMatrix & | operator/= (size_t index) |
| Remove the chain at a given index. | |
| SparseMatrix & | operator/= (const std::vector< size_t > &indices) |
| Build and return a new matrix by copying a matrix and removing all chains with indices in the indices vector. | |
| void | set_coefficient (SparseMatrix &matrix, size_t i, size_t j, const Coefficient_ring d) |
| Sets a given coefficient in matrix. | |
| 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 Storage_format of the matrix). | |
| SparseChain | get_row (const SparseMatrix &matrix, size_t index) |
| Get sthe value of the row at a given index from the matrix (whatever the Storage_format of the matrix). | |
| SparseMatrix | operator/ (const SparseMatrix &matrix, size_t index) |
| Build and return a new matrix by copying a matrix and removing the chain at a given index. | |
| SparseMatrix | operator/ (const SparseMatrix &matrix, const std::vector< size_t > &indices) |
| Build and return a new matrix by copying a matrix and removing the chains with indices in the indices vector. | |
| SparseMatrix & | remove_column (SparseMatrix &matrix, size_t index) |
| Removes a column from the matrix. | |
| SparseMatrix & | remove_row (SparseMatrix &matrix, size_t index) |
| Removes a row from the matrix. | |
| SparseMatrix & | remove_coefficient (SparseMatrix &matrix, size_t i, size_t j) |
| Removes a coefficient from the matrix. | |
| Sparse_matrix & | swap_columns (Sparse_matrix &matrix, size_t i, size_t j) |
| Swaps columns in a matrix. | |
| Sparse_matrix & | swap_rows (Sparse_matrix &matrix, size_t i, size_t j) |
| Swaps rows in a matrix. | |
Input, output | |
| std::ostream & | operator<< (std::ostream &_stream, const SparseMatrix &matrix) |
| Writes a sparse matrix in the output stream with a compact "user friendly" format. | |
| std::ostream & | write_matrix (const SparseMatrix &matrix, std::ostream &out) |
| Write a sparse matrix to an output stream using the .osm file format. | |
| std::ostream & | write_matrix (const SparseMatrix &matrix, std::string filename) |
| Write a sparse matrix to a file using the .osm file format. | |
| template<typename _CT> | |
| std::istream & | read_matrix (SparseMatrix &matrix, std::istream &in) |
| Read a sparse matrix from an input stream using the .osm file format. | |
| template<typename _CT> | |
| std::istream & | read_matrix (SparseMatrix &matrix, std::string filename) |
| Read a sparse matrix from a file using the .osm file format. | |
| SparseMatrix::SparseMatrix | ( | ) |
Creates an empty new sparse matrix object.
Default constructor, initialize an empty matrix of type Storage_format with coefficients of type Coefficient_ring. The default matrix size is 0x0.
| 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 Storage_format with coefficients of type Coefficient_ring and a given size along rows/columns.
|
noexcept |
Iterator to the index of the first non null chain.
Return an iterator to the index of the first non null chain (the iterator visits indices of non null chains along the major dimension of the matrix).
| const SparseChain & SparseMatrix::cget_column | ( | const SparseMatrix & | matrix, |
| size_t | index ) |
Gets a const reference over a column from a column matrix.
Constant time get.
| matrix | The matrix considered. |
| index | The column index. |
| const SparseChain & SparseMatrix::cget_row | ( | const SparseMatrix & | matrix, |
| size_t | index ) |
Gets a constant reference over a row from a row matrix.
Constant time get.
| matrix | The matrix considered. |
| index | The row index. |
| std::pair< size_t, size_t > SparseMatrix::dimensions | ( | ) | const |
Gets the matrix size.
The matrix size as a row/column pair.
|
noexcept |
Iterator past-the-end of chain indices.
| void SparseMatrix::eye | ( | size_t | nrows, |
| size_t | ncols ) |
Sets an identity matrix.
| nrows | Number of rows of the matrix. |
| ncols | Number of columns of the matrix. |
| void SparseMatrix::eye | ( | std::pair< size_t, size_t > | dimensions | ) |
Sets an identity matrix.
| dimensions | Pair containing the number of rows and number of columns of the matrix. |
| bool SparseMatrix::is_empty | ( | ) |
Tests if a Sparse_matrix is empty.
The function return true is the Sparse_matrix is empty (that is, if the number of columns or rows is null) and false otherwise.
| bool SparseMatrix::is_null | ( | ) |
Tests if a sparse matrix is null.
The function returns true if the sparse matrix is null (technically, the sparse matrix is empty, and thus encodes a matrix in which all coefficients are zero) and false otherwise.
| void SparseMatrix::nullify | ( | ) |
Cleans a sparse matrix (set all coefficients to zero).
Empties all structures of the sparse matrix.
| SparseMatrix & SparseMatrix::operator*= | ( | const Coefficient_ring & | lambda | ) |
Applies factor on each coefficient and assign.
This method multiplies the matrix by a scalar factor lambda.
| SparseMatrix & SparseMatrix::operator-= | ( | SparseMatrix & | matrix, |
| const SparseMatrix & | other ) |
Subtracts two matrices into a new matrix.
Subtracts each coefficient of the matrix other and returns a new matrix (of the same type as matrix) representing the result (when possible, prefer -= for efficiency).
| matrix | The first matrix. |
| other | The second matrix. |
| SparseMatrix & SparseMatrix::operator/= | ( | const std::vector< size_t > & | indices | ) |
Build and return a new matrix by copying a matrix and removing all chains with indices in the indices vector.
The result is thus a block of the initial matrix. When possible, for efficiency, prefer /=.
| indices | The indices of the chains to remove. |
| SparseMatrix & SparseMatrix::operator/= | ( | size_t | index | ) |
Remove the chain at a given index.
The result is thus a block of the initial matrix.
| index | The index of the chain to remove. |
| Matrix_chain SparseMatrix::operator[] | ( | size_t | index | ) | const |
Gets the value of a chain from a const matrix.
For COLUMN matrices, returns the index-th column, for ROW matrices, returns the index-th row.
| index | The chain index. |
|
noexcept |
Reverse iterator to the index of the last non null chain.
Return a reverse iiterator to the index of the last non null chain (the iterator visits indices of non null chains, in decreading order, along the major dimension of the matrix).
|
noexcept |
Reverse iterator past-the-end of chain indices.
| void SparseMatrix::set_column | ( | SparseMatrix & | matrix, |
| size_t | index, | ||
| const SparseChain & | column ) |
Set the value of the column at a given index from the matrix to column (whatever the Storage_format of the matrix).
| matrix | The matrix. |
| index | The column index. |
| column | The new column value. |
| void SparseMatrix::set_row | ( | SparseMatrix & | matrix, |
| size_t | index, | ||
| const SparseChain & | row ) |
Set the value of the row at a given index from the matrix to chain (whatever the StorageFormat of the matrix).
| matrix | The matrix. |
| index | The row index. |
| row | The new row value. |
| SparseMatrix SparseMatrix::transpose | ( | ) |
Transposes a matrix.
|
friend |
Gets a given coefficient.
Returns the coefficient on row i and column j of the matrix.
| matrix | Constant reference on the matrix. |
| i | The row index. |
| j | The column index. |
|
friend |
Gets the value of the column at a given index from the matrix (whatever the Storage_format of the matrix).
For column-matrices, the operation comes to copy non zero coefficients of the column; for row-matrices a traversal of the matrix is required (in \(\mathcal O(n)\)). Whenever possible, prefer cget_column().
| matrix | The matrix considered. |
| index | The coefficient index. |
|
friend |
Get sthe value of the row at a given index from the matrix (whatever the Storage_format of the matrix).
For row-matrices, the operation comes to copy non zero coefficients of the row; for column-matrices a traversal of the matrix is required (in \(\mathcal O(n)\)). Whenever possible, prefer cget_row().
| matrix | The matrix considered. |
| index | The coefficient index. |
|
friend |
Perform multiplication of matrices and return a new row-major matrix.
Perform standard linear algebra multiplication of matrices and return a new row-major matrix (when possible, prefer *= for efficiency). Matrices must have the same Coefficient_ring but can have different Storage_format. The multiplication is optimized (using standard definition or block multiplications) for each combination of Storage_format. However, efficiency depends on Storage_format.
| first | The first matrix. |
| second | The second 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).
| lambda | The factor to apply. |
| matrix | The matrix. |
|
friend |
Perform multiplication of a row-chain and a sparse matrix (column or row major).
The function returns a new row-major chain.
Perform standard linear algebra multiplication of a row-chain and a matrix (ie. row vector / matrix multiplication) and returns a new row-major chain. Both arguments must have the same Coefficient_ring but the matrix can have any Storage_format (and the multiplication is optimized for each of them).
| row | The row-major chain. |
| matrix | The matrix. |
|
friend |
Perform multiplication of matrices and return a new column-major matrix.
Perform standard linear algebra multiplication of matrices and return a new column-major matrix (when possible, prefer *= for efficiency). Matrices must have the same Coefficient_ring but can have different Storage_format. The multiplication is optimized (using standard definition or block multiplications) for each combination of Storage_format. However, efficiency depends on Storage_format (when possible, prefer row-major by column-major multiplications).
| first | The first matrix. |
| second | The second 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).
| lambda | The factor to apply. |
|
friend |
Perform multiplication of a sparse matrix (column or row major) and a column-chain.
The function returns a new column-major chain.
Perform standard linear algebra multiplication of a matrix and a column-chain (ie. matrix / column vector multiplication) and returns a new column-major chain. Both arguments must have the same Coefficient_ring but the matrix can have any Storage_format (and the multiplication is optimized for each of them).
| matrix | The matrix. |
| column | The column-major chain. |
|
friend |
Perform multiplication of matrices and assign the result to matrix.
Perform standard linear algebra multiplication. Matrices must have the same Coefficient_ring but can have different Storage_format. The multiplication is optimized for each combination of Storage_format.
| matrix | The first matrix. |
| other | The second matrix. |
|
friend |
Perform addition of matrices and assign the result to matrix.
Perform standard linear algebra addition. Matrices must have the same Coefficient_ring but can have different Storage_format. The addition is optimized for each combination of Storage_format.
| first | The first matrix. |
| second | The second matrix. |
|
friend |
Perform addition of matrices and assign the result to matrix.
Perform standard linear algebra addition. Matrices must have the same Coefficient_ring but can have different Storage_format. The addition is optimized for each combination of Storage_format.
| matrix | The first matrix. |
| other | The second matrix. |
|
friend |
Subtracts two matrices into a new matrix.
Subtracts each coefficient of the matrix other and returns a new matrix (of the same type as this) representing the result (when possible, prefer -= for efficiency).
| first | The first matrix. |
| second | The second matrix. |
|
friend |
Computes the negative of a matrix (unary operator).
|
friend |
Build and return a new matrix by copying a matrix and removing the chains with indices in the indices vector.
The result is thus a block of the initial matrix. When possible, for efficiency, prefer /=.
| matrix | The initial matrix. |
| indices | The indices of the chains to remove. |
|
friend |
Build and return a new matrix by copying a matrix and removing the chain at a given index.
The result is thus a block of the initial matrix. When possible, for efficiency, prefer /=.
| matrix | The initial matrix. |
| index | The index of the chain to remove. |
|
friend |
Writes a sparse matrix in the output stream with a compact "user friendly" format.
| _stream | The output stream. |
| matrix | The matrix to display. |
|
friend |
Read a sparse matrix from an input stream using the .osm file format.
Read a sparse matrix (the input must respect the .osm file format), .see OSM file format documentation.
|
friend |
Read a sparse matrix from a file using the .osm file format.
Read a sparse matrix (the input must respect the .osm file format), .see OSM file format documentation.
|
friend |
|
friend |
Removes a column from the matrix.
Removes column of index index whatever the Storage_format of the matrix. For column matrices, it just comes to the /= operator and for row matrices, it entails a traversal of the matrix.
| matrix | Reference on the matrix to modify. |
| index | The index to remove. |
|
friend |
Removes a row from the matrix.
Removes row of index index whatever the Storage_format of the matrix. For row matrices, it just comes to the /= operator and for column matrices, it entails a traversal of the matrix.
| matrix | Reference on the matrix to modify. |
| index | The index to remove. |
|
friend |
Sets a given coefficient in matrix.
Assign the scalar d to the coefficient on row i and column j.
| matrix | Reference on the matrix to modify. |
| i | The row index. |
| j | The column index. |
| d | The value. |
|
friend |
Swaps columns in a matrix.
Swaps columns at indices i and j whatever the StorageFormat of the matrix. For column matrices, the operation runs in constant time, while it entails a traversal of the matrix for row matrices.
| matrix | Reference on the matrix to modify. |
| i | Index of the first column. |
| j | Index of the second column. |
|
friend |
Swaps rows in a matrix.
Swaps rows at indices i and j whatever the Storage_format of the matrix. For row matrices, the operation runs in constant time, while it entails a traversal of the matrix for column matrices.
| matrix | Reference on the matrix to modify. |
| i | Index of the first row. |
| j | Index of the second row. |
|
friend |
Write a sparse matrix to an output stream using the .osm file format.
Output a sparse matrix (the matrix can be reloaded using read_matrix), see OSM file format documentation.
|
friend |
Write a sparse matrix to a file using the .osm file format.
Output a sparse matrix (the matrix can be reloaded using read_matrix), see OSM file format documentation.