want to save memory in sparse matrix
Harshal
i am a newbie in fortran.
i have a very big parse hessian matrix with lots of zeros.
the code is something,
<snip>
aaa=ac*cc
vvv=dfd*dd
matrix(aaa,vvv)= some+expression
<snip>
many times the value of element matrix(aaa,vvv) will be zero.
but still it will be stored in the memory, and there are some
10000x10000
elements.
what can i do to prevent it from storing the value. pointers??? are
they as good as in C?
Random Programmer
row/column position of each entry. Then either transform your matrix
operations to operate with vectors (easy with something like matrix
addition). If the operations can't be transformed, then only
reconstitute the array as needed. This swaps processor cycles for
memory...not sure if it is a good trade-off!
I'm not sure what kind of Hessian matrix you're using, but IIRC for
orthotropic materials the B-matrix is not populated, and you can
decouple the A & D matrices, so that's 1/2 the memory requirements
gone.
andy2O
There is a very large selection of publically available (free) high
quality software librarues for dealing with sparse matrices. It is an
active and advanced area of research.
So, the first thing I would suggest is to ensure that you are not
re-inventing the wheel. If you need to solve linear system of sparse
equations, or just store and manipulate sparse matrices, then you can
download free software to do it, or buy a commercial library. This
software is specially designed to use memory efficiently - both in
terms of quantity (it does not store zeros) and speed of access
(special storage formats which allow data to be fetched from memory in
an efficient order for solving equations). This should save you a lot
of time and effort!
If you tell us more about the particular work you are trying to do, we
may be able to give more precise recommendations of which software you
should look at. However, you should definitely visit
# Jack Dongarra's guide to linear algebra software on the web
http://www.netlib.org/utk/people/JackDongarra/la-sw.html
if you are trying to solve equations, and also search www.netlib.org
for information if you are trying either to solve equations or
manipulate matrices. The commerical NAG library hs some sparse matrix
code for Fortran. The Harwell subroutine library (google for it) has
good codes too. Also, you might like to look at (copied from my notes):
# Yousef Saad's book on Iterative methods for sparse linear systems
http://www-users.cs.umn.edu/~saad/books.html
Notes: A link to the full text of a very useful book on sparse linear
systems, by Yousef Saad of the University of Minnesota's Department of
Computer Science and Engineering. I'm a fan of the second edition of
this text, which is published by SIAM, but I'm sure the first edition
which is free online is worth a look too. Also available from this page
is the text of a book on Numerical Methods for Large Eigenvalue
Problems. Yousef has also made the sparse matrix software "SPARSKIT"
and a "parallel Algebraic recursive Multilevel Solver" package
available via his homepage.
I hope that helps.
Andy
Harshal
thanks for your reply. i have a code which is used in
molecular dynamics in our lab. basically the code is used for normal
mode analysis. any suggesions are highly welcomed.
thanks in advanced.
Harshal
elements. obiously many times the hess(e_i,e_j) elements is zero.
!xx
e_i=(i-1)*3+1
e_j=(i-1)*3+1
hess(e_i,e_j)=k_st*r_diff/rij + k_st*r0(ti,tj)*xij*xij/rij3 +
hess(e_i,e_j)
!xy
e_i=(i-1)*3+1
e_j=(i-1)*3+2
hess(e_i,e_j)=k_st*r0(ti,tj)*xij*yij/rij3 + hess(e_i,e_j)
hess(e_j,e_i)=hess(e_i,e_j)
Harshal
basically we construct a hessian matrix. then we diagonalise it and get
the eigenvalues.
i am confused. new to this world.
Gordon Sande
> hi,
> i am a newbie in fortran.
> i have a very big parse hessian matrix with lots of zeros.
>
> the code is something,
>
> <snip>
>
> aaa=ac*cc
> vvv=dfd*dd
> matrix(aaa,vvv)= some+expression
>
> <snip>
>
> many times the value of element matrix(aaa,vvv) will be zero.
> but still it will be stored in the memory, and there are some
> 10000x10000
> elements.
Be warned that sparse techniques are only useful it 90% of the
matrix is zero, and maybe it should be 99%. If it is merely half
zeroes the cost of the logic to avoid the computaion with the zeroes
is higher than just letting the hardware quickly evaluate things
with a zero value. More typical sparse applications will have
only a few, count them on your fingers of one hand, nonzero
elements in each column of the matrix. (Polydactylism is
sometimes observed. ;-))
> what can i do to prevent it from storing the value. pointers??? are
> they as good as in C?
Some pieces of software use associative storage techniques to only
store the values of identifiers with nonzero (or nonnull) values.
For such systems the identifier if a matrix element would be
matrix$a##$v##, or some such construction, with the use of subscript
notation a user convenience. Unfortunately such systems have high
overhead and would be viewed as totally inadequate for the purposes
that are usually considered under sparse matrix operations. Such
associative storage makes keeping addresses books and other database
applications very easy as they typically do not restrict the subscript
values to being just numbers.
The ability to do sparse matrix operations with reasonable efficiency
is subject matter of a whole subfield of computer science. There are
many books, many conferences every year, etc, etc so the only useful
advice is to read the literature. But it is more likely that you have
a problem which has already been solved well enough for your immediate
purposes and you should reuse what is already there. Google is your
friend starting from "solving sparse matrix equations" with refinements
as you figure out the terminology in use. Advice of colleagues is also
useful.
beli...@aol.com
codes for sparse linear algebra at the Open Directory at
http://www.dmoz.org/Computers/Programming/Languages/Fortran/Source_Code/Linear_Algebra/Sparse/
.
andy2O
> is (PARPACK and ARPACK) answer for me.
> basically we construct a hessian matrix. then we diagonalise it and get
> the eigenvalues.
> i am confused. new to this world.
>
OK... that's the information we needed. From the ARPACK website, and my
memory of ARPACK, the ARPACK library only requires you to provide code
to calculate the value of the product of your matrix (i.e. the Hessian)
with an arbitrary vector[1].
This is a much simpler task than many of the other possibilities your
original post made us think of! Looking at the code in a couple of
libraries, it seems it is generally implemented in about 20 lines or
so. The important thing is to use the right data structure.
I have to admit I don't know which format/library is THE best for this
particular task. My requirements usually lead me to choose packages for
far broader reasons. I hope someone else reading this can offer advice
too. However, here are some thoughts to get you started:
I suggest you look at the "SLAP column format" for storing sparse
matrices used in the "dlap" library, which you can find at
www.netlib.org/slap, and then look at the code in the file dmvops.f
within this package. There is code there for the task you need - for
symmetric and non-symmetric matrices.
Also, register with HSL archive subroutine library (for free if the
licencing rules are suitable for your code i.e. non-commerical) at
http://hsl.rl.ac.uk/archive/hslarchive.html
and look at routine "MC09: Sparse matrix-vector product" and their
data formats. I'm not sure this exploits symmetry though.
Then google for "sparse matrix vector product". It uncovers many
options and sources....
I hope someone else can more add information to this reply for you.
Best wishes,
Andy
[1] - From the "Important features" page of the ARPACK user guide at
http://www.caam.rice.edu/software/ARPACK/: "For many standard problems,
the action of the matrix on a vector is all that is needed.". You'll
have to check if this is all that is needed in your case....
Harshal
thanks for your reply. very informative.