Scippy

SoPlex

Sequential object-oriented simPlex

Sparse vectors.Class SVectorBase provides packed sparse vectors. Such are a sparse vectors, with a storage scheme that keeps all data in one contiguous block of memory. This is best suited for using them for parallel computing on a distributed memory multiprocessor. More...

#include <dvectorbase.h>

Inheritance diagram for SVectorBase< R >:

Public Types

typedef Nonzero< R > Element
 

Public Member Functions

template<>
SVectorBase< Real > & operator= (const VectorBase< S > &vec)
 Assignment operator (specialization for Real). More...
 
template<>
Real operator* (const SVectorBase< S > &w) const
 specialization for inner product for sparse vectors More...
 
Access
int size () const
 Number of used indices. More...
 
int max () const
 Maximal number of indices. More...
 
int dim () const
 Dimension of the vector defined as maximal index + 1. More...
 
int number (int i) const
 Number of index i. More...
 
operator[] (int i) const
 Value to index i. More...
 
Nonzero< R > & element (int n)
 Reference to the n 'th nonzero element. More...
 
const Nonzero< R > & element (int n) const
 The n 'th nonzero element. More...
 
int & index (int n)
 Reference to index of n 'th nonzero. More...
 
int index (int n) const
 Index of n 'th nonzero. More...
 
R & value (int n)
 Reference to value of n 'th nonzero. More...
 
const R & value (int n) const
 Value of n 'th nonzero. More...
 
void add (int i, const R &v)
 Append one nonzero (i,v). More...
 
void add (int i)
 Append one uninitialized nonzero. More...
 
void add (const SVectorBase &sv)
 Append nonzeros of sv. More...
 
void add (int n, const int i[], const R v[])
 Append n nonzeros. More...
 
template<class S >
void add (int n, const int i[], const S v[])
 Append n nonzeros. More...
 
void add (int n, const Nonzero< R > e[])
 Append n nonzeros. More...
 
void remove (int n, int m)
 Remove nonzeros n thru m. More...
 
void remove (int n)
 Remove n 'th nonzero. More...
 
void clear ()
 Remove all indices. More...
 
void sort ()
 Sort nonzeros to increasing indices. More...
 
Arithmetic operations
maxAbs () const
 Maximum absolute value, i.e., infinity norm. More...
 
minAbs () const
 Minimum absolute value. More...
 
Real length () const
 Floating point approximation of euclidian norm (without any approximation guarantee). More...
 
length2 () const
 Squared norm. More...
 
SVectorBase< R > & operator*= (const R &x)
 Scaling. More...
 
operator* (const VectorBase< R > &w) const
 Inner product. More...
 
template<class S >
operator* (const SVectorBase< S > &w) const
 inner product for sparse vectors More...
 
Constructions, destruction, and assignment
 SVectorBase (int n=0, Nonzero< R > *p_mem=0)
 Default constructor. More...
 
template<class S >
SVectorBase< R > & operator= (const VectorBase< S > &vec)
 Assignment operator. More...
 
SVectorBase< R > & operator= (const SVectorBase< R > &sv)
 Assignment operator. More...
 
template<class S >
SVectorBase< R > & operator= (const SVectorBase< S > &sv)
 Assignment operator. More...
 
template<class S >
SVectorBase< R > & assignArray (const S *rowValues, const int *rowIndices, int rowSize)
 Assignment operator. More...
 
template<class S >
SVectorBase< R > & operator= (const SSVectorBase< S > &sv)
 Assignment operator. More...
 
Memory
Nonzero< R > * mem () const
 get pointer to internal memory. More...
 
void set_size (int s)
 Set size of the vector. More...
 
void set_max (int m)
 Set the maximum number of nonzeros in the vector. More...
 
void setMem (int n, Nonzero< R > *elmem)
 Set the memory area where the nonzeros will be stored. More...
 
Utilities
bool isConsistent () const
 Consistency check. More...
 

Private Attributes

Data
Nonzero< R > * m_elem
 
int memsize
 
int memused
 

Friends

template<class S >
class SVectorBase
 

Detailed Description

template<class R>
class soplex::SVectorBase< R >

Sparse vectors.

Class SVectorBase provides packed sparse vectors. Such are a sparse vectors, with a storage scheme that keeps all data in one contiguous block of memory. This is best suited for using them for parallel computing on a distributed memory multiprocessor.

