#include <lu_factorization.h>

Public Member Functions
	LuFactorization ()

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

LuFactorization &	operator= (const LuFactorization &)=delete

bool	IsIdentityFactorization ()

void	Clear ()

ABSL_MUST_USE_RESULT Status	ComputeFactorization (const CompactSparseMatrixView &compact_matrix)

RowToColMapping	ComputeInitialBasis (const CompactSparseMatrix &matrix, const std::vector< ColIndex > &candidates)

const ColumnPermutation &	GetColumnPermutation () const
	Returns the column permutation used by the LU factorization.

void	SetColumnPermutationToIdentity ()

void	RightSolve (DenseColumn *x) const

void	LeftSolve (DenseRow *y) const

void	RightSolveLWithNonZeros (ScatteredColumn *x) const

void	RightSolveUWithNonZeros (ScatteredColumn *x) const

void	LeftSolveUWithNonZeros (ScatteredRow *y) const

bool	LeftSolveLWithNonZeros (ScatteredRow y, ScatteredColumn result_before_permutation) const

void	LeftSolveLWithNonZeros (ScatteredRow *y) const

void	RightSolveLForColumnView (const ColumnView &b, ScatteredColumn *x) const

void	RightSolveLForScatteredColumn (const ScatteredColumn &b, ScatteredColumn *x) const

void	RightSolveLWithPermutedInput (const DenseColumn &a, ScatteredColumn *x) const

ColIndex	LeftSolveUForUnitRow (ColIndex col, ScatteredRow *y) const

const SparseColumn &	GetColumnOfU (ColIndex col) const

Fractional	RightSolveSquaredNorm (const ColumnView &a) const
	Returns the norm of B^{-1}.a.

Fractional	DualEdgeSquaredNorm (RowIndex row) const
	Returns the norm of (B^T)^{-1}.e_row where e is an unit vector.

double	GetFillInPercentage (const CompactSparseMatrixView &matrix) const

EntryIndex	NumberOfEntries () const

Fractional	ComputeDeterminant () const

Fractional	ComputeInverseOneNorm () const

Fractional	ComputeInverseInfinityNorm () const

Fractional	ComputeOneNormConditionNumber (const CompactSparseMatrixView &matrix) const

Fractional	ComputeInfinityNormConditionNumber (const CompactSparseMatrixView &matrix) const

Fractional	ComputeInverseInfinityNormUpperBound () const

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

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

void	ComputeLowerTimesUpper (SparseMatrix *product) const

double	DeterministicTimeOfLastFactorization () const
	Returns the deterministic time of the last factorization.

const RowPermutation &	row_perm () const
	Visible for testing.

const ColumnPermutation &	inverse_col_perm () const

Detailed Description

An LU-Factorization class encapsulating the LU factorization data and algorithms. The actual algorithm is in markowitz.h and .cc. This class holds all the Solve() functions that deal with the permutations and the L and U factors once they are computed.

Definition at line 37 of file lu_factorization.h.

Constructor & Destructor Documentation

◆ LuFactorization() [1/2]

operations_research::glop::LuFactorization::LuFactorization ( )

Definition at line 29 of file lu_factorization.cc.

◆ LuFactorization() [2/2]

operations_research::glop::LuFactorization::LuFactorization ( const LuFactorization & )

delete

This type is neither copyable nor movable.

Member Function Documentation

◆ Clear()

void operations_research::glop::LuFactorization::Clear ( )

Clears internal data structure and reset this class to the factorization of an identity matrix.

Definition at line 36 of file lu_factorization.cc.

◆ ComputeDeterminant()

Fractional operations_research::glop::LuFactorization::ComputeDeterminant ( ) const

Computes the determinant of the input matrix B. Since P.B.Q^{-1} = L.U, det(P) * det(B) * det(Q^{-1}) = det(L) * det(U). det(L) = 1 since L is a lower-triangular matrix with 1 on the diagonal. det(P) = +1 or -1 (by definition it is the sign of the permutation P) det(Q^{-1}) = +1 or -1 (the sign of the permutation Q^{-1}) Finally det(U) = product of the diagonal elements of U, since U is an upper-triangular matrix. Taking all this into account: det(B) = sign(P) * sign(Q^{-1}) * prod_i u_ii .

Definition at line 493 of file lu_factorization.cc.

◆ ComputeFactorization()

Status operations_research::glop::LuFactorization::ComputeFactorization ( const CompactSparseMatrixView & compact_matrix )

Computes an LU-decomposition for a given matrix B. If for some reason, there was an error, then the factorization is reset to the one of the identity matrix, and an error is reported.

