TheAlgorithms/C++ 1.0.0
All the algorithms implemented in C++
Loading...
Searching...
No Matches
divide_and_conquer::strassens_multiplication::Matrix< T, typename > Class Template Reference

Matrix class. More...

Collaboration diagram for divide_and_conquer::strassens_multiplication::Matrix< T, typename >:
[legend]

Public Member Functions

template<typename Integer, typename = typename std::enable_if< std::is_integral<Integer>::value, Integer>::type>
 Matrix (const Integer size)
 Constructor.
template<typename Integer, typename = typename std::enable_if< std::is_integral<Integer>::value, Integer>::type>
 Matrix (const Integer rows, const Integer cols)
 Constructor.
std::pair< size_t, size_t > size () const
 Get the matrix shape.
template<typename Integer, typename = typename std::enable_if< std::is_integral<Integer>::value, Integer>::type>
std::vector< T > & operator[] (const Integer index)
 returns the address of the element at ith place (here ith row of the matrix)
Matrix slice (const size_t row_start, const size_t row_end=MAX_SIZE, const size_t col_start=MAX_SIZE, const size_t col_end=MAX_SIZE) const
 Creates a new matrix and returns a part of it.
template<typename Number, typename = typename std::enable_if< std::is_integral<Number>::value || std::is_floating_point<Number>::value, Number>::type>
void h_stack (const Matrix< Number > &other)
 Horizontally stack the matrix (one after the other)
template<typename Number, typename = typename std::enable_if< std::is_integral<Number>::value || std::is_floating_point<Number>::value, Number>::type>
void v_stack (const Matrix< Number > &other)
 Horizontally stack the matrix (current matrix above the other)
template<typename Number, typename = typename std::enable_if< std::is_integral<Number>::value || std::is_floating_point<Number>::value, bool>::type>
Matrix operator+ (const Matrix< Number > &other) const
 Add two matrices and returns a new matrix.
template<typename Number, typename = typename std::enable_if< std::is_integral<Number>::value || std::is_floating_point<Number>::value, bool>::type>
Matrix & operator+= (const Matrix< Number > &other) const
 Add another matrices to current matrix.
template<typename Number, typename = typename std::enable_if< std::is_integral<Number>::value || std::is_floating_point<Number>::value, bool>::type>
Matrix operator- (const Matrix< Number > &other) const
 Subtract two matrices and returns a new matrix.
template<typename Number, typename = typename std::enable_if< std::is_integral<Number>::value || std::is_floating_point<Number>::value, bool>::type>
Matrix & operator-= (const Matrix< Number > &other) const
 Subtract another matrices to current matrix.
template<typename Number, typename = typename std::enable_if< std::is_integral<Number>::value || std::is_floating_point<Number>::value, bool>::type>
Matrix operator* (const Matrix< Number > &other) const
 Multiply two matrices and returns a new matrix.
template<typename Number, typename = typename std::enable_if< std::is_integral<Number>::value || std::is_floating_point<Number>::value, bool>::type>
Matrix operator* (const Number other) const
 Multiply matrix with a number and returns a new matrix.
template<typename Number, typename = typename std::enable_if< std::is_integral<Number>::value || std::is_floating_point<Number>::value, bool>::type>
Matrix & operator*= (const Number other) const
 Multiply a number to current matrix.
template<typename Number, typename = typename std::enable_if< std::is_integral<Number>::value || std::is_floating_point<Number>::value, bool>::type>
Matrix naive_multiplication (const Matrix< Number > &other) const
 Naive multiplication performed on this.
template<typename Number, typename = typename std::enable_if< std::is_integral<Number>::value || std::is_floating_point<Number>::value, bool>::type>
Matrix strassens_multiplication (const Matrix< Number > &other) const
 Strassens method of multiplying two matrices References: https://en.wikipedia.org/wiki/Strassen_algorithm.
bool operator== (const Matrix< T > &other) const
 Compares two matrices if each of them are equal or not.

Private Attributes

std::vector< std::vector< T > > _mat

Friends

std::ostream & operator<< (std::ostream &out, const Matrix< T > &mat)

Detailed Description

