Glas List: Re: [glas] return type of operator[](size_type) for sparse vectors?

From: Peter Gottschling (pgottsch_at_[hidden])
Date: 2006-04-27 10:49:21

I also prefer option 3 and I don't believe that it would cause much 
overhead.  Also, I think that vectors are expected to change often in 
applications (much more than matrices) and need the ability to change 
the sparsity pattern and insert non-zeros.

Another question is how to keep the sparsity pattern small.
- When v[i]= 0, should v[i] be removed from the structure?
- What if v[i]= f(x) with f(x)~0?  One could provide user-defined 
predicates that decide when an element can be dropped. How much would 
this complicate the implementation?
- Do have typical sparse vector applications regular assignments v= 0 
so that an element-wise cancellation is not needed?
- Should v= 0 automatically empty the structure or do we prefer to have 
something like v.reset() to do this?  For dense vectors v.reset() would 
set all elements to 0 to keep an unified interface.

Having no operator[] access would be strange for a vector and makes 
many implementations more difficult.  The behavior of operator[] should 
be consistent with dense vectors.  For efficiency reasons, the 
preferred access to vectors which are possibly sparse should be with 
iterators (cursors) over non-zero elements (if the vector is the driven 
data structure).

For instance, multiplying a sparse matrix with a vector, one usually 
iterates over the non-zero elements of the matrix and expects the 
vector elements to be random-accessible (matrix-driven).  For very 
sparse vectors it could be more efficient to iterate over the non-zeros 
of the vector and access the corresponding matrix elements needed for 
multiplication.  This requires that the columns of the matrix are 
accessible efficiently, which is given for a CCS matrix but not for a 
CRS matrix.

Speaking of iterations over sparse data structures.  Karl, Toon and I 
had the idea to provide different traversal tags for begin and end 
functions.  This idea works fine to distinguish for instance between 
row-wise, column-wise or element-wise matrix traversal (under the 
condition that the matrix allows such traversal).  Recently, I intended 
to implement dense traversal for sparse matrices, i.e. to go over all 
elements including structural zeros.  The reason I hesitated was that 
the cursors/iterators need conceptionally different information, 
offsets within internal data structures versus matrix indices.  While 
this is still implementable, kind of, it would introduce a lot of 
overloading and complicating the implementation significantly.  As an 
alternative, I find it clearer to have a dense_view of a sparse matrix 
or vector and use the cursor/iterator of this view to traverse all 
elements.  (Loops over all matrix or vector indices and using 
operator[] or operator() would be equivalent but less generic.)  Better 
we have dense_matrix_view and dense_vector_view which should be both 
implementable generically (without specialization).

Peter

On 26.04.2006, at 15:11, Russell Smiley wrote:

> I think I prefer option 3 (proxy that modifies a structural zero if
> necessary). Presumably there is some penalty for this more 
> sophisticated
> behaviour.
>
> If "proxy_type operator[]" is not provided how would structural zeroes
> normally be modified?
>
> Russell.
>
>> -----Original Message-----
>
>> Subject: [glas] return type of operator[](size_type) for
>> sparse vectors?
>>
>>
>> Given a sparse vector v of size 10, what would v[0] return? Should it
>> return a reference to the element at position 0 in the sparse vector.
>> What if that element is a structural-zero? It clearly is not as
>> straightforward as with dense vectors.
>>
>> The options AFAICT are:
>> 1) provide no 'operator[](size_type)' to avoid confusion
>>
>> 2) return the value at the corresponding position or if the position
>> corresponds to a structural-zero return zero. Thus in that case
>> operator[] will not affect/change the structure and
>> operator[] will not
>> allow to change the value at the corresponding position.
>>
>> 3) return a proxy. If the proxy is being assigned to, the
>> structure will
>> be changed in case the position corresponded with a structural-zero.
>>
> _______________________________________________
> glas mailing list
> glas_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/glas
>
------------
Peter Gottschling
Research Associate
Open Systems Laboratory
Indiana University
301i Lindley Hall
Bloomington, IN 47405
Tel.: [phone]   Fax: [phone]
http://www.osl.iu.edu/~pgottsch