STXXL  1.4.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
matrix.h
Go to the documentation of this file.
1 /***************************************************************************
2  * include/stxxl/bits/containers/matrix.h
3  *
4  * Part of the STXXL. See http://stxxl.sourceforge.net
5  *
6  * Copyright (C) 2010-2011 Raoul Steffen <[email protected]>
7  *
8  * Distributed under the Boost Software License, Version 1.0.
9  * (See accompanying file LICENSE_1_0.txt or copy at
10  * http://www.boost.org/LICENSE_1_0.txt)
11  **************************************************************************/
12 
13 #ifndef STXXL_CONTAINERS_MATRIX_HEADER
14 #define STXXL_CONTAINERS_MATRIX_HEADER
15 
20 
22 
23 //! \defgroup matrix matrix
24 //! Efficient external memory matrix operations
25 //! \ingroup stlcont
26 //! \{
27 
28 /* index-variable naming convention:
29  * [MODIFIER_][UNIT_]DIMENSION[_in_[MODIFIER_]ENVIRONMENT]
30  *
31  * e.g.:
32  * block_row = number of row measured in rows consisting of blocks
33  * element_row_in_block = number of row measured in rows consisting of elements in the (row of) block(s)
34  *
35  * size-variable naming convention:
36  * [MODIFIER_][ENVIRONMENT_]DIMENSION[_in_UNITs]
37  *
38  * e.g.
39  * height_in_blocks
40  */
41 
42 // forward declaration
43 template <typename ValueType, unsigned BlockSideLength>
44 class matrix;
45 
46 //! external column-vector container for matrix multiplication
47 //! \tparam ValueType type of contained objects (POD with no references to internal memory)
48 template <typename ValueType>
49 class column_vector : public vector<ValueType>
50 {
51 public:
54 
55  using vector_type::size;
56 
57  //! \param n number of elements
59  : vector_type(n) { }
60 
61  column_vector operator + (const column_vector& right) const
62  {
63  assert(size() == right.size());
64  column_vector res(size());
65  for (size_type i = 0; i < size(); ++i)
66  res[i] = (*this)[i] + right[i];
67  return res;
68  }
69 
70  column_vector operator - (const column_vector& right) const
71  {
72  assert(size() == right.size());
73  column_vector res(size());
74  for (size_type i = 0; i < size(); ++i)
75  res[i] = (*this)[i] - right[i];
76  return res;
77  }
78 
79  column_vector operator * (const ValueType scalar) const
80  {
81  column_vector res(size());
82  for (size_type i = 0; i < size(); ++i)
83  res[i] = (*this)[i] * scalar;
84  return res;
85  }
86 
88  {
89  assert(size() == right.size());
90  for (size_type i = 0; i < size(); ++i)
91  (*this)[i] += right[i];
92  return *this;
93  }
94 
95  column_vector& operator -= (const column_vector& right)
96  {
97  assert(size() == right.size());
98  for (size_type i = 0; i < size(); ++i)
99  (*this)[i] -= right[i];
100  return *this;
101  }
102 
103  column_vector& operator *= (const ValueType scalar)
104  {
105  for (size_type i = 0; i < size(); ++i)
106  (*this)[i] *= scalar;
107  return *this;
108  }
109 
110  void set_zero()
111  {
112  for (typename vector_type::iterator it = vector_type::begin(); it != vector_type::end(); ++it)
113  *it = 0;
114  }
115 };
116 
117 //! external row-vector container for matrix multiplication
118 //! \tparam ValueType type of contained objects (POD with no references to internal memory)
119 template <typename ValueType>
120 class row_vector : public vector<ValueType>
121 {
122 public:
125 
126  using vector_type::size;
127 
128  //! \param n number of elements
130  : vector_type(n) { }
131 
132  row_vector operator + (const row_vector& right) const
133  {
134  assert(size() == right.size());
135  row_vector res(size());
136  for (size_type i = 0; i < size(); ++i)
137  res[i] = (*this)[i] + right[i];
138  return res;
139  }
140 
141  row_vector operator - (const row_vector& right) const
142  {
143  assert(size() == right.size());
144  row_vector res(size());
145  for (size_type i = 0; i < size(); ++i)
146  res[i] = (*this)[i] - right[i];
147  return res;
148  }
149 
150  row_vector operator * (const ValueType scalar) const
151  {
152  row_vector res(size());
153  for (size_type i = 0; i < size(); ++i)
154  res[i] = (*this)[i] * scalar;
155  return res;
156  }
157 
158  template <unsigned BlockSideLength>
159  row_vector operator * (const matrix<ValueType, BlockSideLength>& right) const
160  { return right.multiply_from_left(*this); }
161 
162  ValueType operator * (const column_vector<ValueType>& right) const
163  {
164  ValueType res = 0;
165  for (size_type i = 0; i < size(); ++i)
166  res += (*this)[i] * right[i];
167  return res;
168  }
169 
171  {
172  assert(size() == right.size());
173  for (size_type i = 0; i < size(); ++i)
174  (*this)[i] += right[i];
175  return *this;
176  }
177 
178  row_vector& operator -= (const row_vector& right)
179  {
180  assert(size() == right.size());
181  for (size_type i = 0; i < size(); ++i)
182  (*this)[i] -= right[i];
183  return *this;
184  }
185 
186  row_vector& operator *= (const ValueType scalar)
187  {
188  for (size_type i = 0; i < size(); ++i)
189  (*this)[i] *= scalar;
190  return *this;
191  }
192 
193  void set_zero()
194  {
195  for (typename vector_type::iterator it = vector_type::begin(); it != vector_type::end(); ++it)
196  *it = 0;
197  }
198 };
199 
200 //! Specialized swappable_block that interprets uninitialized as containing zeros.
201 //! \tparam ValueType type of contained objects (POD with no references to internal memory)
202 //! \tparam BlockSideLength side length of a matrix block
203 //!
204 //! When initializing, all values are set to zero.
205 template <typename ValueType, unsigned BlockSideLength>
206 class matrix_swappable_block : public swappable_block<ValueType, BlockSideLength* BlockSideLength>
207 {
208 public:
210 
212 
214  {
215  // get_internal_block checks acquired
216  internal_block_type& data = get_internal_block();
217  #if STXXL_PARALLEL
218  #pragma omp parallel for
219  #endif
220  for (int_type row = 0; row < int_type(BlockSideLength); ++row)
221  for (int_type col = 0; col < int_type(BlockSideLength); ++col)
222  data[row * BlockSideLength + col] = 0;
223  }
224 };
225 
226 //! External container for a (sub)matrix. Not intended for direct use.
227 //! \tparam ValueType type of contained objects (POD with no references to internal memory)
228 //! \tparam BlockSideLength side length of a matrix block
229 //!
230 //! Stores blocks only, so all measures (height, width, row, col) are in blocks.
231 template <typename ValueType, unsigned BlockSideLength>
233 {
234 public:
239  typedef std::vector<swappable_block_identifier_type> blocks_type;
241 
243 
244 private:
245  // assigning is not allowed
246  swappable_block_matrix& operator = (const swappable_block_matrix& other);
247 
248 protected:
249  //! height of the matrix in blocks
250  size_type height,
251  //! width of the matrix in blocks
252  width,
253  //! height copied from supermatrix in blocks
254  height_from_supermatrix,
255  //! width copied from supermatrix in blocks
257  //! the matrice's blocks in row-major
259  //! if the elements in each block are in col-major instead of row-major
261 
262  //! get identifier of the block at (row, col)
264  { return blocks[row * width + col]; }
265 
266 public:
267  //! Create an empty swappable_block_matrix of given dimensions.
268  swappable_block_matrix(block_scheduler_type& bs, const size_type height_in_blocks, const size_type width_in_blocks, const bool transposed = false)
269  : bs(bs),
270  height(height_in_blocks),
271  width(width_in_blocks),
272  height_from_supermatrix(0),
273  width_from_supermatrix(0),
274  blocks(height * width),
275  elements_in_blocks_transposed(transposed)
276  {
277  for (size_type row = 0; row < height; ++row)
278  for (size_type col = 0; col < width; ++col)
279  bl(row, col) = bs.allocate_swappable_block();
280  }
281 
282  //! Create swappable_block_matrix of given dimensions that
283  //! represents the submatrix of supermatrix starting at (from_row_in_blocks, from_col_in_blocks).
284  //!
285  //! If supermatrix is not large enough, the submatrix is padded with empty blocks.
286  //! The supermatrix must not be destructed or transposed before the submatrix is destructed.
288  const size_type height_in_blocks, const size_type width_in_blocks,
289  const size_type from_row_in_blocks, const size_type from_col_in_blocks)
290  : bs(supermatrix.bs),
291  height(height_in_blocks),
292  width(width_in_blocks),
293  height_from_supermatrix(std::min(supermatrix.height - from_row_in_blocks, height)),
294  width_from_supermatrix(std::min(supermatrix.width - from_col_in_blocks, width)),
295  blocks(height * width),
296  elements_in_blocks_transposed(supermatrix.elements_in_blocks_transposed)
297  {
298  for (size_type row = 0; row < height_from_supermatrix; ++row)
299  {
300  for (size_type col = 0; col < width_from_supermatrix; ++col)
301  bl(row, col) = supermatrix.block(row + from_row_in_blocks, col + from_col_in_blocks);
302  for (size_type col = width_from_supermatrix; col < width; ++col)
303  bl(row, col) = bs.allocate_swappable_block();
304  }
305  for (size_type row = height_from_supermatrix; row < height; ++row)
306  for (size_type col = 0; col < width; ++col)
307  bl(row, col) = bs.allocate_swappable_block();
308  }
309 
310  //! Create swappable_block_matrix that represents the combination matrix ul ur dl dr.
311  //!
312  //! The submatrices are assumed to be of fitting dimensions and equal transposition.
313  //! The submatrices must not be destructed or transposed before the matrix is destructed.
315  const swappable_block_matrix& dl, const swappable_block_matrix& dr)
316  : bs(ul.bs),
317  height(ul.height + dl.height),
318  width(ul.width + ur.width),
319  height_from_supermatrix(height),
320  width_from_supermatrix(width),
321  blocks(height * width),
322  elements_in_blocks_transposed(ul.elements_in_blocks_transposed)
323  {
324  for (size_type row = 0; row < ul.height; ++row)
325  {
326  for (size_type col = 0; col < ul.width; ++col)
327  bl(row, col) = ul.block(row, col);
328  for (size_type col = ul.width; col < width; ++col)
329  bl(row, col) = ur.block(row, col - ul.width);
330  }
331  for (size_type row = ul.height; row < height; ++row)
332  {
333  for (size_type col = 0; col < ul.width; ++col)
334  bl(row, col) = dl.block(row - ul.height, col);
335  for (size_type col = ul.width; col < width; ++col)
336  bl(row, col) = dr.block(row - ul.height, col - ul.width);
337  }
338  }
339 
341  : atomic_counted_object(other),
342  bs(other.bs),
343  height(other.height),
344  width(other.width),
345  height_from_supermatrix(0),
346  width_from_supermatrix(0),
347  blocks(height * width),
348  elements_in_blocks_transposed(false)
349  {
350  for (size_type row = 0; row < height; ++row)
351  for (size_type col = 0; col < width; ++col)
352  bl(row, col) = bs.allocate_swappable_block();
353  // 0 + other is copying
354  Ops::element_op(*this, other, typename Ops::addition());
355  }
356 
358  {
359  for (size_type row = 0; row < height_from_supermatrix; ++row)
360  {
361  for (size_type col = width_from_supermatrix; col < width; ++col)
362  bs.free_swappable_block(bl(row, col));
363  }
364  for (size_type row = height_from_supermatrix; row < height; ++row)
365  for (size_type col = 0; col < width; ++col)
366  bs.free_swappable_block(bl(row, col));
367  }
368 
370  { return index / BlockSideLength; }
371 
373  { return index % BlockSideLength; }
374 
375  // regards transposed
377  {
378  return (is_transposed())
379  ? row % BlockSideLength + col % BlockSideLength * BlockSideLength
380  : row % BlockSideLength * BlockSideLength + col % BlockSideLength;
381  }
382 
383  //! get identifier of the block at (row, col)
384  const swappable_block_identifier_type & block(const size_type row, const size_type col) const
385  { return blocks[row * width + col]; }
386 
387  //! get identifier of the block at (row, col)
388  const swappable_block_identifier_type& operator () (const size_type row, const size_type col) const
389  { return block(row, col); }
390 
391  const size_type & get_height() const
392  { return height; }
393 
394  const size_type & get_width() const
395  { return width; }
396 
397  //! if the elements inside the blocks are in transposed order i.e. column-major
398  const bool & is_transposed() const
399  { return elements_in_blocks_transposed; }
400 
401  void transpose()
402  {
403  // transpose matrix of blocks
404  blocks_type bn(blocks.size());
405  for (size_type row = 0; row < height; ++row)
406  for (size_type col = 0; col < width; ++col)
407  bn[col * height + row] = bl(row, col);
408  bn.swap(blocks);
409  // swap dimensions
410  std::swap(height, width);
411  std::swap(height_from_supermatrix, width_from_supermatrix);
412  elements_in_blocks_transposed = ! elements_in_blocks_transposed;
413  }
414 
415  void set_zero()
416  {
417  for (typename blocks_type::iterator it = blocks.begin(); it != blocks.end(); ++it)
418  bs.deinitialize(*it);
419  }
420 };
421 
422 //! general iterator type that points to single elements inside a matrix
423 //! \tparam ValueType type of contained objects (POD with no references to internal memory)
424 //! \tparam BlockSideLength side length of a matrix block
425 template <typename ValueType, unsigned BlockSideLength>
427 {
428 protected:
435 
436  template <typename VT, unsigned BSL>
437  friend class matrix;
438 
439  template <typename VT, unsigned BSL>
440  friend class const_matrix_iterator;
441 
443  elem_size_type current_row, // \ both indices == -1 <=> empty iterator
444  current_col; // /
446  current_block_col;
447  internal_block_type* current_iblock; // NULL if block is not acquired
448 
450  {
451  if (! current_iblock)
452  current_iblock = &m->data->bs.acquire(m->data->block(current_block_row, current_block_col));
453  }
454 
456  {
457  if (current_iblock)
458  {
459  m->data->bs.release(m->data->block(current_block_row, current_block_col), true);
460  current_iblock = 0;
461  }
462  }
463 
464  //! create iterator pointing to given row and col
465  matrix_iterator(matrix_type& matrix, const elem_size_type start_row, const elem_size_type start_col)
466  : m(&matrix),
467  current_row(start_row),
468  current_col(start_col),
469  current_block_row(m->data->block_index_from_elem(start_row)),
470  current_block_col(m->data->block_index_from_elem(start_col)),
471  current_iblock(0) { }
472 
473  //! create empty iterator
475  : m(&matrix),
476  current_row(-1), // empty iterator
477  current_col(-1),
478  current_block_row(-1),
479  current_block_col(-1),
480  current_iblock(0) { }
481 
482  void set_empty()
483  {
484  release_current_iblock();
485  current_row = -1;
486  current_col = -1;
487  current_block_row = -1;
488  current_block_col = -1;
489  }
490 
491 public:
493  : m(other.m),
494  current_row(other.current_row),
495  current_col(other.current_col),
496  current_block_row(other.current_block_row),
497  current_block_col(other.current_block_col),
498  current_iblock(0)
499  {
500  if (other.current_iblock)
501  acquire_current_iblock();
502  }
503 
504  matrix_iterator& operator = (const matrix_iterator& other)
505  {
506  set_pos(other.current_row, other.current_col);
507  m = other.m;
508  if (other.current_iblock)
509  acquire_current_iblock();
510  return *this;
511  }
512 
514  { release_current_iblock(); }
515 
516  void set_row(const elem_size_type new_row)
517  {
518  const block_size_type new_block_row = m->data->block_index_from_elem(new_row);
519  if (new_block_row != current_block_row)
520  {
521  release_current_iblock();
522  current_block_row = new_block_row;
523  }
524  current_row = new_row;
525  }
526 
527  void set_col(const elem_size_type new_col)
528  {
529  const block_size_type new_block_col = m->data->block_index_from_elem(new_col);
530  if (new_block_col != current_block_col)
531  {
532  release_current_iblock();
533  current_block_col = new_block_col;
534  }
535  current_col = new_col;
536  }
537 
538  void set_pos(const elem_size_type new_row, const elem_size_type new_col)
539  {
540  const block_size_type new_block_row = m->data->block_index_from_elem(new_row),
541  new_block_col = m->data->block_index_from_elem(new_col);
542  if (new_block_col != current_block_col || new_block_row != current_block_row)
543  {
544  release_current_iblock();
545  current_block_row = new_block_row;
546  current_block_col = new_block_col;
547  }
548  current_row = new_row;
549  current_col = new_col;
550  }
551 
552  void set_pos(const std::pair<elem_size_type, elem_size_type> new_pos)
553  { set_pos(new_pos.first, new_pos.second); }
554 
555  const elem_size_type & get_row() const
556  { return current_row; }
557 
558  const elem_size_type & get_col() const
559  { return current_col; }
560 
561  std::pair<elem_size_type, elem_size_type> get_pos() const
562  { return std::make_pair(current_row, current_col); }
563 
564  bool empty() const
565  { return current_row == -1 && current_col == -1; }
566 
567  operator bool () const
568  { return ! empty(); }
569 
570  bool operator == (const matrix_iterator& other) const
571  {
572  return current_row == other.current_row && current_col == other.current_col && m == other.m;
573  }
574 
575  //! Returns reference access to the element referenced by the iterator.
576  //! The reference is only valid so long as the iterator is not moved.
577  ValueType& operator * ()
578  {
579  acquire_current_iblock();
580  return (*current_iblock)[m->data->elem_index_in_block_from_elem(current_row, current_col)];
581  }
582 };
583 
584 //! row-major iterator that points to single elements inside a matrix
585 //! \tparam ValueType type of contained objects (POD with no references to internal memory)
586 //! \tparam BlockSideLength side length of a matrix block
587 template <typename ValueType, unsigned BlockSideLength>
588 class matrix_row_major_iterator : public matrix_iterator<ValueType, BlockSideLength>
589 {
590 protected:
594 
595  template <typename VT, unsigned BSL>
596  friend class matrix;
597 
598  using matrix_iterator_type::m;
599  using matrix_iterator_type::set_empty;
600 
601  //! create iterator pointing to given row and col
603  : matrix_iterator_type(matrix, start_row, start_col) { }
604 
605  //! create empty iterator
607  : matrix_iterator_type(matrix) { }
608 
609 public:
610  //! convert from matrix_iterator
612  : matrix_iterator_type(matrix_iterator) { }
613 
614  // Has to be not empty, else behavior is undefined.
616  {
617  if (get_col() + 1 < m->get_width())
618  // => not matrix_row_major_iterator the end of row, move right
619  set_col(get_col() + 1);
620  else if (get_row() + 1 < m->get_height())
621  // => at end of row but not last row, move to beginning of next row
622  set_pos(get_row() + 1, 0);
623  else
624  // => at end of matrix, set to empty-state
625  set_empty();
626  return *this;
627  }
628 
629  // Has to be not empty, else behavior is undefined.
631  {
632  if (get_col() - 1 >= 0)
633  // => not at the beginning of row, move left
634  set_col(get_col() - 1);
635  else if (get_row() - 1 >= 0)
636  // => at beginning of row but not first row, move to end of previous row
637  set_pos(get_row() - 1, m->get_width() - 1);
638  else
639  // => at beginning of matrix, set to empty-state
640  set_empty();
641  return *this;
642  }
643 
644  using matrix_iterator_type::get_row;
645  using matrix_iterator_type::get_col;
646  using matrix_iterator_type::set_col;
647  using matrix_iterator_type::set_pos;
648 };
649 
650 //! column-major iterator that points to single elements inside a matrix
651 //! \tparam ValueType type of contained objects (POD with no references to internal memory)
652 //! \tparam BlockSideLength side length of a matrix block
653 template <typename ValueType, unsigned BlockSideLength>
654 class matrix_col_major_iterator : public matrix_iterator<ValueType, BlockSideLength>
655 {
656 protected:
660 
661  template <typename VT, unsigned BSL>
662  friend class matrix;
663 
664  using matrix_iterator_type::m;
665  using matrix_iterator_type::set_empty;
666 
667  //! create iterator pointing to given row and col
669  : matrix_iterator_type(matrix, start_row, start_col) { }
670 
671  //! create empty iterator
673  : matrix_iterator_type(matrix) { }
674 
675 public:
676  //! convert from matrix_iterator
678  : matrix_iterator_type(matrix_iterator) { }
679 
680  // Has to be not empty, else behavior is undefined.
682  {
683  if (get_row() + 1 < m->get_height())
684  // => not at the end of col, move down
685  set_row(get_row() + 1);
686  else if (get_col() + 1 < m->get_width())
687  // => at end of col but not last col, move to beginning of next col
688  set_pos(0, get_col() + 1);
689  else
690  // => at end of matrix, set to empty-state
691  set_empty();
692  return *this;
693  }
694 
695  // Has to be not empty, else behavior is undefined.
697  {
698  if (get_row() - 1 >= 0)
699  // => not at the beginning of col, move up
700  set_row(get_row() - 1);
701  else if (get_col() - 1 >= 0)
702  // => at beginning of col but not first col, move to end of previous col
703  set_pos(m->get_height() - 1, get_col() - 1);
704  else
705  // => at beginning of matrix, set to empty-state
706  set_empty();
707  return *this;
708  }
709 
710  using matrix_iterator_type::get_row;
711  using matrix_iterator_type::get_col;
712  using matrix_iterator_type::set_row;
713  using matrix_iterator_type::set_pos;
714 };
715 
716 //! general const_iterator type that points to single elements inside a matrix
717 //! \tparam ValueType type of contained objects (POD with no references to internal memory)
718 //! \tparam BlockSideLength side length of a matrix block
719 template <typename ValueType, unsigned BlockSideLength>
721 {
722 protected:
729 
730  template <typename VT, unsigned BSL>
731  friend class matrix;
732 
733  const matrix_type* m;
734  elem_size_type current_row, // \ both indices == -1 <=> empty iterator
735  current_col; // /
737  current_block_col;
738  internal_block_type* current_iblock; // NULL if block is not acquired
739 
741  {
742  if (! current_iblock)
743  current_iblock = &m->data->bs.acquire(m->data->block(current_block_row, current_block_col));
744  }
745 
747  {
748  if (current_iblock)
749  {
750  m->data->bs.release(m->data->block(current_block_row, current_block_col), false);
751  current_iblock = 0;
752  }
753  }
754 
755  //! create iterator pointing to given row and col
756  const_matrix_iterator(const matrix_type& matrix, const elem_size_type start_row, const elem_size_type start_col)
757  : m(&matrix),
758  current_row(start_row),
759  current_col(start_col),
760  current_block_row(m->data->block_index_from_elem(start_row)),
761  current_block_col(m->data->block_index_from_elem(start_col)),
762  current_iblock(0) { }
763 
764  //! create empty iterator
766  : m(&matrix),
767  current_row(-1), // empty iterator
768  current_col(-1),
769  current_block_row(-1),
770  current_block_col(-1),
771  current_iblock(0) { }
772 
773  void set_empty()
774  {
775  release_current_iblock();
776  current_row = -1;
777  current_col = -1;
778  current_block_row = -1;
779  current_block_col = -1;
780  }
781 
782 public:
784  : m(other.m),
785  current_row(other.current_row),
786  current_col(other.current_col),
787  current_block_row(other.current_block_row),
788  current_block_col(other.current_block_col),
789  current_iblock(0)
790  {
791  if (other.current_iblock)
792  acquire_current_iblock();
793  }
794 
796  : m(other.m),
797  current_row(other.current_row),
798  current_col(other.current_col),
799  current_block_row(other.current_block_row),
800  current_block_col(other.current_block_col),
801  current_iblock(0)
802  {
803  if (other.current_iblock)
804  acquire_current_iblock();
805  }
806 
807  const_matrix_iterator& operator = (const const_matrix_iterator& other)
808  {
809  set_pos(other.current_row, other.current_col);
810  m = other.m;
811  if (other.current_iblock)
812  acquire_current_iblock();
813  return *this;
814  }
815 
817  { release_current_iblock(); }
818 
819  void set_row(const elem_size_type new_row)
820  {
821  const block_size_type new_block_row = m->data->block_index_from_elem(new_row);
822  if (new_block_row != current_block_row)
823  {
824  release_current_iblock();
825  current_block_row = new_block_row;
826  }
827  current_row = new_row;
828  }
829 
830  void set_col(const elem_size_type new_col)
831  {
832  const block_size_type new_block_col = m->data->block_index_from_elem(new_col);
833  if (new_block_col != current_block_col)
834  {
835  release_current_iblock();
836  current_block_col = new_block_col;
837  }
838  current_col = new_col;
839  }
840 
841  void set_pos(const elem_size_type new_row, const elem_size_type new_col)
842  {
843  const block_size_type new_block_row = m->data->block_index_from_elem(new_row),
844  new_block_col = m->data->block_index_from_elem(new_col);
845  if (new_block_col != current_block_col || new_block_row != current_block_row)
846  {
847  release_current_iblock();
848  current_block_row = new_block_row;
849  current_block_col = new_block_col;
850  }
851  current_row = new_row;
852  current_col = new_col;
853  }
854 
855  void set_pos(const std::pair<elem_size_type, elem_size_type> new_pos)
856  { set_pos(new_pos.first, new_pos.second); }
857 
858  const elem_size_type & get_row() const
859  { return current_row; }
860 
861  const elem_size_type & get_col() const
862  { return current_col; }
863 
864  std::pair<elem_size_type, elem_size_type> get_pos() const
865  { return std::make_pair(current_row, current_col); }
866 
867  bool empty() const
868  { return current_row == -1 && current_col == -1; }
869 
870  operator bool () const
871  { return ! empty(); }
872 
873  bool operator == (const const_matrix_iterator& other) const
874  {
875  return current_row == other.current_row && current_col == other.current_col && m == other.m;
876  }
877 
878  //! Returns reference access to the element referenced by the iterator.
879  //! The reference is only valid so long as the iterator is not moved.
880  const ValueType& operator * ()
881  {
882  acquire_current_iblock();
883  return (*current_iblock)[m->data->elem_index_in_block_from_elem(current_row, current_col)];
884  }
885 };
886 
887 //! row-major const_iterator that points to single elements inside a matrix
888 //! \tparam ValueType type of contained objects (POD with no references to internal memory)
889 //! \tparam BlockSideLength side length of a matrix block
890 template <typename ValueType, unsigned BlockSideLength>
891 class const_matrix_row_major_iterator : public const_matrix_iterator<ValueType, BlockSideLength>
892 {
893 protected:
897 
898  template <typename VT, unsigned BSL>
899  friend class matrix;
900 
901  using const_matrix_iterator_type::m;
902  using const_matrix_iterator_type::set_empty;
903 
904  //! create iterator pointing to given row and col
906  : const_matrix_iterator_type(matrix, start_row, start_col) { }
907 
908  //! create empty iterator
910  : const_matrix_iterator_type(matrix) { }
911 
912 public:
913  //! convert from matrix_iterator
915  : const_matrix_iterator_type(matrix_iterator) { }
916 
917  //! convert from matrix_iterator
919  : const_matrix_iterator_type(matrix_iterator) { }
920 
921  // Has to be not empty, else behavior is undefined.
923  {
924  if (get_col() + 1 < m->get_width())
925  // => not matrix_row_major_iterator the end of row, move right
926  set_col(get_col() + 1);
927  else if (get_row() + 1 < m->get_height())
928  // => at end of row but not last row, move to beginning of next row
929  set_pos(get_row() + 1, 0);
930  else
931  // => at end of matrix, set to empty-state
932  set_empty();
933  return *this;
934  }
935 
936  // Has to be not empty, else behavior is undefined.
938  {
939  if (get_col() - 1 >= 0)
940  // => not at the beginning of row, move left
941  set_col(get_col() - 1);
942  else if (get_row() - 1 >= 0)
943  // => at beginning of row but not first row, move to end of previous row
944  set_pos(get_row() - 1, m->get_width() - 1);
945  else
946  // => at beginning of matrix, set to empty-state
947  set_empty();
948  return *this;
949  }
950 
951  using const_matrix_iterator_type::get_row;
952  using const_matrix_iterator_type::get_col;
953  using const_matrix_iterator_type::set_col;
954  using const_matrix_iterator_type::set_pos;
955 };
956 
957 //! column-major const_iterator that points to single elements inside a matrix
958 //! \tparam ValueType type of contained objects (POD with no references to internal memory)
959 //! \tparam BlockSideLength side length of a matrix block
960 template <typename ValueType, unsigned BlockSideLength>
961 class const_matrix_col_major_iterator : public const_matrix_iterator<ValueType, BlockSideLength>
962 {
963 protected:
967 
968  template <typename VT, unsigned BSL>
969  friend class matrix;
970 
971  using const_matrix_iterator_type::m;
972  using const_matrix_iterator_type::set_empty;
973 
974  //! create iterator pointing to given row and col
976  : const_matrix_iterator_type(matrix, start_row, start_col) { }
977 
978  //! create empty iterator
980  : const_matrix_iterator_type(matrix) { }
981 
982 public:
983  //! convert from matrix_iterator
985  : const_matrix_iterator_type(matrix_iterator) { }
986 
987  //! convert from matrix_iterator
989  : const_matrix_iterator_type(matrix_iterator) { }
990 
991  // Has to be not empty, else behavior is undefined.
993  {
994  if (get_row() + 1 < m->get_height())
995  // => not at the end of col, move down
996  set_row(get_row() + 1);
997  else if (get_col() + 1 < m->get_width())
998  // => at end of col but not last col, move to beginning of next col
999  set_pos(0, get_col() + 1);
1000  else
1001  // => at end of matrix, set to empty-state
1002  set_empty();
1003  return *this;
1004  }
1005 
1006  // Has to be not empty, else behavior is undefined.
1008  {
1009  if (get_row() - 1 >= 0)
1010  // => not at the beginning of col, move up
1011  set_row(get_row() - 1);
1012  else if (get_col() - 1 >= 0)
1013  // => at beginning of col but not first col, move to end of previous col
1014  set_pos(m->get_height() - 1, get_col() - 1);
1015  else
1016  // => at beginning of matrix, set to empty-state
1017  set_empty();
1018  return *this;
1019  }
1020 
1021  using const_matrix_iterator_type::get_row;
1022  using const_matrix_iterator_type::get_col;
1023  using const_matrix_iterator_type::set_row;
1024  using const_matrix_iterator_type::set_pos;
1025 };
1026 
1027 //! External matrix container. \n
1028 //! <b> Introduction </b> to matrix container: see \ref tutorial_matrix tutorial. \n
1029 //! <b> Design and Internals </b> of matrix container: see \ref design_matrix.
1030 //!
1031 //! \tparam ValueType type of contained objects (POD with no references to internal memory)
1032 //! \tparam BlockSideLength side length of a matrix block
1033 //!
1034 //! Divides the matrix in square submatrices (blocks).
1035 //! Blocks can be swapped individually to and from external memory.
1036 //! They are only swapped if necessary to minimize I/O.
1037 template <typename ValueType, unsigned BlockSideLength>
1038 class matrix
1039 {
1040 protected:
1049 
1050 public:
1059 
1060 protected:
1061  template <typename VT, unsigned BSL>
1062  friend class matrix_iterator;
1063 
1064  template <typename VT, unsigned BSL>
1066 
1068 
1070 
1071 public:
1072  //! \name Constructors/Destructors
1073  //! \{
1074 
1075  //! Creates a new matrix of given dimensions. Elements' values are set to zero.
1076  //! \param bs block scheduler used
1077  //! \param height height of the created matrix
1078  //! \param width width of the created matrix
1080  const elem_size_type height, const elem_size_type width)
1081  : height(height),
1082  width(width),
1083  data(
1085  bs,
1086  div_ceil(height, BlockSideLength),
1087  div_ceil(width, BlockSideLength))
1088  )
1089  { }
1090 
1092  const column_vector_type& left, const row_vector_type& right)
1093  : height((elem_size_type)left.size()),
1094  width((elem_size_type)right.size()),
1095  data(
1097  bs,
1098  div_ceil(height, BlockSideLength),
1099  div_ceil(width, BlockSideLength))
1100  )
1101  { Ops::recursive_matrix_from_vectors(*data, left, right); }
1102 
1103  ~matrix() { }
1104  //! \}
1105 
1106  //! \name Capacity
1107  //! \{
1108  const elem_size_type & get_height() const
1109  { return height; }
1110 
1111  const elem_size_type & get_width() const
1112  { return width; }
1113  //! \}
1114 
1115  //! \name Iterators
1116  //! \{
1118  {
1119  data.unify();
1120  return iterator(*this, 0, 0);
1121  }
1123  { return const_iterator(*this, 0, 0); }
1125  { return const_iterator(*this, 0, 0); }
1127  {
1128  data.unify();
1129  return iterator(*this);
1130  }
1132  { return const_iterator(*this); }
1134  { return const_iterator(*this); }
1135  const_iterator operator () (const elem_size_type row, const elem_size_type col) const
1136  { return const_iterator(*this, row, col); }
1137 
1138  iterator operator () (const elem_size_type row, const elem_size_type col)
1139  {
1140  data.unify();
1141  return iterator(*this, row, col);
1142  }
1143  //! \}
1144 
1145  //! \name Modifiers
1146  //! \{
1147  void transpose()
1148  {
1149  data.unify();
1150  data->transpose();
1151  std::swap(height, width);
1152  }
1153 
1154  void set_zero()
1155  {
1156  if (data.unique())
1157  data->set_zero();
1158  else
1159  data = new swappable_block_matrix_type
1160  (data->bs, div_ceil(height, BlockSideLength), div_ceil(width, BlockSideLength));
1161  }
1162  //! \}
1163 
1164  //! \name Operations
1165  //! \{
1166  matrix_type operator + (const matrix_type& right) const
1167  {
1168  assert(height == right.height && width == right.width);
1169  matrix_type res(data->bs, height, width);
1170  Ops::element_op(*res.data, *data, *right.data, typename Ops::addition()); // more efficient than copying this and then adding right
1171  return res;
1172  }
1173 
1174  matrix_type operator - (const matrix_type& right) const
1175  {
1176  assert(height == right.height && width == right.width);
1177  matrix_type res(data->bs, height, width);
1178  Ops::element_op(*res.data, *data, *right.data, typename Ops::subtraction()); // more efficient than copying this and then subtracting right
1179  return res;
1180  }
1181 
1182  matrix_type operator * (const matrix_type& right) const
1183  { return multiply(right); }
1184 
1185  matrix_type operator * (const ValueType scalar) const
1186  {
1187  matrix_type res(data->bs, height, width);
1188  Ops::element_op(*res.data, *data, typename Ops::scalar_multiplication(scalar));
1189  return res;
1190  }
1191 
1193  {
1194  assert(height == right.height && width == right.width);
1195  data.unify();
1196  Ops::element_op(*data, *right.data, typename Ops::addition());
1197  return *this;
1198  }
1199 
1200  matrix_type& operator -= (const matrix_type& right)
1201  {
1202  assert(height == right.height && width == right.width);
1203  data.unify();
1204  Ops::element_op(*data, *right.data, typename Ops::subtraction());
1205  return *this;
1206  }
1207 
1208  matrix_type& operator *= (const matrix_type& right)
1209  { return *this = operator * (right); } // implicitly unifies by constructing a result-matrix
1210 
1211  matrix_type& operator *= (const ValueType scalar)
1212  {
1213  data.unify();
1214  Ops::element_op(*data, typename Ops::scalar_multiplication(scalar));
1215  return *this;
1216  }
1217 
1218  column_vector_type operator * (const column_vector_type& right) const
1219  {
1220  assert(elem_size_type(right.size()) == width);
1221  column_vector_type res(height);
1222  res.set_zero();
1223  Ops::recursive_matrix_col_vector_multiply_and_add(*data, right, res);
1224  return res;
1225  }
1226 
1228  {
1229  assert(elem_size_type(left.size()) == height);
1230  row_vector_type res(width);
1231  res.set_zero();
1232  Ops::recursive_matrix_row_vector_multiply_and_add(left, *data, res);
1233  return res;
1234  }
1235 
1236  //! multiply with another matrix
1237  //! \param right matrix to multiply with
1238  //! \param multiplication_algorithm allows to choose the applied algorithm
1239  //! \param scheduling_algorithm allows to choose the applied algorithm
1240  //!
1241  //! Available algorithms are: \n
1242  //! 0: naive_multiply_and_add (I/O inefficient, slow) \n
1243  //! 1: recursive_multiply_and_add (recommended, default, stable time and I/O complexity) \n
1244  //! 2: strassen_winograd_multiply_and_add (sometimes fast but unstable time and I/O complexity) \n
1245  //! 3: multi_level_strassen_winograd_multiply_and_add (sometimes fast but unstable time and I/O complexity) \n
1246  //! 4: strassen_winograd_multiply, optimized pre- and postadditions (sometimes fast but unstable time and I/O complexity) \n
1247  //! 5: strassen_winograd_multiply_and_add_interleaved, optimized preadditions (sometimes fast but unstable time and I/O complexity) \n
1248  //! 6: multi_level_strassen_winograd_multiply_and_add_block_grained (sometimes fast but unstable time and I/O complexity)
1249  matrix_type multiply(const matrix_type& right, const int_type multiplication_algorithm = 1, const int_type scheduling_algorithm = 2) const
1250  {
1251  assert(width == right.height);
1252  assert(&data->bs == &right.data->bs);
1253  matrix_type res(data->bs, height, right.width);
1254 
1255  if (scheduling_algorithm > 0)
1256  {
1257  // all offline algos need a simulation-run
1258  delete data->bs.switch_algorithm_to(
1260  );
1261  switch (multiplication_algorithm)
1262  {
1263  case 0:
1264  Ops::naive_multiply_and_add(*data, *right.data, *res.data);
1265  break;
1266  case 1:
1267  Ops::recursive_multiply_and_add(*data, *right.data, *res.data);
1268  break;
1269  case 2:
1270  Ops::strassen_winograd_multiply_and_add(*data, *right.data, *res.data);
1271  break;
1272  case 3:
1273  Ops::multi_level_strassen_winograd_multiply_and_add(*data, *right.data, *res.data);
1274  break;
1275  case 4:
1276  Ops::strassen_winograd_multiply(*data, *right.data, *res.data);
1277  break;
1278  case 5:
1279  Ops::strassen_winograd_multiply_and_add_interleaved(*data, *right.data, *res.data);
1280  break;
1281  case 6:
1282  Ops::multi_level_strassen_winograd_multiply_and_add_block_grained(*data, *right.data, *res.data);
1283  break;
1284  default:
1285  STXXL_ERRMSG("invalid multiplication-algorithm number");
1286  break;
1287  }
1288  }
1289  switch (scheduling_algorithm)
1290  {
1291  case 0:
1292  delete data->bs.switch_algorithm_to(
1294  );
1295  break;
1296  case 1:
1297  delete data->bs.switch_algorithm_to(
1299  );
1300  break;
1301  case 2:
1302  delete data->bs.switch_algorithm_to(
1304  );
1305  break;
1306  default:
1307  STXXL_ERRMSG("invalid scheduling-algorithm number");
1308  }
1309  switch (multiplication_algorithm)
1310  {
1311  case 0:
1312  Ops::naive_multiply_and_add(*data, *right.data, *res.data);
1313  break;
1314  case 1:
1315  Ops::recursive_multiply_and_add(*data, *right.data, *res.data);
1316  break;
1317  case 2:
1318  Ops::strassen_winograd_multiply_and_add(*data, *right.data, *res.data);
1319  break;
1320  case 3:
1321  Ops::multi_level_strassen_winograd_multiply_and_add(*data, *right.data, *res.data);
1322  break;
1323  case 4:
1324  Ops::strassen_winograd_multiply(*data, *right.data, *res.data);
1325  break;
1326  case 5:
1327  Ops::strassen_winograd_multiply_and_add_interleaved(*data, *right.data, *res.data);
1328  break;
1329  case 6:
1330  Ops::multi_level_strassen_winograd_multiply_and_add_block_grained(*data, *right.data, *res.data);
1331  break;
1332  default:
1333  STXXL_ERRMSG("invalid multiplication-algorithm number");
1334  break;
1335  }
1336  delete data->bs.switch_algorithm_to(
1338  );
1339  return res;
1340  }
1341 
1342  //! Use internal memory multiplication. Designated for testing. May exceed memory limitations.
1343  matrix_type multiply_internal(const matrix_type& right, const int_type scheduling_algorithm = 2) const
1344  {
1345  assert(width == right.height);
1346  assert(&data->bs == &right.data->bs);
1347  matrix_type res(data->bs, height, right.width);
1348 
1349  if (scheduling_algorithm > 0)
1350  {
1351  // all offline algos need a simulation-run
1352  delete data->bs.switch_algorithm_to(
1354  );
1355  multiply_internal(right, res);
1356  }
1357  switch (scheduling_algorithm)
1358  {
1359  case 0:
1360  delete data->bs.switch_algorithm_to(
1362  );
1363  break;
1364  case 1:
1365  delete data->bs.switch_algorithm_to(
1367  );
1368  break;
1369  case 2:
1370  delete data->bs.switch_algorithm_to(
1372  );
1373  break;
1374  default:
1375  STXXL_ERRMSG("invalid scheduling-algorithm number");
1376  }
1377  multiply_internal(right, res);
1378  delete data->bs.switch_algorithm_to(
1380  );
1381  return res;
1382  }
1383  //! \}
1384 
1385 protected:
1386  void multiply_internal(const matrix_type& right, matrix_type& res) const
1387  {
1388  ValueType* A = new ValueType[height * width];
1389  ValueType* B = new ValueType[right.height * right.width];
1390  ValueType* C = new ValueType[res.height * res.width];
1391  ValueType* vit;
1392  vit = A;
1393  for (const_row_major_iterator mit = cbegin(); mit != cend(); ++mit, ++vit)
1394  *vit = *mit;
1395  vit = B;
1396  for (const_row_major_iterator mit = right.cbegin(); mit != right.cend(); ++mit, ++vit)
1397  *vit = *mit;
1398  if (! res.data->bs.is_simulating())
1399  {
1400 #if STXXL_BLAS
1401  gemm_wrapper(height, width, res.width,
1402  ValueType(1), false, A,
1403  false, B,
1404  ValueType(0), false, C);
1405 #else
1406  assert(false /* internal multiplication is only available for testing with blas */);
1407 #endif
1408  }
1409  vit = C;
1410  for (row_major_iterator mit = res.begin(); mit != res.end(); ++mit, ++vit)
1411  *mit = *vit;
1412  delete[] A;
1413  delete[] B;
1414  delete[] C;
1415  }
1416 };
1417 
1418 //! \}
1419 
1421 
1422 #endif // !STXXL_CONTAINERS_MATRIX_HEADER
1423 // vim: et:ts=4:sw=4
matrix_col_major_iterator(const matrix_iterator_type &matrix_iterator)
convert from matrix_iterator
Definition: matrix.h:677
row-major const_iterator that points to single elements inside a matrix
Definition: matrix.h:891
const_matrix_col_major_iterator(const matrix_iterator< ValueType, BlockSideLength > &matrix_iterator)
convert from matrix_iterator
Definition: matrix.h:984
elem_size_type current_col
Definition: matrix.h:734
const_matrix_col_major_iterator< ValueType, BlockSideLength > const_col_major_iterator
Definition: matrix.h:1056
void set_pos(const std::pair< elem_size_type, elem_size_type > new_pos)
Definition: matrix.h:552
const elem_size_type & get_col() const
Definition: matrix.h:861
const_iterator cend() const
Definition: matrix.h:1133
block_size_type current_block_row
Definition: matrix.h:445
compat::remove_const< Integral >::type div_ceil(Integral n, Integral2 d)
Definition: utils.h:199
swappable_block_matrix(const swappable_block_matrix &other)
Definition: matrix.h:340
void transpose()
Definition: matrix.h:1147
matrix_iterator(matrix_type &matrix, const elem_size_type start_row, const elem_size_type start_col)
create iterator pointing to given row and col
Definition: matrix.h:465
std::pair< elem_size_type, elem_size_type > get_pos() const
Definition: matrix.h:864
general const_iterator type that points to single elements inside a matrix
Definition: matrix.h:720
void set_col(const elem_size_type new_col)
Definition: matrix.h:527
block_scheduler_type & bs
Definition: matrix.h:242
void set_row(const elem_size_type new_row)
Definition: matrix.h:516
external column-vector container for matrix multiplication
Definition: matrix.h:49
column_vector< ValueType > column_vector_type
Definition: matrix.h:1057
vector_type::size_type size_type
Definition: matrix.h:124
iterator end()
Definition: matrix.h:1126
SwappableBlockType::internal_block_type internal_block_type
swappable_block< ValueType, BlockSideLength *BlockSideLength >::internal_block_type internal_block_type
Definition: matrix.h:209
matrix_iterator_type::elem_size_type elem_size_type
Definition: matrix.h:659
const elem_size_type & get_width() const
Definition: matrix.h:1111
matrix_col_major_iterator< ValueType, BlockSideLength > col_major_iterator
Definition: matrix.h:1054
elem_size_type current_row
Definition: matrix.h:443
matrix_type::swappable_block_matrix_type swappable_block_matrix_type
Definition: matrix.h:430
general iterator type that points to single elements inside a matrix
Definition: matrix.h:426
const elem_size_type & get_col() const
Definition: matrix.h:558
swappable_block_matrix_type::block_scheduler_type block_scheduler_type
Definition: matrix.h:1044
matrix_iterator_type::elem_size_type elem_size_type
Definition: matrix.h:593
External container for a (sub)matrix. Not intended for direct use.
Definition: matrix.h:232
Provides reference counting abilities for use with counting_ptr with mutex locking.
Definition: counting_ptr.h:461
static uint_pair min()
return an uint_pair instance containing the smallest value possible
Definition: uint_types.h:234
const_matrix_col_major_iterator(const matrix_type &matrix, const elem_size_type start_row, const elem_size_type start_col)
create iterator pointing to given row and col
Definition: matrix.h:975
elem_size_type current_row
Definition: matrix.h:734
matrix_type::swappable_block_matrix_type swappable_block_matrix_type
Definition: matrix.h:724
matrix_type::elem_size_type elem_size_type
Definition: matrix.h:727
size_type size() const
return the size of the vector.
Definition: vector.h:1027
blocks_type blocks
the matrice&#39;s blocks in row-major
Definition: matrix.h:258
void set_zero()
Definition: matrix.h:1154
const swappable_block_identifier_type & block(const size_type row, const size_type col) const
get identifier of the block at (row, col)
Definition: matrix.h:384
const_matrix_iterator< ValueType, BlockSideLength > const_iterator
Definition: matrix.h:1052
External vector container. Introduction to vector container: see STXXL Vector tutorial. Design and Internals of vector container: see Vector.
Definition: vector.h:255
Virtualization of a block of data. Holds information for allocating and swapping. To use in cooperati...
const_matrix_row_major_iterator(const matrix_type &matrix, const elem_size_type start_row, const elem_size_type start_col)
create iterator pointing to given row and col
Definition: matrix.h:905
matrix_row_major_iterator(matrix_type &matrix, const elem_size_type start_row, const elem_size_type start_col)
create iterator pointing to given row and col
Definition: matrix.h:602
const size_type & get_height() const
Definition: matrix.h:391
bool is_simulating() const
Returns if simulation mode is on, i.e. if a prediction sequence is being recorded.
matrix_row_major_iterator(const matrix_iterator_type &matrix_iterator)
convert from matrix_iterator
Definition: matrix.h:611
matrix_row_major_iterator(matrix_type &matrix)
create empty iterator
Definition: matrix.h:606
Block scheduling algorithm caching via the least recently used policy (offline), and prefetching in a...
uint_pair & operator++()
prefix increment operator (directly manipulates the integer parts)
Definition: uint_types.h:163
const_matrix_col_major_iterator(const const_matrix_iterator_type &matrix_iterator)
convert from matrix_iterator
Definition: matrix.h:988
matrix_local::matrix_operations< ValueType, BlockSideLength > Ops
Definition: matrix.h:1047
static size_type block_index_from_elem(elem_size_type index)
Definition: matrix.h:369
void set_row(const elem_size_type new_row)
Definition: matrix.h:819
row_vector< ValueType > row_vector_type
Definition: matrix.h:1058
const_matrix_iterator(const matrix_iterator< ValueType, BlockSideLength > &other)
Definition: matrix.h:783
Block scheduling algorithm caching via the least recently used policy (online).
block_scheduler< matrix_swappable_block< ValueType, BlockSideLength > > block_scheduler_type
Definition: matrix.h:237
matrix_type multiply_internal(const matrix_type &right, const int_type scheduling_algorithm=2) const
Use internal memory multiplication. Designated for testing. May exceed memory limitations.
Definition: matrix.h:1343
const bool & is_transposed() const
if the elements inside the blocks are in transposed order i.e. column-major
Definition: matrix.h:398
block_scheduler_type::swappable_block_identifier_type swappable_block_identifier_type
Definition: matrix.h:238
const_matrix_iterator< ValueType, BlockSideLength > const_matrix_iterator_type
Definition: matrix.h:964
matrix_iterator< ValueType, BlockSideLength > iterator
Definition: matrix.h:1051
column-major const_iterator that points to single elements inside a matrix
Definition: matrix.h:961
uint_pair & operator+=(const uint_pair &b)
addition operator (uses 64-bit arithmetic)
Definition: uint_types.h:183
matrix_col_major_iterator(matrix_type &matrix, const elem_size_type start_row, const elem_size_type start_col)
create iterator pointing to given row and col
Definition: matrix.h:668
const_matrix_iterator(const const_matrix_iterator &other)
Definition: matrix.h:795
swappable_block_identifier_type & bl(const size_type row, const size_type col)
get identifier of the block at (row, col)
Definition: matrix.h:263
vector< ValueType > vector_type
Definition: matrix.h:52
void set_zero()
Definition: matrix.h:193
counting_ptr< swappable_block_matrix_type > swappable_block_matrix_pointer_type
Definition: matrix.h:1043
swappable_block_matrix_pointer_type data
Definition: matrix.h:1069
External matrix container. Introduction to matrix container: see STXXL Matrix tutorial. Design and Internals of matrix container: see Matrix.
Definition: matrix.h:44
matrix_row_major_iterator< ValueType, BlockSideLength > row_major_iterator
Definition: matrix.h:1053
const matrix_type * m
Definition: matrix.h:733
elem_size_type height
Definition: matrix.h:1067
const_matrix_iterator(const matrix_type &matrix, const elem_size_type start_row, const elem_size_type start_col)
create iterator pointing to given row and col
Definition: matrix.h:756
swappable_block_matrix(block_scheduler_type &bs, const size_type height_in_blocks, const size_type width_in_blocks, const bool transposed=false)
Create an empty swappable_block_matrix of given dimensions.
Definition: matrix.h:268
choose_int_types< my_pointer_size >::int_type int_type
Definition: types.h:63
const elem_size_type & get_height() const
Definition: matrix.h:1108
block_size_type current_block_row
Definition: matrix.h:736
size_type height
height of the matrix in blocks
Definition: matrix.h:250
matrix(block_scheduler_type &bs, const column_vector_type &left, const row_vector_type &right)
Definition: matrix.h:1091
swappable_block_matrix(const swappable_block_matrix &ul, const swappable_block_matrix &ur, const swappable_block_matrix &dl, const swappable_block_matrix &dr)
Create swappable_block_matrix that represents the combination matrix ul ur dl dr. ...
Definition: matrix.h:314
matrix_local::matrix_operations< ValueType, BlockSideLength > Ops
Definition: matrix.h:240
block_scheduler_type::internal_block_type internal_block_type
Definition: matrix.h:432
matrix_iterator_type::matrix_type matrix_type
Definition: matrix.h:658
const_matrix_row_major_iterator(const const_matrix_row_major_iterator &matrix_iterator)
convert from matrix_iterator
Definition: matrix.h:914
swappable_block_identifier_type allocate_swappable_block()
Allocate an uninitialized swappable_block.
matrix< ValueType, BlockSideLength > matrix_type
Definition: matrix.h:723
const size_type & get_width() const
Definition: matrix.h:394
Pseudo block scheduling algorithm only recording the request sequence.
#define STXXL_BEGIN_NAMESPACE
Definition: namespace.h:16
std::vector< SwappableBlockType >::size_type swappable_block_identifier_type
block_scheduler_type::internal_block_type internal_block_type
Definition: matrix.h:726
uint_pair & operator--()
prefix decrement operator (directly manipulates the integer parts)
Definition: uint_types.h:173
static int_type elem_index_in_block_from_elem(elem_size_type index)
Definition: matrix.h:372
matrix_type::block_size_type block_size_type
Definition: matrix.h:434
matrix_type::block_size_type block_size_type
Definition: matrix.h:728
vector_type::size_type size_type
Definition: matrix.h:53
column-major iterator that points to single elements inside a matrix
Definition: matrix.h:654
matrix_type::block_scheduler_type block_scheduler_type
Definition: matrix.h:431
matrix_iterator< ValueType, BlockSideLength > matrix_iterator_type
Definition: matrix.h:591
External vector iterator, model of ext_random_access_iterator concept.
Definition: vector.h:275
const_matrix_iterator_type::elem_size_type elem_size_type
Definition: matrix.h:896
void set_pos(const elem_size_type new_row, const elem_size_type new_col)
Definition: matrix.h:841
const_matrix_iterator(const matrix_type &matrix)
create empty iterator
Definition: matrix.h:765
const_matrix_iterator< ValueType, BlockSideLength > const_matrix_iterator_type
Definition: matrix.h:894
const_matrix_iterator_type::matrix_type matrix_type
Definition: matrix.h:895
vector< ValueType > vector_type
Definition: matrix.h:123
const_iterator end() const
Definition: matrix.h:1131
size_type width
width of the matrix in blocks
Definition: matrix.h:250
size_type width_from_supermatrix
width copied from supermatrix in blocks
Definition: matrix.h:250
matrix_iterator_type::matrix_type matrix_type
Definition: matrix.h:592
row_vector_type multiply_from_left(const row_vector_type &left) const
Definition: matrix.h:1227
int_type elem_index_in_block_from_elem(elem_size_type row, elem_size_type col) const
Definition: matrix.h:376
column_vector(size_type n=0)
Definition: matrix.h:58
Block scheduling algorithm caching via the longest forward distance policy (offline).
matrix_iterator< ValueType, BlockSideLength > matrix_iterator_type
Definition: matrix.h:657
#define STXXL_ERRMSG(x)
Definition: verbose.h:80
matrix_swappable_block< ValueType, BlockSideLength > swappable_block_type
Definition: matrix.h:1048
const_matrix_row_major_iterator< ValueType, BlockSideLength > const_row_major_iterator
Definition: matrix.h:1055
void set_pos(const std::pair< elem_size_type, elem_size_type > new_pos)
Definition: matrix.h:855
matrix_type::elem_size_type elem_size_type
Definition: matrix.h:433
bool elements_in_blocks_transposed
if the elements in each block are in col-major instead of row-major
Definition: matrix.h:260
internal_block_type * current_iblock
Definition: matrix.h:447
matrix_type::block_scheduler_type block_scheduler_type
Definition: matrix.h:725
matrix< ValueType, BlockSideLength > matrix_type
Definition: matrix.h:429
void set_col(const elem_size_type new_col)
Definition: matrix.h:830
void multiply_internal(const matrix_type &right, matrix_type &res) const
Definition: matrix.h:1386
SizeType size_type
an unsigned 64-bit integral type
Definition: vector.h:845
std::vector< swappable_block_identifier_type > blocks_type
Definition: matrix.h:239
const_matrix_row_major_iterator(const const_matrix_iterator_type &matrix_iterator)
convert from matrix_iterator
Definition: matrix.h:918
internal_block_type * current_iblock
Definition: matrix.h:738
external row-vector container for matrix multiplication
Definition: matrix.h:120
matrix_type multiply(const matrix_type &right, const int_type multiplication_algorithm=1, const int_type scheduling_algorithm=2) const
multiply with another matrix
Definition: matrix.h:1249
Schedules swapping of blocks and provides blocks for temporary storage.
bool empty() const
Definition: matrix.h:564
row-major iterator that points to single elements inside a matrix
Definition: matrix.h:588
const elem_size_type & get_row() const
Definition: matrix.h:555
matrix_iterator(matrix_type &matrix)
create empty iterator
Definition: matrix.h:474
matrix< ValueType, BlockSideLength > matrix_type
Definition: matrix.h:1041
matrix_type * m
Definition: matrix.h:442
Specialized swappable_block that interprets uninitialized as containing zeros.
Definition: matrix.h:206
const_iterator begin() const
Definition: matrix.h:1122
void acquire_current_iblock()
Definition: matrix.h:449
const elem_size_type & get_row() const
Definition: matrix.h:858
const_matrix_row_major_iterator(const matrix_type &matrix)
create empty iterator
Definition: matrix.h:909
swappable_block_matrix(const swappable_block_matrix &supermatrix, const size_type height_in_blocks, const size_type width_in_blocks, const size_type from_row_in_blocks, const size_type from_col_in_blocks)
Create swappable_block_matrix of given dimensions that represents the submatrix of supermatrix starti...
Definition: matrix.h:287
const_matrix_iterator_type::elem_size_type elem_size_type
Definition: matrix.h:966
elem_size_type current_col
Definition: matrix.h:443
const_matrix_col_major_iterator(const matrix_type &matrix)
create empty iterator
Definition: matrix.h:979
void release_current_iblock()
Definition: matrix.h:455
elem_size_type width
Definition: matrix.h:1067
matrix_col_major_iterator(matrix_type &matrix)
create empty iterator
Definition: matrix.h:672
swappable_block_matrix< ValueType, BlockSideLength > swappable_block_matrix_type
Definition: matrix.h:1042
swappable_block_matrix_type::size_type block_size_type
Definition: matrix.h:1045
const_matrix_iterator_type::matrix_type matrix_type
Definition: matrix.h:965
row_vector(size_type n=0)
Definition: matrix.h:129
std::pair< elem_size_type, elem_size_type > get_pos() const
Definition: matrix.h:561
iterator begin()
Definition: matrix.h:1117
swappable_block_matrix_type::elem_size_type elem_size_type
Definition: matrix.h:1046
bool operator==(const uint_pair &b) const
equality checking operator
Definition: uint_types.h:192
matrix_iterator(const matrix_iterator &other)
Definition: matrix.h:492
matrix(block_scheduler_type &bs, const elem_size_type height, const elem_size_type width)
Creates a new matrix of given dimensions. Elements&#39; values are set to zero.
Definition: matrix.h:1079
#define STXXL_END_NAMESPACE
Definition: namespace.h:17
void set_pos(const elem_size_type new_row, const elem_size_type new_col)
Definition: matrix.h:538
const_iterator cbegin() const
Definition: matrix.h:1124