Re: [eigen] Fast QR for 2x2, 3x3

[Gael Guennebaud <gael.guennebaud@xxxxxxxxx>]

first of all, thanks for the piece of code !


then,  I don't think we want to provide multiple algorithms for the
same matrix sizes. So basically all the logic would be done by the QR
class:

if (matrix_sizes_at_compile_time==2x2)
  use Givens 2x2 path
else if (matrix_sizes_at_compile_time==3x3)
  use Givens 3x3 path
else if (matrix_sizes_at_compile_time<16x16)
  use generic fixed size gram schmidt path
else
  use Householder path

in order to reduce compilation time this branching should be done
using meta programming via either specializations of the whole QR
class or using internal meta selectors. For instance if we do it at
the QR class level, its declaration would be:

template<typename MatrixType, int QrMethod =
ei_qr_method<MatrixType>::ret > class QR;

and to reduce some code duplication we can add a QrBase class. Note
that this option still allow the user to overwrite the QR method to
use a more generic one.

Also, note that we have not guaranteed the API stability of the QR
module yet, so some minor modifications could be acceptable. In
particular we have to find a way to make it more generic such that it
can be used on sub matrices and/or with given matrix storages (this
also holds for LU, Cholesky, Tridiag, etc.)

Another issue: currently the QR class compute the Q and R matrices in
a compact form mixing the triangular R matrix with a set of
householder vectors for Q.  Perhaps it would be better to ask the user
to specify which matrices have to be computed and directly compute
them in an explicit form ?

gael.


On Tue, Feb 24, 2009 at 11:49 PM, Andrea Arteaga <yo.eres@xxxxxxxxx> wrote:
> I thought about how to include the code in th QR.h header. I think that the
> fastest way is to specialize the MatrixBase<Derived>::qr() method such that
> for small matrices it calls one cunstructor of the QR class, for each other
> matrices it calls another constructor. The two constructors can be
> differentiated by add an argument enum qr_algorithm with default value
> Householder in this way:
>>
>> enum qr_algorithm { Householder, Givens, GramSchmidt };
>>
>> QR(const MatrixType& matrix, qr_algorithm alg = Householder)
>
> Old code is also compatible thanks to default value. The constructor will
> also control if alg is Householder (and then execute the normal _compute()
> method) o Givens (or GramSchmidt) and then execute another method (for
> example _compute_givens() ), which does the same using Givens - and the
> Markus' code.
> If this run-time control is too inefficient, we can implement a compile-time
> control (with templates), but that cannot perhaps ensure the
> backward-compatibility of the code.
> Note that all this only works with fixed-size matrices. For
> dynamically-sized matriced we need a run-time implementation without
> specialization of the MatrixBase::qr() method.
> Andrea
>