libMesh
sparsity_pattern.h
Go to the documentation of this file.
1 // The libMesh Finite Element Library.
2 // Copyright (C) 2002-2024 Benjamin S. Kirk, John W. Peterson, Roy H. Stogner
3 
4 // This library is free software; you can redistribute it and/or
5 // modify it under the terms of the GNU Lesser General Public
6 // License as published by the Free Software Foundation; either
7 // version 2.1 of the License, or (at your option) any later version.
8 
9 // This library is distributed in the hope that it will be useful,
10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 // Lesser General Public License for more details.
13 
14 // You should have received a copy of the GNU Lesser General Public
15 // License along with this library; if not, write to the Free Software
16 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17 
18 
19 #ifndef LIBMESH_SPARSITY_PATTERN_H
20 #define LIBMESH_SPARSITY_PATTERN_H
21 
22 // Local Includes
23 #include "libmesh/elem_range.h"
24 #include "libmesh/threads_allocators.h"
25 #include "libmesh/parallel_object.h"
26 
27 // C++ includes
28 #include <algorithm> // is_sorted
29 #include <unordered_set>
30 #include <vector>
31 
32 namespace libMesh
33 {
34 
35 // Forward declarations
36 class DofMap;
37 class CouplingMatrix;
38 
49 namespace SparsityPattern // use a namespace so member classes can be forward-declared.
50 {
51 typedef std::vector<dof_id_type, Threads::scalable_allocator<dof_id_type>> Row;
52 class Graph : public std::vector<Row> {};
53 
54 class NonlocalGraph : public std::map<dof_id_type, Row> {};
55 
65 template<typename BidirectionalIterator>
66 static void sort_row (const BidirectionalIterator begin,
67  BidirectionalIterator middle,
68  const BidirectionalIterator end);
69 
70 
71 
77  {
78  public:
79  virtual ~AugmentSparsityPattern () = default;
80 
84  virtual void augment_sparsity_pattern (SparsityPattern::Graph & sparsity,
85  std::vector<dof_id_type> & n_nz,
86  std::vector<dof_id_type> & n_oz) = 0;
87  };
88 
89 
90 
102 class Build : public ParallelObject
103 {
104 public:
105  Build (const DofMap & dof_map_in,
106  const CouplingMatrix * dof_coupling_in,
107  const std::set<GhostingFunctor *> & coupling_functors_in,
108  const bool implicit_neighbor_dofs_in,
109  const bool need_full_sparsity_pattern_in,
110  const bool calculate_constrained_in = false);
111 
117  Build (const Build &) = default;
118  Build & operator= (const Build &) = delete;
119  Build (Build &&) = default;
120  Build & operator= (Build &&) = delete;
121  ~Build () = default;
122 
126  Build (Build & other, Threads::split);
127 
132  void operator()(const ConstElemRange & range);
133 
138  void join (const Build & other);
139 
144  void parallel_sync ();
145 
151  { return sparsity_pattern; }
152 
159  { return nonlocal_pattern; }
160 
164  std::size_t n_nonzeros() const;
165 
170  const std::vector<dof_id_type> & get_n_nz() const
171  { return n_nz; }
172 
177  const std::vector<dof_id_type> & get_n_oz() const
178  { return n_oz; }
179 
185 
190  std::vector<dof_id_type> & n_nz,
191  std::vector<dof_id_type> & n_oz,
192  void * context),
193  void * context)
194  { func(sparsity_pattern, n_nz, n_oz, context); }
195 
201  {
202  sparsity_pattern.clear();
203  nonlocal_pattern.clear();
204  }
205 
206 private:
207  const DofMap & dof_map;
209  const std::set<GhostingFunctor *> & coupling_functors;
213 
214  // If there are "spider" nodes in the mesh (i.e. a single node which
215  // is connected to many 1D elements) and Constraints, we can end up
216  // sorting the same set of DOFs multiple times in handle_vi_vj(),
217  // only to find that it has no net effect on the final sparsity. In
218  // such cases it is much faster to keep track of (element_dofs_i,
219  // element_dofs_j) pairs which have already been handled and not
220  // repeat the computation. We use this data structure to keep track
221  // of hashes of sets of dofs we have already seen, thus avoiding
222  // unnecessary calculations.
223  std::unordered_set<dof_id_type> hashed_dof_sets;
224 
225  void handle_vi_vj(const std::vector<dof_id_type> & element_dofs_i,
226  const std::vector<dof_id_type> & element_dofs_j);
227 
228  void sorted_connected_dofs(const Elem * elem,
229  std::vector<dof_id_type> & dofs_vi,
230  unsigned int vi);
231 
232 #ifndef LIBMESH_ENABLE_DEPRECATED
233 private:
234 #endif
235 
237 
239 
240  std::vector<dof_id_type> n_nz;
241 
242  std::vector<dof_id_type> n_oz;
243 };
244 
245 }
246 
247 
248 
249 // ------------------------------------------------------------
250 // SparsityPattern inline member functions
251 template<typename BidirectionalIterator>
252 inline
253 void SparsityPattern::sort_row (const BidirectionalIterator begin,
254  BidirectionalIterator middle,
255  const BidirectionalIterator end)
256 {
257  // Assure we have the conditions for an inplace_merge
258 #ifdef DEBUG
259  libmesh_assert(std::is_sorted(begin, middle));
260  libmesh_assert(std::is_sorted(middle, end));
261 #endif
262  libmesh_assert(std::unique(begin, middle) == middle);
263  libmesh_assert(std::unique(middle, end) == end);
264 
265  std::inplace_merge(begin, middle, end);
266 
267  // Assure the algorithm worked if we are in DEBUG mode
268 #ifdef DEBUG
269  libmesh_assert (std::is_sorted(begin,end));
270 #endif
271 
272  // Make sure the two ranges did not contain any common elements
273  libmesh_assert (std::unique (begin, end) == end);
274 }
275 
276 } // namespace libMesh
277 
278 #endif // LIBMESH_SPARSITY_PATTERN_H
SparsityPattern::Graph sparsity_pattern
This helper class can be called on multiple threads to compute the sparsity pattern (or graph) of the...
const std::set< GhostingFunctor * > & coupling_functors
void apply_extra_sparsity_function(void(*func)(SparsityPattern::Graph &sparsity, std::vector< dof_id_type > &n_nz, std::vector< dof_id_type > &n_oz, void *context), void *context)
Let a user-provided function modify our sparsity structure.
const std::vector< dof_id_type > & get_n_oz() const
The number of off-processor nonzeros in my portion of the global matrix.
Dummy "splitting object" used to distinguish splitting constructors from copy constructors.
Definition: threads_none.h:63
std::size_t n_nonzeros() const
The total number of nonzeros in the global matrix.
This is the base class from which all geometric element types are derived.
Definition: elem.h:94
The StoredRange class defines a contiguous, divisible set of objects.
Definition: stored_range.h:54
The libMesh namespace provides an interface to certain functionality in the library.
void parallel_sync()
Send sparsity pattern data relevant to other processors to those processors, and receive and incorpor...
std::unordered_set< dof_id_type > hashed_dof_sets
This class handles the numbering of degrees of freedom on a mesh.
Definition: dof_map.h:169
std::vector< dof_id_type, Threads::scalable_allocator< dof_id_type > > Row
void join(const Build &other)
Combine the sparsity pattern in other with this object&#39;s sparsity pattern.
const SparsityPattern::NonlocalGraph & get_nonlocal_pattern() const
Rows of sparse matrix indices, mapped from global DoF number, which belong on other processors...
const CouplingMatrix * dof_coupling
bool is_sorted(const std::vector< KeyType > &v)
void sorted_connected_dofs(const Elem *elem, std::vector< dof_id_type > &dofs_vi, unsigned int vi)
libmesh_assert(ctx)
std::vector< dof_id_type > n_nz
An object whose state is distributed along a set of processors.
Build(const DofMap &dof_map_in, const CouplingMatrix *dof_coupling_in, const std::set< GhostingFunctor *> &coupling_functors_in, const bool implicit_neighbor_dofs_in, const bool need_full_sparsity_pattern_in, const bool calculate_constrained_in=false)
const SparsityPattern::Graph & get_sparsity_pattern() const
Rows of sparse matrix indices, indexed by the offset from the first DoF on this processor.
void apply_extra_sparsity_object(SparsityPattern::AugmentSparsityPattern &asp)
Let a user-provided AugmentSparsityPattern subclass modify our sparsity structure.
const std::vector< dof_id_type > & get_n_nz() const
The number of on-processor nonzeros in my portion of the global matrix.
SparsityPattern::NonlocalGraph nonlocal_pattern
void clear_full_sparsity()
Clear the "full" details of our sparsity structure, leaving only the counts of non-zero entries...
void handle_vi_vj(const std::vector< dof_id_type > &element_dofs_i, const std::vector< dof_id_type > &element_dofs_j)
void operator()(const ConstElemRange &range)
Add entries from a range of elements to this object&#39;s sparsity pattern.
virtual void augment_sparsity_pattern(SparsityPattern::Graph &sparsity, std::vector< dof_id_type > &n_nz, std::vector< dof_id_type > &n_oz)=0
User-defined function to augment the sparsity pattern.
Abstract base class to be used to add user-defined implicit degree of freedom couplings.
Build & operator=(const Build &)=delete
This class defines a coupling matrix.
static void sort_row(const BidirectionalIterator begin, BidirectionalIterator middle, const BidirectionalIterator end)
Splices the two sorted ranges [begin,middle) and [middle,end) into one sorted range [begin...
std::vector< dof_id_type > n_oz