Thread: Matrix element access

Hello everyone

Lately I've developing a MATRIX class. It went fine (mostly), but now I'm working on a SPARSE MATRIX. (Those unfamiliar with sparse matrix, check the end for a quick explanation). My problem is the following:
When accessing element i,j of the matrix, the user should call something like A(i,j), i.e.

Code:

cout << A(i,j);

Also, the user could like to change the value of the element i,j, so he would call

Code:

A(i,j) = 2;

The point is, in the first use, I can return the element itself and in the second I would have to return the reference to the element, so the user could change it.
So I wrote the code:

Code:

double & MATRIX::operator () (int x, int y)
{
  return (val[(x - 1) * n_col + y - 1]); //matrix is stored using linearization strategy
}

double MATRIX::operator () (int x, int y) const
{
  return (val[(x - 1) * n_col + y - 1]);
}

I found out only now that the second function was never called. But in the case of the MATRIX, it meant nothing, for everything worked fine.
But in the case of the SPARSE matrix, my functions had to change a little. It became something like

Code:

double & SPARSE::operator () (int x, int y)
{
  //...
  //Search for the element, if found return it, if not, create the element and pass the reference
  CREATE (0.0, x, y, k);
  return *(val.begin () + k);
}

double SPARSE::operator () (int x, int y) const
{
  //...
  //Search for the element, if found return it, if not, create the element and pass the reference
  return 0.0;
}

Details have been hid to help visualization. As you can see, I must create a zero element and pass reference to it so the user can change (and I hope the user don't pass another 0.0). The mess here is that anytime it access an element to read, it creates a zero valued element in the matrix and stores it, and that what's wrong.

If anyone can give me a tip on how to use the same function operator() to both tasks, I would be very happy. And if it's not possible, I would be happy to know that as well, thank you very much.

Nepper271.

SPARSE MATRIX

A matrix is said to be sparse if there are many zero elements in it, in fact, many more zeros than non-zeros. As this kind of matrix appears widely on various applications, it's fundamental to research better ways to deal with it. The first thing to consider is that storing all the elements of the matrix is not useful. You store only the non-zero elementos of the matrix and the position they are held. For instance, the matrix

Code:

M =
7 0 0
0 0 8
0 9 0

could be stored as

Code:

val = 7 8 9
lin = 1 2 3
col = 1 3 2

That's all for now

No, it still doesn't work. He still makes the call to the first one.

Originally Posted by laserlight

Basically, you have to fix it such that the matrix does not store elements unless they are supposed to be stored.

I must create a space in the vector that stores the elements of the matrix to pass it to the user, so I create one that will simply waste space if the user do something funny like setting it to zero. The elements must be ordered following the matrix rows, so I can't simply push_back it either.

Originally Posted by matsp

Perhaps returning a reference to a proxy object is the right thing here, where the proxy object contains some information to indicate where it belongs?

I'm sorry, I didn't understand what you meant. What is a proxy object?

Originally Posted by matsp

The other option is to simply scan [when you do math on the array perhaps] for zero's and remove them...

That was though about it at first, but it would slow things down a bit (every operation would need an additional comparison). My other option, which is what I'm doing now, and will keep if have no other choice, is use A.get(...) and A.set() instead. This way I can check whether the number is zero or not.

if the element at (x, y) exists, return it.

But what if the user sets the element to 0?
He needs a "set to 0" detector.
A separate set method may be best.

Yes, considering I must check if the element exists and must erase it if the user set it to zero, I will use a set function separate from the get function.

My function will be

Code:

A.set (int i, int j, double a)

It will find the element (i, j), if he can't find it, it will create a new element with value a, if a is not zero. If he finds it, it will check whether a is zero. If a is zero, it will erase element (i,j), otherwise it will simply change (i,j) element's value to a.

Thank you everyone,
Nepper271.

No, no, of course not. I'm actually naming it 'esparsa', that is, sparse in portuguese, hehe.
But thanks for the tips, are always welcome.

Nepper271.