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

**From:** Gunter Winkler (*guwi17_at_[hidden]*)

**Date:** 2006-12-19 11:41:02

**Next message:**Karl Meerbergen: "Re: [glas] (sparse) operations and temporary storage"**Previous message:**Doug Gregor: "[glas] [Announce] Mailing list outage on December 19th"**Next in thread:**Karl Meerbergen: "Re: [glas] (sparse) operations and temporary storage"**Reply:**Karl Meerbergen: "Re: [glas] (sparse) operations and temporary storage"

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

- application/pgp-signature attachment: stored

**Next message:**Karl Meerbergen: "Re: [glas] (sparse) operations and temporary storage"**Previous message:**Doug Gregor: "[glas] [Announce] Mailing list outage on December 19th"**Next in thread:**Karl Meerbergen: "Re: [glas] (sparse) operations and temporary storage"**Reply:**Karl Meerbergen: "Re: [glas] (sparse) operations and temporary storage"