5#ifndef DUNE_GALERKIN_HH
6#define DUNE_GALERKIN_HH
72 void insert(
const typename M::size_type& index);
76 std::size_t minRowSize();
78 std::size_t maxRowSize();
80 std::size_t sumRowSize();
87 typename M::CreateIterator row_;
89 std::size_t minRowSize_;
91 std::size_t maxRowSize_;
92 std::size_t sumRowSize_;
93#ifdef DUNE_ISTL_WITH_CHECKING
94 bool diagonalInserted;
98 class BaseGalerkinProduct
109 template<
class M,
class V,
class I,
class O>
111 const I& pinfo,
const O& copy);
116 class GalerkinProduct
117 :
public BaseGalerkinProduct
120 typedef T ParallelInformation;
131 template<
class G,
class V,
class Set>
132 typename G::MutableMatrix* build(G& fineGraph, V& visitedMap,
133 const ParallelInformation& pinfo,
135 const typename G::Matrix::size_type&
size,
145 template<
class G,
class I,
class Set>
146 const OverlapVertex<typename G::VertexDescriptor>*
147 buildOverlapVertices(
const G& graph,
const I& pinfo,
150 std::size_t& overlapCount);
155 bool operator()(
const OverlapVertex<A>& o1,
const OverlapVertex<A>& o2)
157 return *o1.aggregate < *o2.aggregate;
163 class GalerkinProduct<SequentialInformation>
164 :
public BaseGalerkinProduct
176 template<
class G,
class V,
class Set>
177 typename G::MutableMatrix* build(G& fineGraph, V& visitedMap,
178 const SequentialInformation& pinfo,
179 const AggregatesMap<typename G::VertexDescriptor>& aggregates,
180 const typename G::Matrix::size_type&
size,
184 struct BaseConnectivityConstructor
186 template<
class R,
class G,
class V>
187 static void constructOverlapConnectivity(R& row, G& graph, V& visitedMap,
188 const AggregatesMap<typename G::VertexDescriptor>& aggregates,
189 const OverlapVertex<typename G::VertexDescriptor>*& seed,
190 const OverlapVertex<typename G::VertexDescriptor>* overlapEnd);
195 template<
class R,
class G,
class V>
196 static void constructNonOverlapConnectivity(R& row, G& graph, V& visitedMap,
197 const AggregatesMap<typename G::VertexDescriptor>& aggregates,
198 const typename G::VertexDescriptor& seed);
204 template<
class G,
class S,
class V>
230 typedef typename Graph::VertexDescriptor
Vertex;
269 template<
class G,
class T>
270 struct ConnectivityConstructor :
public BaseConnectivityConstructor
272 typedef typename G::VertexDescriptor Vertex;
274 template<
class V,
class O,
class R>
275 static void examine(G& graph,
280 const OverlapVertex<Vertex>* overlapVertices,
281 const OverlapVertex<Vertex>* overlapEnd,
286 struct ConnectivityConstructor<G,SequentialInformation> :
public BaseConnectivityConstructor
288 typedef typename G::VertexDescriptor Vertex;
290 template<
class V,
class R>
291 static void examine(G& graph,
293 const SequentialInformation& pinfo,
294 const AggregatesMap<Vertex>& aggregates,
299 struct DirichletBoundarySetter
301 template<
class M,
class O>
302 static void set(M& coarse,
const T& pinfo,
const O& copy);
306 struct DirichletBoundarySetter<SequentialInformation>
308 template<
class M,
class O>
309 static void set(M& coarse,
const SequentialInformation& pinfo,
const O& copy);
312 template<
class R,
class G,
class V>
313 void BaseConnectivityConstructor::constructNonOverlapConnectivity(R& row, G& graph, V& visitedMap,
315 const typename G::VertexDescriptor& seed)
317 assert(row.index()==aggregates[seed]);
318 row.insert(aggregates[seed]);
320 typedef typename G::VertexDescriptor Vertex;
321 typedef std::allocator<Vertex> Allocator;
326 aggregates.template breadthFirstSearch<true,false>(seed,aggregates[seed], graph, vlist, dummy,
327 conBuilder, visitedMap);
330 template<
class R,
class G,
class V>
331 void BaseConnectivityConstructor::constructOverlapConnectivity(R& row, G& graph, V& visitedMap,
333 const OverlapVertex<typename G::VertexDescriptor>*& seed,
334 const OverlapVertex<typename G::VertexDescriptor>* overlapEnd)
336 ConnectedBuilder<G,R,V> conBuilder(aggregates, graph, visitedMap, row);
337 const typename G::VertexDescriptor aggregate=*seed->aggregate;
339 if (row.index()==*seed->aggregate) {
340 while(seed != overlapEnd && aggregate == *seed->aggregate) {
341 row.insert(*seed->aggregate);
345 put(visitedMap, seed->vertex,
true);
351 template<
class G,
class S,
class V>
355 : aggregates_(aggregates), graph_(graph), visitedMap_(visitedMap), connected_(connected)
358 template<
class G,
class S,
class V>
364 connected_.insert(
vertex);
368 template<
class G,
class I,
class Set>
369 const OverlapVertex<typename G::VertexDescriptor>*
370 GalerkinProduct<T>::buildOverlapVertices(
const G& graph,
const I& pinfo,
373 std::size_t& overlapCount)
376 typedef typename G::ConstVertexIterator ConstIterator;
377 typedef typename I::GlobalLookupIndexSet GlobalLookup;
378 typedef typename GlobalLookup::IndexPair
IndexPair;
380 const ConstIterator end = graph.end();
383 const GlobalLookup& lookup=pinfo.globalLookup();
388 if(pair!=0 && overlap.contains(pair->
local().attribute()))
392 typedef typename G::VertexDescriptor Vertex;
394 OverlapVertex<Vertex>* overlapVertices =
new OverlapVertex<Vertex>[overlapCount=0 ? 1 : overlapCount];
396 return overlapVertices;
403 if(pair!=0 && overlap.contains(pair->
local().attribute())) {
404 overlapVertices[overlapCount].aggregate = &aggregates[pair->
local()];
405 overlapVertices[overlapCount].vertex = pair->
local();
410 dverb << overlapCount<<
" overlap vertices"<<std::endl;
412 std::sort(overlapVertices, overlapVertices+overlapCount, OVLess<Vertex>());
415 return overlapVertices;
418 template<
class G,
class T>
419 template<
class V,
class O,
class R>
420 void ConnectivityConstructor<G,T>::examine(G& graph,
423 const AggregatesMap<Vertex>& aggregates,
425 const OverlapVertex<Vertex>* overlapVertices,
426 const OverlapVertex<Vertex>* overlapEnd,
429 typedef typename T::GlobalLookupIndexSet GlobalLookup;
430 const GlobalLookup& lookup = pinfo.globalLookup();
432 typedef typename G::VertexIterator VertexIterator;
434 VertexIterator vend=graph.end();
436#ifdef DUNE_ISTL_WITH_CHECKING
437 std::set<Vertex> examined;
446 typedef typename GlobalLookup::IndexPair IndexPair;
447 const IndexPair* pair = lookup.pair(*
vertex);
448 if(pair==0 || !overlap.contains(pair->local().attribute())) {
449#ifdef DUNE_ISTL_WITH_CHECKING
450 assert(examined.find(aggregates[*
vertex])==examined.end());
451 examined.insert(aggregates[*
vertex]);
453 constructNonOverlapConnectivity(row, graph, visitedMap, aggregates, *
vertex);
458 if(overlapVertices != overlapEnd) {
460 constructOverlapConnectivity(row, graph, visitedMap, aggregates, overlapVertices, overlapEnd);
471 dvverb<<
"constructed "<<row.index()<<
" non-overlapping rows"<<std::endl;
475 while(overlapVertices != overlapEnd)
478#ifdef DUNE_ISTL_WITH_CHECKING
479 typedef typename GlobalLookup::IndexPair IndexPair;
480 const IndexPair* pair = lookup.pair(overlapVertices->vertex);
481 assert(pair!=0 && overlap.contains(pair->local().attribute()));
482 assert(examined.find(aggregates[overlapVertices->vertex])==examined.end());
483 examined.insert(aggregates[overlapVertices->vertex]);
485 constructOverlapConnectivity(row, graph, visitedMap, aggregates, overlapVertices, overlapEnd);
493 template<
class V,
class R>
494 void ConnectivityConstructor<G,SequentialInformation>::examine(G& graph,
496 [[maybe_unused]]
const SequentialInformation& pinfo,
497 const AggregatesMap<Vertex>& aggregates,
500 typedef typename G::VertexIterator VertexIterator;
502 VertexIterator vend=graph.end();
505 constructNonOverlapConnectivity(row, graph, visitedMap, aggregates, *
vertex);
514 : row_(matrix.createbegin()),
515 minRowSize_(
std::numeric_limits<
std::size_t>::
max()),
516 maxRowSize_(0), sumRowSize_(0)
518#ifdef DUNE_ISTL_WITH_CHECKING
519 diagonalInserted =
false;
528 std::size_t SparsityBuilder<M>::minRowSize()
534 std::size_t SparsityBuilder<M>::sumRowSize()
539 void SparsityBuilder<M>::operator++()
541 sumRowSize_ += row_.size();
542 minRowSize_=std::min(minRowSize_, row_.size());
543 maxRowSize_=std::max(maxRowSize_, row_.size());
545#ifdef DUNE_ISTL_WITH_CHECKING
546 assert(diagonalInserted);
547 diagonalInserted =
false;
552 void SparsityBuilder<M>::insert(
const typename M::size_type& index)
555#ifdef DUNE_ISTL_WITH_CHECKING
556 diagonalInserted = diagonalInserted || row_.index()==index;
561 template<
class G,
class V,
class Set>
562 typename G::MutableMatrix*
563 GalerkinProduct<T>::build(G& fineGraph, V& visitedMap,
564 const ParallelInformation& pinfo,
566 const typename G::Matrix::size_type&
size,
569 typedef OverlapVertex<typename G::VertexDescriptor> OverlapVertex;
573 const OverlapVertex* overlapVertices = buildOverlapVertices(fineGraph,
578 typedef typename G::MutableMatrix M;
579 M* coarseMatrix =
new M(
size,
size, M::row_wise);
584 typedef typename G::VertexIterator Vertex;
585 Vertex vend = fineGraph.end();
591 typedef typename G::MutableMatrix M;
594 ConnectivityConstructor<G,T>::examine(fineGraph, visitedMap, pinfo,
597 overlapVertices+count,
600 dinfo<<pinfo.communicator().rank()<<
": Matrix ("<<coarseMatrix->N()<<
"x"<<coarseMatrix->M()<<
" row: min="<<sparsityBuilder.minRowSize()<<
" max="
601 <<sparsityBuilder.maxRowSize()<<
" avg="
602 <<
static_cast<double>(sparsityBuilder.sumRowSize())/coarseMatrix->N()
605 delete[] overlapVertices;
610 template<
class G,
class V,
class Set>
611 typename G::MutableMatrix*
612 GalerkinProduct<SequentialInformation>::build(G& fineGraph, V& visitedMap,
613 const SequentialInformation& pinfo,
615 const typename G::Matrix::size_type&
size,
616 [[maybe_unused]]
const Set& overlap)
618 typedef typename G::MutableMatrix M;
619 M* coarseMatrix =
new M(
size,
size, M::row_wise);
624 typedef typename G::VertexIterator Vertex;
625 Vertex vend = fineGraph.end();
633 ConnectivityConstructor<G,SequentialInformation>::examine(fineGraph, visitedMap, pinfo,
634 aggregates, sparsityBuilder);
635 dinfo<<
"Matrix row: min="<<sparsityBuilder.minRowSize()<<
" max="
636 <<sparsityBuilder.maxRowSize()<<
" average="
637 <<
static_cast<double>(sparsityBuilder.sumRowSize())/coarseMatrix->N()<<std::endl;
641 template<
class M,
class V,
class P,
class O>
642 void BaseGalerkinProduct::calculate(
const M& fine,
const AggregatesMap<V>& aggregates, M& coarse,
643 const P& pinfo, [[maybe_unused]]
const O& copy)
645 coarse =
static_cast<typename M::field_type
>(0);
647 typedef typename M::ConstIterator RowIterator;
648 RowIterator endRow = fine.end();
650 for(RowIterator row = fine.begin(); row != endRow; ++row)
653 typedef typename M::ConstColIterator ColIterator;
654 ColIterator endCol = row->end();
656 for(ColIterator col = row->begin(); col != endCol; ++col)
659 coarse[aggregates[row.index()]][aggregates[col.index()]]+=*col;
664 typedef typename M::block_type BlockType;
665 std::vector<BlockType> rowsize(coarse.N(),BlockType(0));
666 for (RowIterator row = coarse.begin(); row != coarse.end(); ++row)
667 rowsize[row.index()]=coarse[row.index()][row.index()];
668 pinfo.copyOwnerToAll(rowsize,rowsize);
669 for (RowIterator row = coarse.begin(); row != coarse.end(); ++row)
670 coarse[row.index()][row.index()] = rowsize[row.index()];
681 template<
class M,
class O>
682 void DirichletBoundarySetter<T>::set(M& coarse,
const T& pinfo,
const O& copy)
684 typedef typename T::ParallelIndexSet::const_iterator ConstIterator;
685 ConstIterator end = pinfo.indexSet().end();
686 typedef typename M::block_type Block;
687 Block identity=Block(0.0);
688 for(
typename Block::RowIterator b=identity.begin(); b != identity.end(); ++b)
689 b->operator[](b.index())=1.0;
691 for(ConstIterator index = pinfo.indexSet().begin();
692 index != end; ++index) {
693 if(copy.contains(index->local().attribute())) {
694 typedef typename M::ColIterator ColIterator;
695 typedef typename M::row_type Row;
696 Row row = coarse[index->local()];
697 ColIterator cend = row.find(index->local());
698 ColIterator col = row.begin();
699 for(; col != cend; ++col)
707 for(++col; col != cend; ++col)
713 template<
class M,
class O>
714 void DirichletBoundarySetter<SequentialInformation>::set(M& coarse,
715 const SequentialInformation& pinfo,
Provides classes for the Coloring process of AMG.
Class providing information about the mapping of the vertices onto aggregates.
Definition: aggregates.hh:560
Visitor for identifying connected aggregates during a breadthFirstSearch.
Definition: galerkin.hh:206
Functor for building the sparsity pattern of the matrix using examineConnectivity.
Definition: galerkin.hh:63
A pair consisting of a global and local index.
Definition: indexset.hh:85
A single linked list.
Definition: sllist.hh:44
Classes for building sets out of enumeration values.
LocalIndex & local()
Get the local index.
constexpr GeometryType vertex
GeometryType representing a vertex.
Definition: type.hh:492
constexpr auto max
Function object that returns the greater of the given values.
Definition: hybridutilities.hh:484
G Graph
The type of the graph.
Definition: galerkin.hh:211
void operator()(const ConstEdgeIterator &edge)
Process an edge pointing to another aggregate.
Definition: galerkin.hh:359
T Aggregate
The aggregate descriptor.
Definition: galerkin.hh:37
SparsityBuilder(M &matrix)
Constructor.
Definition: galerkin.hh:513
ConnectedBuilder(const AggregatesMap< Vertex > &aggregates, Graph &graph, VisitedMap &visitedMap, Set &connected)
Constructor.
Definition: galerkin.hh:352
Graph::ConstEdgeIterator ConstEdgeIterator
The constant edge iterator.
Definition: galerkin.hh:215
T Vertex
The vertex descriptor.
Definition: galerkin.hh:42
V VisitedMap
The type of the map for marking vertices as visited.
Definition: galerkin.hh:225
int visitNeighbours(const G &graph, const typename G::VertexDescriptor &vertex, V &visitor)
Visit all neighbour vertices of a vertex in a graph.
static const Vertex ISOLATED
Identifier of isolated vertices.
Definition: aggregates.hh:571
S Set
The type of the connected set.
Definition: galerkin.hh:220
Aggregate * aggregate
The aggregate the vertex belongs to.
Definition: galerkin.hh:47
Vertex vertex
The vertex descriptor.
Definition: galerkin.hh:52
Graph::VertexDescriptor Vertex
The vertex descriptor of the graph.
Definition: galerkin.hh:230
void calculate(const M &fine, const AggregatesMap< V > &aggregates, M &coarse, const I &pinfo, const O ©)
Calculate the galerkin product.
DVVerbType dvverb(std::cout)
stream for very verbose output.
Definition: stdstreams.hh:96
DInfoType dinfo(std::cout)
Stream for informative output.
Definition: stdstreams.hh:141
DVerbType dverb(std::cout)
Singleton of verbose debug stream.
Definition: stdstreams.hh:117
Dune namespace.
Definition: alignedallocator.hh:13
constexpr std::integral_constant< std::size_t, sizeof...(II)> size(std::integer_sequence< T, II... >)
Return the size of the sequence.
Definition: integersequence.hh:75
constexpr auto get(std::integer_sequence< T, II... >, std::integral_constant< std::size_t, pos >={})
Return the entry at position pos of the given sequence.
Definition: integersequence.hh:22
An stl-compliant pool allocator.
@ nonoverlapping
Category for non-overlapping solvers.
Definition: solvercategory.hh:27
static Category category(const OP &op, decltype(op.category()) *=nullptr)
Helperfunction to extract the solver category either from an enum, or from the newly introduced virtu...
Definition: solvercategory.hh:34