template<typename T, typename = typename std::enable_if< std::is_integral<T>::value || std::is_floating_point<T>::value, bool>::type>
class divide_and_conquer::strassens_multiplication::Matrix< T, typename >

Matrix class.

Definition at line 40 of file strassen_matrix_multiplication.cpp.

Constructor & Destructor Documentation

◆ Matrix() [1/2]

template<typename T, typename = typename std::enable_if< std::is_integral<T>::value || std::is_floating_point<T>::value, bool>::type>
template<typename Integer, typename = typename std::enable_if< std::is_integral<Integer>::value, Integer>::type>
divide_and_conquer::strassens_multiplication::Matrix< T, typename >::Matrix ( const Integer size)
inlineexplicit

Constructor.

Template Parameters
Integerensuring integers are being evaluated and not other data types.
Parameters
sizedenoting the size of Matrix as size x size

Definition at line 53 of file strassen_matrix_multiplication.cpp.

53 {
54 for (size_t i = 0; i < size; ++i) {
55 _mat.emplace_back(std::vector<T>(size, 0));
56 }
57 }
divide_and_conquer::strassens_multiplication::Matrix
Matrix class.
Definition strassen_matrix_multiplication.cpp:40
divide_and_conquer::strassens_multiplication::Matrix::size
std::pair< size_t, size_t > size() const
Get the matrix shape.
Definition strassen_matrix_multiplication.cpp:79

◆ Matrix() [2/2]

template<typename T, typename = typename std::enable_if< std::is_integral<T>::value || std::is_floating_point<T>::value, bool>::type>
template<typename Integer, typename = typename std::enable_if< std::is_integral<Integer>::value, Integer>::type>
divide_and_conquer::strassens_multiplication::Matrix< T, typename >::Matrix ( const Integer rows,
const Integer cols )
inline

Constructor.

Template Parameters
Integerensuring integers are being evaluated and not other data types.
Parameters
rowsdenoting the total rows of Matrix
colsdenoting the total elements in each row of Matrix

Definition at line 69 of file strassen_matrix_multiplication.cpp.

69 {
70 for (size_t i = 0; i < rows; ++i) {
71 _mat.emplace_back(std::vector<T>(cols, 0));
72 }
73 }

Member Function Documentation

◆ h_stack()

template<typename T, typename = typename std::enable_if< std::is_integral<T>::value || std::is_floating_point<T>::value, bool>::type>
template<typename Number, typename = typename std::enable_if< std::is_integral<Number>::value || std::is_floating_point<Number>::value, Number>::type>
void divide_and_conquer::strassens_multiplication::Matrix< T, typename >::h_stack ( const Matrix< Number > & other)
inline

Horizontally stack the matrix (one after the other)

Template Parameters
Numberany type of number
Parameters
otherthe other matrix: note that this array is not modified
Returns
void, but modifies the current array

Definition at line 134 of file strassen_matrix_multiplication.cpp.

134 {
135 assert(_mat.size() == other._mat.size());
136 for (size_t i = 0; i < other._mat.size(); ++i) {
137 for (size_t j = 0; j < other._mat[i].size(); ++j) {
138 _mat[i].push_back(other._mat[i][j]);
139 }
140 }
141 }

◆ naive_multiplication()

template<typename T, typename = typename std::enable_if< std::is_integral<T>::value || std::is_floating_point<T>::value, bool>::type>
template<typename Number, typename = typename std::enable_if< std::is_integral<Number>::value || std::is_floating_point<Number>::value, bool>::type>
Matrix divide_and_conquer::strassens_multiplication::Matrix< T, typename >::naive_multiplication ( const Matrix< Number > & other) const
inline

Naive multiplication performed on this.

Template Parameters
Numberany real value to multiply
Parameters
otherOther matrix to multiply to this
Returns
new matrix

Definition at line 316 of file strassen_matrix_multiplication.cpp.

316 {
317 Matrix C = Matrix<Number>(_mat.size(), other._mat[0].size());
318
319 for (size_t i = 0; i < _mat.size(); ++i) {
320 for (size_t k = 0; k < _mat[0].size(); ++k) {
321 for (size_t j = 0; j < other._mat[0].size(); ++j) {
322 C._mat[i][j] += _mat[i][k] * other._mat[k][j];
323 }
324 }
325 }
326 return C;
327 }
divide_and_conquer::strassens_multiplication::Matrix::Matrix
Matrix(const Integer size)
Constructor.
Definition strassen_matrix_multiplication.cpp:53

