Re: [ublas] LQ factorization with lapack bindings

From: Jens Seidel (jensseidel_at_[hidden])
Date: 2007-12-22 18:20:21

On Sat, Dec 22, 2007 at 09:32:07PM +0200, Sorkin Dima wrote:
>   I need to solve an undetermined system of equations
> (minimum norm solution), several times, with the same
> matrix. As far as I know Lapack does this via LQ
> factorization.
> 
>   In bindings, only QR factorization currently exists.
> 
> 1) Does someone have bindings for LQ ?
> 
> 2) Is there a simple way to solve undetermined system
>    using QR factorization 

Yep. The least square solution can be obtained as:
 x = R^(-1)*Q^T*y

Please note that this decomposition often requires maximal column rank
of A but allows also generalisations. If you don't have a maximal
column rank you can simply dropping all dependent columns of A and
obtain the QR decomposition for the reduced system. In this case you
have to extent x by zeros for dropped columns.

That's an easy algorithm to obtain a least square solution (there may
exist multiple if the rank is not maximal). See
http://en.wikipedia.org/wiki/Qr_decomposition
and also
http://en.wikipedia.org/wiki/Moore-Penrose_pseudoinverse

> + some tricks with transposes,

I think QR and LQ are indeed very similar and should be transformed into
each other by using a transposed matrix (but I'm not sure, I use always
QR).

>    using the existing bindings' functions ?
>    The matrix A can be pretty big and I would prefer not to
>    create copy of its transpose explicitly -
>    is it unavoidable if I use QR ?

Please note that some QR decompositions (especially if Gram Schmidt
orthogonalisation is used) are very unstable and could cause trouble with
small systems as 5x5 (at least if you expect a high accuracy)!!!!

Jens