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).
Peter
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 lists.boost.org
> http
://lists.boost.org/mailman/listinfo.cgi/glas
>
------------
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
http://www.osl.iu.edu
/~pgottsch
_______________________________________________
glas mailing list
glaslists.boost.org
http
://lists.boost.org/mailman/listinfo.cgi/glas
|