A sparse block matrix with compressed row storage. More...

#include <dune/istl/bcrsmatrix.hh>

Classes
class	CreateIterator
	Iterator class for sequential creation of blocks More...

class	RealRowIterator
	Iterator access to matrix rows More...

Public Types
enum	BuildStage { notbuilt =0 , notAllocated =0 , building =1 , rowSizesBuilt =2 , built =3 }

enum	{ blocklevel = B::blocklevel+1 }
	increment block level counter More...

enum	BuildMode { row_wise , random , implicit , unknown }
	we support two modes More...

typedef B::field_type	field_type
	export the type representing the field

typedef B	block_type
	export the type representing the components

typedef A	allocator_type
	export the allocator type

typedef CompressedBlockVectorWindow< B, A >	row_type
	implement row_type with compressed vector

typedef A::size_type	size_type
	The type for the index access and the size.

typedef ::Dune::CompressionStatistics< size_type >	CompressionStatistics
	The type for the statistics object returned by compress()

typedef RealRowIterator< row_type >	iterator
	The iterator over the (mutable matrix rows.

typedef Iterator	RowIterator
	rename the iterators for easier access

typedef row_type::Iterator	ColIterator
	Iterator for the entries of each row.

typedef RealRowIterator< const row_type >	const_iterator
	The const iterator over the matrix rows.

typedef ConstIterator	ConstRowIterator
	rename the const row iterator for easier access

typedef row_type::ConstIterator	ConstColIterator
	Const iterator to the entries of a row.

Public Member Functions
row_type &	operator[] (size_type i)
	random access to the rows

const row_type &	operator[] (size_type i) const
	same for read only access

Iterator	begin ()
	Get iterator to first row.

Iterator	end ()
	Get iterator to one beyond last row.

Iterator	beforeEnd ()

Iterator	beforeBegin ()

ConstIterator	begin () const
	Get const iterator to first row.

ConstIterator	end () const
	Get const iterator to one beyond last row.

ConstIterator	beforeEnd () const

ConstIterator	beforeBegin () const

	BCRSMatrix ()
	an empty matrix

	BCRSMatrix (size_type _n, size_type _m, size_type _nnz, BuildMode bm)
	matrix with known number of nonzeroes

	BCRSMatrix (size_type _n, size_type _m, BuildMode bm)
	matrix with unknown number of nonzeroes

	BCRSMatrix (size_type _n, size_type _m, size_type _avg, double _overflowsize, BuildMode bm)
	construct matrix with a known average number of entries per row More...

	BCRSMatrix (const BCRSMatrix &Mat)
	copy constructor More...

	~BCRSMatrix ()
	destructor

void	setBuildMode (BuildMode bm)
	Sets the build mode of the matrix. More...

void	setSize (size_type rows, size_type columns, size_type nnz=0)
	Set the size of the matrix. More...

void	setImplicitBuildModeParameters (size_type _avg, double _overflow)
	Set parameters needed for creation in implicit build mode. More...

BCRSMatrix &	operator= (const BCRSMatrix &Mat)
	assignment More...

BCRSMatrix &	operator= (const field_type &k)
	Assignment from a scalar.

CreateIterator	createbegin ()
	get initial create iterator

CreateIterator	createend ()
	get create iterator pointing to one after the last block

void	setrowsize (size_type i, size_type s)
	set number of indices in row i to s

size_type	getrowsize (size_type i) const
	get current number of indices in row i

void	incrementrowsize (size_type i, size_type s=1)
	increment size of row i by s (1 by default)

void	endrowsizes ()
	indicate that size of all rows is defined

void	addindex (size_type row, size_type col)
	add index (row,col) to the matrix More...

template<typename It >
void	setIndices (size_type row, It begin, It end)
	Set all column indices for row from the given iterator range. More...

void	endindices ()
	indicate that all indices are defined, check consistency

B &	entry (size_type row, size_type col)
	Returns reference to entry (row,col) of the matrix. More...

CompressionStatistics	compress ()
	Finishes the buildstage in implicit mode. More...

BCRSMatrix &	*operator=** (const field_type &k)
	vector space multiplication with scalar

BCRSMatrix &	operator/= (const field_type &k)
	vector space division by scalar

BCRSMatrix &	operator+= (const BCRSMatrix &b)
	Add the entries of another matrix to this one. More...

BCRSMatrix &	operator-= (const BCRSMatrix &b)
	Substract the entries of another matrix to this one. More...

BCRSMatrix &	axpy (field_type alpha, const BCRSMatrix &b)
	Add the scaled entries of another matrix to this one. More...

template<class X , class Y >
void	mv (const X &x, Y &y) const
	y = A x

template<class X , class Y >
void	umv (const X &x, Y &y) const
	y += A x

template<class X , class Y >
void	mmv (const X &x, Y &y) const
	y -= A x

template<class X , class Y >
void	usmv (const field_type &alpha, const X &x, Y &y) const
	y += alpha A x

template<class X , class Y >
void	mtv (const X &x, Y &y) const
	y = A^T x

template<class X , class Y >
void	umtv (const X &x, Y &y) const
	y += A^T x

template<class X , class Y >
void	mmtv (const X &x, Y &y) const
	y -= A^T x

template<class X , class Y >
void	usmtv (const field_type &alpha, const X &x, Y &y) const
	y += alpha A^T x

template<class X , class Y >
void	umhv (const X &x, Y &y) const
	y += A^H x

template<class X , class Y >
void	mmhv (const X &x, Y &y) const
	y -= A^H x

template<class X , class Y >
void	usmhv (const field_type &alpha, const X &x, Y &y) const
	y += alpha A^H x

FieldTraits< field_type >::real_type	frobenius_norm2 () const
	square of frobenius norm, need for block recursion

FieldTraits< field_type >::real_type	frobenius_norm () const
	frobenius norm: sqrt(sum over squared values of entries)

FieldTraits< field_type >::real_type	infinity_norm () const
	infinity norm (row sum norm, how to generalize for blocks?)

FieldTraits< field_type >::real_type	infinity_norm_real () const
	simplified infinity norm (uses Manhattan norm for complex values)

size_type	N () const
	number of rows (counted in blocks)

size_type	M () const
	number of columns (counted in blocks)

size_type	nonzeroes () const
	number of blocks that are stored (the number of blocks that possibly are nonzero)

BuildStage	buildStage () const
	The current build stage of the matrix.

BuildMode	buildMode () const
	The currently selected build mode of the matrix.

bool	exists (size_type i, size_type j) const
	return true if (i,j) is in pattern

Detailed Description

template<class B, class A = std::allocator>
class Dune::BCRSMatrix< B, A >

A sparse block matrix with compressed row storage.

Implements a block compressed row storage scheme. The block type B can be any type implementing the matrix interface.

Different ways to build up a compressed row storage matrix are supported:

Row-wise scheme
Random scheme
implicit scheme

Error checking: no error checking is provided normally. Setting the compile time switch DUNE_ISTL_WITH_CHECKING enables error checking.

Details:

Row-wise scheme

Rows are built up in sequential order. Size of the row and the column indices are defined. A row can be used as soon as it is initialized. With respect to memory there are two variants of this scheme: (a) number of non-zeroes known in advance (application finite difference schemes), (b) number of non-zeroes not known in advance (application: Sparse LU, ILU(n)).

#include<dune/common/fmatrix.hh>
#include<dune/istl/bcrsmatrix.hh>
 
...
 
typedef FieldMatrix<double,2,2> M;
// third parameter is an optional upper bound for the number
// of nonzeros. If given the matrix will use one array for all values
// as opposed to one for each row.
BCRSMatrix<M> B(4,4,12,BCRSMatrix<M>::row_wise);
 
typedef BCRSMatrix<M>::CreateIterator Iter;
 
for(Iter row=B.createbegin(); row!=B.createend(); ++row){
  // Add nonzeros for left neighbour, diagonal and right neighbour
  if(row.index()>0)
    row.insert(row.index()-1);
  row.insert(row.index());
  if(row.index()<B.N()-1)
    row.insert(row.index()+1);
}
 
// Now the sparsity pattern is fully set up and we can add values
 
B[0][0]=2;
...

Random scheme

For general finite element implementations the number of rows n is known, the number of non-zeroes might also be known (e.g. #edges + #nodes for P1) but the size of a row and the indices of a row can not be defined in sequential order.

#include<dune/common/fmatrix.hh>
#include<dune/istl/bcrsmatrix.hh>
 
...
 
typedef FieldMatrix<double,2,2> M;
BCRSMatrix<M> B(4,4,BCRSMatrix<M>::random);
 
// initially set row size for each row
B.setrowsize(0,1);
B.setrowsize(3,4);
B.setrowsize(2,1);
B.setrowsize(1,1);
// increase row size for row 2
B.incrementrowsize(2)
 
// finalize row setup phase
B.endrowsizes();
 
// add column entries to rows
B.addindex(0,0);
B.addindex(3,1);
B.addindex(2,2);
B.addindex(1,1);
B.addindex(2,0);
B.addindex(3,2);
B.addindex(3,0);
B.addindex(3,3);
 
// finalize column setup phase
B.endindices();
 
// set entries using the random access operator
B[0][0] = 1;
B[1][1] = 2;
B[2][0] = 3;
B[2][2] = 4;
B[3][1] = 5;
B[3][2] = 6;
B[3][0] = 7;
B[3][3] = 8;

implicit scheme With the above Random Scheme, the sparsity pattern has to be determined and stored before the matrix is assembled. This leads to increased memory usage and computation time. Often, one has good a priori knowledge about the number of entries a row contains on average. implicit mode tries to make use of that knowledge by allocating memory based on that average. Entries in rows with more non-zeroes than the average value are written to an overflow area during the initial assembly phase, up to a specified maximum number of overflow entries that must not be exceeded. After all indices are added a compression step optimizes the matrix and integrates any entries from the overflow area into the standard BCRS storage scheme.

To use this mode use the following methods:

Construct the matrix via

BCRSMatrix(size_type _n, size_type _m, size_type _avg, double _overflowsize, BuildMode bm)
void setSize(size_type rows, size_type columns, size_type nnz=0) after setting the buildmode to implicit and the compression parameters via setImplicitBuildModeParameters(size_type _avg, double _overflow)

Here, the parameter _avg denotes the average number of matrix entries per row, while _overflowsize reserves _n * _overflowsize * _avg entries in the overflow area.

Warning: If you exceed this number of overflow entries during the assembly phase, matrix construction fails and an exception will be thrown!

Start filling your matrix by calling entry(size_type row, size_type col), which returns the corresponding matrix entry, creating it on the fly if it did not exist yet. Please note that this method may be slightly slower than accessing entries via matrix[row][col] after the initial assembly because of the additional overhead of searching the overflow area. The matrix pattern is created by implicitly by simply accessing nonzero entries during the initial matrix assembly.

After the entry-method has been called for each nonzero matrix entry at least once, you can call compress() to reorganize the data into the standard BCRS data layout, which sets the matrix state to built. No matrix entries may be added after this step. compress() returns a value of type Dune::CompressionStatistics, which you can inspect to tune the construction parameters _avg and _overflowsize.

Use of copy constructor, assignment operator and matrix vector arithmetics are not supported until the matrix is fully built.

In the following sample code, an array with 28 entries will be reserved

#include<dune/common/fmatrix.hh>
#include<dune/istl/bcrsmatrix.hh>
 
typedef Dune::BCRSMatrix<Dune::FieldMatrix<double,1,1> > M;
M m(10, 10, 2, 0.4, M::implicit);
 
//fill in some arbitrary entries, even operations on these would be possible,
//you get a reference to the entry! the order of these statements is irrelevant!
m.entry(0,0) = 0.;
m.entry(8,0) = 0.;
m.entry(1,8) = 0.; m.entry(1,0) = 0.; m.entry(1,5) = 0.;
m.entry(2,0) = 0.;
m.entry(3,5) = 0.; m.entry(3,0) = 0.;  m.entry(3,8) = 0.;
m.entry(4,0) = 0.;
m.entry(9,0) = 0.; m.entry(9,5) = 0.; m.entry(9,8) = 0.;
m.entry(5,0) = 0.; m.entry(5,5) = 0.; m.entry(5,8) = 0.;
m.entry(6,0) = 0.;
m.entry(7,0) = 0.; m.entry(7,5) = 0.; m.entry(7,8) = 0.;
 
 
 
// internally the index array now looks like this (second row are the row pointers):
// xxxxxxxx0x800x500x050x050x05
// ........|.|.|.|.|.|.|.|.|.|.
// and the overflow area contains (1,5,0.0), (3,8,0.0), (5,8,0.0), (7,8,0.0), (9,8,0.0)
// the data array has similar structure.
 
//finish building by compressing the array
Dune::CompressionStatistics<M::size_type> stats = m.compress();
 
// internally the index array now looks like this:
// 00580058005800580058xxxxxxxx
// ||..||..||..||..||..........

Member Enumeration Documentation

◆ anonymous enum

template<class B , class A = std::allocator>

anonymous enum

increment block level counter

Enumerator
blocklevel	The number of blocklevels the matrix contains.

◆ BuildMode

template<class B , class A = std::allocator>

enum Dune::BCRSMatrix::BuildMode

we support two modes

Enumerator
row_wise	Build in a row-wise manner. Rows are built up in sequential order. Size of the row and the column indices are defined. A row can be used as soon as it is initialized. With respect to memory there are two variants of this scheme: (a) number of non-zeroes known in advance (application finite difference schemes), (b) number of non-zeroes not known in advance (application: Sparse LU, ILU(n)).
random	Build entries randomly. For general finite element implementations the number of rows n is known, the number of non-zeroes might also be known (e.g. #edges + #nodes for P1) but the size of a row and the indices of a row can not be defined in sequential order.
implicit	Build entries randomly with an educated guess on entries per row. Allows random order generation as in random mode, but row sizes do not need to be given first. Instead an average number of non-zeroes per row is passed to the constructor. Matrix setup is finished with compress(), full data access during build stage is possible.
unknown	Build mode not set!

◆ BuildStage

template<class B , class A = std::allocator>

enum Dune::BCRSMatrix::BuildStage

Enumerator
notbuilt	Matrix is not built at all, no memory has been allocated, build mode and size can still be set.
notAllocated	Matrix is not built at all, no memory has been allocated, build mode and size can still be set.
building	Matrix is currently being built, some memory has been allocated, build mode and size are fixed.
rowSizesBuilt	The row sizes of the matrix are known. Only used in random mode.
built	The matrix structure is fully built.

Constructor & Destructor Documentation

◆ BCRSMatrix() [1/2]

template<class B , class A = std::allocator>

Dune::BCRSMatrix< B, A >::BCRSMatrix	(	size_type	_n,
		size_type	_m,
		size_type	_avg,
		double	_overflowsize,
		BuildMode	bm
	)

inline

construct matrix with a known average number of entries per row

Constructs a matrix in implicit buildmode.

Parameters

_n	number of rows of the matrix
_m	number of columns of the matrix
_avg	expected average number of entries per row
_overflowsize	fraction of _n*_avg which is expected to be needed for elements that exceed _avg entries per row.

References DUNE_THROW, and Dune::BCRSMatrix< B, A >::implicit.

◆ BCRSMatrix() [2/2]

template<class B , class A = std::allocator>

Dune::BCRSMatrix< B, A >::BCRSMatrix ( const BCRSMatrix< B, A > & Mat )

inline

copy constructor

Does a deep copy as expected.

References Dune::BCRSMatrix< B, A >::built, DUNE_THROW, Dune::CompressedBlockVectorWindow< B, A >::getsize(), and Dune::BCRSMatrix< B, A >::notAllocated.

Member Function Documentation

◆ addindex()

template<class B , class A = std::allocator>

void Dune::BCRSMatrix< B, A >::addindex	(	size_type	row,
		size_type	col
	)

inline

add index (row,col) to the matrix

This method can only be used when building the BCRSMatrix in random mode.

addindex adds a new column entry to the row. If this column entry already exists, nothing is done.

Don't call addindex after the setup phase is finished (after endindices is called).

◆ axpy()

template<class B , class A = std::allocator>

BCRSMatrix & Dune::BCRSMatrix< B, A >::axpy	(	field_type	alpha,
		const BCRSMatrix< B, A > &	b
	)

inline

Add the scaled entries of another matrix to this one.

Matrix axpy operation: *this += alpha * b

Parameters

alpha	Scaling factor.
b	The matrix to add to this one. Its sparsity pattern has to be subset of the sparsity pattern of this matrix.

References Dune::BCRSMatrix< B, A >::begin(), Dune::BCRSMatrix< B, A >::built, DUNE_THROW, Dune::BCRSMatrix< B, A >::end(), Dune::BCRSMatrix< B, A >::M(), and Dune::BCRSMatrix< B, A >::N().

◆ beforeBegin() [1/2]

template<class B , class A = std::allocator>

Iterator Dune::BCRSMatrix< B, A >::beforeBegin ( )

inline

Returns: an iterator that is positioned before the first row of the matrix.

◆ beforeBegin() [2/2]

template<class B , class A = std::allocator>

ConstIterator Dune::BCRSMatrix< B, A >::beforeBegin ( ) const

inline

Returns: an iterator that is positioned before the first row of the matrix.

◆ beforeEnd() [1/2]

template<class B , class A = std::allocator>

Iterator Dune::BCRSMatrix< B, A >::beforeEnd ( )

inline

Returns: an iterator that is positioned before the end iterator of the rows, i.e. at the last row.

◆ beforeEnd() [2/2]

template<class B , class A = std::allocator>

ConstIterator Dune::BCRSMatrix< B, A >::beforeEnd ( ) const

inline

Returns: an iterator that is positioned before the end iterator of the rows. i.e. at the last row.

◆ compress()

template<class B , class A = std::allocator>

CompressionStatistics Dune::BCRSMatrix< B, A >::compress ( )

inline

Finishes the buildstage in implicit mode.

Performs compression of index and data arrays with linear complexity in the number of nonzeroes.

After calling this method, the matrix is in the built state and no more entries can be added.

Returns: An object with some statistics about the compression for future optimization.

References Dune::CompressionStatistics< size_type >::avg, Dune::BCRSMatrix< B, A >::begin(), Dune::BCRSMatrix< B, A >::building, Dune::BCRSMatrix< B, A >::built, DUNE_THROW, Dune::shared_ptr< T >::get(), Dune::CompressedBlockVectorWindow< B, A >::getindexptr(), Dune::CompressedBlockVectorWindow< B, A >::getsize(), Dune::BCRSMatrix< B, A >::implicit, Dune::CompressionStatistics< size_type >::maximum, Dune::CompressionStatistics< size_type >::mem_ratio, Dune::BCRSMatrix< B, A >::notAllocated, Dune::CompressionStatistics< size_type >::overflow_total, Dune::CompressedBlockVectorWindow< B, A >::setindexptr(), Dune::CompressedBlockVectorWindow< B, A >::setptr(), and Dune::CompressedBlockVectorWindow< B, A >::setsize().

◆ entry()

template<class B , class A = std::allocator>

B & Dune::BCRSMatrix< B, A >::entry	(	size_type	row,
		size_type	col
	)

inline

Returns reference to entry (row,col) of the matrix.

This method can only be used when the matrix is in implicit building mode.

A reference to entry (row, col) of the matrix is returned. If entry (row, col) is accessed for the first time, it is created on the fly.

This method can only be used while building the matrix, after compression operator[] gives a much better performance.

◆ operator+=()

template<class B , class A = std::allocator>

BCRSMatrix & Dune::BCRSMatrix< B, A >::operator+= ( const BCRSMatrix< B, A > & b )

inline

Add the entries of another matrix to this one.

Parameters

b	The matrix to add to this one. Its sparsity pattern has to be subset of the sparsity pattern of this matrix.

References Dune::BCRSMatrix< B, A >::begin(), Dune::BCRSMatrix< B, A >::built, DUNE_THROW, Dune::BCRSMatrix< B, A >::end(), Dune::BCRSMatrix< B, A >::M(), and Dune::BCRSMatrix< B, A >::N().

◆ operator-=()

template<class B , class A = std::allocator>

BCRSMatrix & Dune::BCRSMatrix< B, A >::operator-= ( const BCRSMatrix< B, A > & b )

inline

Substract the entries of another matrix to this one.

Parameters

b	The matrix to add to this one. Its sparsity pattern has to be subset of the sparsity pattern of this matrix.

References Dune::BCRSMatrix< B, A >::begin(), Dune::BCRSMatrix< B, A >::built, DUNE_THROW, Dune::BCRSMatrix< B, A >::end(), Dune::BCRSMatrix< B, A >::M(), and Dune::BCRSMatrix< B, A >::N().

◆ operator=()

template<class B , class A = std::allocator>

BCRSMatrix & Dune::BCRSMatrix< B, A >::operator= ( const BCRSMatrix< B, A > & Mat )

inline

assignment

Frees and reallocates space. Both sparsity pattern and values are set from Mat.

References Dune::BCRSMatrix< B, A >::built, DUNE_THROW, Dune::CompressedBlockVectorWindow< B, A >::getsize(), and Dune::BCRSMatrix< B, A >::notAllocated.

Referenced by Dune::BDMatrix< B, A >::operator=(), and Dune::BTDMatrix< B, A >::operator=().

◆ setBuildMode()

template<class B , class A = std::allocator>

void Dune::BCRSMatrix< B, A >::setBuildMode ( BuildMode bm )

inline

Sets the build mode of the matrix.

Parameters

bm	The build mode to use.

References Dune::BCRSMatrix< B, A >::building, DUNE_THROW, Dune::BCRSMatrix< B, A >::notAllocated, Dune::BCRSMatrix< B, A >::random, Dune::BCRSMatrix< B, A >::row_wise, and Dune::BCRSMatrix< B, A >::unknown.

◆ setImplicitBuildModeParameters()

template<class B , class A = std::allocator>

void Dune::BCRSMatrix< B, A >::setImplicitBuildModeParameters	(	size_type	_avg,
		double	_overflow
	)

inline

Set parameters needed for creation in implicit build mode.

Use this method before setSize() to define storage behaviour of a matrix in implicit build mode

Parameters

_avg	expected average number of entries per row
_overflowsize	fraction of _n*_avg which is expected to be needed for elements that exceed _avg entries per row.

References DUNE_THROW, and Dune::BCRSMatrix< B, A >::notAllocated.

◆ setIndices()

template<class B , class A = std::allocator>

template<typename It >

void Dune::BCRSMatrix< B, A >::setIndices	(	size_type	row,
		It	begin,
		It	end
	)

inline

Set all column indices for row from the given iterator range.

The iterator range has to be of the same length as the previously set row size. The entries in the iterator range do not have to be in any particular order, but must not contain duplicate values.

Calling this method overwrites any previously set column indices!

◆ setSize()

template<class B , class A = std::allocator>

void Dune::BCRSMatrix< B, A >::setSize	(	size_type	rows,
		size_type	columns,
		size_type	nnz = `0`
	)

inline

Set the size of the matrix.

Sets the number of rows and columns of the matrix and allocates the memory needed for the storage of the matrix entries.

Warning: After calling this methods on an already allocated (and probably setup matrix) results in all the structure and data being deleted. I.~e. one has to setup the matrix again.

Parameters

rows	The number of rows the matrix should contain.
columns	the number of columns the matrix should contain.
nnz	The number of nonzero entries the matrix should hold (if omitted defaults to 0). Must be omitted in implicit mode.

References DUNE_THROW, and Dune::BCRSMatrix< B, A >::implicit.

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

dune/istl/bcrsmatrix.hh

DUNE Distributed and Unified Numerics Environment

Dune Core Modules (2.3.1)

Classes

Public Types

Public Member Functions

Detailed Description

Member Enumeration Documentation

◆ anonymous enum

◆ BuildMode

◆ BuildStage

Constructor & Destructor Documentation

◆ BCRSMatrix() [1/2]

◆ BCRSMatrix() [2/2]

Member Function Documentation

◆ addindex()

◆ axpy()

◆ beforeBegin() [1/2]

◆ beforeBegin() [2/2]

◆ beforeEnd() [1/2]

◆ beforeEnd() [2/2]

◆ compress()

◆ entry()

◆ operator+=()

◆ operator-=()

◆ operator=()

◆ setBuildMode()

◆ setImplicitBuildModeParameters()

◆ setIndices()

◆ setSize()