octave-maintainers
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

2nd: sparse matrices


From: john popeye
Subject: 2nd: sparse matrices
Date: Mon, 26 Apr 2004 01:36:50 -0500

hi,
I am only a time by time visitor to the mailing list
but maybe my "two cent" can help you guys a little
bit.

Before making a decision and start implementing
sparse matrices consider the following:

What shell it be? For whom?
---------------------------
a) just a feature as the mathworks has :-(
b) real good stuff:
- sparse matrices make sense only for LARGE matrices.
LARGE is more or less defined by the memory you have.
assume today 90% of the users do not have more then
2GB of main memory, or simply will never be able to
adress more. Assume one entry holding
the matrix in core (in memory) needs from:
- 4+8 (1 index for compressed col.,real value) => 12
bytes
- 8+8+16 (long index, long index, complex)(full
indices) => 32 byte (for a BIG matrix)
And assume we want to carry out the (simple)
operation ADD. We need then A+B=C
three matrices in memory leaving 600MB=6E8bytes per
matrix.
This means we could at maximumg handle
matrices of size 6E8/32=18750000 nonzero elements.
This would be for a "full" sparse matrix:
octave:2> sqrt(6e8/32)
ans = 4330.1
or for a typcial application of sparse matrices, which

is simulation such as mechanical or electrical
engineering assuming a bandwidth of about 100 elements
per row:
octave:3> 6e8/32/100
ans = 187500
This means for these mentioned applications 187,500
degrees of freedom. To be honest this is not much.
State of the art degrees of freedom are
somewhere between 7 and 40 million.
This means that state of the art is:
- handle several matrices (>10)
- size of matrix > 50 million rows (symmetric,
quadratic) etc.
The standard solution is to HOLD the matrices out of
core, e.g. in special files.
All you need in-core is the information about
the datablock/matrix. For example:
-number of rows
-number of columns
-symmetry flag (if a sparse matrix is symmetric
50+x% storage pays off, despite to a full matrix)
-complexity flag
-number of nonzeros
-maximum number of nonzeros per row
-number of null columns/rows
-etc.
based on that information the
m-file-compiler/interpreter can check the validity of
the approach and choose the proper approach to solve
the problem (there are many different approaches,
depending on the properties of the matrices).
You could even spawn a totally different process
(multiprocessor) to solve the problem.

Summary:
Sparse matrices are a special case of the mathematical

object "matrix". This special case was introduced due
to the simple fact that you can be orders of magnitude
more efficient when you apply certain restrictions on
it.
My recommendation is implementing such a feature makes
 only sense if you do not restrict yourself by the way
you implement it. Focus on what you could achieve with
it and for what is was designed (LARGEness). (you do
not buy an expensive car when all you do is moving it
forward and backward in the garage a few meters, do
you?)

best regards, jp


        

        
                
Mit schönen Grüßen von Yahoo! Mail - http://mail.yahoo.de



reply via email to

[Prev in Thread] Current Thread [Next in Thread]