Boost logo

Ublas :

From: Dan Elliott (c_reply_to_at_[hidden])
Date: 2006-06-13 01:11:10


>>>>> "Gunter" == Gunter Winkler <guwi17_at_[hidden]> writes:

    Gunter> On Wednesday 17 May 2006 05:26, Dan Elliott wrote:

>> I see that the lu.hpp file has a data type permutation_matrix
>> which inherits from the vector type. However, I would like to
>> discuss the merits of creating a matrix permutation matrix type
>> that would behave more like a matrix (e.g. matrix operators for
>> right and left had operations). Permutation matrices could
>> even fall under a larger family of transformation matrices!

    Gunter> It would be very convenient to have a transformation
    Gunter> matrix that behaves like a matrix. But for the simple task
    Gunter> of solving linear equations the current permutation_matrix
    Gunter> is sufficient. The permutation_matrix class does not store
    Gunter> the mapping (old index) -> (new index) but a list of swap
    Gunter> operations needed for inplace reordering of vectors (or
    Gunter> matrices). Therefore we should keep this class - maybe
    Gunter> with a better name.

It is probably a good idea to leave specialized data structures (unpolluted by fancy operators and whatnot) to make algorithms like LU faster; but this representation and the resulting efficiency is part of why I am interested in a permutation matrix type.

Of course, storing matrix elements in such a manner complicates matrix operations; but if you know how you will use the matrix, it is an excellent tool to have at your disposal. In addition, I have been able to hack together some simple algorithms to take advantage of this representation for more than just matrix/vector operations.

That said, it would be silly to constrain a general permutation matrix type to a swap-vector representation only. However, this would be a nice feature.

>> Operations of other types against this type could have
>> specialized algorithms which take advantage of their particular
>> structure. For example, if T were a permutation matrix, and S
>> were diagonal, the operation transpose(T) * S * T has a
>> predictable structure as it goes from left to right.

    Gunter> I think a new matrix_ternary_expression class can
    Gunter> cover all products of this type and can be dispatched to
    Gunter> specialized algorithms.

I hadn't thought of this alternative. This would certainly allow individuals to contribute highly specialized algorithms to perform all kinds of crazy combinations like my permutation/diagonal/permuation matrix transposed operation above.

Would this preclude the addition of transformation matrix classes, or would these ternary expressions rely upon these classes? Can the current binary expression design allow for this type of extension?

    Gunter> However, I am not sure if this
    Gunter> should be part of ublas or at a higher level of
    Gunter> abstraction (e.g. some glas frontend).

This is the first I have heard of an attempt to limit the scope of uBLAS. This is probably a good idea. Is there a movement to limit uBLAS to functionality analogous to BLAS and leave higher order operations like the one proposed in my original post as well operations like LU to another library built upon uBLAS?

    Gunter> btw. I never used products of 3 matrices except for small
    Gunter> (3 by 3 upto 5 by 5) matrices. And here we could write a
    Gunter> new class for fixed size matrices and vectors that removes
    Gunter> all unused load from bounded_matrix and bounded_vector.

My needs are very high dimension - computer vision stuff - 4096 dimensions is a typical size. Sadly, much of the stuff I write is dynamically sized. However, even when I do know the dimensionality of my problem before hand I am dealing with something like 4096 dimensions.

It sounds like there is some interest in having transformation and perhaps a permutation matrix specialization available in some form (in uBLAS or some derivative thereof). As you know, I am only a user of uBLAS and have very little idea of where to go from here.

Thank you.

-- 
Dan