SVectorBase does not provide any memory management (this will be done by class DSVectorBase). This means, that the constructor of SVectorBase expects memory where to save the nonzeros. Further, adding nonzeros to an SVectorBase may fail if no more memory is available for saving them (see also DSVectorBase).

When nonzeros are added to an SVectorBase, they are appended to the set of nonzeros, i.e., they recieve numbers size(), size()+1 ... . An SVectorBase can hold atmost max() nonzeros, where max() is given in the constructor. When removing nonzeros, the remaining nonzeros are renumbered. However, only the numbers greater than the number of the first removed nonzero are affected.

The following mathematical operations are provided by class SVectorBase (SVectorBase a, b, c; R x):

OperationDescription  
-= subtraction a -= b
+= addition a += b
* skalar product x = a * b
*= scaling a *= x
maxAbs() infinity norm a.maxAbs() == $\|a\|_{\infty}$
length() eucledian norm a.length() == $\sqrt{a^2}$
length2()square norm a.length2() == $a^2$

Operators += and -= should be used with caution, since no efficient implementation is available. One should think of assigning the left handside vector to a dense VectorBase first and perform the addition on it. The same applies to the scalar product *.

There are two numberings of the nonzeros of an SVectorBase. First, an SVectorBase is supposed to act like a linear algebra VectorBase. An index refers to this view of an SVectorBase: operator[]() is provided which returns the value at the given index of the vector, i.e., 0 for all indices which are not in the set of nonzeros. The other view of SVectorBases is that of a set of nonzeros. The nonzeros are numbered from 0 to size()-1. The methods index(int n) and value(int n) allow to access the index and value of the n 'th nonzero. n is referred to as the number of a nonzero.

Todo:
SVectorBase should get a new implementation. There maybe a lot of memory lost due to padding the Nonzero structure. A better idea seems to be class SVectorBase { int size; int used; int* idx; R* val; }; which for several reasons could be faster or slower. If SVectorBase is changed, also DSVectorBase and SVSet have to be modified.

Definition at line 31 of file dvectorbase.h.

Member Typedef Documentation

typedef Nonzero<R> Element

Definition at line 145 of file svectorbase.h.

Constructor & Destructor Documentation

SVectorBase ( int  n = 0,
Nonzero< R > *  p_mem = 0 
)
explicit

Default constructor.

The constructor expects one memory block where to store the nonzero elements. This must be passed to the constructor, where the number of Nonzeros needs that fit into the memory must be given and a pointer to the beginning of the memory block. Once this memory has been passed, it shall not be modified until the SVectorBase is no longer used.

Definition at line 569 of file svectorbase.h.

Member Function Documentation

void add ( int  i)

Append one uninitialized nonzero.

Definition at line 287 of file svectorbase.h.

void add ( const SVectorBase< R > &  sv)

Append nonzeros of sv.

Definition at line 301 of file svectorbase.h.

void add ( int  n,
const int  i[],
const R  v[] 
)

Append n nonzeros.

Definition at line 307 of file svectorbase.h.

void add ( int  n,
const int  i[],
const S  v[] 
)

Append n nonzeros.

Definition at line 327 of file svectorbase.h.

void add ( int  n,
const Nonzero< R >  e[] 
)

Append n nonzeros.

Definition at line 346 of file svectorbase.h.

SVectorBase<R>& assignArray ( const S *  rowValues,
const int *  rowIndices,
int  rowSize 
)

Assignment operator.

Definition at line 627 of file svectorbase.h.

Referenced by SVSetBase< Real >::add().

int dim ( ) const

Dimension of the vector defined as maximal index + 1.

Definition at line 166 of file svectorbase.h.

Referenced by SSVectorBase< R >::assign(), VectorBase< R >::operator*(), DVectorBase< R >::operator=(), and SSVectorBase< Real >::SSVectorBase().

const Nonzero<R>& element ( int  n) const

The n 'th nonzero element.

Definition at line 227 of file svectorbase.h.

int& index ( int  n)

Reference to index of n 'th nonzero.

Definition at line 236 of file svectorbase.h.

