Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > sparse matrix class implementation

Reply
Thread Tools

sparse matrix class implementation

 
 
mariaczi
Guest
Posts: n/a
 
      06-08-2006
Hi,
I code class to storage sparse matrix row compressed and i have a
problem with implements method to setVal and addVal.
I will replace later this methods overloaded operator().
Please, can You help me?
Thanks in advance.

I write this, but it's not so good


#include <iostream>
#include <vector>

using namespace std;

template <class T>
class SparseMatrixCR {
public:
SparseMatrixCR() {}
SparseMatrixCR(size_t m, size_t n) : rows_(m),
cols_(n) {
row_ptr.resize(m+1);
}

// read
T operator()(size_t row, size_t col) const;
// write
T& operator()(size_t row, size_t col);

int setSize(size_t _size);
void setVal(size_t row, size_t col, T val);
void addVal(size_t row, size_t col, T val);

// -- friend func --
friend ostream& operator<< (ostream& os, const
SparseMatrixCR<T>& rha) {
// os << "[" << rha.GetRows() << "][" <<
rha.GetCols() << "]" << endl;

for(size_t i(0); i < rha.GetRows(); ++i) {
for(size_t j(0); j < rha.GetCols();
++j) {
os.setf(ios::scientific,
ios::floatfield);
os.width(14);
os << rha(i, j) << " ";
}
os << endl;
}
return os;
}


private:
vector< T > values;
vector< size_t > row_ptr;
vector< size_t > colidx;

size_t rows_;
size_t cols_;

}; // end of: class SparseMatrixCR

template <class T>
void SparseMatrixCR<T>::setVal(size_t row, size_t col, T val) {

if(val != 0 && values.size() == 0) {
colidx.push_back(col);
values.push_back(val);
for(size_t i(row+1); i < row_ptr.size(); ++i) {
row_ptr[i] += 1;
}
}
else {

bool exist(false);

for(size_t idx(row_ptr[row]); idx < row_ptr[row+1];
++idx) {
if(colidx[idx] == col) {
values[idx] = val;
exist = true;
break;
}

}
if(exist == false) {
if(val != 0) {
colidx.insert( colidx.begin() +
row_ptr[row], col );
values.insert( values.begin() +
row_ptr[row], val );
for(size_t i(row+1); i <
row_ptr.size(); ++i) {
row_ptr[i] += 1;
}
}
else {
colidx.erase( colidx.begin() +
row_ptr[row] );
values.erase( values.begin() +
row_ptr[row] );
for(size_t i(row+1); i <
row_ptr.size(); ++i) {
row_ptr[i] -= 1;
}
}
}
}

} // end of: setVal()




template <class T>
void SparseMatrixCR<T>::addVal(size_t row, size_t col, T val) {

if(values.size() == 0) {
colidx.push_back(col);
values.push_back(val);
for(size_t i(row+1); i < row_ptr.size(); ++i) {
row_ptr[i] += 1;
}
}
else {

bool exist(false);

for(size_t idx(row_ptr[row]); idx < row_ptr[row+1];
++idx) {
if(colidx[idx] == col) {
values[idx] += val;
exist = true;
break;
}
if(colidx[idx] > col) {
poz = idx;
}
}
if(exist == false) {
if(val != 0) {
colidx.insert( colidx.begin() +
row_ptr[row], col );
values.insert( values.begin() +
row_ptr[row], val );
for(size_t i(row+1); i <
row_ptr.size(); ++i) {
row_ptr[i] += 1;
}
}
}
}
} // end of: addVal()
 
Reply With Quote
 
 
 
 
Daniel T.
Guest
Posts: n/a
 
      06-08-2006

mariaczi wrote:
> Hi,
> I code class to storage sparse matrix row compressed and i have a
> problem with implements method to setVal and addVal.
> I will replace later this methods overloaded operator().
> Please, can You help me?


Here's a simple sparse matrix class that you can use and is already
pretty efficient:

template < typename T >
class SparseMatrix {
std::map< std:air< size_t, size_t >, T > rep;
public:
T operator()( size_t x, size_t y ) const {
return rep[ std::make_pair( x, y ) ];
}
T& operator()( size_t x, size_t y ) {
return rep[ std::make_pair( x, y ) ];
}
};