◆ operator*() [1/2]

template<typename T, typename = typename std::enable_if< std::is_integral<T>::value || std::is_floating_point<T>::value, bool>::type>
template<typename Number, typename = typename std::enable_if< std::is_integral<Number>::value || std::is_floating_point<Number>::value, bool>::type>
Matrix divide_and_conquer::strassens_multiplication::Matrix< T, typename >::operator* ( const Matrix< Number > & other) const
inline

Multiply two matrices and returns a new matrix.

Template Parameters
Numberany real value to multiply
Parameters
otherOther matrix to multiply to this
Returns
new matrix

Definition at line 255 of file strassen_matrix_multiplication.cpp.

255 {
256 assert(_mat[0].size() == other._mat.size());
257 auto size = this->size();
258 const size_t row = size.first, col = size.second;
259 // Main condition for applying strassen's method:
260 // 1: matrix should be a square matrix
261 // 2: matrix should be of even size (mat.size() % 2 == 0)
262 return (row == col && (row & 1) == 0)
263 ? this->strassens_multiplication(other)
264 : this->naive_multiplication(other);
265 }
divide_and_conquer::strassens_multiplication::Matrix::naive_multiplication
Matrix naive_multiplication(const Matrix< Number > &other) const
Naive multiplication performed on this.
Definition strassen_matrix_multiplication.cpp:316
divide_and_conquer::strassens_multiplication::Matrix::strassens_multiplication
Matrix strassens_multiplication(const Matrix< Number > &other) const
Strassens method of multiplying two matrices References: https://en.wikipedia.org/wiki/Strassen_algor...
Definition strassen_matrix_multiplication.cpp:340

◆ operator*() [2/2]

template<typename T, typename = typename std::enable_if< std::is_integral<T>::value || std::is_floating_point<T>::value, bool>::type>
template<typename Number, typename = typename std::enable_if< std::is_integral<Number>::value || std::is_floating_point<Number>::value, bool>::type>
Matrix divide_and_conquer::strassens_multiplication::Matrix< T, typename >::operator* ( const Number other) const
inline

Multiply matrix with a number and returns a new matrix.

Template Parameters
Numberany real value to multiply
Parameters
otherOther real number to multiply to current matrix
Returns
new matrix

Definition at line 277 of file strassen_matrix_multiplication.cpp.

277 {
278 Matrix C = Matrix<Number>(_mat.size(), _mat[0].size());
279 for (size_t i = 0; i < _mat.size(); ++i) {
280 for (size_t j = 0; j < _mat[i].size(); ++j) {
281 C._mat[i][j] = _mat[i][j] * other;
282 }
283 }
284 return C;
285 }

◆ operator*=()

template<typename T, typename = typename std::enable_if< std::is_integral<T>::value || std::is_floating_point<T>::value, bool>::type>
template<typename Number, typename = typename std::enable_if< std::is_integral<Number>::value || std::is_floating_point<Number>::value, bool>::type>
Matrix & divide_and_conquer::strassens_multiplication::Matrix< T, typename >::operator*= ( const Number other) const
inline

Multiply a number to current matrix.

Template Parameters
Numberany real value to multiply
Parameters
otherOther matrix to multiply to this
Returns
reference of current matrix

Definition at line 297 of file strassen_matrix_multiplication.cpp.

297 {
298 for (size_t i = 0; i < _mat.size(); ++i) {
299 for (size_t j = 0; j < _mat[i].size(); ++j) {
300 _mat[i][j] *= other;
301 }
302 }
303 return this;
304 }

◆ operator+()

template<typename T, typename = typename std::enable_if< std::is_integral<T>::value || std::is_floating_point<T>::value, bool>::type>
template<typename Number, typename = typename std::enable_if< std::is_integral<Number>::value || std::is_floating_point<Number>::value, bool>::type>
Matrix divide_and_conquer::strassens_multiplication::Matrix< T, typename >::operator+ ( const Matrix< Number > & other) const
inline

Add two matrices and returns a new matrix.

