thomas.hpp File Reference

Thomas algorithm – direct O(n) tridiagonal solver. More...

#include "core/types.hpp"
#include "core/vector.hpp"
#include "core/policy.hpp"

Go to the source code of this file.

Namespaces
namespace	num

Functions
void	num::thomas (const Vector &a, const Vector &b, const Vector &c, const Vector &d, Vector &x, Backend backend=Backend::seq)
	Thomas algorithm (LU for tridiagonal systems), O(n).

Detailed Description

Thomas algorithm – direct O(n) tridiagonal solver.

Solves the tridiagonal system:

[ b[0] c[0] ] [ x[0] ] [ d[0] ] [ a[0] b[1] c[1] ] [ x[1] ] = [ d[1] ] [ a[1] b[2] c[2] ] [ x[2] ] [ d[2] ] [ ... ... ... ] [ : ] [ : ] [ a[n-2] b[n-1] ] [ x[n-1] ] [ d[n-1] ]

Algorithm: LU factorisation of the tridiagonal structure, O(n) time and O(n) extra space. Numerically stable for strictly diagonally dominant or symmetric positive definite tridiagonals; may fail for singular pivots.

Definition in file thomas.hpp.