#include <sparse.h>

Public Member Functions
	SparseMatrix ()

	SparseMatrix (std::initializer_list< std::initializer_list< Fractional > > init_list)

	SparseMatrix (const SparseMatrix &)=delete
	This type is neither copyable nor movable.

SparseMatrix &	operator= (const SparseMatrix &)=delete

void	Clear ()

bool	IsEmpty () const

void	CleanUp ()

bool	CheckNoDuplicates () const
	Call CheckNoDuplicates() on all columns, useful for doing a DCHECK.

bool	IsCleanedUp () const
	Call IsCleanedUp() on all columns, useful for doing a DCHECK.

void	SetNumRows (RowIndex num_rows)
	Change the number of row of this matrix.

ColIndex	AppendEmptyColumn ()
	Appends an empty column and returns its index.

void	AppendUnitVector (RowIndex row, Fractional value)

void	Swap (SparseMatrix *matrix)

void	PopulateFromZero (RowIndex num_rows, ColIndex num_cols)

void	PopulateFromIdentity (ColIndex num_cols)

template<typename Matrix >
void	PopulateFromTranspose (const Matrix &input)
	Instantiate needed templates.

void	PopulateFromSparseMatrix (const SparseMatrix &matrix)

template<typename Matrix >
void	PopulateFromPermutedMatrix (const Matrix &a, const RowPermutation &row_perm, const ColumnPermutation &inverse_col_perm)

void	PopulateFromLinearCombination (Fractional alpha, const SparseMatrix &a, Fractional beta, const SparseMatrix &b)

void	PopulateFromProduct (const SparseMatrix &a, const SparseMatrix &b)
	Multiplies SparseMatrix a by SparseMatrix b.

void	DeleteColumns (const DenseBooleanRow &columns_to_delete)

void	DeleteRows (RowIndex num_rows, const RowPermutation &permutation)

bool	AppendRowsFromSparseMatrix (const SparseMatrix &matrix)

void	ApplyRowPermutation (const RowPermutation &row_perm)
	Applies the row permutation.

Fractional	LookUpValue (RowIndex row, ColIndex col) const

bool	Equals (const SparseMatrix &a, Fractional tolerance) const

void	ComputeMinAndMaxMagnitudes (Fractional min_magnitude, Fractional max_magnitude) const

RowIndex	num_rows () const
	Return the matrix dimension.

ColIndex	num_cols () const

const SparseColumn &	column (ColIndex col) const
	Access the underlying sparse columns.

SparseColumn *	mutable_column (ColIndex col)

EntryIndex	num_entries () const

Fractional	ComputeOneNorm () const

Fractional	ComputeInfinityNorm () const

std::string	Dump () const
	Returns a dense representation of the matrix.

Detailed Description

SparseMatrix SparseMatrix is a class for sparse matrices suitable for computation. Data is represented using the so-called compressed-column storage scheme. Entries (row, col, value) are stored by column using a SparseColumn.

Citing [Duff et al, 1987], a matrix is sparse if many of its coefficients are zero and if there is an advantage in exploiting its zeros. For practical reasons, not all zeros are exploited (for example those that result from calculations.) The term entry refers to those coefficients that are handled explicitly. All non-zeros are entries while some zero coefficients may also be entries.

Note: no special ordering of entries is assumed.

Definition at line 70 of file sparse.h.

Constructor & Destructor Documentation

◆ SparseMatrix() [1/3]

operations_research::glop::SparseMatrix::SparseMatrix ( )

SparseMatrix

Definition at line 96 of file sparse.cc.

◆ SparseMatrix() [2/3]

operations_research::glop::SparseMatrix::SparseMatrix ( std::initializer_list< std::initializer_list< Fractional > > init_list )

Useful for testing. This makes it possible to write: SparseMatrix matrix { {1, 2, 3}, {4, 5, 6}, {7, 8, 9}};

Definition at line 99 of file sparse.cc.

◆ SparseMatrix() [3/3]

operations_research::glop::SparseMatrix::SparseMatrix ( const SparseMatrix & )

delete

This type is neither copyable nor movable.

Member Function Documentation

◆ AppendEmptyColumn()

ColIndex operations_research::glop::SparseMatrix::AppendEmptyColumn ( )

Appends an empty column and returns its index.

Definition at line 154 of file sparse.cc.

◆ AppendRowsFromSparseMatrix()

bool operations_research::glop::SparseMatrix::AppendRowsFromSparseMatrix ( const SparseMatrix & matrix )

Appends all rows from the given matrix to the calling object after the last row of the calling object. Both matrices must have the same number of columns. The method returns true if the rows were added successfully and false if it can't add the rows because the number of columns of the matrices are different.

Definition at line 311 of file sparse.cc.

◆ AppendUnitVector()

void operations_research::glop::SparseMatrix::AppendUnitVector	(	RowIndex	row,
		Fractional	value )

