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>

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	pos (int i) const
	Position of index `i`. More...

R	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
R	maxAbs () const
	Maximum absolute value, i.e., infinity norm. More...

R	minAbs () const
	Minimum absolute value. More...

Real	length () const
	Floating point approximation of euclidian norm (without any approximation guarantee). More...

R	length2 () const
	Squared norm. More...

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

R	operator* (const VectorBase< R > &w) const
	Inner product. More...

template<class S >
R	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...

SVectorBase< Real > &	scaleAssign (int scaleExp, const SVectorBase< Real > &sv)
	scale and assign More...

SVectorBase< Real > &	scaleAssign (const int *scaleExp, const SVectorBase< Real > &sv, bool negateExp=false)
	scale and assign 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):

Operation	Description
`-=`	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

◆ Element

typedef Nonzero<R> Element

Definition at line 146 of file svectorbase.h.

Constructor & Destructor Documentation

◆ SVectorBase()

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 613 of file svectorbase.h.

Member Function Documentation

◆ add() [1/6]

void add	(	int	i,
		const R &	v
	)

Append one nonzero (i,v).

Definition at line 271 of file svectorbase.h.

Referenced by SoPlex::_lift(), DSVectorBase< Real >::add(), SVSetBase< Rational >::add(), SVSetBase< Rational >::add2(), SPxMainSM::FreeZeroObjVariablePS::execute(), soplex::initConstVecs(), SVSetBase< Rational >::operator=(), and UnitVectorBase< R >::UnitVectorBase().

◆ add() [2/6]

void add ( int i )

Append one uninitialized nonzero.

Definition at line 289 of file svectorbase.h.

◆ add() [3/6]

void add ( const SVectorBase< R > & sv )

Append nonzeros of sv.

Definition at line 303 of file svectorbase.h.

◆ add() [4/6]

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

Append n nonzeros.

Definition at line 309 of file svectorbase.h.

◆ add() [5/6]

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

Append n nonzeros.

Definition at line 339 of file svectorbase.h.

◆ add() [6/6]

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

Append n nonzeros.

Definition at line 368 of file svectorbase.h.

◆ assignArray()

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

Assignment operator.

Definition at line 738 of file svectorbase.h.

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

◆ clear()

◆ dim()

int dim ( ) const

Dimension of the vector defined as maximal index + 1.

Definition at line 167 of file svectorbase.h.

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

◆ element() [1/2]

Nonzero<R>& element ( int n )

Reference to the n 'th nonzero element.

Definition at line 217 of file svectorbase.h.

Referenced by SSVectorBase< Real >::assign2product1(), SSVectorBase< Real >::assign2productAndSetup(), SSVectorBase< Real >::assign2productFull(), SSVectorBase< Real >::assign2productShort(), and SVectorBase< Real >::operator*().

◆ element() [2/2]

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

The n 'th nonzero element.

Definition at line 226 of file svectorbase.h.

◆ index() [1/2]

int& index ( int n )

Reference to index of n 'th nonzero.

Definition at line 235 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(), SPxMainSM::aggregateVars(), SPxScaler::applyScaling(), VectorBase< Real >::assign(), SSVectorBase< Real >::assign(), SPxLPBase< Real >::changeCol(), SPxLPBase< Real >::changeRow(), SPxMainSM::checkSolution(), SPxEquiliSC::computeEquiExpVec(), SPxMainSM::computeMinMaxResidualActivity(), SPxScaler::computeScaleExp(), soplex::computeScalingVec(), 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(), SPxScaler::getColMaxAbsUnscaled(), SPxScaler::getColMinAbsUnscaled(), SPxScaler::getColUnscaled(), SPxScaler::getRowMaxAbsUnscaled(), SPxScaler::getRowMinAbsUnscaled(), SPxScaler::getRowUnscaled(), SPxMainSM::handleExtremes(), soplex::initConstVecs(), CLUFactor::initFactorMatrix(), CLUFactorRational::initFactorMatrix(), SPxLPBase< Real >::isConsistent(), soplex::maxPrescaledRatio(), VectorBase< Real >::multAdd(), SSVectorBase< Real >::multAdd(), SPxMainSM::multiaggregation(), VectorBase< Real >::multSub(), VectorBase< Real >::operator*(), soplex::operator*(), VectorBase< Real >::operator+=(), VectorBase< Real >::operator-=(), VectorBase< Real >::operator=(), SPxBasis::printMatrixMTX(), SPxSolver::qualConstraintViolation(), SPxSolver::qualSlackViolation(), SPxLPBase< Real >::readLPF(), SPxMainSM::removeRowSingleton(), SVectorBase< Real >::scaleAssign(), SPxVectorST::setupWeights(), SPxMainSM::simplifyCols(), SPxMainSM::simplifyDual(), SPxMainSM::simplifyRows(), SPxSolver::solve(), SPxMainSM::trivialHeuristic(), SPxScaler::unscale(), and SPxLPBase< Real >::writeMPS().