Template Parameters
Numberany real value to add
Parameters
otherOther matrix to add to this
Returns
new matrix

Definition at line 173 of file strassen_matrix_multiplication.cpp.

173 {
174 assert(this->size() == other.size());
175 Matrix C = Matrix<Number>(_mat.size(), _mat[0].size());
176 for (size_t i = 0; i < _mat.size(); ++i) {
177 for (size_t j = 0; j < _mat[i].size(); ++j) {
178 C._mat[i][j] = _mat[i][j] + other._mat[i][j];
179 }
180 }
181 return C;
182 }

◆ operator+=()

template<typename T, typename = typename std::enable_if< std::is_integral<T>::value || std::is_floating_point<T>::value, bool>::type>
template<typename Number, typename = typename std::enable_if< std::is_integral<Number>::value || std::is_floating_point<Number>::value, bool>::type>
Matrix & divide_and_conquer::strassens_multiplication::Matrix< T, typename >::operator+= ( const Matrix< Number > & other) const
inline

Add another matrices to current matrix.

Template Parameters
Numberany real value to add
Parameters
otherOther matrix to add to this
Returns
reference of current matrix

Definition at line 194 of file strassen_matrix_multiplication.cpp.

194 {
195 assert(this->size() == other.size());
196 for (size_t i = 0; i < _mat.size(); ++i) {
197 for (size_t j = 0; j < _mat[i].size(); ++j) {
198 _mat[i][j] += other._mat[i][j];
199 }
200 }
201 return this;
202 }

◆ operator-()

template<typename T, typename = typename std::enable_if< std::is_integral<T>::value || std::is_floating_point<T>::value, bool>::type>
template<typename Number, typename = typename std::enable_if< std::is_integral<Number>::value || std::is_floating_point<Number>::value, bool>::type>
Matrix divide_and_conquer::strassens_multiplication::Matrix< T, typename >::operator- ( const Matrix< Number > & other) const
inline

Subtract two matrices and returns a new matrix.

Template Parameters
Numberany real value to multiply
Parameters
otherOther matrix to subtract to this
Returns
new matrix

Definition at line 214 of file strassen_matrix_multiplication.cpp.

214 {
215 assert(this->size() == other.size());
216 Matrix C = Matrix<Number>(_mat.size(), _mat[0].size());
217 for (size_t i = 0; i < _mat.size(); ++i) {
218 for (size_t j = 0; j < _mat[i].size(); ++j) {
219 C._mat[i][j] = _mat[i][j] - other._mat[i][j];
220 }
221 }
222 return C;
223 }

◆ operator-=()

template<typename T, typename = typename std::enable_if< std::is_integral<T>::value || std::is_floating_point<T>::value, bool>::type>
template<typename Number, typename = typename std::enable_if< std::is_integral<Number>::value || std::is_floating_point<Number>::value, bool>::type>
Matrix & divide_and_conquer::strassens_multiplication::Matrix< T, typename >::operator-= ( const Matrix< Number > & other) const
inline

Subtract another matrices to current matrix.

Template Parameters
Numberany real value to Subtract
Parameters
otherOther matrix to Subtract to this
Returns
reference of current matrix

Definition at line 235 of file strassen_matrix_multiplication.cpp.

235 {
236 assert(this->size() == other.size());
237 for (size_t i = 0; i < _mat.size(); ++i) {
238 for (size_t j = 0; j < _mat[i].size(); ++j) {
239 _mat[i][j] -= other._mat[i][j];
240 }
241 }
242 return this;
243 }

◆ operator==()

template<typename T, typename = typename std::enable_if< std::is_integral<T>::value || std::is_floating_point<T>::value, bool>::type>
bool divide_and_conquer::strassens_multiplication::Matrix< T, typename >::operator== ( const Matrix< T > & other) const
inline

Compares two matrices if each of them are equal or not.

Parameters
otherother matrix to compare
Returns
whether they are equal or not

Definition at line 393 of file strassen_matrix_multiplication.cpp.

