|
row_type & | operator[] (size_type i) |
| random access to the rows More...
|
|
const row_type & | operator[] (size_type i) const |
| same for read only access More...
|
|
Iterator | begin () |
| Get iterator to first row. More...
|
|
Iterator | end () |
| Get iterator to one beyond last row. More...
|
|
Iterator | beforeEnd () |
|
Iterator | beforeBegin () |
|
ConstIterator | begin () const |
| Get const iterator to first row. More...
|
|
ConstIterator | end () const |
| Get const iterator to one beyond last row. More...
|
|
ConstIterator | beforeEnd () const |
|
ConstIterator | beforeBegin () const |
|
| BCRSMatrix () |
| an empty matrix More...
|
|
| BCRSMatrix (size_type _n, size_type _m, size_type _nnz, BuildMode bm) |
| matrix with known number of nonzeroes More...
|
|
| BCRSMatrix (size_type _n, size_type _m, BuildMode bm) |
| matrix with unknown number of nonzeroes More...
|
|
| BCRSMatrix (size_type _n, size_type _m, size_type _avg, double compressionBufferSize, BuildMode bm) |
| construct matrix with a known average number of entries per row More...
|
|
| BCRSMatrix (const BCRSMatrix &Mat) |
| copy constructor More...
|
|
| ~BCRSMatrix () |
| destructor More...
|
|
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 compressionBufferSize) |
| 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. More...
|
|
CreateIterator | createbegin () |
| get initial create iterator More...
|
|
CreateIterator | createend () |
| get create iterator pointing to one after the last block More...
|
|
void | setrowsize (size_type i, size_type s) |
| Set number of indices in row i to s. More...
|
|
size_type | getrowsize (size_type i) const |
| get current number of indices in row i More...
|
|
void | incrementrowsize (size_type i, size_type s=1) |
| increment size of row i by s (1 by default) More...
|
|
void | endrowsizes () |
| indicate that size of all rows is defined More...
|
|
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 More...
|
|
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 More...
|
|
BCRSMatrix & | operator/= (const field_type &k) |
| vector space division by scalar More...
|
|
BCRSMatrix & | operator+= (const BCRSMatrix &b) |
| Add the entries of another matrix to this one. More...
|
|
BCRSMatrix & | operator-= (const BCRSMatrix &b) |
| Subtract the entries of another matrix from 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 More...
|
|
template<class X , class Y > |
void | umv (const X &x, Y &y) const |
| y += A x More...
|
|
template<class X , class Y > |
void | mmv (const X &x, Y &y) const |
| y -= A x More...
|
|
template<class X , class Y , class F > |
void | usmv (F &&alpha, const X &x, Y &y) const |
| y += alpha A x More...
|
|
template<class X , class Y > |
void | mtv (const X &x, Y &y) const |
| y = A^T x More...
|
|
template<class X , class Y > |
void | umtv (const X &x, Y &y) const |
| y += A^T x More...
|
|
template<class X , class Y > |
void | mmtv (const X &x, Y &y) const |
| y -= A^T x More...
|
|
template<class X , class Y > |
void | usmtv (const field_type &alpha, const X &x, Y &y) const |
| y += alpha A^T x More...
|
|
template<class X , class Y > |
void | umhv (const X &x, Y &y) const |
| y += A^H x More...
|
|
template<class X , class Y > |
void | mmhv (const X &x, Y &y) const |
| y -= A^H x More...
|
|
template<class X , class Y > |
void | usmhv (const field_type &alpha, const X &x, Y &y) const |
| y += alpha A^H x More...
|
|
FieldTraits< field_type >::real_type | frobenius_norm2 () const |
| square of frobenius norm, need for block recursion More...
|
|
FieldTraits< field_type >::real_type | frobenius_norm () const |
| frobenius norm: sqrt(sum over squared values of entries) More...
|
|
template<typename ft = field_type, typename std::enable_if<!HasNaN< ft >::value, int >::type = 0> |
FieldTraits< ft >::real_type | infinity_norm () const |
| infinity norm (row sum norm, how to generalize for blocks?) More...
|
|
template<typename ft = field_type, typename std::enable_if<!HasNaN< ft >::value, int >::type = 0> |
FieldTraits< ft >::real_type | infinity_norm_real () const |
| simplified infinity norm (uses Manhattan norm for complex values) More...
|
|
template<typename ft = field_type, typename std::enable_if< HasNaN< ft >::value, int >::type = 0> |
FieldTraits< ft >::real_type | infinity_norm () const |
| infinity norm (row sum norm, how to generalize for blocks?) More...
|
|
template<typename ft = field_type, typename std::enable_if< HasNaN< ft >::value, int >::type = 0> |
FieldTraits< ft >::real_type | infinity_norm_real () const |
| simplified infinity norm (uses Manhattan norm for complex values) More...
|
|
size_type | N () const |
| number of rows (counted in blocks) More...
|
|
size_type | M () const |
| number of columns (counted in blocks) More...
|
|
size_type | nonzeroes () const |
| number of blocks that are stored (the number of blocks that possibly are nonzero) More...
|
|
BuildStage | buildStage () const |
| The current build stage of the matrix. More...
|
|
BuildMode | buildMode () const |
| The currently selected build mode of the matrix. More...
|
|
bool | exists (size_type i, size_type j) const |
| return true if (i,j) is in pattern More...
|
|
template<class B, class A = std::allocator<B>>
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>
...
typedef FieldMatrix<double,2,2>
M;
for(Iter row=B.createbegin(); row!=B.createend(); ++row){
if(row.index()>0)
row.insert(row.index()-1);
row.insert(row.index());
if(row.index()<B.N()-1)
row.insert(row.index()+1);
}
B[0][0]=2;
...
Implementation of the BCRSMatrix class.
friend class CreateIterator
allow CreateIterator to access internal data
Definition: bcrsmatrix.hh:1092
@ row_wise
Build in a row-wise manner.
Definition: bcrsmatrix.hh:519
size_type M() const
number of columns (counted in blocks)
Definition: bcrsmatrix.hh:1976
- 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 P2) but the size of a row and the indices of a row can not be defined in sequential order.
#include<dune/common/fmatrix.hh>
...
typedef FieldMatrix<double,2,2>
M;
B.setrowsize(0,1);
B.setrowsize(3,4);
B.setrowsize(2,1);
B.setrowsize(1,1);
B.incrementrowsize(2);
B.endrowsizes();
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);
B.endindices();
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;
@ random
Build entries randomly.
Definition: bcrsmatrix.hh:528
- implicit scheme
With the 'random scheme` described above, the sparsity pattern has to be determined and stored before the matrix is assembled. This requires a dedicated iteration over the grid elements, which can be costly in terms of time. Also, additional memory is needed to store the pattern before it can be given to the 'random' build mode.
On the other hand, often one has good a priori knowledge about the number of entries a row contains on average. The implicit
mode tries to make use of that knowledge, and allows the setup of matrix pattern and numerical values together.
Constructing and filling a BCRSMatrix with the 'implicit' mode is performed in two steps: In a setup phase, matrix entries with numerical values can be inserted into the matrix. Then, a compression algorithm is called which defragments and optimizes the memory layout. After this compression step, the matrix is ready to be used, and no further nonzero entries can be added.
To use this mode, either construct a matrix object via
or default-construct the matrix and then call
The parameter _avg
specifies the expected number of (block) entries per matrix row.
When the BCRSMatrix object is first constructed with the 'implicit' build mode, two areas for matrix entry storage are allocated:
1) A large continuous chunk of memory that can hold the expected number of entries. In addition, this chunk contains an extra part of memory called the 'compression buffer', located before the memory for the matrix itself. The size of this buffer will be _avg * _n * compressionBufferSize
.
2) An associative container indexed by
-pairs, which will hold surplus matrix entries during the setup phase (the 'overflow area'). Its content is merged into the main memory during compression.
You can then 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 does not exist yet. The matrix pattern is hence created implicitly by simply accessing nonzero entries during the initial matrix assembly. Note that new entries are not zero-initialized, though, and hence the first operation on each entry has to be an assignment.
If a row contains more non-zero entries than what was specified in the _avg parameter, the surplus entries are stored in the 'overflow area' during the initial setup phase. After all indices are added, call compress() to trigger the compression step that optimizes the matrix and integrates any entries from the overflow area into the standard BCRS storage. This compression step builds up the final memory layout row by row. It will fail with an exception if the compression buffer is not large enough, which would lead to compressed rows overwriting uncompressed ones. More precisely, if
denotes the number of non-zeros in the
-th row, then the compression algorithm will succeed if the maximal number of non-zeros in the
-th row is
for all
, where
is the total size of the compression buffer determined by the parameters explained above.
The data of the matrix is now located at the beginning of the allocated area, and covers what used to be the compression buffer. In exchange, there is now unused space at the end of the large allocated piece of memory. This will go unused and cannot be freed during the lifetime of the matrix, but it has no negative impact on run-time performance. No matrix entries may be added after the compression step.
The compress() method returns a value of type Dune::CompressionStatistics, which you can inspect to tune the construction parameters _avg
and compressionBufferSize
.
Use of copy constructor, assignment operator and matrix vector arithmetics are not supported until the matrix is fully built.
The following sample code constructs a
matrix, with an expected number of two entries per matrix row. The compression buffer size is set to 0.4. Hence the main chunk of allocated memory will be able to hold 10 * 2
entries in the matrix rows, and 10 * 2 * 0.4
entries in the compression buffer. In total that's 28 entries.
M m(10, 10, 2, 0.4, M::implicit);
m.entry(1,8) = 0.;
m.entry(1,0) = 0.;
m.entry(1,5) = 0.;
m.entry(3,5) = 0.;
m.entry(3,0) = 0.;
m.entry(3,8) = 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(7,0) = 0.;
m.entry(7,5) = 0.;
m.entry(7,8) = 0.;
A sparse block matrix with compressed row storage.
Definition: bcrsmatrix.hh:464
size_type m
Definition: bcrsmatrix.hh:2029
Internally the index array now looks like this:
The second row denotes the beginnings of the matrix rows. The eight 'x' on the left are the compression buffer. The overflow area contains the entries (1,5,0.0), (3,8,0.0), (5,8,0.0), (7,8,0.0), and (9,8,0.0). These are entries of rows 1, 3, 5, 7, and 9, which have three entries each, even though only two were anticipated.
Statistics about compression achieved in implicit mode.
Definition: bcrsmatrix.hh:86
Internally the index array now looks like this:
The compression buffer on the left is gone now, and the matrix has a real CRS layout. The 'x' on the right will be unused for the rest of the matrix' lifetime.