operations_research::glop::CompactSparseMatrix Class Reference

Detailed Description

Another matrix representation which is more efficient than a SparseMatrix but doesn't allow matrix modification. It is faster to construct, uses less memory and provides a better cache locality when iterating over the non-zeros of the matrix columns.

Definition at line 299 of file sparse.h.

#include <sparse.h>

Inheritance diagram for operations_research::glop::CompactSparseMatrix:

Classes
class	ConstView

Public Member Functions
	CompactSparseMatrix ()=default
ConstView	view () const
	CompactSparseMatrix (const SparseMatrix &matrix)
	CompactSparseMatrix (const CompactSparseMatrix &)=delete
	This type is neither copyable nor movable.
CompactSparseMatrix &	operator= (const CompactSparseMatrix &)=delete
void	PopulateFromMatrixView (const MatrixView &input)
void	PopulateFromSparseMatrixAndAddSlacks (const SparseMatrix &input)
void	PopulateFromTranspose (const CompactSparseMatrix &input)
void	Reset (RowIndex num_rows)
void	AddEntryToCurrentColumn (RowIndex row, Fractional coeff)
	Api to add columns one at the time.
void	CloseCurrentColumn ()
ColIndex	AddDenseColumn (const DenseColumn &dense_column)
ColIndex	AddDenseColumnPrefix (DenseColumn::ConstView dense_column, RowIndex start)
	Same as AddDenseColumn(), but only adds the non-zero from the given start.
ColIndex	AddDenseColumnWithNonZeros (const DenseColumn &dense_column, absl::Span< const RowIndex > non_zeros)
ColIndex	AddAndClearColumnWithNonZeros (DenseColumn *column, std::vector< RowIndex > *non_zeros)
EntryIndex	ColumnNumEntries (ColIndex col) const
	Returns the number of entries (i.e. degree) of the given column.
EntryIndex	num_entries () const
	Returns the matrix dimensions. See same functions in SparseMatrix.
RowIndex	num_rows () const
ColIndex	num_cols () const
bool	IsEmpty () const
	Returns whether or not this matrix contains any non-zero entries.
ColumnView	column (ColIndex col) const
bool	ColumnIsEmpty (ColIndex col) const
Fractional	ColumnScalarProduct (ColIndex col, const DenseRow &vector) const
void	ColumnAddMultipleToDenseColumn (ColIndex col, Fractional multiplier, DenseColumn::View dense_column) const
void	ColumnAddMultipleToDenseColumn (ColIndex col, Fractional multiplier, DenseColumn *dense_column) const
void	ColumnAddMultipleToSparseScatteredColumn (ColIndex col, Fractional multiplier, ScatteredColumn *column) const
void	ColumnCopyToDenseColumn (ColIndex col, DenseColumn *dense_column) const
void	ColumnCopyToClearedDenseColumn (ColIndex col, DenseColumn *dense_column) const
void	ColumnCopyToClearedDenseColumnWithNonZeros (ColIndex col, DenseColumn *dense_column, RowIndexVector *non_zeros) const
	Same as ColumnCopyToClearedDenseColumn() but also fills non_zeros.
void	Swap (CompactSparseMatrix *other)

Protected Member Functions
::util::IntegerRange< EntryIndex >	Column (ColIndex col) const
	Functions to iterate on the entries of a given column.

Protected Attributes
RowIndex	num_rows_
	The matrix dimensions, properly updated by full and incremental builders.
ColIndex	num_cols_
StrictITIVector< EntryIndex, Fractional >	coefficients_
StrictITIVector< EntryIndex, RowIndex >	rows_
StrictITIVector< ColIndex, EntryIndex >	starts_

Constructor & Destructor Documentation

CompactSparseMatrix() [1/3]

operations_research::glop::CompactSparseMatrix::CompactSparseMatrix ( )

default

CompactSparseMatrix() [2/3]

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

inlineexplicit

Convenient constructors for tests.

Todo

(user): If this is needed in production code, it can be done faster.

Definition at line 346 of file sparse.h.

CompactSparseMatrix() [3/3]

operations_research::glop::CompactSparseMatrix::CompactSparseMatrix ( const CompactSparseMatrix & )

delete

This type is neither copyable nor movable.

Member Function Documentation

AddAndClearColumnWithNonZeros()

ColIndex operations_research::glop::CompactSparseMatrix::AddAndClearColumnWithNonZeros	(	DenseColumn *	column,
		std::vector< RowIndex > *	non_zeros )