393 {
394 if (_mat.size() != other._mat.size() ||
395 _mat[0].size() != other._mat[0].size()) {
396 return false;
397 }
398 for (size_t i = 0; i < _mat.size(); ++i) {
399 for (size_t j = 0; j < _mat[i].size(); ++j) {
400 if (_mat[i][j] != other._mat[i][j]) {
401 return false;
402 }
403 }
404 }
405 return true;
406 }

◆ operator[]()

template<typename T, typename = typename std::enable_if< std::is_integral<T>::value || std::is_floating_point<T>::value, bool>::type>
template<typename Integer, typename = typename std::enable_if< std::is_integral<Integer>::value, Integer>::type>
std::vector< T > & divide_and_conquer::strassens_multiplication::Matrix< T, typename >::operator[] ( const Integer index)
inline

returns the address of the element at ith place (here ith row of the matrix)

Template Parameters
Integerany valid integer
Parameters
indexindex which is requested
Returns
the address of the element (here ith row or array)

Definition at line 93 of file strassen_matrix_multiplication.cpp.

93 {
94 return _mat[index];
95 }

◆ size()

template<typename T, typename = typename std::enable_if< std::is_integral<T>::value || std::is_floating_point<T>::value, bool>::type>
std::pair< size_t, size_t > divide_and_conquer::strassens_multiplication::Matrix< T, typename >::size ( ) const
inline

Get the matrix shape.

Returns
pair of integer denoting total rows and columns

Definition at line 79 of file strassen_matrix_multiplication.cpp.

79 {
80 return {_mat.size(), _mat[0].size()};
81 }

◆ slice()

template<typename T, typename = typename std::enable_if< std::is_integral<T>::value || std::is_floating_point<T>::value, bool>::type>
Matrix divide_and_conquer::strassens_multiplication::Matrix< T, typename >::slice ( const size_t row_start,
const size_t row_end = MAX_SIZE,
const size_t col_start = MAX_SIZE,
const size_t col_end = MAX_SIZE ) const
inline

Creates a new matrix and returns a part of it.

Parameters
row_startstart of the row
row_endend of the row
col_startstart of the col
col_endend of the column
Returns
A slice of (row_end - row_start) x (col_end - col_start) size of array starting from row_start row and col_start column

Definition at line 106 of file strassen_matrix_multiplication.cpp.

108 {
109 const size_t h_size =
110 (row_end != MAX_SIZE ? row_end : _mat.size()) - row_start;
111 const size_t v_size = (col_end != MAX_SIZE ? col_end : _mat[0].size()) -
112 (col_start != MAX_SIZE ? col_start : 0);
113 Matrix result = Matrix<T>(h_size, v_size);
114
115 const size_t v_start = (col_start != MAX_SIZE ? col_start : 0);
116 for (size_t i = 0; i < h_size; ++i) {
117 for (size_t j = 0; j < v_size; ++j) {
118 result._mat[i][j] = _mat[i + row_start][j + v_start];
119 }
120 }
121 return result;
122 }

◆ strassens_multiplication()

template<typename T, typename = typename std::enable_if< std::is_integral<T>::value || std::is_floating_point<T>::value, bool>::type>
template<typename Number, typename = typename std::enable_if< std::is_integral<Number>::value || std::is_floating_point<Number>::value, bool>::type>
Matrix divide_and_conquer::strassens_multiplication::Matrix< T, typename >::strassens_multiplication ( const Matrix< Number > & other) const
inline

Strassens method of multiplying two matrices References: https://en.wikipedia.org/wiki/Strassen_algorithm.

Template Parameters
Numberany real value to multiply
Parameters
otherOther matrix to multiply to this
Returns
new matrix

Definition at line 340 of file strassen_matrix_multiplication.cpp.