Appends a unit vector defined by the single entry (row, value).

Note: the row should be smaller than the number of rows of the matrix.

Definition at line 160 of file sparse.cc.

◆ ApplyRowPermutation()

void operations_research::glop::SparseMatrix::ApplyRowPermutation ( const RowPermutation & row_perm )

Applies the row permutation.

Definition at line 325 of file sparse.cc.

◆ CheckNoDuplicates()

bool operations_research::glop::SparseMatrix::CheckNoDuplicates ( ) const

Call CheckNoDuplicates() on all columns, useful for doing a DCHECK.

Definition at line 135 of file sparse.cc.

◆ CleanUp()

void operations_research::glop::SparseMatrix::CleanUp ( )

Cleans the columns, i.e. removes zero-values entries, removes duplicates entries and sorts remaining entries in increasing row order. Call with care: Runs in O(num_cols * column_cleanup), with each column cleanup running in O(num_entries * log(num_entries)).

Definition at line 128 of file sparse.cc.

◆ Clear()

void operations_research::glop::SparseMatrix::Clear ( )

Clears internal data structure, i.e. erases all the columns and set the number of rows to zero.

Definition at line 119 of file sparse.cc.

◆ column()

const SparseColumn & operations_research::glop::SparseMatrix::column ( ColIndex col ) const

inline

Access the underlying sparse columns.

Definition at line 194 of file sparse.h.

◆ ComputeInfinityNorm()

Fractional operations_research::glop::SparseMatrix::ComputeInfinityNorm ( ) const

Computes the oo-norm (infinity-norm) of the matrix. The oo-norm A is defined as max_i sum_j a_ij or max_row sum_col |a(row,col)|.

Definition at line 404 of file sparse.cc.

◆ ComputeMinAndMaxMagnitudes()

void operations_research::glop::SparseMatrix::ComputeMinAndMaxMagnitudes	(	Fractional *	min_magnitude,
		Fractional *	max_magnitude ) const

Returns, in min_magnitude and max_magnitude, the minimum and maximum magnitudes of the non-zero coefficients of the calling object.

Definition at line 378 of file sparse.cc.

◆ ComputeOneNorm()

Fractional operations_research::glop::SparseMatrix::ComputeOneNorm ( ) const

Computes the 1-norm of the matrix. The 1-norm A is defined as max_j sum_i a_ij or max_col sum_row |a(row,col)|.

Definition at line 401 of file sparse.cc.

◆ DeleteColumns()

void operations_research::glop::SparseMatrix::DeleteColumns ( const DenseBooleanRow & columns_to_delete )

Removes the marked columns from the matrix and adjust its size. This runs in O(num_cols).

Definition at line 285 of file sparse.cc.

◆ DeleteRows()

void operations_research::glop::SparseMatrix::DeleteRows	(	RowIndex	num_rows,
		const RowPermutation &	permutation )

Applies the given row permutation and deletes the rows for which permutation[row] is kInvalidRow. Sets the new number of rows to num_rows. This runs in O(num_entries).

Definition at line 298 of file sparse.cc.

◆ Dump()

std::string operations_research::glop::SparseMatrix::Dump ( ) const

Returns a dense representation of the matrix.

Definition at line 408 of file sparse.cc.

◆ Equals()

bool operations_research::glop::SparseMatrix::Equals	(	const SparseMatrix &	a,
		Fractional	tolerance ) const

Returns true if the matrix equals a (with a maximum error smaller than given the tolerance).

Store all entries of current matrix in a dense column.

Check all entries of a are those stored in the dense column.

Store all entries of matrix a in a dense column.

Check all entries are those stored in the dense column a.

Definition at line 336 of file sparse.cc.

◆ IsCleanedUp()

bool operations_research::glop::SparseMatrix::IsCleanedUp ( ) const

Call IsCleanedUp() on all columns, useful for doing a DCHECK.

Definition at line 144 of file sparse.cc.

◆ IsEmpty()

bool operations_research::glop::SparseMatrix::IsEmpty ( ) const

Returns true if the matrix is empty. That is if num_rows() OR num_cols() are zero.

Definition at line 124 of file sparse.cc.

◆ LookUpValue()

Fractional operations_research::glop::SparseMatrix::LookUpValue	(	RowIndex	row,
		ColIndex	col ) const

Returns the coefficient at position row in column col. Call with care: runs in O(num_entries_in_col) as entries may not be sorted.

Definition at line 332 of file sparse.cc.

◆ mutable_column()

SparseColumn * operations_research::glop::SparseMatrix::mutable_column ( ColIndex col )

inline

Definition at line 195 of file sparse.h.

◆ num_cols()

ColIndex operations_research::glop::SparseMatrix::num_cols ( ) const

inline

Definition at line 191 of file sparse.h.

◆ num_entries()

EntryIndex operations_research::glop::SparseMatrix::num_entries ( ) const

