Reference documentation for deal.II version 8.1.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Modules Pages
Typedefs | Functions
SparsityTools Namespace Reference

Typedefs

typedef types::global_dof_index size_type
 

Functions

void partition (const SparsityPattern &sparsity_pattern, const unsigned int n_partitions, std::vector< unsigned int > &partition_indices)
 
void reorder_Cuthill_McKee (const SparsityPattern &sparsity, std::vector< size_type > &new_indices, const std::vector< size_type > &starting_indices=std::vector< size_type >())
 
template<class CSP_t >
void distribute_sparsity_pattern (CSP_t &csp, const std::vector< size_type > &rows_per_cpu, const MPI_Comm &mpi_comm, const IndexSet &myrange)
 
template<class CSP_t >
void distribute_sparsity_pattern (CSP_t &csp, const std::vector< IndexSet > &owned_set_per_cpu, const MPI_Comm &mpi_comm, const IndexSet &myrange)
 
 DeclException0 (ExcMETISNotInstalled)
 
 DeclException1 (ExcInvalidNumberOfPartitions, int,<< "The number of partitions you gave is "<< arg1<< ", but must be greater than zero.")
 
 DeclException1 (ExcMETISError, int,<< " An error with error number "<< arg1<< " occurred while calling a METIS function")
 
 DeclException2 (ExcInvalidArraySize, int, int,<< "The array has size "<< arg1<< " but should have size "<< arg2)
 

Detailed Description

A namespace for functions that deal with things that one can do on sparsity patterns, such as renumbering rows and columns (or degrees of freedom if you want) according to the connectivity, or partitioning degrees of freedom.

Typedef Documentation

Declare type for container size.

Definition at line 52 of file sparsity_tools.h.

Function Documentation

void SparsityTools::partition ( const SparsityPattern sparsity_pattern,
const unsigned int  n_partitions,
std::vector< unsigned int > &  partition_indices 
)

Use the METIS partitioner to generate a partitioning of the degrees of freedom represented by this sparsity pattern. In effect, we view this sparsity pattern as a graph of connections between various degrees of freedom, where each nonzero entry in the sparsity pattern corresponds to an edge between two nodes in the connection graph. The goal is then to decompose this graph into groups of nodes so that a minimal number of edges are cut by the boundaries between node groups. This partitioning is done by METIS. Note that METIS can only partition symmetric sparsity patterns, and that of course the sparsity pattern has to be square. We do not check for symmetry of the sparsity pattern, since this is an expensive operation, but rather leave this as the responsibility of caller of this function.

After calling this function, the output array will have values between zero and n_partitions-1 for each node (i.e. row or column of the matrix).

This function will generate an error if METIS is not installed unless n_partitions is one. I.e., you can write a program so that it runs in the single-processor single-partition case without METIS installed, and only requires METIS when multiple partitions are required.

Note that the sparsity pattern itself is not changed by calling this function. However, you will likely use the information generated by calling this function to renumber degrees of freedom, after which you will of course have to regenerate the sparsity pattern.

This function will rarely be called separately, since in finite element methods you will want to partition the mesh, not the matrix. This can be done by calling GridTools::partition_triangulation.

void SparsityTools::reorder_Cuthill_McKee ( const SparsityPattern sparsity,
std::vector< size_type > &  new_indices,
const std::vector< size_type > &  starting_indices = std::vector< size_type >() 
)

For a given sparsity pattern, compute a re-enumeration of row/column indices based on the algorithm by Cuthill-McKee.

This algorithm is a graph renumbering algorithm in which we attempt to find a new numbering of all nodes of a graph based on their connectivity to other nodes (i.e. the edges that connect nodes). This connectivity is here represented by the sparsity pattern. In many cases within the library, the nodes represent degrees of freedom and edges are nonzero entries in a matrix, i.e. pairs of degrees of freedom that couple through the action of a bilinear form.

The algorithms starts at a node, searches the other nodes for those which are coupled with the one we started with and numbers these in a certain way. It then finds the second level of nodes, namely those that couple with those of the previous level (which were those that coupled with the initial node) and numbers these. And so on. For the details of the algorithm, especially the numbering within each level, we refer the reader to the book of Schwarz (H. R. Schwarz: Methode der finiten Elemente).

These algorithms have one major drawback: they require a good starting node, i.e. node that will have number zero in the output array. A starting node forming the initial level of nodes can thus be given by the user, e.g. by exploiting knowledge of the actual topology of the domain. It is also possible to give several starting indices, which may be used to simulate a simple upstream numbering (by giving the inflow nodes as starting values) or to make preconditioning faster (by letting the Dirichlet boundary indices be starting points).

If no starting index is given, one is chosen automatically, namely one with the smallest coordination number (the coordination number is the number of other nodes this node couples with). This node is usually located on the boundary of the domain. There is, however, large ambiguity in this when using the hierarchical meshes used in this library, since in most cases the computational domain is not approximated by tilting and deforming elements and by plugging together variable numbers of elements at vertices, but rather by hierarchical refinement. There is therefore a large number of nodes with equal coordination numbers. The renumbering algorithms will therefore not give optimal results.

If the graph has two or more unconnected components and if no starting indices are given, the algorithm will number each component consecutively. However, this requires the determination of a starting index for each component; as a consequence, the algorithm will produce an exception if starting indices are given, taking the latter as an indication that the caller of the function would like to override the part of the algorithm that chooses starting indices.

template<class CSP_t >
void SparsityTools::distribute_sparsity_pattern ( CSP_t &  csp,
const std::vector< size_type > &  rows_per_cpu,
const MPI_Comm &  mpi_comm,
const IndexSet myrange 
)

Communciate rows in a compressed sparsity pattern over MPI.

Parameters
cspis the sparsity pattern that has been built locally and for which we need to exchange entries with other processors to make sure that each processor knows all the elements of the rows of a matrix it stores and that may eventually be written to. This sparsity pattern will be changed as a result of this function: All entries in rows that belong to a different processor are sent to them and added there.
rows_per_cpudetermines ownership of rows.
mpi_commis the MPI communicator that is shared between the processors that all participate in this operation.
myrangeindicates the range of elements stored locally and should be the one used in the constructor of the CompressedSimpleSparsityPattern. This should be the locally relevant set. Only rows contained in myrange are checked in csp for transfer. This function needs to be used with PETScWrappers::MPI::SparseMatrix for it to work correctly in a parallel computation.
template<class CSP_t >
void SparsityTools::distribute_sparsity_pattern ( CSP_t &  csp,
const std::vector< IndexSet > &  owned_set_per_cpu,
const MPI_Comm &  mpi_comm,
const IndexSet myrange 
)

similar to the function above, but includes support for BlockCompressedSimpleSparsityPattern. owned_set_per_cpu is typically DoFHandler::locally_owned_dofs_per_processor and myrange are locally_relevant_dofs.

SparsityTools::DeclException0 ( ExcMETISNotInstalled  )

Exception

SparsityTools::DeclException1 ( ExcInvalidNumberOfPartitions  ,
int  ,
<< "The number of partitions you gave is "<< arg1<< "  ,
but must be greater than zero."   
)

Exception

SparsityTools::DeclException1 ( ExcMETISError  ,
int  ,
<< " An error with error number "<< arg1<< " occurred while calling a METIS function"   
)

Exception

SparsityTools::DeclException2 ( ExcInvalidArraySize  ,
int  ,
int  ,
<< "The array has size "<< arg1<< " but should have size "<<  arg2 
)

Exception