#include <alpaqa/include/alpaqa/accelerators/internal/limited-memory-qr.hpp>

Detailed Description

template<Config Conf = DefaultConfig>
class alpaqa::LimitedMemoryQR< Conf >

Incremental QR factorization using modified Gram-Schmidt with reorthogonalization.

Computes A = QR while allowing efficient removal of the first column of A or adding new columns at the end of A.

Definition at line 14 of file limited-memory-qr.hpp.

Collaboration diagram for LimitedMemoryQR< Conf >:

Public Types
template<class Derived >
using	solve_ret_t = std::conditional_t< Eigen::internal::traits< Derived >::ColsAtCompileTime==1, vec, mat >

Public Member Functions
	LimitedMemoryQR ()=default

	LimitedMemoryQR (length_t n, length_t m)

length_t	n () const

length_t	m () const

length_t	size () const

length_t	history () const

template<class VecV >
void	add_column (const VecV &v)
	Add the given column to the right.

void	remove_column ()
	Remove the leftmost column.

template<class VecB , class VecX >
void	solve_col (const VecB &b, VecX &x, real_t tol=0) const
	Solve the least squares problem Ax = b.

template<class MatB , class MatX >
void	solve (const MatB &B, MatX &X, real_t tol=0) const
	Solve the least squares problem AX = B.

template<class Derived >
solve_ret_t< Derived >	solve (const Eigen::DenseBase< Derived > &B)
	Solve the least squares problem AX = B.

const mat &	get_raw_Q () const
	Get the full, raw storage for the orthogonal matrix Q.

const mat &	get_raw_R () const
	Get the full, raw storage for the upper triangular matrix R.

mat	get_full_R () const
	Get the full storage for the upper triangular matrix R but with the columns in the correct order.

mat	get_R () const
	Get the matrix R such that Q times R is the original matrix.

mat	get_Q () const
	Get the matrix Q such that Q times R is the original matrix.

void	scale_R (real_t scal)
	Multiply the matrix R by a scalar.

unsigned long	get_reorth_count () const
	Get the number of MGS reorthogonalizations.

void	clear_reorth_count ()
	Reset the number of MGS reorthogonalizations.

real_t	get_min_eig () const
	Get the minimum eigenvalue of R.

real_t	get_max_eig () const
	Get the maximum eigenvalue of R.

void	reset ()
	Reset all indices, clearing the Q and R matrices.

void	resize (length_t n, length_t m)
	Re-allocate storage for a problem with a different size.

length_t	num_columns () const
	Get the number of columns that are currently stored.

index_t	ring_head () const
	Get the head index of the circular buffer (points to the oldest element).

index_t	ring_tail () const
	Get the tail index of the circular buffer (points to one past the most recent element).

index_t	ring_next (index_t i) const
	Get the next index in the circular buffer.

index_t	ring_prev (index_t i) const
	Get the previous index in the circular buffer.

length_t	current_history () const
	Get the number of columns currently stored in the buffer.

CircularRange< index_t >	ring_iter () const
	Get iterators in the circular buffer.

ReverseCircularRange< index_t >	ring_reverse_iter () const
	Get reverse iterators in the circular buffer.

Private Member Functions
index_t	r_succ (index_t i) const
	Get the next index in the circular storage for R.

index_t	r_pred (index_t i) const
	Get the previous index in the circular storage for R.

Private Attributes
mat	Q
	Storage for orthogonal factor Q.

mat	R
	Storage for upper triangular factor R.

index_t	q_idx = 0
	Number of columns of Q being stored.

index_t	r_idx_start = 0
	Index of the first column of R.

index_t	r_idx_end = 0
	Index of the one-past-last column of R.

unsigned long	reorth_count = 0
	Number of MGS reorthogonalizations.

real_t	min_eig = +inf<config_t>
	Minimum eigenvalue of R.

real_t	max_eig = -inf<config_t>
	Maximum eigenvalue of R.

Member Typedef Documentation

◆ solve_ret_t

using solve_ret_t = std::conditional_t< Eigen::internal::traits<Derived>::ColsAtCompileTime == 1, vec, mat>

Definition at line 171 of file limited-memory-qr.hpp.

Constructor & Destructor Documentation

◆ LimitedMemoryQR() [1/2]

LimitedMemoryQR ( )

default

◆ LimitedMemoryQR() [2/2]

LimitedMemoryQR	(	length_t	n,
		length_t	m
	)

