operations_research::glop::RankOneUpdateElementaryMatrix Class Reference

#include <rank_one_update.h>

Public Member Functions
	RankOneUpdateElementaryMatrix (const CompactSparseMatrix *storage, ColIndex u_index, ColIndex v_index, Fractional u_dot_v)
bool	IsSingular () const
void	RightSolve (DenseColumn *x) const
void	RightSolveWithNonZeros (ScatteredColumn *x) const
void	LeftSolve (DenseRow *y) const
void	LeftSolveWithNonZeros (ScatteredRow *y) const
void	RightMultiply (DenseColumn *x) const
	Computes T.x for a given column vector.
void	LeftMultiply (DenseRow *y) const
	Computes y.T for a given row vector.
EntryIndex	num_entries () const

Detailed Description

This class holds a matrix of the form T = I + u.Tr(v) where I is the identity matrix and u and v are two column vectors of the same size as I. It allows for efficient left and right solves with T. When T is non-singular, it is easy to show that T^{-1} = I - 1 / mu * u.Tr(v) where mu = 1.0 + Tr(v).u

Note

when v is a unit vector, T is a regular Eta matrix and when u is a unit vector, T is a row-wise Eta matrix.

This is based on section 3.1 of: Qi Huangfu, J. A. Julian Hall, "Novel update techniques for the revised simplex method", 28 january 2013, Technical Report ERGO-13-0001

Definition at line 40 of file rank_one_update.h.

Constructor & Destructor Documentation

RankOneUpdateElementaryMatrix()

operations_research::glop::RankOneUpdateElementaryMatrix::RankOneUpdateElementaryMatrix ( const CompactSparseMatrix * storage, ColIndex u_index, ColIndex v_index, Fractional u_dot_v )

inline

Rather than copying the vectors u and v, RankOneUpdateElementaryMatrix takes two columns of a provided CompactSparseMatrix which is used for storage. This has a couple of advantages, especially in the context of the RankOneUpdateFactorization below:

• It uses less overall memory (and avoid allocation overhead).
• It has a better cache behavior for the RankOneUpdateFactorization solves.

Definition at line 48 of file rank_one_update.h.

Member Function Documentation

IsSingular()

bool operations_research::glop::RankOneUpdateElementaryMatrix::IsSingular ( ) const

inline

Returns whether or not this matrix is singular.

Note

the RightSolve() and LeftSolve() function will fail if this is the case.

Definition at line 59 of file rank_one_update.h.

LeftMultiply()

void operations_research::glop::RankOneUpdateElementaryMatrix::LeftMultiply ( DenseRow * y ) const

inline

Computes y.T for a given row vector.

Definition at line 106 of file rank_one_update.h.

LeftSolve()

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

inline

Solves y.T = rhs with rhs initialy in y (a row vector). The non-zeros version keeps track of the new non-zeros.

Definition at line 81 of file rank_one_update.h.

LeftSolveWithNonZeros()

void operations_research::glop::RankOneUpdateElementaryMatrix::LeftSolveWithNonZeros ( ScatteredRow * y ) const

inline

Definition at line 88 of file rank_one_update.h.

num_entries()

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

inline

Definition at line 112 of file rank_one_update.h.

RightMultiply()

void operations_research::glop::RankOneUpdateElementaryMatrix::RightMultiply ( DenseColumn * x ) const

inline

Computes T.x for a given column vector.

Definition at line 99 of file rank_one_update.h.

RightSolve()

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

inline

Solves T.x = rhs with rhs initialy in x (a column vector). The non-zeros version keeps track of the new non-zeros.

Definition at line 63 of file rank_one_update.h.

RightSolveWithNonZeros()

void operations_research::glop::RankOneUpdateElementaryMatrix::RightSolveWithNonZeros ( ScatteredColumn * x ) const

inline

Definition at line 69 of file rank_one_update.h.

---

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

• ortools/glop/rank_one_update.h