gslmm::qr_decomposition_pivot< double > Struct Template Reference
[QR decomposition]

#include <qr_decomposition_pivot_double.hh>

Inheritance diagram for gslmm::qr_decomposition_pivot< double >:

[legend]Collaboration diagram for gslmm::qr_decomposition_pivot< double >:

[legend]List of all members.

Detailed Description

template<>
struct gslmm::qr_decomposition_pivot< double >

class template specialisation for QR decompositions with column pivoting of matricies of type double .

The QR decomposition can be extended to the rank deficient case by introducing a column permutation $ P$ ,

$A P = Q R$

The first $ r$ columns of $ Q$ form an orthonormal basis for the range of $ A$ for a matrix with column rank $ r$ . This decomposition can also be used to convert the linear system $ A x = b$ into the triangular system $ R y = Q^T b$ , $ x = P y$ , which can be solved by back-substitution and permutation. We denote the QR decomposition with column pivoting by $ QRP^T$ since $ A = Q R P^T$ .

Todo:: implement gsl_linalg_QR_update

Public Types

typedef vector< double > vector_type

typedef matrix< double > matrix_type

typedef matrix_type::value_type value_type

typedef matrix_type::element_type element_type

Public Member Functions

qr_decomposition_pivot (const matrix_type &m, bool unpack=false)

virtual bool solve (const vector_type &b, vector_type &x) const

virtual bool solve (vector_type &x) const

virtual bool r_solve (const vector_type &b, vector_type &x) const

virtual bool r_solve (vector_type &x) const

virtual bool qr_solve (const vector_type &b, vector_type &x) const

virtual bool update (const vector_type &w, const vector_type &v)

virtual int sign () const

virtual const permutation & p () const

Private Types

typedef matrix_type::data_type data_type

Private Member Functions

bool solve (const vector_type &, vector_type &, vector_type &) const

bool qt_multiply (vector_type &)

bool q_multiply (vector_type &)

Private Attributes

vector_type _n

permutation _p

int _sign

Member Typedef Documentation

typedef matrix_type::data_type gslmm::qr_decomposition_pivot< double >::data_type [private]

The low level matrix type.

Reimplemented from gslmm::qr_decomposition< double >.

typedef matrix_type::element_type gslmm::qr_decomposition_pivot< double >::element_type

The element type.

Reimplemented from gslmm::qr_decomposition< double >.

typedef matrix<double > gslmm::qr_decomposition_pivot< double >::matrix_type

The matrix type.

Reimplemented from gslmm::qr_decomposition< double >.

typedef matrix_type::value_type gslmm::qr_decomposition_pivot< double >::value_type

The element type.

Reimplemented from gslmm::qr_decomposition< double >.

typedef vector<double > gslmm::qr_decomposition_pivot< double >::vector_type

The vector type.

Reimplemented from gslmm::qr_decomposition< double >.

Constructor & Destructor Documentation

gslmm::qr_decomposition_pivot< double >::qr_decomposition_pivot ( const matrix_type & m,

bool unpack = false

) [inline]