Referenced by SoPlex::_lift(), SoPlex::_performOptIRStable(), SoPlex::_transformEquality(), SoPlex::_transformFeasibility(), SoPlex::_untransformEquality(), SoPlex::_untransformUnbounded(), SPxLPBase< Real >::addCols(), SPxLPBase< Real >::addDualActivity(), SPxLPBase< Real >::added2Set(), SPxLPBase< Real >::addPrimalActivity(), SPxLPBase< Real >::addRows(), SPxScaler::applyScaling(), VectorBase< R >::assign(), SSVectorBase< R >::assign(), SPxLPBase< Real >::changeCol(), SPxLPBase< Real >::changeRow(), SPxScaler::computeScalingVecs(), SPxLPBase< Real >::doAddCol(), SPxLPBase< Real >::doAddCols(), SPxLPBase< Real >::doAddRow(), SPxLPBase< Real >::doAddRows(), SPxLPBase< Real >::doRemoveCol(), SPxLPBase< Real >::doRemoveCols(), SPxLPBase< Real >::doRemoveRow(), SPxLPBase< Real >::doRemoveRows(), SPxMainSM::duplicateCols(), SPxMainSM::duplicateRows(), SPxMainSM::DuplicateRowsPS::DuplicateRowsPS(), SPxMainSM::ForceConstraintPS::execute(), SPxMainSM::FreeZeroObjVariablePS::execute(), SPxMainSM::fixColumn(), SPxMainSM::ForceConstraintPS::ForceConstraintPS(), SPxMainSM::FreeZeroObjVariablePS::FreeZeroObjVariablePS(), SPxWeightST::generate(), SPxMainSM::handleExtremes(), CLUFactor::initFactorMatrix(), CLUFactorRational::initFactorMatrix(), SPxLPBase< Real >::isConsistent(), VectorBase< R >::multAdd(), SSVectorBase< R >::multAdd(), VectorBase< R >::multSub(), VectorBase< R >::operator*(), soplex::operator*(), VectorBase< R >::operator+=(), VectorBase< R >::operator-=(), VectorBase< R >::operator=(), SPxBasis::printMatrixMTX(), SoPlexLegacy::qualConstraintViolation(), SPxSolver::qualConstraintViolation(), SPxSolver::qualSlackViolation(), SPxLPBase< R >::readLPF(), SPxMainSM::removeRowSingleton(), SPxVectorST::setupWeights(), SPxMainSM::simplifyCols(), SPxMainSM::simplifyDual(), SPxMainSM::simplifyRows(), SPxSolver::solve(), and SPxLPBase< R >::writeMPS().

int index ( int  n) const

Index of n 'th nonzero.

Definition at line 245 of file svectorbase.h.

bool isConsistent ( ) const

Consistency check.

Definition at line 691 of file svectorbase.h.

Referenced by UnitVectorBase< R >::isConsistent(), SVSetBase< Real >::operator=(), and SVSetBase< Real >::SVSetBase().

Real length ( ) const

Floating point approximation of euclidian norm (without any approximation guarantee).

Definition at line 471 of file svectorbase.h.

R length2 ( ) const

Squared norm.

Definition at line 477 of file svectorbase.h.

Referenced by SPxWeightPR::computeRP(), SPxSumST::setupWeights(), and SPxSteepPR::setupWeights().

R maxAbs ( ) const

Maximum absolute value, i.e., infinity norm.

Definition at line 439 of file svectorbase.h.

Referenced by SPxWeightST::generate().

Nonzero<R>* mem ( ) const

get pointer to internal memory.

Definition at line 654 of file svectorbase.h.

Referenced by SVSetBase< Real >::deleteVec(), UnitVectorBase< R >::isConsistent(), and SVSetBase< Real >::xtend().

R minAbs ( ) const

Minimum absolute value.

Definition at line 455 of file svectorbase.h.

int number ( int  i) const

Number of index i.

Returns
The number of the first index i. If no index i is available in the IdxSet, -1 is returned. Otherwise, index(number(i)) == i holds.

Definition at line 185 of file svectorbase.h.

Referenced by SPxLPBase< Real >::changeCol(), SPxLPBase< Real >::changeElement(), SPxLPBase< Real >::changeRow(), SPxLPBase< Real >::doRemoveCol(), SPxLPBase< Real >::doRemoveRow(), SPxMainSM::handleExtremes(), SPxLPBase< Real >::isConsistent(), SPxLPBase< R >::readLPF(), and SVSetBase< Real >::remove().

