#include <deal.II/lac/qr.h>

Inheritance diagram for QR< VectorType >:

Public Types
typedef VectorType::value_type	Number

Public Member Functions
	QR ()

virtual	~QR ()=default

virtual bool	append_column (const VectorType &column)

virtual void	remove_column (const unsigned int k=0)

virtual void	multiply_with_Q (VectorType &y, const Vector< Number > &x) const

virtual void	multiply_with_QT (Vector< Number > &y, const VectorType &x) const

virtual void	multiply_with_A (VectorType &y, const Vector< Number > &x) const

virtual void	multiply_with_AT (Vector< Number > &y, const VectorType &x) const

Public Member Functions inherited from BaseQR< VectorType >
virtual	~BaseQR ()=default

unsigned int	size () const

const LAPACKFullMatrix< Number > &	get_R () const

void	solve (Vector< Number > &x, const Vector< Number > &y, const bool transpose=false) const

boost::signals2::connection	connect_givens_slot (const std::function< void(const unsigned int i, const unsigned int j, const std::array< Number, 3 > &csr)> &slot)

Private Member Functions
void	apply_givens_rotation (const unsigned int i, const unsigned int k)

Private Attributes
VectorType	tmp

Additional Inherited Members
Protected Member Functions inherited from BaseQR< VectorType >
	BaseQR ()

void	multiply_with_cols (VectorType &y, const Vector< Number > &x) const

void	multiply_with_colsT (Vector< Number > &y, const VectorType &x) const

Protected Attributes inherited from BaseQR< VectorType >
std::vector< std::unique_ptr< VectorType > >	columns

LAPACKFullMatrix< Number >	R

unsigned int	current_size

boost::signals2::signal< void(const unsigned int i, const unsigned int j, const std::array< Number, 3 > &)>	givens_signal

Detailed Description

template<typename VectorType>
class QR< VectorType >

A class to compute and store the QR factorization of a matrix represented by a set of column vectors.

The class is design to update a given (possibly empty) QR factorization of a matrix \(A\) (constructed incrementally by providing its columns) due to the addition of a new column vector to \(A\). This is equivalent to constructing an orthonormal basis by the Gram-Schmidt procedure. The class also provides update functionality when the first column is removed.

The VectorType template argument may either be a parallel and serial vector, and only need to have basic operations such as additions, scalar product, etc. It also needs to have a copy-constructor.

See sections 6.5.2-6.5.3 on pp. 335-338 in

@Book{Golub2013,
  title     = {Matrix computations},
  publisher = {Johns Hopkins University Press},
  year      = {2013},
  author    = {Golub, Gene H and Van Loan, Charles F},
  edition   = {4},
 }

as well as

