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
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
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
> If "proxy_type operator" is not provided how would structural zeroes
> normally be modified?
>> -----Original Message-----
>> Subject: [glas] return type of operator(size_type) for
>> sparse vectors?
>> Given a sparse vector v of size 10, what would v 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
Open Systems Laboratory
301i Lindley Hall
Bloomington, IN 47405
Tel.: +1 812 855-8898 Fax: +1 812 856 0853