## Glas :## Re: [glas] (sparse) operations and temporary storage |

**From:** Karl Meerbergen (*Karl.Meerbergen_at_[hidden]*)

**Date:** 2006-12-20 03:23:08

**Next message:**Karl Meerbergen: "Re: [glas] (sparse) operations and temporary storage"**Previous message:**Gunter Winkler: "[glas] (sparse) operations and temporary storage"**In reply to:**Gunter Winkler: "[glas] (sparse) operations and temporary storage"**Next in thread:**Karl Meerbergen: "Re: [glas] (sparse) operations and temporary storage"**Reply:**Karl Meerbergen: "Re: [glas] (sparse) operations and temporary storage"**Reply:**Gunter Winkler: "Re: [glas] (sparse) operations and temporary storage"

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

**Next message:**Karl Meerbergen: "Re: [glas] (sparse) operations and temporary storage"**Previous message:**Gunter Winkler: "[glas] (sparse) operations and temporary storage"**In reply to:**Gunter Winkler: "[glas] (sparse) operations and temporary storage"**Next in thread:**Karl Meerbergen: "Re: [glas] (sparse) operations and temporary storage"**Reply:**Karl Meerbergen: "Re: [glas] (sparse) operations and temporary storage"**Reply:**Gunter Winkler: "Re: [glas] (sparse) operations and temporary storage"