Large Sparse Matrix Storage

[bransford]

I need to efficiently store the indices of nonzero elements in very large sparse matrix in a F90/95 program. Every row of the matrix has at least one nonzero but the number of nonzeros in any given row varies. The nonzero indices are found one at a time by looping through an array. I don't want to store repeated indices. By the way, this is a Finite Element code. This is the structure I'd like to build

Head(1) => {linked list of nonzeros in row 1}
.
.
.
Head(i) => {linked list of nonzeros in row i}
.
.
.
Head(N) => {linked list of nonzeros in row N}

where Head(i) is an element of an array of pointers and N is determined at run time.

Is this structure, or something equivalent, possible in Fortran 90/95? If it is, please tell me how to declare the variables and set it up. Thanks.

 

[xwb]

Try

TYPE SList
    TYPE (SList), POINTER :: mNext
    INTEGER :: mIndex
END TYPE Slist

! Assuming N is a parameter constant
TYPE (SList), DIMENSION (N):: head

You use ALLOCATE to create new ones, => for pointer assignment and % to get at the members.

Having said that, I personally think than an array containing the indices of all the non zero elements would be faster - all you are doing is double indexing. With a singly linked list, to get to the 10th element you have to start from the first and step through until the 10th one. The more you have to step through, the longer it gets, unless you are processing the data sequentially.

Sorry, what I know about Finite Element Method can fit at the back of a standard UK postage stamp. I don't know if you need the indices randomly or sequentially. If it is sequential then a link list is OK, if it is ranom then an array of indices would be simpler.

 

[bransford]

Thank you for responding. I ended up resolving the issue several days ago by that method. The program is sufficiently fast now, requiring about 45 minutes to setup and solve about 25 sets of 120,000 linear algebraic equations. The memory requirement is also reasonable.