Boost logo

Glas :

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

From: Karl Meerbergen (Karl.Meerbergen_at_[hidden])
Date: 2006-04-28 03:08:54

I recall similar discussions earlier on and wonder whether we have to
provide an operator[] for non-const sparse vectors in the GLAS core. It
is very interpretation dependent and therefore it is probably better to
provide containers/adaptors that implement a specific interpretation of
operator[]. A few possibilities:

* v[i] never inserts (assumes the structure does not change)
* v[i] returns a proxy and allows insertion (the most general, but
potentially most inefficient case)
Then there are issues such as: do we always need a sorted sparse
structure? Does v[i]=0 create a structural zero?
* v[i] returns a proxy, but only allows push_back to the structure

This is all application dependent. In the applications I am implementing
I use all of these strategies in different situations, so I am unable to
say which interpretation of operator[] I need. I need them all!

In my opinion, this does not mean we have to implement all these
strategies, but allow the user to make a tuned adaptor or container that
does the right job for him. The GLAS core should provide the tools to
implement strategies efficiently.

I suggest to only provide the functionalities in the GLAS core that we
need to implement the algorithms that are suppported by GLAS. We can
talk later about functionalities that make GLAS more sexy or easier to use.


Toon Knapen wrote:

>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.
>glas mailing list

Karl Meerbergen
Free Field Technologies
Axis Park Louvain-la-Neuve
rue Emile Francqui, 1
B-1435 Mont-Saint Guibert - BELGIUM
Company Phone:  +32 10 45 12 26
Company Fax:    +32 10 45 46 26
Mobile Phone:   +32 474 26 66 59
Home Phone:     +32 2 306 38 10