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

From: Toon Knapen (toon.knapen_at_[hidden])
Date: 2006-04-27 15:53:29

Peter Gottschling wrote:
> 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.

if option 3 is taken and thus if operator[] can have an effect on the 
structure, the questions above are difficult to answer and semantics 
will become even more subtle (and thus unclear for the user).

> 
> 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.  

That is impossible. Even if operator[] can change the structure (as in 
option 3), operator[] might change the structure and therefore will 
invalidate the iterators. The iterators for a dense-vector are however 
not invalidated when using operator[] so I think it will never be 
possible to have the same behavior as dense.

Anyway we also foresee to have other members to insert non-zero's 
explicitly so operator[] is not the only way. The discussion about 
operator[] is purely about convenience, not about features.

> 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).

agreed

> 
> 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).

The one does not exclude the other. The dense-views seem indeed 
interesting but we can play around with both (if we really want) and see 
what is most convenient/performant.