@article{Daniel1976,
  author   = {Daniel, James W and Gragg, Walter Bill and Kaufman, Linda and Stewart, Gilbert W},
  title    = {{Reorthogonalization and stable algorithms for updating the Gram-Schmidt QR factorization}},
  journal  = {Mathematics of Computation},
  year     = {1976},
  volume   = {30},
  number   = {136},
  pages    = {772--795},
}
@Article{Reichel1990,
  author     = {Reichel, L. and Gragg, W. B.},
  title      = {{Algorithm 686: FORTRAN Subroutines for Updating the QR Decomposition}},
  journal    = {ACM Trans. Math. Softw.},
  year       = {1990},
  volume     = {16},
  number     = {4},
  pages      = {369--377},
  month      = dec,
  issn       = {0098-3500},
  acmid      = {98291},
  address    = {New York, NY, USA},
  doi        = {10.1145/98267.98291},
  issue_date = {Dec. 1990},
  numpages   = {9},
  publisher  = {ACM},
  url        = {http://doi.acm.org/10.1145/98267.98291},
 }

Definition at line 238 of file qr.h.

Member Typedef Documentation

◆ Number

template<typename VectorType >

typedef VectorType::value_type QR< VectorType >::Number

Number type for R matrix.

Definition at line 244 of file qr.h.

Constructor & Destructor Documentation

◆ QR()

template<typename VectorType >

QR< VectorType >::QR ( )

Default constructor.

◆ ~QR()

template<typename VectorType >

virtual QR< VectorType >::~QR ( )

virtualdefault

Destructor.

Member Function Documentation

◆ append_column()

template<typename VectorType >

virtual bool QR< VectorType >::append_column ( const VectorType & column )

virtual

Append column to the QR factorization. Returns true if the result is successful, i.e. the columns are linearly independent. Otherwise the column is rejected and the return value is false.

Note: Currently this function always returns true.

Implements BaseQR< VectorType >.

◆ remove_column()

template<typename VectorType >

virtual void QR< VectorType >::remove_column ( const unsigned int k = 0 )

virtual

Remove first column and update QR factorization.

Starting from the given QR decomposition \(QR= A = [a_1\,\dots a_n], \quad a_i \in {\mathbb R}^m\) we aim at computing factorization of \(\tilde Q \tilde R= \tilde A = [a_2\,\dots a_n], \quad a_i \in {\mathbb R}^m\).

The standard approach is to partition \(R\) as

\[ R = \begin{bmatrix} r_{11} & w^T \\ 0 & R_{33} \end{bmatrix} \]

It then follows that

\[ Q^T \tilde A = \begin{bmatrix} 0 & w^T \\ 0 & R_{33} \end{bmatrix} \]

is upper Hessenberg where unwanted sub-diagonal elements can be zeroed by a sequence of Givens rotations.

Note that \(\tilde R^T \tilde R = \tilde A^T \tilde A\), where the RHS is included in \(A^T A = R^T R\). Therefore \(\tilde R\) can be obtained by Cholesky decomposition.

Implements BaseQR< VectorType >.

◆ multiply_with_Q()

template<typename VectorType >

virtual void QR< VectorType >::multiply_with_Q	(	VectorType &	y,
		const Vector< Number > &	x
	)		const

virtual

Set \(y = Qx\). The size of \(x\) should be consistent with the size of the R matrix.

Implements BaseQR< VectorType >.

◆ multiply_with_QT()

template<typename VectorType >

virtual void QR< VectorType >::multiply_with_QT	(	Vector< Number > &	y,
		const VectorType &	x
	)		const

virtual

Set \(y = Q^Tx\). The size of \(x\) should be consistent with the size of column vectors.

Implements BaseQR< VectorType >.

◆ multiply_with_A()

template<typename VectorType >

virtual void QR< VectorType >::multiply_with_A	(	VectorType &	y,
		const Vector< Number > &	x
	)		const

virtual

Set \(y = QRx\). The size of \(x\) should be consistent with the size of the R matrix.

Implements BaseQR< VectorType >.

◆ multiply_with_AT()

template<typename VectorType >

virtual void QR< VectorType >::multiply_with_AT	(	Vector< Number > &	y,
		const VectorType &	x
	)		const

virtual

Set \(y = R^T Q^Tx\). The size of \(x\) should be consistent with the size of column vectors.

Implements BaseQR< VectorType >.

◆ apply_givens_rotation()

template<typename VectorType >

void QR< VectorType >::apply_givens_rotation	(	const unsigned int	i,
		const unsigned int	k
	)

private

Apply givens rotation in the (i,j)-plane to Q and R so that R(k,k) is zeroed.

See Chapter 5.1.9 of Golub 2013, Matrix computations.

Member Data Documentation

◆ tmp

template<typename VectorType >

VectorType QR< VectorType >::tmp

private

Temporary vector needed to do Givens rotation of Q.

Definition at line 324 of file qr.h.

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

deal.II/lac/qr.h

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

template<typename VectorType> class QR< VectorType >

Member Typedef Documentation

◆ Number

Constructor & Destructor Documentation

◆ QR()

◆ ~QR()

Member Function Documentation

◆ append_column()

◆ remove_column()

◆ multiply_with_Q()

◆ multiply_with_QT()

◆ multiply_with_A()

◆ multiply_with_AT()

◆ apply_givens_rotation()

Member Data Documentation

◆ tmp

template<typename VectorType>
class QR< VectorType >