340 {
341 const size_t size = _mat.size();
342 // Base case: when a matrix is small enough for faster naive
343 // multiplication, or the matrix is of odd size, then go with the naive
344 // multiplication route;
345 // else; go with the strassen's method.
346 if (size <= 64ULL || (size & 1ULL)) {
347 return this->naive_multiplication(other);
348 } else {
349 const Matrix<Number>
350 A = this->slice(0ULL, size >> 1, 0ULL, size >> 1),
351 B = this->slice(0ULL, size >> 1, size >> 1, size),
352 C = this->slice(size >> 1, size, 0ULL, size >> 1),
353 D = this->slice(size >> 1, size, size >> 1, size),
354 E = other.slice(0ULL, size >> 1, 0ULL, size >> 1),
355 F = other.slice(0ULL, size >> 1, size >> 1, size),
356 G = other.slice(size >> 1, size, 0ULL, size >> 1),
357 H = other.slice(size >> 1, size, size >> 1, size);
358
359 Matrix P1 = A.strassens_multiplication(F - H);
360 Matrix P2 = (A + B).strassens_multiplication(H);
361 Matrix P3 = (C + D).strassens_multiplication(E);
362 Matrix P4 = D.strassens_multiplication(G - E);
363 Matrix P5 = (A + D).strassens_multiplication(E + H);
364 Matrix P6 = (B - D).strassens_multiplication(G + H);
365 Matrix P7 = (A - C).strassens_multiplication(E + F);
366
367 // Building final matrix C11 would be
368 // [ | ]
369 // [ C11 | C12 ]
370 // C = [ ____ | ____ ]
371 // [ | ]
372 // [ C21 | C22 ]
373 // [ | ]
374
375 Matrix C11 = P5 + P4 - P2 + P6;
376 Matrix C12 = P1 + P2;
377 Matrix C21 = P3 + P4;
378 Matrix C22 = P1 + P5 - P3 - P7;
379
380 C21.h_stack(C22);
381 C11.h_stack(C12);
382 C11.v_stack(C21);
383
384 return C11;
385 }
386 }
divide_and_conquer::strassens_multiplication::Matrix::slice
Matrix slice(const size_t row_start, const size_t row_end=MAX_SIZE, const size_t col_start=MAX_SIZE, const size_t col_end=MAX_SIZE) const
Creates a new matrix and returns a part of it.
Definition strassen_matrix_multiplication.cpp:106
divide_and_conquer::strassens_multiplication::Matrix::h_stack
void h_stack(const Matrix< Number > &other)
Horizontally stack the matrix (one after the other)
Definition strassen_matrix_multiplication.cpp:134
divide_and_conquer::strassens_multiplication::Matrix::v_stack
void v_stack(const Matrix< Number > &other)
Horizontally stack the matrix (current matrix above the other)
Definition strassen_matrix_multiplication.cpp:153

◆ v_stack()

template<typename T, typename = typename std::enable_if< std::is_integral<T>::value || std::is_floating_point<T>::value, bool>::type>
template<typename Number, typename = typename std::enable_if< std::is_integral<Number>::value || std::is_floating_point<Number>::value, Number>::type>
void divide_and_conquer::strassens_multiplication::Matrix< T, typename >::v_stack ( const Matrix< Number > & other)
inline

Horizontally stack the matrix (current matrix above the other)

Template Parameters
Numberany type of number (Integer or floating point)
Parameters
otherthe other matrix: note that this array is not modified
Returns
void, but modifies the current array

Definition at line 153 of file strassen_matrix_multiplication.cpp.

153 {
154 assert(_mat[0].size() == other._mat[0].size());
155 for (size_t i = 0; i < other._mat.size(); ++i) {
156 _mat.emplace_back(std::vector<T>(other._mat[i].size()));
157 for (size_t j = 0; j < other._mat[i].size(); ++j) {
158 _mat.back()[j] = other._mat[i][j];
159 }
160 }
161 }

◆ operator<<

template<typename T, typename = typename std::enable_if< std::is_integral<T>::value || std::is_floating_point<T>::value, bool>::type>
std::ostream & operator<< ( std::ostream & out,
const Matrix< T > & mat )
friend

Definition at line 408 of file strassen_matrix_multiplication.cpp.

408 {
409 for (auto &row : mat._mat) {
410 for (auto &elem : row) {
411 out << elem << " ";
412 }
413 out << "\n";
414 }
415 return out << "\n";
416 }

Member Data Documentation

◆ _mat

template<typename T, typename = typename std::enable_if< std::is_integral<T>::value || std::is_floating_point<T>::value, bool>::type>
std::vector<std::vector<T> > divide_and_conquer::strassens_multiplication::Matrix< T, typename >::_mat
private

Definition at line 41 of file strassen_matrix_multiplication.cpp.

The documentation for this class was generated from the following file: