#include <markowitz.h>

Public Member Functions
	MatrixNonZeroPattern ()=default

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

MatrixNonZeroPattern &	operator= (const MatrixNonZeroPattern &)=delete

void	Clear ()
	Releases the memory used by this class.

void	Reset (RowIndex num_rows, ColIndex num_cols)
	Resets the pattern to the one of an empty square matrix of the given size.

void	InitializeFromMatrixSubset (const CompactSparseMatrixView &basis_matrix, const RowPermutation &row_perm, const ColumnPermutation &col_perm, std::vector< ColIndex > singleton_columns, std::vector< RowIndex > singleton_rows)

void	AddEntry (RowIndex row, ColIndex col)
	Adds a non-zero entry to the matrix. There should be no duplicates.

void	DeleteRowAndColumn (RowIndex pivot_row, ColIndex pivot_col)

int32_t	DecreaseRowDegree (RowIndex row)

int32_t	DecreaseColDegree (ColIndex col)

bool	IsColumnDeleted (ColIndex col) const
	Returns true if the column has been deleted by DeleteRowAndColumn().

void	RemoveDeletedColumnsFromRow (RowIndex row)

ColIndex	GetFirstNonDeletedColumnFromRow (RowIndex row) const

void	Update (RowIndex pivot_row, ColIndex pivot_col, const SparseColumn &column)

int32_t	ColDegree (ColIndex col) const

int32_t	RowDegree (RowIndex row) const

const absl::InlinedVector< ColIndex, 6 > &	RowNonZero (RowIndex row) const

Detailed Description

Holds the non-zero positions (by row) and column/row degree of the residual matrix during the Gaussian elimination.

During each step of Gaussian elimination, a row and a column will be "removed" from the residual matrix. Note however that the row and column indices of the non-removed part do not change, so the residual matrix at a given step will only correspond to a subset of the initial indices.

Definition at line 102 of file markowitz.h.

Constructor & Destructor Documentation

◆ MatrixNonZeroPattern() [1/2]

operations_research::glop::MatrixNonZeroPattern::MatrixNonZeroPattern ( )

default

◆ MatrixNonZeroPattern() [2/2]

operations_research::glop::MatrixNonZeroPattern::MatrixNonZeroPattern ( const MatrixNonZeroPattern & )

delete

This type is neither copyable nor movable.

Member Function Documentation

◆ AddEntry()

void operations_research::glop::MatrixNonZeroPattern::AddEntry	(	RowIndex	row,
		ColIndex	col )

Adds a non-zero entry to the matrix. There should be no duplicates.

Definition at line 632 of file markowitz.cc.

◆ Clear()

void operations_research::glop::MatrixNonZeroPattern::Clear ( )

Releases the memory used by this class.

Definition at line 561 of file markowitz.cc.

◆ ColDegree()

int32_t operations_research::glop::MatrixNonZeroPattern::ColDegree ( ColIndex col ) const

inline

Returns the degree (i.e. the number of non-zeros) of the given column. This is only valid for the column indices still in the residual matrix.

Definition at line 162 of file markowitz.h.

◆ DecreaseColDegree()

int32_t operations_research::glop::MatrixNonZeroPattern::DecreaseColDegree ( ColIndex col )

Definition at line 638 of file markowitz.cc.

◆ DecreaseRowDegree()

int32_t operations_research::glop::MatrixNonZeroPattern::DecreaseRowDegree ( RowIndex row )

Decreases the degree of a row/column. This is the basic operation used to keep the correct degree after a call to DeleteRowAndColumn(). This is because row_non_zero_[row] is only lazily cleaned.

Definition at line 642 of file markowitz.cc.

◆ DeleteRowAndColumn()

void operations_research::glop::MatrixNonZeroPattern::DeleteRowAndColumn	(	RowIndex	pivot_row,
		ColIndex	pivot_col )

Marks the given pivot row and column as deleted. This is called at each step of the Gaussian elimination on the pivot.

We do that to optimize RemoveColumnFromResidualMatrix().

Definition at line 646 of file markowitz.cc.

◆ GetFirstNonDeletedColumnFromRow()

ColIndex operations_research::glop::MatrixNonZeroPattern::GetFirstNonDeletedColumnFromRow ( RowIndex row ) const

Returns the first non-deleted column index from this row or kInvalidCol if none can be found.

Definition at line 674 of file markowitz.cc.

◆ InitializeFromMatrixSubset()

void operations_research::glop::MatrixNonZeroPattern::InitializeFromMatrixSubset	(	const CompactSparseMatrixView &	basis_matrix,
		const RowPermutation &	row_perm,
		const ColumnPermutation &	col_perm,
		std::vector< ColIndex > *	singleton_columns,
		std::vector< RowIndex > *	singleton_rows )

Resets the pattern to the one of the given matrix but only for the rows/columns whose given permutation is kInvalidRow or kInvalidCol. This also fills the singleton columns/rows with the corresponding entries.

Reset the matrix and initialize the vectors to the correct sizes.

Compute the number of entries in each row.

Reserve the row_non_zero_ vector sizes.

This is needed because in the row degree computation above, we do not test for row_perm[row] == kInvalidRow because it is a bit faster.

Initialize row_non_zero_.

Definition at line 580 of file markowitz.cc.

◆ IsColumnDeleted()

bool operations_research::glop::MatrixNonZeroPattern::IsColumnDeleted ( ColIndex col ) const

Returns true if the column has been deleted by DeleteRowAndColumn().

Definition at line 656 of file markowitz.cc.

◆ operator=()

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

delete

◆ RemoveDeletedColumnsFromRow()

void operations_research::glop::MatrixNonZeroPattern::RemoveDeletedColumnsFromRow ( RowIndex row )

Removes from the corresponding row_non_zero_[row] the columns that have been previously deleted by DeleteRowAndColumn().

Definition at line 660 of file markowitz.cc.

◆ Reset()

void operations_research::glop::MatrixNonZeroPattern::Reset	(	RowIndex	num_rows,
		ColIndex	num_cols )

Resets the pattern to the one of an empty square matrix of the given size.

Definition at line 570 of file markowitz.cc.

◆ RowDegree()

int32_t operations_research::glop::MatrixNonZeroPattern::RowDegree ( RowIndex row ) const

inline

Returns the degree (i.e. the number of non-zeros) of the given row. This is only valid for the row indices still in the residual matrix.

Definition at line 169 of file markowitz.h.

◆ RowNonZero()

const absl::InlinedVector< ColIndex, 6 > & operations_research::glop::MatrixNonZeroPattern::RowNonZero ( RowIndex row ) const

inline

Returns the set of non-zeros of the given row (unsorted). Call RemoveDeletedColumnsFromRow(row) to clean the row first. This is only valid for the row indices still in the residual matrix.

Definition at line 174 of file markowitz.h.

◆ Update()

void operations_research::glop::MatrixNonZeroPattern::Update	(	RowIndex	pivot_row,
		ColIndex	pivot_col,
		const SparseColumn &	column )

Performs a generic Gaussian update of the residual matrix:

DeleteRowAndColumn() must already have been called.
The non-zero pattern is augmented (set union) by the one of the outer product of the pivot column and row.

Important: as a small optimization, this function does not call DecreaseRowDegree() on the row in the pivot column. This has to be done by the client.

Since DeleteRowAndColumn() must be called just before this function, the pivot column has been marked as deleted but degrees have not been updated yet. Hence the +1.

We only need to merge the row for the position with a coefficient different from 0.0. Note that the column must contain all the symbolic non-zeros for the row degree to be updated correctly. Note also that decreasing the row degrees due to the deletion of pivot_col will happen outside this function.

If the row is fully dense, there is nothing to do (the merge below will not change anything). This is a small price to pay for a huge gain when the matrix becomes dense.

We only clean row_non_zero_[row] if there are more than 4 entries to delete. Note(user): the 4 is somewhat arbitrary, but gives good results on the Netlib (23/04/2013). Note that calling RemoveDeletedColumnsFromRow() is not mandatory and does not change the LU decomposition, so we could call it all the time or never and the algorithm would still work.

Todo: (user): Special case if row_non_zero_[pivot_row].size() == 1?

This is currently not used, but kept as an alternative algorithm to investigate. The performance is really similar, but the final L.U is different. Note that when this is used, there is no need to modify bool_scratchpad_ at the beginning of this function.

Todo: (user): Add unit tests before using this.

Definition at line 682 of file markowitz.cc.

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

ortools/glop/markowitz.h
ortools/glop/markowitz.cc

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ MatrixNonZeroPattern() [1/2]

◆ MatrixNonZeroPattern() [2/2]

Member Function Documentation

◆ AddEntry()

◆ Clear()

◆ ColDegree()

◆ DecreaseColDegree()

◆ DecreaseRowDegree()

◆ DeleteRowAndColumn()

◆ GetFirstNonDeletedColumnFromRow()

◆ InitializeFromMatrixSubset()

◆ IsColumnDeleted()

◆ operator=()

◆ RemoveDeletedColumnsFromRow()

◆ Reset()

◆ RowDegree()

◆ RowNonZero()

◆ Update()