Hi all,
I'm Eduardo, one of the GSOC students. I'm working on implementing the incomplete LU decomposition (ilu function in Matlab). I am having some doubts regarding the best way to deal with a sparse matrix that is expanding incrementally at every step of the algorithm in terms of memory management.
In my implementation I have followed 3 different approaches for a NxN matrix to test how they perform .Lets say I have three output vectors cidx_out, ridx_out, data_out (output matrix would be built from them):
* cidx_out is fixed to N as it will not change. Only ridx_out and data_out does change in size.
1) I fix their size to the maximum size they can achieve N^2 (naive)
2) I expanded them at each iteration as needed (reallocation)
3) The three vector are implemented as lists (they are not random-accessed at any time so they can be built as lists).
What I have found is that using 2) and 3) things slooooow too much,specially with lists, (vector seems to perform better due to efficient use of caches). The execution time doubles with respect to Matlab in some cases. With case 1) all goes smooth and my version of the algorithms perform even better. Maybe some kind of "adaptative reallocation" policy would be the way to go. Lets say, start with a maximun size of k*nzz for the vector and expand if needed at some point using another k that depends on "some things" like the number of iterations that have been done.
My question is the following: Anyone knows which is the trend for handling that situation when working with octave sparse matrices (CCS structure)?
Thanks in advance.
Eduardo