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