What is the most efficient way to work with arrays of variables size?

[aortizb]

Dear All,

I would like to receive comments on the following problem. Suppose you have a matrix K and a matrix M. Matrix M is small compared to K. The problem I have is that matrix K is large and sparse. Matrix K is formed by assembly of several matrix M. So, I work with one matrix M whose size is changing every time that I need to perform an assembly in matrix K. I always know the size of matrix M just before performing the assembly. Because of matrix K is sparse and large, I just want to store non-zero elements.

Here is the question: What would be the most efficient programming technique for the assembly stage, i.e., put matrix M into matrix K?

Any comments is much appreciated.

Thanks,
Alejandro.

[firedraco]

Ok, so this is basically what you are saying, please correct me if I misinterpeted you:

Two matrixes, M and K

M < K
K is several of M in a row:
M = 1,2,3 K = 1,2,3,1,2,3,1,2,3,...

And you want to have a good way to allocate K based on the size of M, which you know just before storing the data into K?

[Duthomhas]

My naïve response is to use some form of associative array, but how exactly depends on what you mean by "Matrix K is formed by assembly of several matrix M."

Do you mean that K's elements are M?
Or do you mean that K's elements are references to elements of M?

[helios]

I understood it as K being a matrix of pointers to Ms.

[satm2008]

If understand it right, it just like a double dimentions but the columns are varying, correct me if I am wrong.

It is similar to an array of strings which each varies in its length.

For example:
K[0] = {"IndianaJones" } -> M[12]
K[1] = {"WorldIsNotEnough" } -> M[16]
k[2] = {"ForYourEyesOnly" } -> M[14]
...
and so forth.

Is it like that? If so, just go for dynamic allocation as you find the size and allocate it accordingly, dynamically.

It would be like:

desired_type *k[kSize];
desired_type *m;

for (i = 0; i < kSize; i++)
{
  // find the size for M 

   m or k[i] = new desired_type[desired_size];  // allocate enough size of it
 
  // further process

}

Check it out. Good luck :)

[aortizb]

Thanks to all for the insights. Maybe I need to explain more deeply.

First of all, I am using allocatable arrays. I don't have problems with the use of C++. It is about an algorithm issue and how to do it efficiently from the memory manage and running time to do the assembly stage point of view.

Actually, this is a code for a meshfree method (MM) to solve a Partial Differential Equation (PDM). The method is similar to Finite Element Method (FEM). Basically, I need to construct a system of linear equations: Ku = f, where K is large and sparse (a lot of zeros inside). I don't need the zeros so I am using a row compressed format to store matrix K. The solution of the linear system is not a problem for me since I am using TAUCS which is a library to solve sparse linear systems. My problem is the assembly stage. In FEM the M matrices are always of the same size, so I can assembly them into K very efficiently (BTW K has fixed size also). In MM the size of M is not fixed, meaning that in one assembly stage it can be, for instance, 10 x 10 and in the next stage it can be 50 x 50, and in the next stage 20 x 20, and so on.

Some other things: Matrix K is formed by the elements of M and K has a fixed size, say 6000 x 6000. Once M is assembled (copy into K), element of matrix M are not needed anymore, so I can deallocate it to allocate again in the next stage. So, I need to send the elements of M to an appropriate index in K. There are a couple of way to do this, but I would like to know which is more efficient. Maybe, I should detail how can it be done, so you can figure out what would be more efficient from the memory and running time point of view.

First option: Since I know the size of M previous to perform the assembly, I can form the M matrix, say of size m_x_m, and then assembly the complete matrix M with a loop structure into K with the aid of a vector that has stored in some way the index (i,j) of the matrix K in which element (k,r) of matrix M must be copied.

Second option: Instead of forming matrix M. I can just compute each element of M, say (k,r) directly into position (i,j) of K with the aid of the same vector described in the first option.

I really don't like to bold words, but I did it above to make evident the difference between the two options. The difference is in option 1, I assembly a complete matrix M into K while in option 2, I compute each element of matrix M directly into K.

In both options, I have to do the operation several times. In the assembly process when a position (i,j) of matrix K has already been copied with another number in a previous stage, simply the new element of (i,j) is added to the previous one.

There is another data that maybe it is needed to know. Entries in matrix K are not known until you place the element of matrix M into K.

In option 1, you compute a complete matrix M (too small compared to K) and then, with the aid of a vector which has stored the index of K in which the elements of M must be placed, you do the assembly of the complete M into K. Thus, option 1 has a loop over elements of M, but not in K becuase of the index vector you know exactly the position in K.

In option 2, you don't have to allocate memory for M, simply you compute a number for which you have a variable of type double to store it, and using the index stored in the vector mentioned in option 1, you place it directly into K. This option also has a loop but not over a matrix M. The loop is actually to compute several times the number in the variable of type double which is then placed into K

So, I would like to know which of the above options should run faster.

Thanks again.