inline

Parameters

n	The size of the vectors, the number of rows of A.
m	The maximum number of columns of A.

The maximum dimensions of Q are n×m and the maximum dimensions of R are m×m.

Definition at line 26 of file limited-memory-qr.hpp.

Member Function Documentation

◆ n()

length_t n ( ) const

inline

Definition at line 28 of file limited-memory-qr.hpp.

Here is the caller graph for this function:

◆ m()

length_t m ( ) const

inline

Definition at line 29 of file limited-memory-qr.hpp.

Here is the caller graph for this function:

◆ size()

length_t size ( ) const

inline

Definition at line 30 of file limited-memory-qr.hpp.

Here is the call graph for this function:

◆ history()

length_t history ( ) const

inline

Definition at line 31 of file limited-memory-qr.hpp.

Here is the call graph for this function:

◆ add_column()

void add_column ( const VecV & v )

inline

Add the given column to the right.

Definition at line 35 of file limited-memory-qr.hpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ remove_column()

void remove_column ( )

inline

Remove the leftmost column.

Definition at line 81 of file limited-memory-qr.hpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ solve_col()

void solve_col	(	const VecB &	b,
		VecX &	x,
		real_t	tol = `0`
	)		const

inline

Solve the least squares problem Ax = b.

Do not divide by elements that are smaller in absolute value than tol.

Definition at line 125 of file limited-memory-qr.hpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ solve() [1/2]

void solve	(	const MatB &	B,
		MatX &	X,
		real_t	tol = `0`
	)		const

inline

Solve the least squares problem AX = B.

Do not divide by elements that are smaller in absolute value than tol.

Definition at line 158 of file limited-memory-qr.hpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ solve() [2/2]

solve_ret_t< Derived > solve ( const Eigen::DenseBase< Derived > & B )

inline

Solve the least squares problem AX = B.

Definition at line 176 of file limited-memory-qr.hpp.

Here is the call graph for this function:

◆ get_raw_Q()

const mat & get_raw_Q ( ) const

inline

Get the full, raw storage for the orthogonal matrix Q.

Definition at line 183 of file limited-memory-qr.hpp.

◆ get_raw_R()

const mat & get_raw_R ( ) const

inline

Get the full, raw storage for the upper triangular matrix R.

The columns of this matrix are permuted because it's stored as a circular buffer for efficiently appending columns to the end and popping columns from the front.

Definition at line 188 of file limited-memory-qr.hpp.

◆ get_full_R()

mat get_full_R ( ) const

inline

Get the full storage for the upper triangular matrix R but with the columns in the correct order.

Note: Meant for tests only, creates a permuted copy.

Definition at line 193 of file limited-memory-qr.hpp.

Here is the caller graph for this function:

◆ get_R()

mat get_R ( ) const

inline

Get the matrix R such that Q times R is the original matrix.

Note: Meant for tests only, creates a permuted copy.

Definition at line 207 of file limited-memory-qr.hpp.

Here is the call graph for this function:

◆ get_Q()

mat get_Q ( ) const

inline

Get the matrix Q such that Q times R is the original matrix.

Note: Meant for tests only, creates a copy.

Definition at line 214 of file limited-memory-qr.hpp.

Here is the call graph for this function:

◆ scale_R()

void scale_R ( real_t scal )

inline

Multiply the matrix R by a scalar.

Definition at line 217 of file limited-memory-qr.hpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ get_reorth_count()

unsigned long get_reorth_count ( ) const

inline

Get the number of MGS reorthogonalizations.

Definition at line 225 of file limited-memory-qr.hpp.

◆ clear_reorth_count()

void clear_reorth_count ( )

inline

Reset the number of MGS reorthogonalizations.

Definition at line 227 of file limited-memory-qr.hpp.

◆ get_min_eig()

real_t get_min_eig ( ) const

inline

Get the minimum eigenvalue of R.

Definition at line 230 of file limited-memory-qr.hpp.

◆ get_max_eig()

real_t get_max_eig ( ) const

inline

Get the maximum eigenvalue of R.

Definition at line 232 of file limited-memory-qr.hpp.

Here is the caller graph for this function:

◆ reset()

void reset ( )

inline

Reset all indices, clearing the Q and R matrices.

Definition at line 235 of file limited-memory-qr.hpp.

Here is the caller graph for this function:

◆ resize()

void resize	(	length_t	n,
		length_t	m
	)

inline

