Sprase matrix

[nestini]

Hello everybody,
I am student who just begin learning about programming
I want to know what is Sprase Matrix.
And would you please show me how to add the 2 Sprase Matrix in C
soursecode.

 

[Trent Buck]

Quoth nestini on or about 2004-11-11:

I am student who just begin learning about programming
I want to know what is Sprase Matrix.

I think you must've misread/mistyped `sparse matrix'. Some immediate
references spring to mind:

http://en.wikipedia.org/wiki/Sparse_matrix
http://planetmath.org/encyclopedia/MatricesOfSpecialForm.html

And would you please show me how to add the 2 Sprase Matrix in C
sourcecode.

That sounds like homework. Mathematically, addition of sparse matrices
works like `ordinary' matrices. I suspect the distinction occurs when
sparse matrices are expressed in a compressed form.

-trent

 

[Mike Wahler]

Hello everybody,
I am student who just begin learning about programming
I want to know what is Sprase Matrix.

I don't know what a "sprase matrix" is, but a "sparse matrix"
is a matrix in which unused elements do not consume storage.

And would you please show me how to add the 2 Sprase Matrix in C
soursecode.

Perhaps if you show us *your* code which implements a sparse
matrix, we could offer advice on how to add 2 of them togther.
(Can you do it with a 'normal' matrix? If not, I advise you
to work on that first.)

Nobody here is going to hand you the code on a silver platter.
Show your best efforts first, then you'll get plenty of help.


-Mike

 

[Joona I Palaste]

I don't know what a "sprase matrix" is, but a "sparse matrix"
is a matrix in which unused elements do not consume storage.

I have never needed to make a sparse matrix myself, but can't this be
done with a linked list of linked lists? Every actual object in the
lists would, of course, have to carry information not only about the
element itself, but about its coordinates in the matrix as well. This
would triple its size, not counting pointers. The matrix would have to
be *very* sparse for the total storage to be less than a dense matrix,
or whatever a conventional matrix is called.

 

[Gregory Toomey]

I have never needed to make a sparse matrix myself, but can't this be
done with a linked list of linked lists? Every actual object in the
lists would, of course, have to carry information not only about the
element itself, but about its coordinates in the matrix as well. This
would triple its size, not counting pointers. The matrix would have to
be *very* sparse for the total storage to be less than a dense matrix,
or whatever a conventional matrix is called.

It could. but access would be O(n).
With a hash table it would be O(1).

gtoomey

 

[Thomas Lumley]

I have never needed to make a sparse matrix myself, but can't this be
done with a linked list of linked lists? Every actual object in the
lists would, of course, have to carry information not only about the
element itself, but about its coordinates in the matrix as well. This
would triple its size, not counting pointers. The matrix would have to
be *very* sparse for the total storage to be less than a dense matrix,
or whatever a conventional matrix is called.

Sparse matrices are mostly used for large linear algebra problems
(including solving partial differential equations), where it is
important that the storage structure fits well with the access pattern
of the algorithms being used. The matrices can indeed be very
sparse: it is not uncommon to have the matrix size proportional to the
square of the number of nonzero elements.

Details are OT here; sci.math.num-analysis might be a better place.

-thomas

 

[Elliott Back]

Hello everybody,
I am student who just begin learning about programming
I want to know what is Sprase Matrix.
And would you please show me how to add the 2 Sprase Matrix in C
soursecode.

A sparse matrix is a matrix whose entries are mostly zeros. You add a
sparse matrix like a regular matrix--element by element:

for i=1:n
for j=1:n
A[j] = A[j] + B[j];
end
end

Of course, the representation of a sparse matrix is usually some sort of
other datastructure holding the (x, y) coordinate and the entry. You
can use a linked list, if you'd like, although a hashmap with an
iterator would be better.

 

[Scott J. McCaughrin]

: nestini wrote:
: > Hello everybody,
: > I am student who just begin learning about programming
: > I want to know what is Sprase Matrix.
: > And would you please show me how to add the 2 Sprase Matrix in C
: > soursecode.
: >

: A sparse matrix is a matrix whose entries are mostly zeros. You add a
: sparse matrix like a regular matrix--element by element:

: for i=1:n
: for j=1:n
: A[j] = A[j] + B[j];
: end
: end

: Of course, the representation of a sparse matrix is usually some sort of
: other datastructure holding the (x, y) coordinate and the entry. You
: can use a linked list, if you'd like, although a hashmap with an
: iterator would be better.
: --
: Thanks,
: Elliott C. B?ck
: --------------------------
: www.elliottback.com
: www.spreadIE.com

Why would hashing ever be better, or even as good? First, the hash-table
takes up extra space, which is just what you want to avoid (you are
trying to _conserve_ space by avoiding representation of zeroes).
Secondly, hashing is involved when you want to look up a particular
element. For many sparse matrix applications, this is irrelevant: you
only need sequential access across rows and columns for
addition/subtraction, inversion, adjunct, determinant, etc.

 

[Merrill & Michele]

: nestini wrote:
: > Hello everybody,
: > I am student who just begin learning about programming
: > I want to know what is Sprase Matrix.
: > And would you please show me how to add the 2 Sprase Matrix in C
: > soursecode.
: >

: A sparse matrix is a matrix whose entries are mostly zeros. You add a
: sparse matrix like a regular matrix--element by element:

: for i=1:n
: for j=1:n
: A[j] = A[j] + B[j];
: end
: end

: Of course, the representation of a sparse matrix is usually some sort of
: other datastructure holding the (x, y) coordinate and the entry. You
: can use a linked list, if you'd like, although a hashmap with an
: iterator would be better.
: --
: Thanks,
: Elliott C. B?ck
: --------------------------
: www.elliottback.com
: www.spreadIE.com

Why would hashing ever be better, or even as good? First, the hash-table
takes up extra space, which is just what you want to avoid (you are
trying to _conserve_ space by avoiding representation of zeroes).
Secondly, hashing is involved when you want to look up a particular
element. For many sparse matrix applications, this is irrelevant: you
only need sequential access across rows and columns for
addition/subtraction, inversion, adjunct, determinant, etc.

There's a lot of different ways to have a sparse array. Speaking of
computational tactics in generality is beyond the scope of tapping out an
e-mail message. MPJ