◆ index() [2/2]

int index ( int n ) const

Index of n 'th nonzero.

Definition at line 244 of file svectorbase.h.

◆ isConsistent()

bool isConsistent ( ) const

Consistency check.

Definition at line 803 of file svectorbase.h.

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

◆ length()

Real length ( ) const

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

Definition at line 507 of file svectorbase.h.

◆ length2()

R length2 ( ) const

Squared norm.

Definition at line 513 of file svectorbase.h.

Referenced by SPxSteepPR::setupWeights().

◆ max()

int max ( ) const

Maximal number of indices.

Definition at line 160 of file svectorbase.h.

Referenced by SoPlex::_ensureDSVectorRationalMemory(), SVSetBase< Rational >::deleteVec(), SVSetBase< Rational >::ensurePSVec(), UnitVectorBase< R >::isConsistent(), and SVSetBase< Rational >::xtend().

◆ maxAbs()

R maxAbs ( ) const

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

Definition at line 475 of file svectorbase.h.

Referenced by SPxWeightST::generate().

◆ mem()

Nonzero<R>* mem ( ) const

get pointer to internal memory.

Definition at line 766 of file svectorbase.h.

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

◆ minAbs()

R minAbs ( ) const

Minimum absolute value.

Definition at line 491 of file svectorbase.h.

◆ operator*() [1/3]

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

Inner product.

Definition at line 1039 of file basevectors.h.

◆ operator*() [2/3]

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

inner product for sparse vectors

Definition at line 550 of file svectorbase.h.

◆ operator*() [3/3]

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

specialization for inner product for sparse vectors

Definition at line 839 of file svectorbase.h.

◆ operator*=()

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

Scaling.

Definition at line 529 of file svectorbase.h.

◆ operator=() [1/5]

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

Assignment operator.

Definition at line 944 of file basevectors.h.

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

◆ operator=() [2/5]

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

Assignment operator.

Definition at line 623 of file svectorbase.h.

◆ operator=() [3/5]

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

Assignment operator.

Definition at line 655 of file svectorbase.h.

◆ operator=() [4/5]

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

Assignment operator.

Definition at line 1006 of file basevectors.h.

◆ operator=() [5/5]

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

Assignment operator (specialization for Real).

Definition at line 975 of file basevectors.h.

◆ operator[]()

R operator[] ( int i ) const

Value to index i.

Definition at line 206 of file svectorbase.h.

◆ pos()

int pos ( int i ) const

Position of index i.

Returns: Finds the position of the first index i in the index set. If no such index i is found, -1 is returned. Otherwise, index(pos(i)) == i holds.

Definition at line 186 of file svectorbase.h.

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

◆ remove() [1/2]

void remove	(	int	n,
		int	m
	)

Remove nonzeros n thru m.

Definition at line 394 of file svectorbase.h.

Referenced by SoPlex::_updateComplementaryDualFixedPrimalVars(), SPxLPBase< Real >::changeCol(), SPxLPBase< Real >::changeElement(), SPxLPBase< Real >::changeRow(), SPxLPBase< Real >::doRemoveCol(), SPxLPBase< Real >::doRemoveCols(), SPxLPBase< Real >::doRemoveRow(), SPxLPBase< Real >::doRemoveRows(), SPxMainSM::handleExtremes(), and SPxLPBase< Real >::readLPF().