Adds a dense column for which we know the non-zero positions and clears it.

Note

this function supports duplicate indices in non_zeros. The complexity is in O(non_zeros.size()). Only the indices present in non_zeros will be cleared. Returns the index of the added column.

Definition at line 626 of file sparse.cc.

AddDenseColumn()

ColIndex operations_research::glop::CompactSparseMatrix::AddDenseColumn

(

const DenseColumn &

dense_column

)

Adds a dense column to the CompactSparseMatrix (only the non-zero will be actually stored). This work in O(input.size()) and returns the index of the added column.

Definition at line 593 of file sparse.cc.

AddDenseColumnPrefix()

ColIndex operations_research::glop::CompactSparseMatrix::AddDenseColumnPrefix	(	DenseColumn::ConstView	dense_column,
		RowIndex	start )

Same as AddDenseColumn(), but only adds the non-zero from the given start.

Definition at line 597 of file sparse.cc.

AddDenseColumnWithNonZeros()

ColIndex operations_research::glop::CompactSparseMatrix::AddDenseColumnWithNonZeros	(	const DenseColumn &	dense_column,
		absl::Span< const RowIndex >	non_zeros )

Same as AddDenseColumn(), but uses the given non_zeros pattern of input. If non_zeros is empty, this actually calls AddDenseColumn().

Definition at line 611 of file sparse.cc.

AddEntryToCurrentColumn()

void operations_research::glop::CompactSparseMatrix::AddEntryToCurrentColumn	(	RowIndex	row,
		Fractional	coeff )

Api to add columns one at the time.

Definition at line 582 of file sparse.cc.

CloseCurrentColumn()

void operations_research::glop::CompactSparseMatrix::CloseCurrentColumn

(

)

Definition at line 588 of file sparse.cc.

Column()

::util::IntegerRange< EntryIndex > operations_research::glop::CompactSparseMatrix::Column ( ColIndex col ) const

inlineprotected

Functions to iterate on the entries of a given column.

Definition at line 515 of file sparse.h.

column()

ColumnView operations_research::glop::CompactSparseMatrix::column ( ColIndex col ) const

inline

Alternative iteration API compatible with the one from SparseMatrix. The ConstView alternative should be faster.

Note

the start may be equal to row.size() if the last columns are empty, it is why we don't use &row[start].

Definition at line 419 of file sparse.h.

ColumnAddMultipleToDenseColumn() [1/2]

void operations_research::glop::CompactSparseMatrix::ColumnAddMultipleToDenseColumn ( ColIndex col, Fractional multiplier, DenseColumn * dense_column ) const

inline

Definition at line 453 of file sparse.h.

ColumnAddMultipleToDenseColumn() [2/2]

void operations_research::glop::CompactSparseMatrix::ColumnAddMultipleToDenseColumn ( ColIndex col, Fractional multiplier, DenseColumn::View dense_column ) const

inline

Adds a multiple of the given column of this matrix to the given dense_column. If multiplier is 0.0, this function does nothing. This function is declared in the .h for efficiency.

Definition at line 444 of file sparse.h.

ColumnAddMultipleToSparseScatteredColumn()

void operations_research::glop::CompactSparseMatrix::ColumnAddMultipleToSparseScatteredColumn ( ColIndex col, Fractional multiplier, ScatteredColumn * column ) const

inline

Same as ColumnAddMultipleToDenseColumn() but also adds the new non-zeros to the non_zeros vector. A non-zero is "new" if is_non_zero[row] was false, and we update dense_column[row]. This function also updates is_non_zero.

Definition at line 462 of file sparse.h.

ColumnCopyToClearedDenseColumn()

void operations_research::glop::CompactSparseMatrix::ColumnCopyToClearedDenseColumn ( ColIndex col, DenseColumn * dense_column ) const

inline

Same as ColumnCopyToDenseColumn() but assumes the column to be initially all zero.

Definition at line 484 of file sparse.h.

ColumnCopyToClearedDenseColumnWithNonZeros()

void operations_research::glop::CompactSparseMatrix::ColumnCopyToClearedDenseColumnWithNonZeros ( ColIndex col, DenseColumn * dense_column, RowIndexVector * non_zeros ) const

inline

Same as ColumnCopyToClearedDenseColumn() but also fills non_zeros.

Definition at line 496 of file sparse.h.

ColumnCopyToDenseColumn()

