[Home]UBLAS Matrix Iterators

BOOST WIKI | RecentChanges | Preferences | Page List | Links List

Difference (from prior major revision) (minor diff, author diff)

Changed: 26c26
The mapping of the pair (major index, minor index) to the pair (row index, column index) can be implemented using a traits class and the orientation category of the matrix. The existing index_M and index_m in the row/column_major storage layout types provide such a mapping
The mapping of the pair (major index, minor index) to the pair (row index, column index) can be implemented using a traits class and the orientation category of the matrix. The existing index_M and index_m in the row/column_major storage layout types provide such a mapping. Thus we should make layout_type public.

Added: 31a32

other issues with iterators




Added: 32a34,37
Dense matrices allow for a simple definition of iterators operating over all elements. When sparse and special matrices are considered the definition is not so clear. For sparse matrices operation over the non-zeros is required.

However for symmetric and triangular special matrices there are other choices.
In particular when using a mutable iterator we can only iterate over the primary mutable elements. This does not define all iterators as 'iterating over non-zeros' as there may be over non-zero elements.

current state

As of today (2006-07-06) ublas' matrix iterators look like this:

const_iterator1 moves from one row to another for a fixed column.

const_iterator2 moves from one column to another for a fixed row.

One can always switch from one iterator to the other (called dual iterator) by calling the begin() or end() member function. Both iterators store the current row and column index and have to implement the movement in both fast (inner loop) and slow (outer loop) direction. Thus the code is complex and the memory footprint is not optimal. On the other hand the design of generic algorithms is easy because you can arbitrarily choose which iterator is outer or inner loop (but this is typically a bad design).

current implementation

In fact the current expression assignment machinary is almost completely duplicated with 2 versions of each algorithm. One for row_major_tag and one for column_major_tag.

quick survey

Does anyone use the duality feature?

edit by Gunter: Up to now I got only negative answers.

ideas for a better design

Drop the strong duality and provide a major (outer loop) and minor (inner loop) iterator. The major iterator could always be a random access dense iterator that only stores an index. The minor iterator holds a copy of the major index and can use an optimized way to traverse along matrix elements. The minor iterator should have an advance_to_index(k) function that moves the iterator at the first element with index >= k (like std::lower_bound). This way traversal orthogonal to the storage layout can be emulated and we don't need any find functions.

The advance_to_index(k) function could be implemented as a free function specialized for different iterator types (bidirectional, random access). Syntax: iterator& advance_to_index(iterator& it, iterator const& it_end, size_type index).

The mapping of the pair (major index, minor index) to the pair (row index, column index) can be implemented using a traits class and the orientation category of the matrix. The existing index_M and index_m in the row/column_major storage layout types provide such a mapping. Thus we should make layout_type public.

sample implementation

Download the source files from [1].

other issues with iterators

Dense matrices allow for a simple definition of iterators operating over all elements. When sparse and special matrices are considered the definition is not so clear. For sparse matrices operation over the non-zeros is required.

However for symmetric and triangular special matrices there are other choices. In particular when using a mutable iterator we can only iterate over the primary mutable elements. This does not define all iterators as 'iterating over non-zeros' as there may be over non-zero elements.


BOOST WIKI | RecentChanges | Preferences | Page List | Links List
Edit text of this page | View other revisions
Last edited July 20, 2006 12:32 am (diff)
Search:
Disclaimer: This site not officially maintained by Boost Developers