Create an QR decomposition of the input matrix m.
Factorise a general $M \times N$ matrix $ A$ into
$A P = Q R$
where $ Q$ is orthogonal ( $M \times M$ ) and $ R$ is upper triangular ( $M \times N$ ). When $ A$ is rank deficient, $ r = rank(A) < n$ , then the permutation is used to ensure that the lower $ n - r$ rows of $ R$ are zero and the first $ r$ columns of $ Q$ form an orthonormal basis for $ A$ .
$ Q$ is stored as a packed set of Householder transformations in the strict lower triangular part of the input matrix.
$ R$ is stored in the diagonal and upper triangle of the input matrix.
Column $ j$ of $ P$ is column $ k$ of the identity matrix, where $ k = P_j$ . The sign of the permutation is $ (-1)^n$ where $ n$ is the number of interchanges in $ P$ .
The full matrix for $ Q$ can be obtained as the product
$Q = Q_k .. Q_2 Q_1$
where $k = \min(M,N)$ and
$Q_i = (I - \tau_i v_i v_i')$
and where $ v_i$ is a Householder vector
$v_i = \left[1, m_{i+1,i}, m_{i+2,i}, ... , m_{M,i}\right]$
This storage scheme is the same as in LAPACK.
Parameters:

m Matrix to decompose.

unpack If true, then separate values of $ Q$ and $ R$ are stored.

Member Function Documentation

virtual const permutation& gslmm::qr_decomposition_pivot< double >::p ( ) const [inline, virtual]

Returns:
The permutation $ P$ of the QR decomposition

bool gslmm::qr_decomposition_pivot< double >::q_multiply ( vector_type & ) [inline, private]

Hide base classes' member function.

bool gslmm::qr_decomposition_pivot< double >::qr_solve ( const vector_type & b,

vector_type & x

) const [inline, virtual]

This function solves the system $ R x = Q^T b$ for $ x$ .
It can be used when the QR decomposition of a matrix is wanted in unpacked form as $(Q, R)$
Parameters:

b The vector $ b$

x The vector $ x$ , the solution to .

Returns:
true on success.

Reimplemented from gslmm::qr_decomposition< double >.

bool gslmm::qr_decomposition_pivot< double >::qt_multiply ( vector_type & ) [inline, private]

Hide base classes' member function.

bool gslmm::qr_decomposition_pivot< double >::r_solve ( vector_type & x ) const [inline, virtual]

This function solves the triangular system $ R x = b$ for $ x$ in-place.
On input $ x$ should contain the right-hand side $ b$ and is replaced by the solution on output. This member function can be used only if the decompososition is stored in packed ( $QR, P, \tau$ ).
Parameters:

x On input, the vector $ b$ On return, the vector $ x$ that solves $ R x = b$

Returns:
true on success.

Reimplemented from gslmm::qr_decomposition< double >.

bool gslmm::qr_decomposition_pivot< double >::r_solve ( const vector_type & b,

vector_type & x

) const [inline, virtual]

This function solves the triangular system $ R x = b$ for $ x$ .
This member function can be used only if the decompososition is stored in packed ( $QR, P, \tau$ ).
Parameters:

b The vector $ b$

x On return, the vector $ x$ that solves

Returns:
true on success.

Reimplemented from gslmm::qr_decomposition< double >.

virtual int gslmm::qr_decomposition_pivot< double >::sign ( ) const [inline, virtual]

Returns:
Sign of the permutation matrix $ P$

bool gslmm::qr_decomposition_pivot< double >::solve ( vector_type & x ) const [inline, virtual]

This member function solve the system $ A x = b$ using the QR decomposition of $ A$ .
This member function can be used only if the decompososition is stored in packed ( $QR, P, \tau$ ).
Parameters:

x On input, the vector $ b$ , and on output the vector $ x$

Reimplemented from gslmm::qr_decomposition< double >.

bool gslmm::qr_decomposition_pivot< double >::solve ( const vector_type & b,

vector_type & x

) const [inline, virtual]

This member function solve the system $ A x = b$ using the $ QRP^T$ decomposition of $ A$ .
This member function can be used regardless of whether the decompososition is stored in packed ( $QR, P, \tau$ ) or unpacked ( $ Q, R$ ) form.
Parameters:

b The vector $ b$

x The vector $ x$

Returns:
true on success

Reimplemented from gslmm::qr_decomposition< double >.

bool gslmm::qr_decomposition_pivot< double >::solve ( const vector_type & ,

vector_type & ,

vector_type &

) const [inline, private, virtual]

Hide base classes' member function.

Reimplemented from gslmm::qr_decomposition< double >.

bool gslmm::qr_decomposition_pivot< double >::update ( const vector_type & w,

const vector_type & v

) [inline, virtual]

This function performs a rank-1 update $ w v^T$ of the $ QR$ decomposition ( $ Q, R$ ).
The update is given by
$Q'R' = Q R + w v^T$
where the output matrices $ Q'$ and $ R'$ are also orthogonal and right triangular. Update a $ Q R P^T$ factorisation for $ A P = Q R$ , $ A' = A + u v^T$ ,
$\begin{eqnarray*} Q' R' P^-1 = QR P^-1 + u v^T = Q (R + Q^T u v^T P ) P^-1 = Q (R + w v^T P) P^-1 \end{eqnarray*}$
where $ w = Q^T u.$ Algorithm from Golub and Van Loan, "Matrix Computations", Section 12.5 (Updating Matrix Factorizations, Rank-One Changes)
Reimplemented from gslmm::qr_decomposition< double >.

Member Data Documentation

vector_type gslmm::qr_decomposition_pivot< double >::_n [private]

The $ N$ of the QR decomposition.

permutation gslmm::qr_decomposition_pivot< double >::_p [private]

The permutation $ P$ .

int gslmm::qr_decomposition_pivot< double >::_sign [private]

Sign of permutation.

The documentation for this struct was generated from the following file:

qr_decomposition_pivot_double.hh

Top of page	Last update Tue May 9 10:11:31 2006
Christian Holm	Created by DoxyGen 1.4.6

gslmm::qr_decomposition_pivot< double > Struct Template Reference [QR decomposition]

Detailed Description

template<> struct gslmm::qr_decomposition_pivot< double >

Public Types

Public Member Functions

Private Types