R operator* ( const VectorBase< R > &  w) const

Inner product.

Definition at line 990 of file basevectors.h.

References Nonzero< R >::idx, and Nonzero< R >::val.

R operator* ( const SVectorBase< S > &  w) const

inner product for sparse vectors

Definition at line 514 of file svectorbase.h.

Real operator* ( const SVectorBase< S > &  w) const

specialization for inner product for sparse vectors

Definition at line 725 of file svectorbase.h.

References SVectorBase< R >::element(), Nonzero< R >::idx, SVectorBase< R >::size(), and Nonzero< R >::val.

SVectorBase<R>& operator*= ( const R &  x)

Scaling.

Definition at line 493 of file svectorbase.h.

SVectorBase<R>& operator= ( const SVectorBase< R > &  sv)

Assignment operator.

Definition at line 579 of file svectorbase.h.

SVectorBase<R>& operator= ( const SVectorBase< S > &  sv)

Assignment operator.

Definition at line 603 of file svectorbase.h.

SVectorBase< R > & operator= ( const SSVectorBase< S > &  sv)

Assignment operator.

Definition at line 967 of file basevectors.h.

References Nonzero< R >::idx, SSVectorBase< R >::index(), and SSVectorBase< R >::size().

SVectorBase< Real > & operator= ( const VectorBase< S > &  vec)

Assignment operator (specialization for Real).

Definition at line 936 of file basevectors.h.

References VectorBase< R >::dim(), Nonzero< R >::idx, and Nonzero< R >::val.

R operator[] ( int  i) const

Value to index i.

Definition at line 207 of file svectorbase.h.

void remove ( int  n)

Remove n 'th nonzero.

Definition at line 384 of file svectorbase.h.

void set_max ( int  m)

Set the maximum number of nonzeros in the vector.

Definition at line 667 of file svectorbase.h.

void set_size ( int  s)
void setMem ( int  n,
Nonzero< R > *  elmem 
)
int size ( ) const

Number of used indices.

Definition at line 152 of file svectorbase.h.

Referenced by SoPlex::_ensureDSVectorRationalMemory(), SoPlex::_lift(), SoPlex::_performOptIRStable(), SoPlex::_transformFeasibility(), SoPlex::_untransformUnbounded(), DSVectorBase< Real >::add(), SVectorBase< Real >::add(), SVSetBase< Real >::add(), SVSetBase< Real >::add2(), SPxLPBase< Real >::addCols(), SPxLPBase< Real >::addDualActivity(), SPxLPBase< Real >::added2Set(), SPxLPBase< Real >::addPrimalActivity(), SPxLPBase< Real >::addRows(), SPxScaler::applyScaling(), VectorBase< R >::assign(), SSVectorBase< R >::assign(), SSVectorBase< R >::assign2product1(), SSVectorBase< R >::assign2productAndSetup(), SSVectorBase< R >::assign2productFull(), SSVectorBase< R >::assign2productShort(), SPxBasis::change(), SPxLPBase< Real >::changeCol(), SPxLPBase< Real >::changeRow(), SPxScaler::computeScalingVecs(), SVSetBase< Real >::deleteVec(), SPxLPBase< Real >::doAddCol(), SPxLPBase< Real >::doAddCols(), SPxLPBase< Real >::doAddRow(), SPxLPBase< Real >::doAddRows(), SPxLPBase< Real >::doRemoveCol(), SPxLPBase< Real >::doRemoveCols(), SPxLPBase< Real >::doRemoveRow(), SPxLPBase< Real >::doRemoveRows(), SPxMainSM::duplicateCols(), SPxMainSM::duplicateRows(), SPxMainSM::DuplicateRowsPS::DuplicateRowsPS(), SPxMainSM::ForceConstraintPS::execute(), SPxMainSM::FreeZeroObjVariablePS::execute(), SPxMainSM::fixColumn(), SPxMainSM::ForceConstraintPS::ForceConstraintPS(), SPxMainSM::FreeZeroObjVariablePS::FreeZeroObjVariablePS(), SPxWeightST::generate(), SPxMainSM::handleExtremes(), CLUFactor::initFactorMatrix(), CLUFactorRational::initFactorMatrix(), UnitVectorBase< R >::isConsistent(), SPxLPBase< Real >::isConsistent(), SLUFactor::load(), SLUFactorRational::load(), SPxScaler::maxColRatio(), SPxScaler::maxRowRatio(), VectorBase< R >::multAdd(), SSVectorBase< R >::multAdd(), VectorBase< R >::multSub(), VectorBase< R >::operator*(), SVectorBase< Real >::operator*(), SVectorBase< R >::operator*(), soplex::operator*(), VectorBase< R >::operator+=(), VectorBase< R >::operator-=(), VectorBase< R >::operator=(), DSVectorBase< Real >::operator=(), SVectorBase< Real >::operator=(), SPxBasis::printMatrixMTX(), SoPlexLegacy::qualConstraintViolation(), SPxSolver::qualConstraintViolation(), SPxSolver::qualSlackViolation(), SPxLPBase< R >::readLPF(), SPxMainSM::removeEmpty(), SPxMainSM::removeRowSingleton(), DSVectorBase< Real >::setMax(), DSVectorBase< R >::setMax(), SPxVectorST::setupWeights(), SPxWeightST::setupWeights(), SPxMainSM::simplifyCols(), SPxMainSM::simplifyDual(), SPxMainSM::simplifyRows(), SPxSolver::solve(), SPxLPBase< R >::writeMPS(), and SVSetBase< Real >::xtend().

