/usr/include/deal.II/lac/sparsity_tools.h is in libdeal.ii-dev 6.3.1-1.1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 | //---------------------------------------------------------------------------
// $Id: sparsity_tools.h 21162 2010-06-07 20:47:13Z bangerth $
// Version: $Name$
//
// Copyright (C) 2008, 2009, 2010 by the deal.II authors
//
// This file is subject to QPL and may not be distributed
// without copyright and license information. Please refer
// to the file deal.II/doc/license.html for the text and
// further information on this license.
//
//---------------------------------------------------------------------------
#ifndef __deal2__sparsity_tools_h
#define __deal2__sparsity_tools_h
#include <base/config.h>
#include <base/exceptions.h>
#include <vector>
#ifdef DEAL_II_COMPILER_SUPPORTS_MPI
#include <mpi.h>
#include <base/index_set.h>
#endif
DEAL_II_NAMESPACE_OPEN
class SparsityPattern;
/*! @addtogroup Sparsity
*@{
*/
/**
* 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.
*/
namespace SparsityTools
{
/**
* 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 @p 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
* @p 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
* @p GridTools::partition_triangulation.
*/
void partition (const SparsityPattern &sparsity_pattern,
const unsigned int n_partitions,
std::vector<unsigned int> &partition_indices);
/**
* 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.
*/
void
reorder_Cuthill_McKee (const SparsityPattern &sparsity,
std::vector<unsigned int> &new_indices,
const std::vector<unsigned int> &starting_indices = std::vector<unsigned int>());
#ifdef DEAL_II_COMPILER_SUPPORTS_MPI
/**
* Communciate rows in a compressed
* sparsity pattern over MPI. The @param
* csp is modified inline. All entries in
* rows that belong to a different
* processor are send to them and added
* there. The ownership is determined by
* parameter @param rows_per_cpu. The
* IndexSet @param myrange should be the
* one used in the constructor of the
* CompressedSimpleSparsityPattern. All
* rows contained in @param myrange are
* checked in @param csp. This function
* needs to be used with
* PETScWrappers::MPI::SparseMatrix for it
* to work correctly.
*/
template <class CSP_t>
void distribute_sparsity_pattern(CSP_t & csp,
const std::vector<unsigned int> & rows_per_cpu,
const MPI_Comm & mpi_comm,
const IndexSet & myrange);
#endif
/**
* Exception
*/
DeclException0 (ExcMETISNotInstalled);
/**
* Exception
*/
DeclException1 (ExcInvalidNumberOfPartitions,
int,
<< "The number of partitions you gave is " << arg1
<< ", but must be greater than zero.");
/**
* Exception
*/
DeclException2 (ExcInvalidArraySize,
int, int,
<< "The array has size " << arg1 << " but should have size "
<< arg2);
}
/**
*@}
*/
DEAL_II_NAMESPACE_CLOSE
#endif
|