Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
Loading...
Searching...
No Matches
Public Member Functions | Private Attributes | Friends | List of all members
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.

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
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::size
std::pair< size_t, size_t > size() const
Get the matrix shape.
Definition strassen_matrix_multiplication.cpp:79
std::vector::emplace_back
T emplace_back(T... args)
Here is the call graph for this function:

◆ 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
69 {
70 for (size_t i = 0; i < rows; ++i) {
71 _mat.emplace_back(std::vector<T>(cols, 0));
72 }
73 }
Here is the call graph for this function:

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
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 }
std::vector::push_back
T push_back(T... args)
std::vector::size
T size(T... args)
Here is the call graph for this function:

◆ 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
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
numerical_methods::simpson_method::k
double k(double x)
Another test function.
Definition composite_simpson_rule.cpp:117
Here is the call graph for this function:

◆ 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
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
strassens_multiplication
Namespace for performing strassen's multiplication.
Here is the call graph for this function:

◆ 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
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 }
Here is the call graph for this function:

◆ 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
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 }
Here is the call graph for this function:

◆ 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
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 }
Here is the call graph for this function:

◆ 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
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 }
Here is the call graph for this function:

◆ 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
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 }
Here is the call graph for this function:

◆ 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
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 }
Here is the call graph for this function:

◆ 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
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 }
Here is the call graph for this function:

◆ 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)
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
79 {
80 return {_mat.size(), _mat[0].size()};
81 }
Here is the call graph for this function:

◆ 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
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 }
math::fibonacci_sum::result
uint64_t result(uint64_t n)
Definition fibonacci_sum.cpp:76
Here is the call graph for this function:

◆ 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
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::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
Here is the call graph for this function:

◆ 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
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 }
std::vector::back
T back(T... args)
Here is the call graph for this function:

Friends And Related Symbol Documentation

◆ 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
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 }
The documentation for this class was generated from the following file: