#include <markowitz.h>

Public Member Functions
	Markowitz ()=default

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

Markowitz &	operator= (const Markowitz &)=delete

ABSL_MUST_USE_RESULT Status	ComputeLU (const CompactSparseMatrixView &basis_matrix, RowPermutation row_perm, ColumnPermutation col_perm, TriangularMatrix lower, TriangularMatrix upper)

ABSL_MUST_USE_RESULT Status	ComputeRowAndColumnPermutation (const CompactSparseMatrixView &basis_matrix, RowPermutation row_perm, ColumnPermutation col_perm)

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

double	DeterministicTimeOfLastFactorization () const
	Returns an estimate of the time spent in the last factorization.

std::string	StatString () const
	Returns a string containing the statistics for this class.

void	SetParameters (const GlopParameters &parameters)
	Sets the current parameters.

Detailed Description

The class that computes either the actual L.U decomposition, or the permutation P and Q such that P.B.Q^{-1} will have a sparse L.U decomposition.

Definition at line 286 of file markowitz.h.

Constructor & Destructor Documentation

◆ Markowitz() [1/2]

operations_research::glop::Markowitz::Markowitz ( )

default

◆ Markowitz() [2/2]

operations_research::glop::Markowitz::Markowitz ( const Markowitz & )

delete

This type is neither copyable nor movable.

Member Function Documentation

◆ Clear()

void operations_research::glop::Markowitz::Clear ( )

Releases the memory used by this class.

Definition at line 173 of file markowitz.cc.

◆ ComputeLU()

Status operations_research::glop::Markowitz::ComputeLU	(	const CompactSparseMatrixView &	basis_matrix,
		RowPermutation *	row_perm,
		ColumnPermutation *	col_perm,
		TriangularMatrix *	lower,
		TriangularMatrix *	upper )

Computes the full factorization with P, Q, L and U.

If the matrix is singular, the returned status will indicate it and the permutation (col_perm) will contain a maximum non-singular set of columns of the matrix. Moreover, by adding singleton columns with a one at the rows such that 'row_perm[row] == kInvalidRow', then the matrix will be non-singular.

The two first swaps allow to use less memory since this way upper_ and lower_ will always stay empty at the end of this function.

Definition at line 153 of file markowitz.cc.

◆ ComputeRowAndColumnPermutation()

Status operations_research::glop::Markowitz::ComputeRowAndColumnPermutation	(	const CompactSparseMatrixView &	basis_matrix,
		RowPermutation *	row_perm,
		ColumnPermutation *	col_perm )

Only computes P and Q^{-1}, L and U can be computed later from these permutations using another algorithm (for instance left-looking L.U). This may be faster than computing the full L and U at the same time but the current implementation is not optimized for this.

It behaves the same as ComputeLU() for singular matrices.

This function also works with a non-square matrix. It will return a set of independent columns of maximum size. If all the given columns are independent, the returned Status will be OK.

Get the empty matrix corner case out of the way.

Initialize all the matrices.

Start by moving the singleton columns to the front and by putting their non-zero coefficient on the diagonal. The general algorithm below would have the same effect, but this function is a lot faster.

Initialize residual_matrix_non_zero_ with the submatrix left after we removed the singleton and residual singleton columns.

Perform Gaussian elimination.

Todo: (user): If we don't need L and U, we can abort when the residual matrix becomes dense (i.e. when its density factor is above a certain threshold). The residual size is 'end_index - index' and the density can either be computed exactly or estimated from min_markowitz.

Singular matrix? No pivot will be selected if a column has no entries. If a column has some entries, then we are sure that a pivot will be selected but its magnitude can be really close to zero. In both cases, we report the singularity of the matrix.

Update residual_matrix_non_zero_.

Todo: (user): This step can be skipped, once a fully dense matrix is obtained. But note that permuted_lower_column_needs_solve_ needs to be updated.

Todo: (user): Note that in some rare cases, because of numerical cancellation, the column degree may actually be smaller than pivot_col_degree. Exploit that better?

Update the permutations.

To get a better deterministic time, we add a factor that depend on the final number of entries in the result.

Definition at line 31 of file markowitz.cc.

◆ DeterministicTimeOfLastFactorization()

double operations_research::glop::Markowitz::DeterministicTimeOfLastFactorization ( ) const

Returns an estimate of the time spent in the last factorization.

Definition at line 557 of file markowitz.cc.

◆ operator=()

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

delete

◆ SetParameters()

void operations_research::glop::Markowitz::SetParameters ( const GlopParameters & parameters )

inline

Sets the current parameters.

Definition at line 330 of file markowitz.h.

◆ StatString()

std::string operations_research::glop::Markowitz::StatString ( ) const