Re-allocate storage for a problem with a different size.

Causes a reset.

Definition at line 246 of file limited-memory-qr.hpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ num_columns()

length_t num_columns ( ) const

inline

Get the number of columns that are currently stored.

Definition at line 253 of file limited-memory-qr.hpp.

Here is the caller graph for this function:

◆ ring_head()

index_t ring_head ( ) const

inline

Get the head index of the circular buffer (points to the oldest element).

Definition at line 256 of file limited-memory-qr.hpp.

◆ ring_tail()

index_t ring_tail ( ) const

inline

Get the tail index of the circular buffer (points to one past the most recent element).

Definition at line 259 of file limited-memory-qr.hpp.

Here is the caller graph for this function:

◆ ring_next()

index_t ring_next ( index_t i ) const

inline

Get the next index in the circular buffer.

Definition at line 261 of file limited-memory-qr.hpp.

Here is the call graph for this function:

◆ ring_prev()

index_t ring_prev ( index_t i ) const

inline

Get the previous index in the circular buffer.

Definition at line 263 of file limited-memory-qr.hpp.

Here is the call graph for this function:

◆ current_history()

length_t current_history ( ) const

inline

Get the number of columns currently stored in the buffer.

Definition at line 265 of file limited-memory-qr.hpp.

Here is the caller graph for this function:

◆ ring_iter()

CircularRange< index_t > ring_iter ( ) const

inline

Get iterators in the circular buffer.

Definition at line 268 of file limited-memory-qr.hpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ ring_reverse_iter()

ReverseCircularRange< index_t > ring_reverse_iter ( ) const

inline

Get reverse iterators in the circular buffer.

Definition at line 272 of file limited-memory-qr.hpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ r_succ()

index_t r_succ ( index_t i ) const

inlineprivate

Get the next index in the circular storage for R.

Definition at line 290 of file limited-memory-qr.hpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ r_pred()

index_t r_pred ( index_t i ) const

inlineprivate

Get the previous index in the circular storage for R.

Definition at line 292 of file limited-memory-qr.hpp.

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

◆ Q

mat Q

private

Storage for orthogonal factor Q.

Definition at line 277 of file limited-memory-qr.hpp.

◆ R

mat R

private

Storage for upper triangular factor R.

Definition at line 278 of file limited-memory-qr.hpp.

◆ q_idx

index_t q_idx = 0

private

Number of columns of Q being stored.

Definition at line 280 of file limited-memory-qr.hpp.

◆ r_idx_start

index_t r_idx_start = 0

private

Index of the first column of R.

Definition at line 281 of file limited-memory-qr.hpp.

◆ r_idx_end

index_t r_idx_end = 0

private

Index of the one-past-last column of R.

Definition at line 282 of file limited-memory-qr.hpp.

◆ reorth_count

unsigned long reorth_count = 0

private

Number of MGS reorthogonalizations.

Definition at line 284 of file limited-memory-qr.hpp.

◆ min_eig

real_t min_eig = +inf<config_t>

private

Minimum eigenvalue of R.

Definition at line 286 of file limited-memory-qr.hpp.

◆ max_eig

real_t max_eig = -inf<config_t>

private

Maximum eigenvalue of R.

Definition at line 287 of file limited-memory-qr.hpp.

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

limited-memory-qr.hpp

Detailed Description

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Member Typedef Documentation

◆ solve_ret_t

Constructor & Destructor Documentation

◆ LimitedMemoryQR() [1/2]

◆ LimitedMemoryQR() [2/2]

Member Function Documentation

◆ n()

◆ m()

◆ size()

◆ history()

◆ add_column()

◆ remove_column()

◆ solve_col()

◆ solve() [1/2]

◆ solve() [2/2]

◆ get_raw_Q()

◆ get_raw_R()

◆ get_full_R()

◆ get_R()

◆ get_Q()

◆ scale_R()

◆ get_reorth_count()

◆ clear_reorth_count()

◆ get_min_eig()

◆ get_max_eig()

◆ reset()

◆ resize()

◆ num_columns()

◆ ring_head()

◆ ring_tail()

◆ ring_next()

◆ ring_prev()

◆ current_history()

◆ ring_iter()

◆ ring_reverse_iter()

◆ r_succ()

◆ r_pred()

Member Data Documentation

◆ Q

◆ R

◆ q_idx

◆ r_idx_start

◆ r_idx_end

◆ reorth_count

◆ min_eig

◆ max_eig