All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
LevelElimination.h
Go to the documentation of this file.
1 /*
2  * LevelElimination.h
3  *
4  * Created on: 10.01.2015
5  * Author: Michael
6  */
7 
8 #ifndef LEVELELIMINATION_H_
9 #define LEVELELIMINATION_H_
10 
11 #include "Level.h"
12 #include "EliminationStage.h"
13 
14 namespace NetworKit {
15 
19 template<class Matrix>
20 class LevelElimination : public Level<Matrix> {
21 private:
22  std::vector<EliminationStage<Matrix>> coarseningStages;
23  std::vector<index> cIndexFine;
24 
25  void subVectorExtract(Vector& subVector, const Vector& vector, const std::vector<index>& elements) const;
26 
27 public:
28  LevelElimination(const Matrix& A, const std::vector<EliminationStage<Matrix>>& coarseningStages);
29 
30  void coarseType(const Vector& xf, Vector& xc) const;
31  void restrict(const Vector& bf, Vector& bc, std::vector<Vector>& bStages) const;
32  void interpolate(const Vector& xc, Vector& xf, const std::vector<Vector>& bStages) const;
33 };
34 
35 template<class Matrix>
36 LevelElimination<Matrix>::LevelElimination(const Matrix& A, const std::vector<EliminationStage<Matrix>>& coarseningStages) : Level<Matrix>(LevelType::ELIMINATION, A), coarseningStages(coarseningStages) {
37  cIndexFine = std::vector<index>(this->A.numberOfRows());
38 #pragma omp parallel for
39  for (index i = 0; i < cIndexFine.size(); ++i) {
40  cIndexFine[i] = i;
41  }
42 
43  for (index k = coarseningStages.size(); k-- > 0;) {
44  for (index i = 0; i < cIndexFine.size(); ++i) {
45  assert(cIndexFine[i] < coarseningStages[k].getCSet().size());
46  cIndexFine[i] = coarseningStages[k].getCSet()[cIndexFine[i]];
47  }
48  }
49 }
50 
51 template<class Matrix>
53  xc = Vector(this->A.numberOfRows());
54 #pragma omp parallel for
55  for (index i = 0; i < xc.getDimension(); ++i) {
56  xc[i] = xf[cIndexFine[i]];
57  }
58 }
59 
60 template<class Matrix>
61 void LevelElimination<Matrix>::restrict(const Vector& bf, Vector& bc, std::vector<Vector>& bStages) const {
62  bStages.resize(coarseningStages.size() + 1);
63  bStages[0] = bf;
64  bc = bf;
65  index curStage = 0;
66  for (const EliminationStage<Matrix>& s : coarseningStages) {
67  //Vector bOld = bStages[curStage];
68  Vector bCSet;
69  subVectorExtract(bCSet, bc, s.getCSet());
70 
71  Vector bFSet;
72  subVectorExtract(bFSet, bc, s.getFSet());
73  bc = bCSet + s.getR() * bFSet;
74  bStages[curStage+1] = bc; // b = b.c + s.P^T * b.f
75 
76  curStage++;
77  }
78 }
79 
80 template<class Matrix>
81 void LevelElimination<Matrix>::interpolate(const Vector& xc, Vector& xf, const std::vector<Vector>& bStages) const {
82  Vector currX = xc;
83  for (index k = coarseningStages.size(); k-- > 0;) {
84  const EliminationStage<Matrix>& s = coarseningStages[k];
85  xf = Vector(s.getN());
86  Vector bFSet;
87  subVectorExtract(bFSet, bStages[k], s.getFSet());
88 
89  Vector bq(bFSet.getDimension());
90  const Vector &q = s.getQ();
91 #pragma omp parallel for
92  for (index i = 0; i < bq.getDimension(); ++i) { // bq = s.q .* b.f
93  bq[i] = q[i] * bFSet[i];
94  }
95  Vector xFSet = s.getP() * currX + bq;
96 
97  const std::vector<index> &fSet = s.getFSet();
98 #pragma omp parallel for
99  for (index i = 0; i < xFSet.getDimension(); ++i) {
100  xf[fSet[i]] = xFSet[i];
101  }
102 
103  const std::vector<index> &cSet = s.getCSet();
104 #pragma omp parallel for
105  for (index i = 0; i < currX.getDimension(); ++i) {
106  xf[cSet[i]] = currX[i];
107  }
108 
109  currX = xf;
110  }
111 }
112 
113 template<class Matrix>
114 void LevelElimination<Matrix>::subVectorExtract(Vector& subVector, const Vector& vector, const std::vector<index>& elements) const {
115  subVector = Vector(elements.size());
116 #pragma omp parallel for
117  for (index i = 0; i < elements.size(); ++i) {
118  subVector[i] = vector[elements[i]];
119  }
120 }
121 
122 } /* namespace NetworKit */
123 
124 #endif /* LEVELELIMINATION_H_ */
Definition: LevelElimination.h:20
void coarseType(const Vector &xf, Vector &xc) const
Definition: LevelElimination.h:52
Matrix A
Definition: Level.h:29
count getDimension() const
Definition: Vector.h:74
uint64_t index
Typedefs.
Definition: Globals.h:20
const std::vector< index > & getCSet() const
Definition: EliminationStage.h:46
void restrict(const Vector &bf, Vector &bc, std::vector< Vector > &bStages) const
Definition: LevelElimination.h:61
Definition: Level.h:16
std::vector< std::vector< count > > Matrix
Definition: DynamicNMIDistance.h:16
LevelType
Definition: Level.h:15
LevelElimination(const Matrix &A, const std::vector< EliminationStage< Matrix >> &coarseningStages)
Definition: LevelElimination.h:36
const std::vector< index > & getFSet() const
Definition: EliminationStage.h:42
The Vector class represents a basic vector with double coefficients.
Definition: Vector.h:25
void interpolate(const Vector &xc, Vector &xf, const std::vector< Vector > &bStages) const
Definition: LevelElimination.h:81
Abstract base class for an LAMG Level.
Definition: Level.h:26
const Vector & getQ() const
Definition: EliminationStage.h:38
const Matrix & getP() const
Definition: EliminationStage.h:30
count getN() const
Definition: EliminationStage.h:50
Definition: EliminationStage.h:19