void sort ( )

Sort nonzeros to increasing indices.

Definition at line 402 of file svectorbase.h.

R& value ( int  n)

Reference to value of n 'th nonzero.

Definition at line 254 of file svectorbase.h.

Referenced by SoPlex::_lift(), SoPlex::_performOptIRStable(), SoPlex::_transformFeasibility(), SoPlex::_untransformUnbounded(), SPxLPBase< Real >::addCols(), SPxLPBase< Real >::addDualActivity(), SPxLPBase< Real >::added2Set(), SPxLPBase< Real >::addPrimalActivity(), SPxLPBase< Real >::addRows(), SPxScaler::applyScaling(), VectorBase< R >::assign(), SSVectorBase< R >::assign(), SPxLPBase< Real >::changeElement(), SPxScaler::computeScalingVecs(), SPxLPBase< Real >::doAddCol(), SPxLPBase< Real >::doAddCols(), SPxLPBase< Real >::doAddRow(), SPxLPBase< Real >::doAddRows(), SPxMainSM::duplicateCols(), SPxMainSM::duplicateRows(), SPxMainSM::ForceConstraintPS::execute(), SPxMainSM::FreeZeroObjVariablePS::execute(), SPxMainSM::fixColumn(), SPxMainSM::FreeZeroObjVariablePS::FreeZeroObjVariablePS(), SPxWeightST::generate(), SPxMainSM::handleExtremes(), CLUFactor::initFactorMatrix(), CLUFactorRational::initFactorMatrix(), SPxLPBase< Real >::isConsistent(), SLUFactor::load(), SPxScaler::maxColRatio(), SPxScaler::maxRowRatio(), VectorBase< R >::multAdd(), SSVectorBase< R >::multAdd(), VectorBase< R >::multSub(), VectorBase< R >::operator*(), soplex::operator*(), VectorBase< R >::operator+=(), VectorBase< R >::operator-=(), VectorBase< R >::operator=(), SPxBasis::printMatrixMTX(), SoPlexLegacy::qualConstraintViolation(), SPxSolver::qualConstraintViolation(), SPxSolver::qualSlackViolation(), SPxLPBase< R >::readLPF(), SPxMainSM::removeRowSingleton(), SPxVectorST::setupWeights(), SPxMainSM::simplifyCols(), SPxMainSM::simplifyDual(), SPxMainSM::simplifyRows(), SPxSolver::solve(), and SPxLPBase< R >::writeMPS().

const R& value ( int  n) const

Value of n 'th nonzero.

Definition at line 263 of file svectorbase.h.

Friends And Related Function Documentation

friend class SVectorBase
friend

Definition at line 129 of file svectorbase.h.

Member Data Documentation

Nonzero<R>* m_elem
private

Definition at line 137 of file svectorbase.h.

Referenced by SVectorBase< Real >::add(), and SVectorBase< Real >::operator=().

int memsize
private

Definition at line 138 of file svectorbase.h.

int memused
private

Definition at line 139 of file svectorbase.h.