Returns the total numbers of entries in the matrix. Runs in O(num_cols).

Definition at line 398 of file sparse.cc.

◆ num_rows()

RowIndex operations_research::glop::SparseMatrix::num_rows ( ) const

inline

Return the matrix dimension.

Definition at line 190 of file sparse.h.

◆ operator=()

SparseMatrix & operations_research::glop::SparseMatrix::operator= ( const SparseMatrix & )

delete

◆ PopulateFromIdentity()

void operations_research::glop::SparseMatrix::PopulateFromIdentity ( ColIndex num_cols )

Populates the matrix from the Identity matrix of size num_cols. Previous columns/values are deleted.

Definition at line 181 of file sparse.cc.

◆ PopulateFromLinearCombination()

void operations_research::glop::SparseMatrix::PopulateFromLinearCombination	(	Fractional	alpha,
		const SparseMatrix &	a,
		Fractional	beta,
		const SparseMatrix &	b )

Populates a SparseMatrix from the result of alpha * A + beta * B, where alpha and beta are Fractionals, A and B are sparse matrices.

Definition at line 234 of file sparse.cc.

◆ PopulateFromPermutedMatrix()

template<typename Matrix >

template void operations_research::glop::SparseMatrix::PopulateFromPermutedMatrix< CompactSparseMatrixView >	(	const Matrix &	a,
		const RowPermutation &	row_perm,
		const ColumnPermutation &	inverse_col_perm )

Populates a SparseMatrix from the image of a matrix A through the given row_perm and inverse_col_perm. See permutation.h for more details.

Definition at line 221 of file sparse.cc.

◆ PopulateFromProduct()

void operations_research::glop::SparseMatrix::PopulateFromProduct	(	const SparseMatrix &	a,
		const SparseMatrix &	b )

Multiplies SparseMatrix a by SparseMatrix b.

Populate column col_b.

Definition at line 259 of file sparse.cc.

◆ PopulateFromSparseMatrix()

void operations_research::glop::SparseMatrix::PopulateFromSparseMatrix ( const SparseMatrix & matrix )

Populates a SparseMatrix from another one (copy), note that this run in O(number of entries in the matrix).

Definition at line 215 of file sparse.cc.

◆ PopulateFromTranspose()

template<typename Matrix >

template void operations_research::glop::SparseMatrix::PopulateFromTranspose< SparseMatrix > ( const Matrix & input )

Instantiate needed templates.

Populates the matrix from the transposed of the given matrix.

Note: this preserve the property of lower/upper triangular matrix to have the diagonal coefficients first/last in each columns. It actually sorts the entries in each columns by their indices.

We do a first pass on the input matrix to resize the new columns properly.

Definition at line 190 of file sparse.cc.

◆ PopulateFromZero()

void operations_research::glop::SparseMatrix::PopulateFromZero	(	RowIndex	num_rows,
		ColIndex	num_cols )

Populates the matrix with num_cols columns of zeros. As the number of rows is specified by num_rows, the matrix is not necessarily square. Previous columns/values are deleted.

Definition at line 173 of file sparse.cc.

◆ SetNumRows()

void operations_research::glop::SparseMatrix::SetNumRows ( RowIndex num_rows )

Change the number of row of this matrix.

Definition at line 152 of file sparse.cc.

◆ Swap()

void operations_research::glop::SparseMatrix::Swap ( SparseMatrix * matrix )

Swaps the content of this SparseMatrix with the one passed as argument. Works in O(1).

We do not need to swap the different mutable scratchpads we use.

Definition at line 167 of file sparse.cc.

The documentation for this class was generated from the following files:

ortools/lp_data/sparse.h
ortools/lp_data/sparse.cc

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ SparseMatrix() [1/3]

◆ SparseMatrix() [2/3]

◆ SparseMatrix() [3/3]

Member Function Documentation

◆ AppendEmptyColumn()

◆ AppendRowsFromSparseMatrix()

◆ AppendUnitVector()

◆ ApplyRowPermutation()

◆ CheckNoDuplicates()

◆ CleanUp()

◆ Clear()

◆ column()

◆ ComputeInfinityNorm()

◆ ComputeMinAndMaxMagnitudes()

◆ ComputeOneNorm()

◆ DeleteColumns()

◆ DeleteRows()

◆ Dump()

◆ Equals()

◆ IsCleanedUp()

◆ IsEmpty()

◆ LookUpValue()

◆ mutable_column()

◆ num_cols()

◆ num_entries()

◆ num_rows()

◆ operator=()

◆ PopulateFromIdentity()

◆ PopulateFromLinearCombination()

◆ PopulateFromPermutedMatrix()

◆ PopulateFromProduct()

◆ PopulateFromSparseMatrix()

◆ PopulateFromTranspose()

◆ PopulateFromZero()

◆ SetNumRows()

◆ Swap()