Boost logo

Glas :

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


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]
Peter Gottschling
Research Associate
Open Systems Laboratory
Indiana University
301i Lindley Hall
Bloomington, IN 47405
Tel.: +1 812 855-8898 Fax: +1 812 856 0853