Re: [pooma-dev] Sparse Engine

[Richard Guenther]

On Fri, 26 Sep 2003, Sergei Mingaleev wrote:

> 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.

Yes, you'd reduce the memory requirement by doing run length encoding.
This way the size of the bitmap will not be bigger as the number of used
cells (usually a lot less).

> 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.

You should be able to do log n time searches in the bitmap, if you really
need to. But in the common use of applying an Evaluator youd just traverse
the bitmap in optimal oder and determining which elements are used is
nearly a noop.

But maybe we're again talking about "different" sparsity here... I'd call
the unused (what you call zero) elements not participate in calculation,
just like with an arbitrary shaped domain. You seem to suggest more like a
compressed engine approach?

> 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.

Yes, for sparse matrices one usually uses very special data-structures.
And these tend to be used for statically shaped matrices only, too.

> 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?

Hmm, this sounds different to what I have in mind. It sounds like you want
to do a multidimensional wavelet compression here.

Richard.