All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
GaussSeidelRelaxation.h
Go to the documentation of this file.
1 /*
2  * GaussSeidelRelaxation.h
3  *
4  * Created on: 27.10.2014
5  * Author: Michael Wegner (michael.wegner@student.kit.edu)
6  */
7 
8 #ifndef GAUSSSEIDELRELAXATION_H_
9 #define GAUSSSEIDELRELAXATION_H_
10 
11 #include "Smoother.h"
12 
13 namespace NetworKit {
14 
19 template<class Matrix>
20 class GaussSeidelRelaxation : public Smoother<Matrix> {
21 
22 private:
23  double tolerance;
24 
25 public:
30  GaussSeidelRelaxation(double tolerance=1e-15) : tolerance(tolerance) {}
31 
42  Vector relax(const Matrix& A, const Vector& b, const Vector& initialGuess, const count maxIterations = std::numeric_limits<count>::max()) const;
43 
52  Vector relax(const Matrix& A, const Vector& b, const count maxIterations = std::numeric_limits<count>::max()) const;
53 
54 };
55 
56 template<class Matrix>
57 Vector GaussSeidelRelaxation<Matrix>::relax(const Matrix& A, const Vector& b, const Vector& initialGuess, const count maxIterations) const {
58  count iterations = 0;
59  Vector x_old = initialGuess;
60  Vector x_new = initialGuess;
61  if (maxIterations == 0) return initialGuess;
62 
63  count dimension = A.numberOfColumns();
64  Vector diagonal = A.diagonal();
65 
66  do {
67  x_old = x_new;
68 
69  for (index i = 0; i < dimension; ++i) {
70  double sigma = 0.0;
71  A.forNonZeroElementsInRow(i, [&](index column, double value) {
72  if (column != i) {
73  sigma += value * x_new[column];
74  }
75  });
76 
77  x_new[i] = (b[i] - sigma) / diagonal[i];
78  }
79 
80  iterations++;
81  } while (iterations < maxIterations && (A*x_new - b).length() / b.length() > tolerance);
82 
83  return x_new;
84 }
85 
86 template<class Matrix>
87 Vector GaussSeidelRelaxation<Matrix>::relax(const Matrix& A, const Vector& b, const count maxIterations) const {
88  Vector x(b.getDimension());
89  return relax(A, b, x, maxIterations);
90 }
91 
92 
93 } /* namespace NetworKit */
94 
95 #endif /* GAUSSSEIDELRELAXATION_H_ */
GaussSeidelRelaxation(double tolerance=1e-15)
Constructs a Gauss-Seidel smoother with the given tolerance (default: 1e-15).
Definition: GaussSeidelRelaxation.h:30
count getDimension() const
Definition: Vector.h:74
uint64_t index
Typedefs.
Definition: Globals.h:20
uint64_t count
Definition: Globals.h:21
std::vector< std::vector< count > > Matrix
Definition: DynamicNMIDistance.h:16
double length() const
Calculates and returns the Euclidean length of this vector.
Definition: Vector.cpp:34
The Vector class represents a basic vector with double coefficients.
Definition: Vector.h:25
Abstract base class of a smoother.
Definition: Smoother.h:24
Implementation of the Gauss-Seidel smoother.
Definition: GaussSeidelRelaxation.h:20
Vector relax(const Matrix &A, const Vector &b, const Vector &initialGuess, const count maxIterations=std::numeric_limits< count >::max()) const
Utilizes Gauss-Seidel relaxations until the given number of maxIterations is reached or the relative ...
Definition: GaussSeidelRelaxation.h:57