|
|
Glas :Re: [glas] (sparse) operations and temporary storage |
From: Karl Meerbergen (Karl.Meerbergen_at_[hidden])
Date: 2006-12-20 03:23:08
Hi Gunter,
I am currently writing a proposal for the first GLAS concepts.
The concepts are very minimal and make a distinction between dense and
sparse. The common concepts are VectorExpression and VectorCollection.
See the dia file in http://www.cs.kuleuven.be/~karlm/glas/expression.dia
Details about temporary storage, I would personally keep in the backend
since they are most likely implementation dependent.
Again, this is my view. We haven't really discussed these issues yet.
Concerning your example, I haven't really thought about this in detail
yet, but my first bet would be to split
z = alpha x + beta y
into
z = alpha x
z += beta y
when x or y are a SparseExpression with different sparse structure.
Karl
Gunter Winkler wrote:
>Hallo,
>
>will the glas-concepts consider the need for temporary storage or is this only
>interesting for the backends?
>
>Lets for example consider a linear combination of two sparse vectors:
>
>z = alpha x + beta y
>
>in the case x and y being conformant (the pairs (index,value) are sorted by
>index) the result can be computed in order by a parallel run through both
>vectors. The index sequence of z is just a merge of two sorted sequences.
>However, if x or y are not conformant one could either use
>z = alpha x; z += beta y;
>or utilize a temporary dense vector "temp" known to be zero everywhere:
>temp = alpha x; // sparse assign because temp is zero ("scatter")
>temp += beta y; // sparse update of a dense vector
>for each index i in x do {
> z(i) = temp(i); temp(i) = 0;
>} // "gather and clear"
>for each index i in y do {
> if temp(i)!=0 {
> z(i) = temp(i);
> temp(i) = 0;
> }
>} // "gather if nonzero and clear"
>
>One important point is, that the vector "temp" has to be reused many times in
>order to amortize is allocation cost. Thus it has to be a parameter of the
>assign operation.
>
>(This algorithm is expected to be even faster than the conformant merge,
>especially when more vectors are combined - but I never tried it.)
>
>The question is now, should this be considered in the general concepts, or
>could this be hidden inside backend functions, or should these optimizations
>left to the enduser by only providing some building blocks?
>
>Another question is, whether to have concepts (and implementations) which are
>independent of the actual implementation and provide refinements for dense
>and sparse types (which might be quite different) or to have concepts (and
>models) mainly for dense types and refine these for sparse types.
>
>What do you think?
>
>mfg
>Gunter
>
>
>------------------------------------------------------------------------
>
>_______________________________________________
>glas mailing list
>glas_at_[hidden]
>http://lists.boost.org/mailman/listinfo.cgi/glas
>
Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm