alfi::util::linalg Namespace Reference

Functions
template<typename Number = DefaultNumber, template< typename, typename... > class Container = DefaultContainer>
Container< Number >	lup_solve (Container< Container< Number > > &&A, Container< Number > &&B, Number epsilon=std::numeric_limits< Number >::epsilon())
	Solves a system of linear equations using LUP decomposition.
template<typename Number = DefaultNumber, template< typename, typename... > class Container = DefaultContainer>
Container< Number >	tridiag_solve_unstable (const Container< Number > &lower, Container< Number > &&diag, const Container< Number > &upper, Container< Number > &&right)
	Solves a tridiagonal system of linear equations.
template<typename Number = DefaultNumber, template< typename, typename... > class Container = DefaultContainer>
Container< Number >	tridiag_solve (Container< Number > &&lower, Container< Number > &&diag, Container< Number > &&upper, Container< Number > &&right)
	Solves a tridiagonal system of linear equations.

Function Documentation

lup_solve()

template<typename Number = DefaultNumber, template< typename, typename... > class Container = DefaultContainer>

Container< Number > alfi::util::linalg::lup_solve	(	Container< Container< Number > > &&	A,
		Container< Number > &&	B,
		Number	epsilon = std::numeric_limits<Number>::epsilon() )

Solves a system of linear equations using LUP decomposition.

This function solves the system of linear equations \(AX = B\), where \(A\) is a square matrix, by performing LUP decomposition and forward-backward substitution.
The input matrix \(A\) is decomposed into lower \(L\) and upper \(U\) triangular matrices, such that \(PA = LU\), transforming the equation into \(PLUX = B\) or \(LUX = PB\).

The solution is found in two stages:

1. The first stage solves the system \(LY = PB\) for the intermediate vector \(Y\) using forward substitution.
2. The second stage solves the system \(UX = Y\) for the final solution \(X\) using backward substitution.

If the pivot element in a given column is too small (less than the specified \(epsilon\)), the function returns an empty container, indicating that the matrix is degenerate, and prints the corresponding message to std::cerr.

The input matrix \(A\) and vector \(B\) are modified in place.

Parameters

A	the matrix (2D container of size \(n \times n\))
B	the right-hand side vector (1D container of size \(n\))
epsilon	a small threshold value to detect degeneracy (default is machine epsilon)

Returns

the solution vector or an empty container if the matrix is degenerate

tridiag_solve_unstable()

template<typename Number = DefaultNumber, template< typename, typename... > class Container = DefaultContainer>

Container< Number > alfi::util::linalg::tridiag_solve_unstable	(	const Container< Number > &	lower,
		Container< Number > &&	diag,
		const Container< Number > &	upper,
		Container< Number > &&	right )

Solves a tridiagonal system of linear equations.

This function solves a system of linear equations \(AX = B\), where \(A\) is a tridiagonal matrix. The input vectors are modified in place.

Unlike tridiag_solve, this algorithm is generally unstable.
The sufficient conditions for this algorithm to be stable are (see this article: https://stsynkov.math.ncsu.edu/book_sample_material/Sections_5.4-5.5.pdf):

• \(\abs{diag[0]} \ge \abs{upper[0]}\),
• \(\abs{diag[k]} \ge \abs{lower[k]} + \abs{upper[k]}, k = 1, 2, ..., n - 2\),
• \(\abs{diag[n-1]} \ge \abs{lower[n-1]}\),
• one of \(n\) inequalities is strict, i.e., \(>\) rather than \(\ge\).

The first element of lower and the last element of upper are ignored.

Parameters

lower	the subdiagonal elements of the tridiagonal matrix (first element is ignored)
diag	the diagonal elements of the tridiagonal matrix
upper	the superdiagonal elements of the tridiagonal matrix (last element is ignored)
right	the right-hand side vector of the system

Returns

the solution vector

tridiag_solve()

template<typename Number = DefaultNumber, template< typename, typename... > class Container = DefaultContainer>

Container< Number > alfi::util::linalg::tridiag_solve	(	Container< Number > &&	lower,
		Container< Number > &&	diag,
		Container< Number > &&	upper,
		Container< Number > &&	right )

Solves a tridiagonal system of linear equations.

This function solves a system of linear equations \(AX = B\), where \(A\) is a tridiagonal matrix. The input vectors are modified in place.

Unlike tridiag_solve_unstable, this algorithm is stable.

The first element of lower and the last element of upper are ignored.

Note

Based on the https://github.com/snsinfu/cxx-spline/blob/625d4d325cb2/include/spline.hpp#L40-L105 code from https://github.com/snsinfu, which was licensed under the BSL-1.0 (Boost Software License 1.0).

Parameters

lower	the subdiagonal elements of the tridiagonal matrix (first element is ignored)
diag	the diagonal elements of the tridiagonal matrix
upper	the superdiagonal elements of the tridiagonal matrix (last element is ignored)
right	the right-hand side vector of the system

Returns

the solution vector