![]() |
Reference documentation for deal.II version 8.1.0
|
Namespaces | |
ChunkSparsityPatternIterators | |
TrilinosWrappers | |
SparsityTools | |
SparsityPatternIterators | |
Typedefs | |
typedef BlockCompressedSparsityPattern CompressedBlockSparsityPattern | DEAL_II_DEPRECATED |
In deal.II, sparsity patterns are typically separated from the actual sparse matrices (with the exception of the SparseMatrixEZ class and some classes from interfaces to external libraries such as PETSc). The reason is that one often has several matrices that share the same sparsity pattern; examples include the stiffness and mass matrices necessary for time stepping schemes, or the left and right hand side matrix of generalized eigenvalue problems. It would therefore be wasteful if each of them had to store their sparsity pattern separately.
Consequently, deal.II has sparsity pattern classes that matrix classes build on. There are two main groups of sparsity pattern classes, as discussed below:
The main sparse matrix class in deal.II, SparseMatrix, only stores a value for each matrix entry, but not where these entries are located. For this, it relies on the information it gets from a sparsity pattern object associated with this matrix. This sparsity pattern object must be of type SparsityPattern.
Because matrices are large objects and because it is comparatively expensive to change them, SparsityPattern objects are built in two phases: first, in a "dynamic" phase, one allocates positions where one expects matrices built on it to have nonzero entries; in a second "static" phase, the representation of these nonzero locations is "compressed" into the usual Compressed Row Storage (CSR) format. After this, no new nonzero locations can be added any more. Only after compression can a sparsity pattern be associated to a matrix, since the latter requires the efficient compressed data format of the former. Building a sparsity pattern during the dynamic phase often happens with the DoFTools:make_sparsity_pattern() function. Although this may appear a restriction, it is typically not a significant problem to first build a sparsity pattern and then to write into the matrix only in the previously allocated locations, since in finite element codes it is normally quite clear which elements of a matrix can possibly be nonzero and which are definitely zero.
The advantage of this two-phase generation of a sparsity pattern is that when it is actually used with a matrix, a very efficient format is available. In particular, the locations of entries are stored in a linear array that allows for rapid access friendly to modern CPU types with deep hierarchies of caches. Consequently, the static SparsityPattern class is the only one on which deal.II's main SparseMatrix class can work.
The main drawback of static sparsity patterns is that their efficient construction requires a reasonably good guess how many entries each of the rows may maximally have. During the actual construction, for example in the DoFTools:make_sparsity_pattern() function, only at most as many entries can be allocated as previously stated. This is a problem because it is often difficult to estimate the maximal number of entries per row. Consequently, a common strategy is to first build and intermediate sparsity pattern that uses a less efficient storage scheme during construction of the sparsity pattern and later copy it directly into the static, compressed form. Most tutorial programs do this, starting at step-2 (see also, for example the step-11, step-18, and step-27 tutorial programs).
As explained above, it is often complicated to obtain good estimates for the maximal number of entries in each row of a sparsity pattern. Consequently, any attempts to allocate a regular SparsityPattern with bad estimates requires huge amounts of memory, almost all of which will not be used and be de-allocated upon compression.
To avoid this, deal.II contains a number of "dynamic" or "compressed" sparsity patterns that only allocate as much memory as necessary to hold the currently added entries. While this saves much memory compared to the worst-case behavior mentioned above, it requires the use of less efficient storage schemes for insertion of elements, and the frequent allocation of memory often also takes significant compute time. The tradeoff to avoid excessive memory allocation cannot be avoided, however.
The following classes implement this "dynamic" memory scheme in deal.II:
These classes have different performance characteristics and memory requirements. Which one is the "best" changes from case to case because it is dependent on the number of dofs, the number of couplings per dof, the strategy used to insert and the amount of memory available.
CompressedSparsityPattern and CompressedSimpleSparsityPattern are very similar, where CompressedSimpleSparsityPattern trades some memory (requires up to twice the memory in the worst case) for additional speed which is noticeable in cases with many nonzero entries. CompressedSetSparsityPattern on the other hand uses a lot more memory but may perform better in cases with many nonzero entries per row. See for example the step-27 and step-22 tutorial programs.
As a guideline you should start using CompressedSparsityPattern and try the other variants if you run into problems. Switching between them should be as simple as changing the class name because all classes have the same interface for adding entries. In either case, these classes are typically used in the following way (replace the class CompressedSparsityPattern with a different one from above):
* CompressedSparsityPattern compressed_pattern (dof_handler.n_dofs()); * DoFTools::make_sparsity_pattern (dof_handler, * compressed_pattern); * constraints.condense (compressed_pattern); * * SparsityPattern final_sparsity_pattern; * final_sparsity_pattern.copy_from (compressed_pattern); *
The intermediate, compressed sparsity pattern is directly copied into the "compressed" form of the final static pattern.
The following classes implement an array of dynamic sparsity patterns:
These classes inherit the same tradeoffs regarding their efficiency from their non-block classes (see above). See their documentation and step-22 for more information.
typedef BlockCompressedSparsityPattern CompressedBlockSparsityPattern DEAL_II_DEPRECATED |
A typdef to preserve the old name CompressedBlockSparsityPattern even after we changed the naming of the class to BlockCompressedSparsityPattern. The old name is now deprecated and user codes should use the name BlockCompressedSparsityPattern instead.
Definition at line 758 of file block_sparsity_pattern.h.