33 #ifndef __H__UG__CPU_ALGEBRA__SPARSEMATRIX_IMPL__
34 #define __H__UG__CPU_ALGEBRA__SPARSEMATRIX_IMPL__
52 template <
class __T>
inline bool
68 if(bNeedsValues) values.resize(32);
74 std::vector<int>().swap(rowStart);
75 std::vector<int>().swap(rowMax);
76 std::vector<int>().swap(rowEnd);
80 std::vector<int>().swap(cols);
81 std::vector<value_type>().swap(values);
84 #ifdef CHECK_ROW_ITERATORS
85 std::vector<int>().swap(nrOfRowIterators);
94 rowStart.clear(); rowStart.resize(newRows+1, -1);
95 rowMax.clear(); rowMax.resize(newRows);
96 rowEnd.clear(); rowEnd.resize(newRows, -1);
100 cols.clear(); cols.resize(newRows);
102 if(bNeedsValues) values.resize(newRows);
105 #ifdef CHECK_ROW_ITERATORS
106 nrOfRowIterators.clear();
107 nrOfRowIterators.resize(newRows, 0);
116 if(newRows == 0 && newCols == 0)
117 return resize_and_clear(0,0);
122 rowStart.resize(newRows+1, -1);
123 rowMax.resize(newRows);
124 rowEnd.resize(newRows, -1);
125 #ifdef CHECK_ROW_ITERATORS
126 nrOfRowIterators.resize(newRows, 0);
128 for(
size_t i=oldrows; i<newRows; i++)
134 if((
int)newCols < m_numCols)
135 copyToNewSize(get_nnz_max_cols(newCols), newCols);
176 for(
size_t r=0; r<B.
num_rows(); r++)
179 for(const_row_iterator it = B.
begin_row(r); it != itEnd; ++it)
195 assert(rowMax[r] == 0);
198 std::vector<int> rowsize(
num_rows());
210 ++rowMax[it.index()];
218 rowStart[c] = rowMax[c-1];
219 rowMax[c] = rowStart[c]+rowMax[c];
220 rowEnd[c] = rowStart[c];
233 int idx = rowEnd[it.index()]++;
235 values[idx] = scale * it.value();
245 assert(rowMax[r] == rowEnd[r]);
248 assert(nnz <= B.
nnz);
251 assert(rowEnd[r] == rowMax[r]);
258 template<
typename vector_t>
262 size_t itEnd=rowEnd[row];
263 for(
size_t rowIt=rowStart[row]; rowIt != itEnd; ++rowIt)
272 template<
typename vector_t>
274 const number &beta1,
const vector_t &w1)
const
276 for(
size_t i=0; i <
num_rows(); i++)
278 size_t rowIt=rowStart[i];
279 size_t itEnd=rowEnd[i];
283 MatMult(dest[i], beta1, values[rowIt], w1[cols[rowIt]]);
284 for(++rowIt; rowIt != itEnd; ++rowIt)
286 MatMultAdd(dest[i], 1.0, dest[i], beta1, values[rowIt], w1[cols[rowIt]]);
293 template<
typename vector_t>
295 const number &alpha1,
const vector_t &v1,
296 const number &beta1,
const vector_t &w1)
const
299 check_fragmentation();
302 for(
size_t i=0; i <
num_rows(); i++)
304 size_t rowIt=rowStart[i];
305 size_t itEnd=rowEnd[i];
311 MatMult(dest[i], beta1, values[rowIt], w1[cols[rowIt]]);
312 for(++rowIt; rowIt != itEnd; ++rowIt)
314 MatMultAdd(dest[i], 1.0, dest[i], beta1, values[rowIt], w1[cols[rowIt]]);
317 else if(&dest == &v1)
320 for(
size_t i=0; i <
num_rows(); i++)
323 mat_mult_add_row(i, dest[i], beta1, w1);
327 for(
size_t i=0; i <
num_rows(); i++)
328 mat_mult_add_row(i, dest[i], beta1, w1);
333 for(
size_t i=0; i <
num_rows(); i++)
336 mat_mult_add_row(i, dest[i], beta1, w1);
343 template<
typename vector_t>
345 const number &alpha1,
const vector_t &v1,
346 const number &beta1,
const vector_t &w1)
const
349 check_fragmentation();
353 else if(alpha1 != 1.0)
356 else if(alpha1 == 0.0)
364 size_t itEnd=rowEnd[i];
365 for(
size_t rowIt=rowStart[i]; rowIt != itEnd; ++rowIt)
367 if(values[rowIt] != 0.0)
374 template<
typename vector_t>
376 const number &beta1,
const vector_t &w1)
const
382 dest[conn.index()] = 0.0;
387 size_t itEnd=rowEnd[i];
388 for(
size_t rowIt=rowStart[i]; rowIt != itEnd; ++rowIt)
390 if(values[rowIt] != 0.0)
400 check_fragmentation();
401 for(
size_t row=0; row<
num_rows(); row++)
406 if(it.index() == row)
422 if(it.index() != i && it.value() != 0.0)
457 for(
size_t i=0; i<nr; i++)
458 operator()(row, c[i].
iIndex) = c[i].dValue;
466 for(
size_t i=0; i<nr; i++)
467 operator()(row, c[i].
iIndex) += c[i].dValue;
476 for(
size_t i=0; i < B.
num_rows(); i++)
490 for(
size_t i=0; i <
num_rows(); i++)
509 for(
size_t i=0; i < mat.num_rows(); i++)
511 int r = mat.row_index(i);
512 for(
size_t j=0; j < mat.num_cols(); j++)
514 int c = mat.col_index(j);
515 (*this)(r,c) += mat(i,j);
525 for(
size_t i=0; i < mat.num_rows(); i++)
527 int r = mat.row_index(i);
528 for(
size_t j=0; j < mat.num_cols(); j++)
530 int c = mat.col_index(j);
531 (*this)(r,c) = mat(i,j);
540 for(
size_t i=0; i < mat.num_rows(); i++)
542 int r = mat.row_index(i);
543 for(
size_t j=0; j < mat.num_cols(); j++)
545 int c = mat.col_index(j);
546 mat(i,j) = (*this)(r,c);
556 assert(rowStart[row] != -1);
557 int l = rowStart[row];
565 else if(cols[mid] > col)
572 if(mid < rowStart[row])
574 else if(mid == rowEnd[row] || col <= cols[mid])
577 UG_ASSERT(ret <= rowEnd[row] && ret >= rowStart[row],
"row iterator row " << row <<
" pos " << ret <<
" out of bounds [" << rowStart[row] <<
", " << rowEnd[row] <<
"]");
586 if(rowStart[r] == -1 || rowStart[r] == rowEnd[r])
return -1;
587 int index=get_index_internal(r, c);
588 if(index >= rowStart[r] && index < rowEnd[r] && cols[index] == c)
600 if(rowStart[r] == -1 || rowStart[r] == rowEnd[r])
604 assureValuesSize(maxValues+1);
605 rowStart[r] = maxValues;
606 rowEnd[r] = maxValues+1;
607 rowMax[r] = maxValues+1;
608 if(bNeedsValues) values[maxValues] = 0.0;
620 int index=get_index_internal(r, c);
631 check_row_modifiable(r);
634 assert(index == rowEnd[r] || cols[index] > c);
635 assert(index == rowStart[r] || cols[index-1] < c);
636 for(
int i=rowStart[r]+1; i<rowEnd[r]; i++)
637 assert(cols[i] > cols[i-1]);
639 if(rowEnd[r] == rowMax[r] && rowEnd[r] == maxValues
640 && maxValues < (
int)cols.size())
648 if(rowEnd[r] == rowMax[r])
652 int newSize = (rowEnd[r]-rowStart[r])*2;
653 if(maxValues+newSize > (
int)cols.size())
656 assureValuesSize(maxValues+newSize);
657 index=get_index_internal(r, c);
660 fragmented += rowEnd[r]-rowStart[r];
661 index = index-rowStart[r]+maxValues;
662 int j=rowEnd[r]-rowStart[r]+maxValues;
664 for(
int i=rowEnd[r]-1; i>=rowStart[r]; i--, j--)
667 if(bNeedsValues) values[j] = values[i];
669 if(i==rowStart[r])
break;
671 rowEnd[r] = maxValues+rowEnd[r]-rowStart[r]+1;
672 rowStart[r] = maxValues;
673 rowMax[r] = maxValues+newSize;
674 maxValues += newSize;
681 for(
int i=rowEnd[r]-1; i>=index; i--)
683 if(bNeedsValues) values[i+1] = values[i];
689 if(bNeedsValues) values[index] = 0.0;
694 assert(index >= rowStart[r] && index < rowEnd[r]);
695 for(
int i=rowStart[r]+1; i<rowEnd[r]; i++)
696 assert(cols[i] > cols[i-1]);
712 || (newSize > values.size() && (100.0*nnz)/newSize < 20 && newSize <= cols.capacity()) )
714 UG_ASSERT(newSize > values.size(),
"no nnz-defragmenting while using iterators.");
716 cols.resize(newSize);
717 cols.resize(cols.capacity());
718 if(bNeedsValues) { values.resize(newSize); values.resize(cols.size()); }
722 std::vector<value_type> v(newSize);
723 std::vector<int> c(newSize);
727 if(rowStart[r] == -1)
728 rowStart[r] = rowEnd[r] = rowMax[r] = j;
732 for(
int k=rowStart[r]; k<rowEnd[r]; k++)
734 if(cols[k] < (
int)maxCol)
736 if(bNeedsValues) v[j] = values[k];
742 rowEnd[r] = rowMax[r] = j;
748 if(bNeedsValues) values.swap(v);
755 if((
double)nnz/(
double)maxValues < 0.9)
762 if(
s <= cols.size())
return;
763 size_t newSize = nnz*2;
764 if(newSize <
s) newSize =
s;
765 copyToNewSize(newSize);
775 if(rowStart[r] == -1)
continue;
776 for(
int k=rowStart[r]; k<rowEnd[r]; k++)
777 if(cols[k] < (
int)maxCols)
bool MatMultAdd(vector_t &dest, const number &alpha1, const vector_t &v1, const number &beta1, const matrix_t &A1, const vector_t &w1)
calculates dest = alpha1*v1 + beta1 * A1 *w1;
bool MatMult(vector_t &dest, const matrix_t &A1, const vector_t &w1)
calculates dest = A1 * w1;
Definition: connection.h:40
size_t iIndex
Definition: connection.h:42
Definition: sparsematrix.h:421
Definition: sparsematrix.h:366
sparse matrix for big, variable sparse matrices.
Definition: sparsematrix.h:99
size_t nnz
Definition: sparsematrix.h:742
TValueType value_type
Definition: sparsematrix.h:101
size_t num_rows() const
returns number of rows
Definition: sparsematrix.h:342
int maxValues
Definition: sparsematrix.h:746
SparseMatrix()
constructor for empty SparseMatrix
Definition: sparsematrix_impl.h:59
row_iterator end_row(size_t r)
Definition: sparsematrix.h:485
size_t num_cols() const
returns the number of cols
Definition: sparsematrix.h:345
row_iterator begin_row(size_t r)
Definition: sparsematrix.h:484
bool bNeedsValues
Definition: sparsematrix.h:743
DenseMatrix< TStorage > MatrixTranspose(const DenseMatrix< TStorage > &A)
Definition: densematrix.h:240
#define UG_ASSERT(expr, msg)
Definition: assert.h:70
double number
Definition: types.h:124
SM_edge_weight_map< typename T::value_type, ug::BidirectionalMatrix< T > > get(edge_weight_t, ug::BidirectionalMatrix< T > const &g)
Definition: bidirectional_boost.h:157
bool iszero(__T __val)
Definition: sparsematrix_impl.h:53
bool MatMultTransposedAdd(vector_t &dest, const number &alpha1, const vector_t &v1, const number &beta1, const matrix_t &A1, const vector_t &w1)
calculates dest = alpha1*v1 + beta1 * A1 *w1;
Definition: operations_mat.h:121
void VecScaleAssign(double &dest, double alpha1, const double &v1)
calculates dest = alpha1*v1. for doubles
Definition: operations_vec.h:49
#define PROFILE_SPMATRIX(name)
Definition: sparsematrix.h:47
T value_type
Definition: sparsematrix_interface.h:2
size_t num_rows() const
Definition: sparsematrix_interface.h:38
const_row_iterator end_row(size_t row) const
value_type & operator()(size_t r, size_t c)
const_row_iterator begin_row(size_t row) const
size_t num_cols() const
Definition: sparsematrix_interface.h:39