Add operations to taste. For example you might want to add a
member-function that tells wether a particular node exists.

 
Reply With Quote
 
 
 
 
Dervish
Guest
Posts: n/a
 
      06-08-2006
> Here's a simple sparse matrix class that you can use and is already
> pretty efficient:
>

Here is even more simple sparse matrix (not it is zero initialized)

template <class T> class Matrix : public map<size_t, map<size_t, T> >
{};

int main ()
{
Matrix<double> mat;
mat[4238749][6234234] = 123.456;
cout << mat[4238749][6234234] << endl;
cout << mat[10000][2323436] << endl;
return 0;
}

 
Reply With Quote
 
mariaczi
Guest
Posts: n/a
 
      06-08-2006
On 8 Jun 2006 04:06:59 -0700, "Daniel T." <(E-Mail Removed)>
wrote:

>Here's a simple sparse matrix class that you can use and is already
>pretty efficient:

[cut]
>Add operations to taste. For example you might want to add a
>member-function that tells wether a particular node exists.

it's ok, but i need my implementation to comparision with sparse
matrix implemented that You write
 
Reply With Quote
 
rwf_20
Guest
Posts: n/a
 
      06-08-2006
Daniel T. wrote:
> template < typename T >
> class SparseMatrix {
> std::map< std:air< size_t, size_t >, T > rep;
> public:
> T operator()( size_t x, size_t y ) const {
> return rep[ std::make_pair( x, y ) ];
> }
> T& operator()( size_t x, size_t y ) {
> return rep[ std::make_pair( x, y ) ];
> }
> };
>
> Add operations to taste. For example you might want to add a
> member-function that tells wether a particular node exists.


IIRC, operator[] on a std::map will allocate a new entry if one does
not already exist, no?

T operator()(size_t x, size_t y) const {
std::map<std:air<size_t, size_t>, T>::const_iterator mapItr =
rep.find(std::make_pair<size_t, size_t>(x, y));
if (mapItr != rep.end()) return mapItr->second;
else return 0;
}

This is of course overkill if you can control calls to operator() such
that it will never be called on a nonexistent location. But, since I
believe [] reduces to a map lookup anyway, the performace overhead is
minimal. The advantage is that routines written for standard matrices
can work with the above with filling your map with a bunch of zeroes.

Ryan

 
Reply With Quote
 
Daniel T.
Guest
Posts: n/a
 
      06-08-2006

mariaczi wrote:
> On 8 Jun 2006 04:06:59 -0700, "Daniel T." <(E-Mail Removed)>
> wrote:
>
> >Here's a simple sparse matrix class that you can use and is already
> >pretty efficient:

> [cut]
> >Add operations to taste. For example you might want to add a
> >member-function that tells wether a particular node exists.

> it's ok, but i need my implementation to comparision with sparse
> matrix implemented that You write


If I understand you... Just write an op== and it will.

 
Reply With Quote
 
Noah Roberts
Guest
Posts: n/a
 
      06-08-2006

rwf_20 wrote:

> IIRC, operator[] on a std::map will allocate a new entry if one does
> not already exist, no?


That is true.

 
Reply With Quote
 
mariaczi
Guest
Posts: n/a
 
      06-09-2006
On 8 Jun 2006 12:14:33 -0700, "Daniel T." <(E-Mail Removed)>
wrote:

>If I understand you... Just write an op== and it will.

Hmm... i use my sparse matrix implementation to solve linear
equations, and i need two assorted implementation of sparse matrix to
compare solving time with this and this and test usage memory for all

sorry for my english
regards
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
suggestions about data structures for a sparse matrix class aaragon C++ 3 02-16-2009 03:41 AM
Sparse Matrix Mark C++ 7 01-04-2008 11:57 PM
Sparse Matrix implemented as a doubly-linked list adam.kleinbaum@gmail.com C Programming 5 06-25-2007 01:33 PM
Finding Nonzero Elements in a Sparse Matrix deLenn Python 4 11-08-2006 06:43 AM
Sparse Matrix operations friends C Programming 0 09-17-2005 04:30 AM



Advertisments