(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
_______________________________________________
glas mailing list
glaslists.boost.org
http
://lists.boost.org/mailman/listinfo.cgi/glas

(sparse) operations and temporary storage

Thread: (sparse) operations and temporary storage