All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
DenseMatrix.h
Go to the documentation of this file.
1 /*
2  * DenseMatrix.h
3  *
4  * Created on: Nov 25, 2015
5  * Author: Michael Wegner (michael.wegner@student.kit.edu)
6  */
7 
8 #ifndef NETWORKIT_CPP_ALGEBRAIC_DENSEMATRIX_H_
9 #define NETWORKIT_CPP_ALGEBRAIC_DENSEMATRIX_H_
10 
11 #include "../Globals.h"
12 #include "AlgebraicGlobals.h"
13 #include "Vector.h"
14 #include <cassert>
15 #include <vector>
16 
17 namespace NetworKit {
18 
24 class DenseMatrix {
25 private:
26  count nRows;
27  count nCols;
28  std::vector<double> entries;
29  double zero;
30 
31 public:
33  DenseMatrix();
34 
40  DenseMatrix(const count dimension, double zero = 0.0);
41 
48  DenseMatrix(const count nRows, const count nCols, double zero = 0.0);
49 
56  DenseMatrix(const count dimension, const std::vector<Triplet>& triplets, double zero = 0.0);
57 
65  DenseMatrix(const count nRows, const count nCols, const std::vector<Triplet>& triplets, double zero = 0.0);
66 
76  DenseMatrix(const count nRows, const count nCols, const std::vector<double>& entries, double zero = 0.0);
77 
79  virtual ~DenseMatrix() = default;
80 
82  DenseMatrix (const DenseMatrix &other) = default;
83 
85  DenseMatrix (DenseMatrix &&other) = default;
86 
88  DenseMatrix& operator=(DenseMatrix &&other) = default;
89 
91  DenseMatrix& operator=(const DenseMatrix &other) = default;
92 
96  inline count numberOfRows() const {
97  return nRows;
98  }
99 
103  inline count numberOfColumns() const {
104  return nCols;
105  }
106 
110  inline double getZero() const {
111  return zero;
112  }
113 
119  count nnzInRow(const index i) const;
120 
125  count nnz() const;
126 
130  double operator()(const index i, const index j) const;
131 
135  void setValue(const index i, const index j, const double value);
136 
137 
141  Vector row(const index i) const;
142 
146  Vector column(const index j) const;
147 
151  Vector diagonal() const;
152 
157  DenseMatrix operator+(const DenseMatrix &other) const;
158 
163  DenseMatrix& operator+=(const DenseMatrix &other);
164 
170  DenseMatrix operator-(const DenseMatrix &other) const;
171 
176  DenseMatrix& operator-=(const DenseMatrix &other);
177 
182  DenseMatrix operator*(const double &scalar) const;
183 
188  DenseMatrix& operator*=(const double &scalar);
189 
194  Vector operator*(const Vector &vector) const;
195 
200  DenseMatrix operator*(const DenseMatrix &other) const;
201 
206  DenseMatrix operator/(const double &divisor) const;
207 
212  DenseMatrix& operator/=(const double &divisor);
213 
217  DenseMatrix transpose() const;
218 
226  DenseMatrix extract(const std::vector<index>& rowIndices, const std::vector<index>& columnIndices) const;
227 
237  void assign(const std::vector<index>& rowIndices, const std::vector<index>& columnIndices, const DenseMatrix& source);
238 
244  template<typename F>
245  void apply(const F unaryElementFunction);
246 
251  static void LUDecomposition(DenseMatrix &matrix);
252 
259  static Vector LUSolve(const DenseMatrix &LU, const Vector &b);
260 
269  template<typename L> static DenseMatrix binaryOperator(const DenseMatrix &A, const DenseMatrix &B, L binaryOp);
270 
274  template<typename L> void forElementsInRow(index row, L handle) const;
275 
279  template<typename L> void parallelForElementsInRow(index row, L handle) const;
280 
284  template<typename L> void forElementsInRowOrder(L handle) const;
285 
289  template<typename L> void parallelForElementsInRowOrder(L handle) const;
290 
296  template<typename L> void forNonZeroElementsInRow(index row, L handle) const;
297 
303  template<typename L> void parallelForNonZeroElementsInRow(index row, L handle) const;
304 
310  template<typename L> void forNonZeroElementsInRowOrder(L handle) const;
311 
317  template<typename L> void parallelForNonZeroElementsInRowOrder(L handle) const;
318 };
319 
320 template<typename F>
321 void DenseMatrix::apply(const F unaryElementFunction) {
322 #pragma omp parallel for
323  for (index k = 0; k < entries.size(); ++k) {
324  entries[k] = unaryElementFunction(entries[k]);
325  }
326 }
327 
328 template<typename L> inline DenseMatrix NetworKit::DenseMatrix::binaryOperator(const DenseMatrix &A, const DenseMatrix &B, L binaryOp) {
329  assert(A.nRows == B.nRows && A.nCols == B.nCols);
330 
331  std::vector<double> resultEntries(A.numberOfRows() * A.numberOfColumns(), 0.0);
332 
333 #pragma omp parallel for
334  for (index i = 0; i < A.numberOfRows(); ++i) {
335  index offset = i * A.numberOfColumns();
336  for (index j = offset; j < offset + A.numberOfColumns(); ++j) {
337  resultEntries[j] = binaryOp(A.entries[j], B.entries[j]);
338  }
339  }
340 
341  return DenseMatrix(A.numberOfRows(), A.numberOfColumns(), resultEntries);
342 }
343 
344 template<typename L>
345 inline void NetworKit::DenseMatrix::forElementsInRow(index i, L handle) const {
346  index offset = i * numberOfColumns();
347  for (index k = offset, j = 0; k < offset + numberOfColumns(); ++k, ++j) {
348  handle(j, entries[k]);
349  }
350 }
351 
352 template<typename L>
354  index offset = i * numberOfColumns();
355 #pragma omp parallel for
356  for (index j = 0; j < numberOfColumns(); ++j) {
357  handle(j, entries[offset + j]);
358  }
359 }
360 
361 template<typename L>
363  for (index i = 0; i < nRows; ++i) {
364  index offset = i * numberOfColumns();
365  for (index k = offset, j = 0; k < offset + numberOfColumns(); ++k, ++j) {
366  handle(i, j, entries[k]);
367  }
368  }
369 }
370 
371 template<typename L>
373 #pragma omp parallel for
374  for (index i = 0; i < nRows; ++i) {
375  index offset = i * numberOfColumns();
376  for (index k = offset, j = 0; k < offset + numberOfColumns(); ++k, ++j) {
377  handle(i, j, entries[k]);
378  }
379  }
380 }
381 
382 template<typename L>
383 inline void DenseMatrix::forNonZeroElementsInRow(index row, L handle) const {
384  for (index j = 0, k = row * numberOfColumns(); j < numberOfColumns(); ++j, ++k) {
385  if (entries[k] != getZero()) {
386  handle(j, entries[k]);
387  }
388  }
389 }
390 
391 template<typename L>
392 inline void DenseMatrix::parallelForNonZeroElementsInRow(index row, L handle) const {
393 #pragma omp parallel for
394  for (index j = 0; j < numberOfColumns(); ++j) {
395  index k = row * numberOfColumns() + j;
396  if (entries[k] != getZero()) {
397  handle(j, entries[k]);
398  }
399  }
400 }
401 
402 template<typename L>
403 inline void DenseMatrix::forNonZeroElementsInRowOrder(L handle) const {
404  for (index i = 0; i < numberOfRows(); ++i) {
405  for (index j = 0, k = i * numberOfColumns(); j < numberOfColumns(); ++j, ++k) {
406  if (entries[k] != getZero()) {
407  handle(i,j,entries[k]);
408  }
409  }
410  }
411 }
412 
413 template<typename L>
415 #pragma omp parallel for
416  for (index i = 0; i < numberOfRows(); ++i) {
417  for (index j = 0, k = i * numberOfColumns(); j < numberOfColumns(); ++j, ++k) {
418  if (entries[k] != getZero()) {
419  handle(i,j,entries[k]);
420  }
421  }
422  }
423 }
424 
425 } /* namespace NetworKit */
426 
427 #endif /* NETWORKIT_CPP_ALGEBRAIC_DENSEMATRIX_H_ */
DenseMatrix extract(const std::vector< index > &rowIndices, const std::vector< index > &columnIndices) const
Extracts a matrix with rows and columns specified by rowIndices and columnIndices from this matrix...
Definition: DenseMatrix.cpp:176
void forNonZeroElementsInRowOrder(L handle) const
Iterate over all non-zero elements of the matrix in row order and call handler (lambda closure)...
Definition: DenseMatrix.h:403
DenseMatrix & operator+=(const DenseMatrix &other)
Adds other to this matrix.
Definition: DenseMatrix.cpp:95
virtual ~DenseMatrix()=default
Default destructor.
void forNonZeroElementsInRow(index row, L handle) const
Iterate over all non-zero elements of row row in the matrix and call handler(index column...
Definition: DenseMatrix.h:383
void apply(const F unaryElementFunction)
Applies the unary function unaryElementFunction to each value in the matrix.
Definition: DenseMatrix.h:321
static void LUDecomposition(DenseMatrix &matrix)
Decomposes the given matrix into lower L and upper U matrix (in-place).
Definition: DenseMatrix.cpp:201
DenseMatrix operator-(const DenseMatrix &other) const
Subtracts other from this matrix and returns the result.
Definition: DenseMatrix.cpp:101
DenseMatrix()
Default constructor.
Definition: DenseMatrix.cpp:12
void parallelForElementsInRowOrder(L handle) const
Iterate in parallel over all rows and call handler (lambda closure) on non-zero elements of the matri...
Definition: DenseMatrix.h:372
Vector row(const index i) const
Definition: DenseMatrix.cpp:59
void forElementsInRow(index row, L handle) const
Iterate over all non-zero elements of row row in the matrix and call handler(index column...
Definition: DenseMatrix.h:345
static Vector LUSolve(const DenseMatrix &LU, const Vector &b)
Computes the solution vector x to the system LU * x = b where LU is a matrix decomposed into L and U...
Definition: DenseMatrix.cpp:213
Vector diagonal() const
Definition: DenseMatrix.cpp:80
Vector column(const index j) const
Definition: DenseMatrix.cpp:70
uint64_t index
Typedefs.
Definition: Globals.h:20
count nnzInRow(const index i) const
Definition: DenseMatrix.cpp:35
DenseMatrix operator*(const double &scalar) const
Multiplies this matrix with a scalar specified in scalar and returns the result.
Definition: DenseMatrix.cpp:112
count numberOfColumns() const
Definition: DenseMatrix.h:103
Represents a dense matrix.
Definition: DenseMatrix.h:24
void assign(const std::vector< index > &rowIndices, const std::vector< index > &columnIndices, const DenseMatrix &source)
Assign the contents of the matrix source to this matrix at rows and columns specified by rowIndices a...
Definition: DenseMatrix.cpp:190
double operator()(const index i, const index j) const
Definition: DenseMatrix.cpp:51
count numberOfRows() const
Definition: DenseMatrix.h:96
DenseMatrix operator+(const DenseMatrix &other) const
Adds this matrix to other and returns the result.
Definition: DenseMatrix.cpp:90
count nnz() const
Definition: DenseMatrix.cpp:43
void setValue(const index i, const index j, const double value)
Set the matrix at position (i, j) to value.
Definition: DenseMatrix.cpp:55
uint64_t count
Definition: Globals.h:21
static DenseMatrix binaryOperator(const DenseMatrix &A, const DenseMatrix &B, L binaryOp)
Computes A binaryOp B on the elements of matrix A and matrix B.
Definition: DenseMatrix.h:328
void parallelForElementsInRow(index row, L handle) const
Iterate in parallel over all non-zero elements of row row in the matrix and call handler(index column...
Definition: DenseMatrix.h:353
void parallelForNonZeroElementsInRowOrder(L handle) const
Iterate in parallel over all rows and call handler (lambda closure) on non-zero elements of the matri...
Definition: DenseMatrix.h:414
void forElementsInRowOrder(L handle) const
Iterate over all non-zero elements of the matrix in row order and call handler (lambda closure)...
Definition: DenseMatrix.h:362
The Vector class represents a basic vector with double coefficients.
Definition: Vector.h:25
void parallelForNonZeroElementsInRow(index row, L handle) const
Iterate in parallel over all non-zero elements of row row in the matrix and call handler(index column...
Definition: DenseMatrix.h:392
DenseMatrix & operator*=(const double &scalar)
Multiplies this matrix with a scalar specified in scalar.
Definition: DenseMatrix.cpp:116
DenseMatrix & operator=(DenseMatrix &&other)=default
Default copy assignment operator.
double getZero() const
Returns the zero element of the matrix.
Definition: DenseMatrix.h:110
DenseMatrix & operator/=(const double &divisor)
Divides this matrix by a divisor specified in divisor.
Definition: DenseMatrix.cpp:163
DenseMatrix operator/(const double &divisor) const
Divides this matrix by a divisor specified in divisor and returns the result in a new matrix...
Definition: DenseMatrix.cpp:159
DenseMatrix transpose() const
Transposes this matrix and returns it.
Definition: DenseMatrix.cpp:167
DenseMatrix & operator-=(const DenseMatrix &other)
Subtracts other from this matrix.
Definition: DenseMatrix.cpp:106