Note(user): Since a client must use the result, there is little chance of it being confused by this revert to identity factorization behavior. The reason behind it is that this way, calling any public function of this class will never cause a crash of the program.

Note(user): This might fail on badly scaled matrices. I still prefer to keep it as a DCHECK() for tests though, but I only test it for small matrices.

Definition at line 49 of file lu_factorization.cc.

◆ ComputeInfinityNormConditionNumber()

Fractional operations_research::glop::LuFactorization::ComputeInfinityNormConditionNumber ( const CompactSparseMatrixView & matrix ) const

Definition at line 554 of file lu_factorization.cc.

◆ ComputeInitialBasis()

RowToColMapping operations_research::glop::LuFactorization::ComputeInitialBasis	(	const CompactSparseMatrix &	matrix,
		const std::vector< ColIndex > &	candidates )

Given a set of columns, find a maximum linearly independent subset that can be factorized in a stable way, and complete it into a square matrix using slack columns. The initial set can have less, more or the same number of columns as the number of rows.

Starts by the missing slacks.

Add the slack for this row.

Then add the used candidate columns.

Definition at line 78 of file lu_factorization.cc.

◆ ComputeInverseInfinityNorm()

Fractional operations_research::glop::LuFactorization::ComputeInverseInfinityNorm ( ) const

Computes the infinity-norm of the inverse of the input matrix B. The infinity-norm B is defined as max_i sum_j a_ij http://en.wikipedia.org/wiki/Matrix_norm

Get a column of the matrix inverse.

Compute sum_j basis_matrix_ij.

Compute max_i sum_j basis_matrix_ij

Definition at line 525 of file lu_factorization.cc.

◆ ComputeInverseInfinityNormUpperBound()

Fractional operations_research::glop::LuFactorization::ComputeInverseInfinityNormUpperBound ( ) const

Definition at line 560 of file lu_factorization.cc.

◆ ComputeInverseOneNorm()

Fractional operations_research::glop::LuFactorization::ComputeInverseOneNorm ( ) const

Computes the 1-norm of the inverse of the input matrix B. For this we iteratively solve B.x = e_j, where e_j is the jth unit vector. The result of this computation is the jth column of B^-1. The 1-norm B is defined as max_j sum_i a_ij http://en.wikipedia.org/wiki/Matrix_norm

Get a column of the matrix inverse.

Compute sum_i basis_matrix_ij.

Compute max_j sum_i basis_matrix_ij

Definition at line 504 of file lu_factorization.cc.

◆ ComputeLowerTimesUpper()

void operations_research::glop::LuFactorization::ComputeLowerTimesUpper ( SparseMatrix * product ) const

inline

This is only used for testing and in debug mode.

Todo: (user): avoid the matrix conversion by multiplying TriangularMatrix directly.

Definition at line 216 of file lu_factorization.h.

◆ ComputeOneNormConditionNumber()

Fractional operations_research::glop::LuFactorization::ComputeOneNormConditionNumber ( const CompactSparseMatrixView & matrix ) const

Computes the condition number of the input matrix B. For a given norm, this is the matrix norm times the norm of its inverse.

Note: because the LuFactorization class does not keep the non-factorized matrix in memory, it needs to be passed to these functions. It is up to the client to pass exactly the same matrix as the one used for ComputeFactorization().

Todo: (user): separate this from LuFactorization.

Definition at line 548 of file lu_factorization.cc.

◆ DeterministicTimeOfLastFactorization()

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

Returns the deterministic time of the last factorization.

Definition at line 105 of file lu_factorization.cc.

◆ DualEdgeSquaredNorm()

Fractional operations_research::glop::LuFactorization::DualEdgeSquaredNorm ( RowIndex row ) const

Returns the norm of (B^T)^{-1}.e_row where e is an unit vector.

Definition at line 183 of file lu_factorization.cc.

◆ GetColumnOfU()

const SparseColumn & operations_research::glop::LuFactorization::GetColumnOfU ( ColIndex col ) const

Returns the given column of U. It will only be valid until the next call to GetColumnOfU().

Definition at line 466 of file lu_factorization.cc.

◆ GetColumnPermutation()

const ColumnPermutation & operations_research::glop::LuFactorization::GetColumnPermutation ( ) const

inline

Returns the column permutation used by the LU factorization.

Definition at line 73 of file lu_factorization.h.

◆ GetFillInPercentage()

double operations_research::glop::LuFactorization::GetFillInPercentage ( const CompactSparseMatrixView & matrix ) const

