Re: [pooma-dev] Sparse Engine

[Sergei Mingaleev]

Hi Richard,

>> I think this notion of a sparse engine is different from Jeans. In fact

Yes, now I see that it is quite different...

>> Just the sparsity you invented looks like it could be done better by
>> having a (possibly shared) bitmap of valid locations and a evaluator
>> taking that into account. Memory usage would be reduced by not accessing
>> the unused parts and such only wasting virtual memory. 

Do you mean creation of the bitmap array with the same size as the size of 
the Sparse Array? This realization is good only for not very large Sparse 
Arrays, but what if we need to work with the array having (1000000 x 1000000) 
points or larger one? In this case the bitmap will be about 100 GBytes - too  
huge! So, we need to remember only positions of non-zero elements. And we 
need some fast way of determining if the point (i,j) has non-zero value of 
A(i,j) or not? - it would be very slow just to search for the given point 
(i,j) in the list of non-zero elements. Thus, we need to use some complicated 
chain-like organization of the list of non-zero elements, with possibility to 
add, as fast as possible, new non-zero elements, and remove (set to zero) old 
elements. 

My realization of the SparseEngine uses the standard storage scheme commonly 
used for Sparse Matrices - and for 2D arrays it is rather efficient for both, 
memeory usage and speed of access/modification of elements. Unfortunately, it 
can be hardly extended to arbitrary-dimensional arrays. 

By the way - the tolerance, determined initially by the constant 
SPARSE_TOLERANCE, can be later on changed to new value by the command: 

A.engine().tolerance()=1.0e-5;

One can also add the command: 

A.engine().resize(N);

to be able to increase/decrease the physical memory occupied by the Sparse 
Array. I am not only sure - may be, there is some more elegant way to 
add such kind of functionality? 

Cheers,
Sergei.