Hi,
This is very good news, indeed!
Could I ask whether there are plans to rewrite the iterator
interface of ublas? As only the parallelization oriented projects
were accepted to ublas, are there still plans for the unification
of vector and matrix interface?
Otherwise i would like to propose a set of changes. I implemented
most of them in my local fork (which is however not fully
operational because this turned out to be a lot of work...), and
it should resolve most of the basic performance issues regarding
sparse operations.
1. replace the current matrix iterators with iterators iterating
ONLY a single row or column. Remove dual iterators.
The interface could look like
typedef ... row_iterator;
typedef ... const_row_iterator;
row_iterator row_begin(size_type row_index), row_iterator
row_end(size_type row_index)
(same for column).
Reasoning:
1.1 Dual operators are costly to implement as the iterators always
need two sets of states. This is no problem for dense as the set
is more or less the current index (i,j) but for sparse vectors
there is a considerable overhead (factor 3 in run time, not
counting find() which is also really slow)
1.2 The matrix iterators are essentially the same as for the
vectors. for example in matrix addition the exact same iterator
can be used only iterating over row-iterators instead of vector
iterators. This saves a lot of code
1.3 the same holds for row and column iterators! For example dense
row/column and dense vector iterators can be implemented using one
class (using the current position in the storage array and
stride). Very often this also holds for const and non-const.
1.4 Most proxies are easy to implement. for example matrix_row and
matrix_column can just return matrix_row(i); Also for example a
matrix_transpose-proxy class (replacing matrix_unary2 which can be
implemented using matrix_transpose + matrix_unary1) is incredible
simple.
1.5 One could interpret this change as unification of vectors and
matrices by regarding matrices as a set of vectors(rows/columns).
There is a small disadvantage:
This proposed interface can't skip empty rows/columns in
sparse-matrices. However assuming nnz>rows this should not make
a notable difference in most cases.
On my local fork I used a ~25.000 loc subset of ublas which is now
well below 9000 lines after applying these changes.
2. replace make_conformant in assignment by something new.
The problem for sparse vectors/matrices is that aliasing has a
different meaning than for dense. for example two rows of a dense
matrix only alias if they are pointing to the same memory. This
does not hold for sparse matrices as changes in the one row might
invalidate iterators in the other.
The way ublas solves the problem is to first check which non-zero
elements are created by the assigned expression, than create the
missing entries in the target proxy and afterwards assign the
expression (this might need some documentation in matrix_assign,
took my long to figure out what make_conformant does).
This evaluates the expression twice because we first have to know
which elements are non-zero and than we can assign them. I propose
to merge both to one operation:
right now make_conformant creates an
std::vector<std::size_t> (in the vector-assignment case)
storing the new indices which are than inserted afterwards.
what about:
template<class value_type>
struct Element{
std::size_t index;
value_type value;
};
std::vector<Element<Vector::value_type> >
new_elements?
In this way we would at last not have to evaluate the expression
twice.
3. extend sparse interfaces.
Even with the proposed change, make_conformant is slow, because
inserting in a compressed_vector using operator() is O(log(n)).
so i propose a new method for vectors(and similar for matrices):
iterator set_element(iterator position,size_type index, value_type
value);
which inserts the element (index,value) at position returning an
iterator to the newly inserted element.This way insertion of k
elements in a vector with n elements can be implmented in O(n+k).
This could also replace the current push_back method as it is a
special case with vec.set_element(vec.end(),index,value);
similarly we should have operations like reserve/reserve_row etc
in proxies to make the make_conformant case fast.
Also swapping might need some love as this is ridiculous right now
(i need that some times and right now just straight copying the
reordered matrices is a lot faster)
4. Only one sparse-matrix for all.
Optimizing code for sparse matrices is hard. Optimizing it for
multiple formats is impossibly hard. I would propose to remove all
variants of the sparse matrix except compressed_matrix. This
should be reimplemented such that it is not densely packed inside
the arrays but instead there should be a bit of space between the
matrix rows (or columns depending on orientation). This way
inserting elements in the middle (as with operator+=) is not as
expensive.
Ohh, this was rather long. But I want to get this discussion
rolling, as I regard sparseness as an important feature of ublas.
Please ask if you have questions! I am happy to elaborate on
unclear points.
Greetings,
Oswin
On 28.05.2013 17:41, Nasos Iliopoulos wrote:
Yes,
additionally with the boost transition to github we are planning
to make contributing to uBlas much easier. We would like though
to stress quality and find a way to define performance
requirements specifications. When the github repo (a fork of
boostorg/ublas) is ready (I hope I can have it ready this
weekend) we will include instructions on how to work with pull
requests (to submit an algorithm or a small bugfix for example),
or in cases where larger involvement is required maybe give
access to the ublas development repo to ppl that want to
contribute.
-Nasos
On 05/28/2013 10:59 AM, Salman Javaid wrote:
Are there any plans to integrate Karl's QR
Decomposition implementation into Boost.uBLAS? I will be
grateful for a response.
_______________________________________________
ublas mailing list
ublas@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/ublas
Sent to: athanasios.iliopoulos.ctr.gr@nrl.navy.mil
_______________________________________________
ublas mailing list
ublas@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/ublas
Sent to: Oswin.Krause@ruhr-uni-bochum.de