Sparse Matrix Question

[JC]

Hello,

I am confronted with a data editing problem that basically involves
storing the rules entries of a decision logic table into a sparse
matrix. A sparse matrix is definitely the way to go here but I am
wondering what might be the best sparse matrix algorithm out of the
bunch to use based on the fact that the matrix must be:

- Easily cloneable
- Remove entire columns efficiently
- Remove entire rows efficiently
- Adding of new values can be relatively slower

Basically, as certain conditions are met within the edits we can
eliminate entire rules (represented as columns) and certain results of
conditions (represented as rows).

We will be developing this in C# so if there is a freeware/open source
alternative (or even commercial) that implements the desired solution
and you know where it is then please point me to it.

Any help is appreciated!

Thanks

[Gordon Sande]

You did not say what types of operations you expect to do with the matrices.
(If you are only ever going to delete things then just delete everything
at the beginning and be done with it!)

Sometimes it pays to have redundent information. Be aware that many
data structures were initially studied when memory was very tight.
Many data structures seem more oriented toward static information than
dynamic information. How is storeage management and recovery expected
to be done? If the computation is expected to last for an extended time,
storeage is a serious requirement and needs to be designed in at the
beginning.

For sparse matrix manipulation, including updating of LU factorizaations,
I have found it convenient to use both row and column oriented versions
as it makes differing operatons easy at a minor cost in updating both.
Vectors are kept either compact or scattered with pahse markers depending
on the immediate operation. Moveable block allocation does the job.

[Victor Eijkhout]

JC <jeffrey...@gmail.com> wrote:

> matrix. A sparse matrix is definitely the way to go here but I am
> wondering what might be the best sparse matrix algorithm out of the
> bunch to use based on the fact that the matrix must be:
>
> - Easily cloneable
> - Remove entire columns efficiently
> - Remove entire rows efficiently
> - Adding of new values can be relatively slower

Use a variant of Compressed Row Storage, where you overallocate each row
slightly. Then you need two pointers per row instead of one: the start
of each row and the end. That way deleting columns is doable by
compacting the rows that have elements in that column. Deleting a row
can also be done by compacting the whole data structure, or by using
mask bits, or by moving the pointer for the i-th row to the i+1st if you
remove the i-th row.

Victor.
--
Victor Eijkhout -- eijkhout at tacc utexas edu

[glenn.m...@gmail.com]

On Apr 28, 11:00 pm, s...@sig.for.address (Victor Eijkhout) wrote:

If you need double type for your matrices, you could try

http://sourceforge.net/projects/mtxfx/

It is highly efficient for removing/adding columns (but requires
copying for row removing/addition).