The fill-in of the LU-factorization is defined as the sum of the number of entries of both the lower- and upper-triangular matrices L and U minus the number of entries in the initial matrix B.

This returns the number of entries in lower + upper as the percentage of the number of entries in B.

Definition at line 477 of file lu_factorization.cc.

◆ inverse_col_perm()

const ColumnPermutation & operations_research::glop::LuFactorization::inverse_col_perm ( ) const

inline

Definition at line 228 of file lu_factorization.h.

◆ IsIdentityFactorization()

bool operations_research::glop::LuFactorization::IsIdentityFactorization ( )

inline

Returns true if the LuFactorization is a factorization of the identity matrix. In this state, all the Solve() functions will work for any vector dimension.

Definition at line 48 of file lu_factorization.h.

◆ LeftSolve()

void operations_research::glop::LuFactorization::LeftSolve ( DenseRow * y ) const

Solves 'y.B = r', y initially contains r, and is replaced by r.B^{-1}. Internally, it takes x = y^T, b = r^T and solves B^T.x = b. We have P.B.Q^{-1} = P.B.Q^T = L.U, thus (L.U)^T = Q.B^T.P^T. Therefore B^T = Q^{-1}.U^T.L^T.P^T.P^{-1} = Q^{-1}.U^T.L^T.P The procedure is thus: 1/ Solve Q^{-1}.y = b for y, by computing y = Q.b, 2/ solve U^T.z = y for z, 3/ solve L^T.t = z for t, 4/ finally, solve P.x = t for x by computing x = P^{-1}.t.

We need to interpret y as a column for the permutation functions.

Definition at line 119 of file lu_factorization.cc.

◆ LeftSolveLWithNonZeros() [1/2]

void operations_research::glop::LuFactorization::LeftSolveLWithNonZeros ( ScatteredRow * y ) const

Definition at line 429 of file lu_factorization.cc.

◆ LeftSolveLWithNonZeros() [2/2]

bool operations_research::glop::LuFactorization::LeftSolveLWithNonZeros	(	ScatteredRow *	y,
		ScatteredColumn *	result_before_permutation ) const

Specialized version of LeftSolveL() that may exploit the initial non_zeros of y if it is non empty. Moreover, if result_before_permutation is not NULL, it might be filled with the result just before row_perm_ is applied to it and true is returned. If result_before_permutation is not filled, then false is returned.

It is not advantageous to fill result_before_permutation in this case.

Hypersparse?

Note(user): For the behavior of the two functions to be exactly the same, we need the positions listed in nz to be the "exact" non-zeros of x. This should be the case because the hyper-sparse functions makes sure of that. We also DCHECK() this below.

This computes the same thing as in the other branch but also keeps the original x in result_before_permutation. Because of this, it is faster to use a different algorithm.

Definition at line 364 of file lu_factorization.cc.

◆ LeftSolveUForUnitRow()

ColIndex operations_research::glop::LuFactorization::LeftSolveUForUnitRow	(	ColIndex	col,
		ScatteredRow *	y ) const

Specialized version of LeftSolveU() for an unit right-hand side. non_zeros will either be cleared or set to the non zeros of the results. It also returns the value of col permuted by Q (which is the position of the unit-vector rhs in the solve system: y.U = rhs). Important: the output y must be of the correct size and all zero.

Using the transposed matrix here is faster (even accounting the time to construct it). Note the small optimization in case the inversion is trivial.

Definition at line 433 of file lu_factorization.cc.

◆ LeftSolveUWithNonZeros()

void operations_research::glop::LuFactorization::LeftSolveUWithNonZeros ( ScatteredRow * y ) const

Definition at line 330 of file lu_factorization.cc.

◆ NumberOfEntries()

EntryIndex operations_research::glop::LuFactorization::NumberOfEntries ( ) const

Returns the number of entries in L + U. If the factorization is the identity, this returns 0.

Definition at line 487 of file lu_factorization.cc.

◆ operator=()

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

delete

◆ RightSolve()

void operations_research::glop::LuFactorization::RightSolve ( DenseColumn * x ) const

Solves 'B.x = b', x initially contains b, and is replaced by 'B^{-1}.b'. Since P.B.Q^{-1} = L.U, we have B = P^{-1}.L.U.Q. 1/ Solve P^{-1}.y = b for y by computing y = P.b, 2/ solve L.z = y for z, 3/ solve U.t = z for t, 4/ finally solve Q.x = t, by computing x = Q^{-1}.t.

Definition at line 109 of file lu_factorization.cc.

◆ RightSolveLForColumnView()

void operations_research::glop::LuFactorization::RightSolveLForColumnView	(	const ColumnView &	b,
		ScatteredColumn *	x ) const