◆ remove() [2/2]

void remove ( int n )

Remove n 'th nonzero.

Definition at line 418 of file svectorbase.h.

◆ scaleAssign() [1/2]

SVectorBase<Real>& scaleAssign	(	int	scaleExp,
		const SVectorBase< Real > &	sv
	)

scale and assign

Definition at line 686 of file svectorbase.h.

◆ scaleAssign() [2/2]

SVectorBase<Real>& scaleAssign	(	const int *	scaleExp,
		const SVectorBase< Real > &	sv,
		bool	negateExp = `false`
	)

scale and assign

Definition at line 705 of file svectorbase.h.

◆ set_max()

void set_max ( int m )

Set the maximum number of nonzeros in the vector.

Definition at line 779 of file svectorbase.h.

◆ set_size()

void set_size ( int s )

Set size of the vector.

Definition at line 772 of file svectorbase.h.

Referenced by SVSetBase< Rational >::deleteVec(), DSVectorBase< Real >::setMax(), and SVSetBase< Rational >::xtend().

◆ setMem()

void setMem	(	int	n,
		Nonzero< R > *	elmem
	)

Set the memory area where the nonzeros will be stored.

Definition at line 786 of file svectorbase.h.

Referenced by DSVectorBase< Real >::allocMem(), SVSetBase< Rational >::deleteVec(), DSVectorBase< Real >::setMax(), and SVSetBase< Rational >::xtend().

◆ size()

int size ( ) const

Number of used indices.

Definition at line 153 of file svectorbase.h.

◆ sort()

void sort ( )

Sort nonzeros to increasing indices.

Definition at line 437 of file svectorbase.h.

Referenced by soplex::initConstVecs().

◆ value() [1/2]

R& value ( int n )

Reference to value of n 'th nonzero.

Definition at line 253 of file svectorbase.h.

◆ value() [2/2]

const R& value ( int n ) const

Value of n 'th nonzero.

Definition at line 262 of file svectorbase.h.

Friends And Related Function Documentation

◆ SVectorBase

friend class SVectorBase

friend

Definition at line 130 of file svectorbase.h.

Member Data Documentation

◆ m_elem

Nonzero<R>* m_elem

private

Definition at line 138 of file svectorbase.h.

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

◆ memsize

int memsize

private

Definition at line 139 of file svectorbase.h.

◆ memused

int memused

private

Definition at line 140 of file svectorbase.h.

SoPlex

Public Types

Public Member Functions

Private Attributes

Friends

Detailed Description

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

Member Typedef Documentation

◆ Element

Constructor & Destructor Documentation

◆ SVectorBase()

Member Function Documentation

◆ add() [1/6]

◆ add() [2/6]

◆ add() [3/6]

◆ add() [4/6]

◆ add() [5/6]

◆ add() [6/6]

◆ assignArray()

◆ clear()

◆ dim()

◆ element() [1/2]

◆ element() [2/2]

◆ index() [1/2]

◆ index() [2/2]

◆ isConsistent()

◆ length()

◆ length2()

◆ max()

◆ maxAbs()

◆ mem()

◆ minAbs()

◆ operator*() [1/3]

◆ operator*() [2/3]

◆ operator*() [3/3]

◆ operator*=()

◆ operator=() [1/5]

◆ operator=() [2/5]

◆ operator=() [3/5]

◆ operator=() [4/5]

◆ operator=() [5/5]

◆ operator[]()

◆ pos()

◆ remove() [1/2]

◆ remove() [2/2]

◆ scaleAssign() [1/2]

◆ scaleAssign() [2/2]

◆ set_max()

◆ set_size()

◆ setMem()

◆ size()

◆ sort()

◆ value() [1/2]

◆ value() [2/2]

Friends And Related Function Documentation

◆ SVectorBase

Member Data Documentation

◆ m_elem

◆ memsize

◆ memused

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