void operations_research::glop::CompactSparseMatrix::ColumnCopyToDenseColumn ( ColIndex col, DenseColumn * dense_column ) const

inline

Copies the given column of this matrix into the given dense_column. This function is declared in the .h for efficiency.

Definition at line 476 of file sparse.h.

ColumnIsEmpty()

bool operations_research::glop::CompactSparseMatrix::ColumnIsEmpty ( ColIndex col ) const

inline

Returns true if the given column is empty. Note that for triangular matrix this does not include the diagonal coefficient (see below).

Definition at line 431 of file sparse.h.

ColumnNumEntries()

EntryIndex operations_research::glop::CompactSparseMatrix::ColumnNumEntries ( ColIndex col ) const

inline

Returns the number of entries (i.e. degree) of the given column.

Definition at line 399 of file sparse.h.

ColumnScalarProduct()

Fractional operations_research::glop::CompactSparseMatrix::ColumnScalarProduct ( ColIndex col, const DenseRow & vector ) const

inline

Returns the scalar product of the given row vector with the column of index col of this matrix.

Definition at line 437 of file sparse.h.

IsEmpty()

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

inline

Returns whether or not this matrix contains any non-zero entries.

Definition at line 412 of file sparse.h.

num_cols()

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

inline

Definition at line 409 of file sparse.h.

num_entries()

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

inline

Returns the matrix dimensions. See same functions in SparseMatrix.

Definition at line 404 of file sparse.h.

num_rows()

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

inline

Definition at line 408 of file sparse.h.

operator=()

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

delete

PopulateFromMatrixView()

void operations_research::glop::CompactSparseMatrix::PopulateFromMatrixView

(

const MatrixView &

input

)

Creates a CompactSparseMatrix from the given MatrixView. The matrices are the same, only the representation differ. Note that the entry order in each column is preserved.

Definition at line 447 of file sparse.cc.

PopulateFromSparseMatrixAndAddSlacks()

void operations_research::glop::CompactSparseMatrix::PopulateFromSparseMatrixAndAddSlacks

(

const SparseMatrix &

input

)

Creates a CompactSparseMatrix by copying the input and adding an identity matrix to the left of it.

Definition at line 466 of file sparse.cc.

PopulateFromTranspose()

void operations_research::glop::CompactSparseMatrix::PopulateFromTranspose

(

const CompactSparseMatrix &

input

)

Creates a CompactSparseMatrix from the transpose of the given CompactSparseMatrix. Note that the entries in each columns will be ordered by row indices.

Fill the starts_ vector by computing the number of entries of each rows and then doing a cumulative sum. After this step starts_[col + 1] will be the actual start of the column col when we are done.

Use starts_ to fill the matrix. Note that starts_ is modified so that at the end it has its final values.

Definition at line 495 of file sparse.cc.

Reset()

void operations_research::glop::CompactSparseMatrix::Reset

(

RowIndex

num_rows

)

Clears the matrix and sets its number of rows. If none of the Populate() function has been called, Reset() must be called before calling any of the Add*() functions below.

Definition at line 561 of file sparse.cc.

Swap()

void operations_research::glop::CompactSparseMatrix::Swap

(

CompactSparseMatrix *

other

)

Definition at line 642 of file sparse.cc.

view()

ConstView operations_research::glop::CompactSparseMatrix::view ( ) const

inline

Definition at line 342 of file sparse.h.

Member Data Documentation

coefficients_

StrictITIVector<EntryIndex, Fractional> operations_research::glop::CompactSparseMatrix::coefficients_

protected

Holds the columns non-zero coefficients and row positions. The entries for the column of index col are stored in the entries [starts_[col], starts_[col + 1]).

Definition at line 526 of file sparse.h.

num_cols_

ColIndex operations_research::glop::CompactSparseMatrix::num_cols_

protected

Definition at line 521 of file sparse.h.

num_rows_

RowIndex operations_research::glop::CompactSparseMatrix::num_rows_

protected

The matrix dimensions, properly updated by full and incremental builders.

Definition at line 520 of file sparse.h.

rows_

StrictITIVector<EntryIndex, RowIndex> operations_research::glop::CompactSparseMatrix::rows_

protected

Definition at line 527 of file sparse.h.

starts_

StrictITIVector<ColIndex, EntryIndex> operations_research::glop::CompactSparseMatrix::starts_

protected

Definition at line 528 of file sparse.h.

---

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

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