Specialized version of RightSolveLWithNonZeros() that takes a SparseColumn or a ScatteredColumn as input. non_zeros will either be cleared or set to the non zeros of the result. Important: the output x must be of the correct size and all zero.

Definition at line 276 of file lu_factorization.cc.

◆ RightSolveLForScatteredColumn()

void operations_research::glop::LuFactorization::RightSolveLForScatteredColumn	(	const ScatteredColumn &	b,
		ScatteredColumn *	x ) const

Definition at line 311 of file lu_factorization.cc.

◆ RightSolveLWithNonZeros()

void operations_research::glop::LuFactorization::RightSolveLWithNonZeros ( ScatteredColumn * x ) const

More fine-grained right/left solve functions that may exploit the initial non-zeros of the input vector if non-empty. Note that a solve involving L actually solves P^{-1}.L and a solve involving U actually solves U.Q. To solve a system with the initial matrix B, one needs to call:

RightSolveL() and then RightSolveU() for a right solve (B.x = initial x).
LeftSolveU() and then LeftSolveL() for a left solve (y.B = initial y).

Definition at line 292 of file lu_factorization.cc.

◆ RightSolveLWithPermutedInput()

void operations_research::glop::LuFactorization::RightSolveLWithPermutedInput	(	const DenseColumn &	a,
		ScatteredColumn *	x ) const

Specialized version of RightSolveLWithNonZeros() where x is originally equal to 'a' permuted by row_perm_. Note that 'a' is only used for DCHECK.

Definition at line 228 of file lu_factorization.cc.

◆ RightSolveSquaredNorm()

Fractional operations_research::glop::LuFactorization::RightSolveSquaredNorm ( const ColumnView & a ) const

Returns the norm of B^{-1}.a.

Definition at line 150 of file lu_factorization.cc.

◆ RightSolveUWithNonZeros()

void operations_research::glop::LuFactorization::RightSolveUWithNonZeros ( ScatteredColumn * x ) const

If non-zeros is non-empty, we use an hypersparse solve. Note that if non_zeros starts to be too big, we clear it and thus switch back to a normal sparse solve.

Definition at line 346 of file lu_factorization.cc.

◆ row_perm()

const RowPermutation & operations_research::glop::LuFactorization::row_perm ( ) const

inline

Visible for testing.

Definition at line 227 of file lu_factorization.h.

◆ SetColumnPermutationToIdentity()

void operations_research::glop::LuFactorization::SetColumnPermutationToIdentity ( )

inline

Sets the column permutation to the identity permutation. The idea is that the column permutation can be incorporated in the basis RowToColMapping, and once this is done, then a client can call this and effectively remove the need for a column permutation on each solve.

Definition at line 79 of file lu_factorization.h.

◆ SetParameters()

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

inline

Sets the current parameters.

Definition at line 203 of file lu_factorization.h.

◆ StatString()

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

inline

Returns a string containing the statistics for this class.

Definition at line 209 of file lu_factorization.h.

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

ortools/glop/lu_factorization.h
ortools/glop/lu_factorization.cc

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ LuFactorization() [1/2]

◆ LuFactorization() [2/2]

Member Function Documentation

◆ Clear()

◆ ComputeDeterminant()

◆ ComputeFactorization()

◆ ComputeInfinityNormConditionNumber()

◆ ComputeInitialBasis()

◆ ComputeInverseInfinityNorm()

◆ ComputeInverseInfinityNormUpperBound()

◆ ComputeInverseOneNorm()

◆ ComputeLowerTimesUpper()

◆ ComputeOneNormConditionNumber()

◆ DeterministicTimeOfLastFactorization()

◆ DualEdgeSquaredNorm()

◆ GetColumnOfU()

◆ GetColumnPermutation()

◆ GetFillInPercentage()

◆ inverse_col_perm()

◆ IsIdentityFactorization()

◆ LeftSolve()

◆ LeftSolveLWithNonZeros() [1/2]

◆ LeftSolveLWithNonZeros() [2/2]

◆ LeftSolveUForUnitRow()

◆ LeftSolveUWithNonZeros()

◆ NumberOfEntries()

◆ operator=()

◆ RightSolve()

◆ RightSolveLForColumnView()

◆ RightSolveLForScatteredColumn()

◆ RightSolveLWithNonZeros()

◆ RightSolveLWithPermutedInput()

◆ RightSolveSquaredNorm()

◆ RightSolveUWithNonZeros()

◆ row_perm()

◆ SetColumnPermutationToIdentity()

◆ SetParameters()

◆ StatString()