Debian Codegraph @

dune/istl/paamg/indicescoarsener.hh

raw
1 // SPDX-FileCopyrightText: Copyright © DUNE Project contributors, see file LICENSE.md in module root
2 // SPDX-License-Identifier: LicenseRef-GPL-2.0-only-with-DUNE-exception
3 // -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*-
4 // vi: set et ts=4 sw=2 sts=2:
5 #ifndef DUNE_AMG_INDICESCOARSENER_HH
6 #define DUNE_AMG_INDICESCOARSENER_HH
7
8 #include <dune/common/parallel/indicessyncer.hh>
9 #include <vector>
10 #include "renumberer.hh"
11
12 #if HAVE_MPI
13 #include <dune/istl/owneroverlapcopy.hh>
14 #endif
15
16 #include "pinfo.hh"
17
18 namespace Dune
19 {
20 namespace Amg
21 {
22
23 /**
24 * @addtogroup ISTL_PAAMG
25 *
26 * @{
27 */
28 /** @file
29 * @author Markus Blatt
30 * @brief Provides a class for building the index set
31 * and remote indices on the coarse level.
32 */
33
34 template<typename T, typename E>
35 class IndicesCoarsener
36 {};
37
38
39 #if HAVE_MPI
40
41 template<typename T, typename E>
42 class ParallelIndicesCoarsener
43 {
44 public:
45 /**
46 * @brief The set of excluded attributes
47 */
48 typedef E ExcludedAttributes;
49
50 /**
51 * @brief The type of the parallel information.
52 */
53 typedef T ParallelInformation;
54
55 typedef typename ParallelInformation::ParallelIndexSet ParallelIndexSet;
56
57 /**
58 * @brief The type of the global index.
59 */
60 typedef typename ParallelIndexSet::GlobalIndex GlobalIndex;
61
62 /**
63 * @brief The type of the local index.
64 */
65 typedef typename ParallelIndexSet::LocalIndex LocalIndex;
66
67 /**
68 * @brief The type of the attribute.
69 */
70 typedef typename LocalIndex::Attribute Attribute;
71
72 /**
73 * @brief The type of the remote indices.
74 */
75 typedef Dune::RemoteIndices<ParallelIndexSet> RemoteIndices;
76
77 /**
78 * @brief Build the coarse index set after the aggregatio.
79 *
80 * @param fineInfo The parallel information at the fine level.
81 * @param fineGraph The graph of the fine lecel,
82 * @param visitedMap Map for marking vertices as visited.
83 * @param aggregates The mapping of unknowns onto aggregates.
84 * @param coarseInfo The information about the parallel data decomposition
85 * on the coarse level.
86 * @param noAggregates
87 * @param useFixedOrder Flag indicating if creating indices for the coarser level
88 * should be done in a fixed order, i.e., the order in which the rows were sent.
89 * If set to true, this makes the runs reproducible but it might slow down performance.
90 * @return The number of unknowns on the coarse level.
91 */
92 template<typename Graph, typename VM>
93 static typename Graph::VertexDescriptor
94 coarsen(ParallelInformation& fineInfo,
95 Graph& fineGraph,
96 VM& visitedMap,
97 AggregatesMap<typename Graph::VertexDescriptor>& aggregates,
98 ParallelInformation& coarseInfo,
99 typename Graph::VertexDescriptor noAggregates,
100 bool useFixedOrder = false);
101
102 private:
103 template<typename G, typename I>
104 class ParallelAggregateRenumberer : public AggregateRenumberer<G>
105 {
106 typedef typename G::VertexDescriptor Vertex;
107
108 typedef I GlobalLookupIndexSet;
109
110 typedef typename GlobalLookupIndexSet::IndexPair IndexPair;
111
112 typedef typename IndexPair::GlobalIndex GlobalIndex;
113
114 public:
115 ParallelAggregateRenumberer(AggregatesMap<Vertex>& aggregates, const I& lookup)
116 : AggregateRenumberer<G>(aggregates), isPublic_(false), lookup_(lookup),
117 globalIndex_(std::numeric_limits<GlobalIndex>::max())
118 {}
119
120
121 void operator()(const typename G::ConstEdgeIterator& edge)
122 {
123 AggregateRenumberer<G>::operator()(edge);
124 const IndexPair* pair= lookup_.pair(edge.target());
125 if(pair!=0) {
126 globalIndex(pair->global());
127 attribute(pair->local().attribute());
128 isPublic(pair->local().isPublic());
129 }
130 }
131
132 Vertex operator()([[maybe_unused]] const GlobalIndex& global)
133 {
134 Vertex current = this->number_;
135 this->operator++();
136 return current;
137 }
138
139 bool isPublic()
140 {
141 return isPublic_;
142 }
143
144 void isPublic(bool b)
145 {
146 isPublic_ = isPublic_ || b;
147 }
148
149 void reset()
150 {
151 globalIndex_ = std::numeric_limits<GlobalIndex>::max();
152 isPublic_=false;
153 }
154
155 void attribute(const Attribute& attribute)
156 {
157 attribute_=attribute;
158 }
159
160 Attribute attribute()
161 {
162 return attribute_;
163 }
164
165 const GlobalIndex& globalIndex() const
166 {
167 return globalIndex_;
168 }
169
170 void globalIndex(const GlobalIndex& global)
171 {
172 globalIndex_ = global;
173 }
174
175 private:
176 bool isPublic_;
177 Attribute attribute_;
178 const GlobalLookupIndexSet& lookup_;
179 GlobalIndex globalIndex_;
180 };
181
182 template<typename Graph, typename VM, typename I>
183 static void buildCoarseIndexSet(const ParallelInformation& pinfo,
184 Graph& fineGraph,
185 VM& visitedMap,
186 AggregatesMap<typename Graph::VertexDescriptor>& aggregates,
187 ParallelIndexSet& coarseIndices,
188 ParallelAggregateRenumberer<Graph,I>& renumberer);
189
190 template<typename Graph,typename I>
191 static void buildCoarseRemoteIndices(const RemoteIndices& fineRemote,
192 const AggregatesMap<typename Graph::VertexDescriptor>& aggregates,
193 ParallelIndexSet& coarseIndices,
194 RemoteIndices& coarseRemote,
195 ParallelAggregateRenumberer<Graph,I>& renumberer,
196 bool useFixedOrder);
197
198 };
199
200 /**
201 * @brief Coarsen Indices in the parallel case.
202 */
203 template<typename G, typename L, typename E>
204 class IndicesCoarsener<OwnerOverlapCopyCommunication<G,L>,E>
205 : public ParallelIndicesCoarsener<OwnerOverlapCopyCommunication<G,L>,E>
206 {};
207
208
209 #endif
210
211 /**
212 * @brief Coarsen Indices in the sequential case.
213 *
214 * Nothing to be coarsened here. Just renumber the aggregates
215 * consecutively
216 */
217 template<typename E>
218 class IndicesCoarsener<SequentialInformation,E>
219 {
220 public:
221 template<typename Graph, typename VM>
222 static typename Graph::VertexDescriptor
223 coarsen(const SequentialInformation & fineInfo,
224 Graph& fineGraph,
225 VM& visitedMap,
226 AggregatesMap<typename Graph::VertexDescriptor>& aggregates,
227 SequentialInformation& coarseInfo,
228 typename Graph::VertexDescriptor noAggregates,
229 bool useFixedOrder = false);
230 };
231
232 #if HAVE_MPI
233 template<typename T, typename E>
234 template<typename Graph, typename VM>
235 inline typename Graph::VertexDescriptor
236 ParallelIndicesCoarsener<T,E>::coarsen(ParallelInformation& fineInfo,
237 Graph& fineGraph,
238 VM& visitedMap,
239 AggregatesMap<typename Graph::VertexDescriptor>& aggregates,
240 ParallelInformation& coarseInfo,
241 [[maybe_unused]] typename Graph::VertexDescriptor noAggregates,
242 bool useFixedOrder)
243 {
244 ParallelAggregateRenumberer<Graph,typename ParallelInformation::GlobalLookupIndexSet> renumberer(aggregates, fineInfo.globalLookup());
245 buildCoarseIndexSet(fineInfo, fineGraph, visitedMap, aggregates,
246 coarseInfo.indexSet(), renumberer);
247 buildCoarseRemoteIndices(fineInfo.remoteIndices(), aggregates, coarseInfo.indexSet(),
248 coarseInfo.remoteIndices(), renumberer, useFixedOrder);
249
250 return renumberer;
251 }
252
253 template<typename T, typename E>
254 template<typename Graph, typename VM, typename I>
255 void ParallelIndicesCoarsener<T,E>::buildCoarseIndexSet(const ParallelInformation& pinfo,
256 Graph& fineGraph,
257 VM& visitedMap,
258 AggregatesMap<typename Graph::VertexDescriptor>& aggregates,
259 ParallelIndexSet& coarseIndices,
260 ParallelAggregateRenumberer<Graph,I>& renumberer)
261 {
262 // fineGraph is the local subgraph corresponding to the vertices the process owns.
263 // i.e. no overlap/copy vertices can be visited traversing the graph
264 typedef typename Graph::ConstVertexIterator Iterator;
265 typedef typename ParallelInformation::GlobalLookupIndexSet GlobalLookupIndexSet;
266
267 Iterator end = fineGraph.end();
268 const GlobalLookupIndexSet& lookup = pinfo.globalLookup();
269
270 coarseIndices.beginResize();
271
272 // Setup the coarse index set and renumber the aggregate consecutively
273 // ascending from zero according to the minimum global index belonging
274 // to the aggregate
275 for(Iterator index = fineGraph.begin(); index != end; ++index) {
276 if(aggregates[*index]!=AggregatesMap<typename Graph::VertexDescriptor>::ISOLATED)
277 // Isolated vertices will not be represented on the next level.
278 // These should only be there if skipIsolated is activiated in
279 // the coarsening criterion as otherwise they will be aggregated
280 // and should have real aggregate number in the map right now.
281 if(!get(visitedMap, *index)) {
282 // This vertex was not visited by breadthFirstSearch yet.
283 typedef typename GlobalLookupIndexSet::IndexPair IndexPair;
284 const IndexPair* pair= lookup.pair(*index);
285
286 renumberer.reset(); // reset attribute and global index.
287 if(pair!=0) {
288 // vertex is in the index set. Note that not all vertices have
289 // to be in the index set, just the ones where communication
290 // will happen.
291 assert(!ExcludedAttributes::contains(pair->local().attribute()));
292 renumberer.attribute(pair->local().attribute());
293 renumberer.isPublic(pair->local().isPublic());
294 renumberer.globalIndex(pair->global());
295 }
296
297 // Reconstruct aggregate and mark vertices as visited
298 aggregates.template breadthFirstSearch<false>(*index, aggregates[*index],
299 fineGraph, renumberer, visitedMap);
300
301 if(renumberer.globalIndex()!=std::numeric_limits<GlobalIndex>::max()) {
302 // vertex is in the index set.
303 //std::cout <<" Adding global="<< renumberer.globalIndex()<<" local="<<static_cast<std::size_t>(renumberer)<<std::endl;
304 coarseIndices.add(renumberer.globalIndex(),
305 LocalIndex(renumberer, renumberer.attribute(),
306 renumberer.isPublic()));
307 }
308
309 aggregates[*index] = renumberer;
310 ++renumberer;
311 }
312 }
313
314 coarseIndices.endResize();
315
316 assert(static_cast<std::size_t>(renumberer) >= coarseIndices.size());
317
318 // Reset the visited flags
319 for(Iterator vertex=fineGraph.begin(); vertex != end; ++vertex)
320 put(visitedMap, *vertex, false);
321 }
322
323 template<typename T, typename E>
324 template<typename Graph, typename I>
325 void ParallelIndicesCoarsener<T,E>::buildCoarseRemoteIndices(const RemoteIndices& fineRemote,
326 const AggregatesMap<typename Graph::VertexDescriptor>& aggregates,
327 ParallelIndexSet& coarseIndices,
328 RemoteIndices& coarseRemote,
329 ParallelAggregateRenumberer<Graph,I>& renumberer,
330 bool useFixedOrder)
331 {
332 std::vector<char> attributes(static_cast<std::size_t>(renumberer));
333
334 GlobalLookupIndexSet<ParallelIndexSet> coarseLookup(coarseIndices, static_cast<std::size_t>(renumberer));
335
336 typedef typename RemoteIndices::const_iterator Iterator;
337 Iterator end = fineRemote.end();
338
339 for(Iterator neighbour = fineRemote.begin();
340 neighbour != end; ++neighbour) {
341 int process = neighbour->first;
342
343 assert(neighbour->second.first==neighbour->second.second);
344
345 // Mark all as not known
346 typedef typename std::vector<char>::iterator CIterator;
347
348 for(CIterator iter=attributes.begin(); iter!= attributes.end(); ++iter)
349 *iter = std::numeric_limits<char>::max();
350
351 auto riEnd = neighbour->second.second->end();
352
353 for(auto index = neighbour->second.second->begin();
354 index != riEnd; ++index) {
355 if(!E::contains(index->localIndexPair().local().attribute()) &&
356 aggregates[index->localIndexPair().local()] !=
357 AggregatesMap<typename Graph::VertexDescriptor>::ISOLATED)
358 {
359 assert(aggregates[index->localIndexPair().local()]<attributes.size());
360 if (attributes[aggregates[index->localIndexPair().local()]] != 3)
361 attributes[aggregates[index->localIndexPair().local()]] = index->attribute();
362 }
363 }
364
365 // Build remote index list
366 typedef RemoteIndexListModifier<ParallelIndexSet,typename RemoteIndices::Allocator,false> Modifier;
367 typedef typename RemoteIndices::RemoteIndex RemoteIndex;
368 typedef typename ParallelIndexSet::const_iterator IndexIterator;
369
370 Modifier coarseList = coarseRemote.template getModifier<false,true>(process);
371
372 IndexIterator iend = coarseIndices.end();
373 for(IndexIterator index = coarseIndices.begin(); index != iend; ++index)
374 if(attributes[index->local()] != std::numeric_limits<char>::max()) {
375 // remote index is present
376 coarseList.insert(RemoteIndex(Attribute(attributes[index->local()]), &(*index)));
377 }
378 //std::cout<<coarseRemote<<std::endl;
379 }
380
381 // The number of neighbours should not change!
382 assert(coarseRemote.neighbours()==fineRemote.neighbours());
383
384 // sync the index set and the remote indices to recompute missing
385 // indices
386 IndicesSyncer<ParallelIndexSet> syncer(coarseIndices, coarseRemote);
387 syncer.sync(renumberer, useFixedOrder);
388
389 }
390
391 #endif
392
393 template<typename E>
394 template<typename Graph, typename VM>
395 typename Graph::VertexDescriptor
396 IndicesCoarsener<SequentialInformation,E>::coarsen(
397 [[maybe_unused]] const SequentialInformation& fineInfo,
398 [[maybe_unused]] Graph& fineGraph,
399 [[maybe_unused]] VM& visitedMap,
400 [[maybe_unused]] AggregatesMap<typename Graph::VertexDescriptor>& aggregates,
401 [[maybe_unused]] SequentialInformation& coarseInfo,
402 [[maybe_unused]] typename Graph::VertexDescriptor noAggregates,
403 [[maybe_unused]] bool useFixedOrder)
404 {
405 return noAggregates;
406 }
407
408 } //namespace Amg
409 } // namespace Dune
410 #endif