## 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

**Next message:**Peter Gottschling: "Re: [glas] A few more thoughts about return type of operator[](size_type) for sparse vectors"**Previous message:**Toon Knapen: "Re: [glas] [boost] Possible class submission: Sparse Array"**In reply to:**Russell Smiley: "Re: [glas] return type of operator[](size_type) for sparse vectors?"**Next in thread:**Toon Knapen: "Re: [glas] return type of operator[](size_type) for sparse vectors?"**Reply:**Toon Knapen: "Re: [glas] return type of operator[](size_type) for sparse vectors?"

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_at_[hidden]

> 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

**Next message:**Peter Gottschling: "Re: [glas] A few more thoughts about return type of operator[](size_type) for sparse vectors"**Previous message:**Toon Knapen: "Re: [glas] [boost] Possible class submission: Sparse Array"**In reply to:**Russell Smiley: "Re: [glas] return type of operator[](size_type) for sparse vectors?"**Next in thread:**Toon Knapen: "Re: [glas] return type of operator[](size_type) for sparse vectors?"**Reply:**Toon Knapen: "Re: [glas] return type of operator[](size_type) for sparse vectors?"