Runtime-size dense LU factorization with partial pivoting shared by a group of threads, solving one n x n system per group. More...

#include <solver_dynamic.hpp>

Static Public Member Functions
TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr int	threads_per_system (const int n) noexcept
	Threads solving one system of dimension n: ceil(n / rows_per_thread).

TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr int	workspace_size (const int n) noexcept
	Elements of the workspace shared by the threads of a group: the two elements of the deduced CPU barrier, then 3 * n under logical row interchanges, 2 * n + 2 * threads_per_system(n) + 5 under physical ones.

TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr void	init_piv (const int tx, const int threads, int(&rpiv)[rows_per_thread]) noexcept
	Initial pivot entries: no row has moved yet, so the entry of each slot is the index of its row, phantom rows included (theirs stays at or above n). Under logical row interchanges the entry is the position of the row of the slot, under physical ones the original index of the row held by the slot: both start there.

TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr void	load_piv (const int n, const int tx, const int threads, const int *TDLS_RESTRICT piv, const int piv_stride, int(&rpiv)[rows_per_thread]) noexcept
	Load the pivot entries recorded by factorize.

TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr void	store_piv (const int n, const int tx, const int threads, int *TDLS_RESTRICT piv, const int piv_stride, const int(&rpiv)[rows_per_thread]) noexcept
	Record the pivot entries of the calling thread.

TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr void	load_rhs (const int n, const int tx, const int threads, const T *TDLS_RESTRICT b, const int rhs_stride, T(&rB)[rows_per_thread]) noexcept
	Load the right-hand-side entries of the rows of the calling thread.

TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr void	store_solution (const int n, const int tx, const int threads, T *TDLS_RESTRICT x, const int rhs_stride, const T(&rB)[rows_per_thread]) noexcept
	Store the solution entries held by the calling thread.

TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr bool	keeps_pivot (const T in_place, const T column_max) noexcept
	Relative threshold of the pivot choice: whether the row in place keeps the pivot (see CooperativeLUppConfig::relative_pivot_threshold).

template<bool fuse_rhs, typename Sync >
TDLS_EXEC_CHECK_DISABLE TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr void	logical_elimination_step (const int n, const int i, const int tx, const int threads, T TDLS_RESTRICT A, const int A_stride, T(&rB)[rows_per_thread], int(&rowid)[rows_per_thread], T sB, T sx, T dsx, int &linfo, Sync &sync) noexcept(detail::nothrow_sync< Sync >)
	One column of the factorization under logical row interchanges. With fuse_rhs, the forward pass of the right-hand side as in the compile-time solver: L y = P b under the column-major layout, U^T z = b under the row-major one.

TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr void	save_row (const int n, const T TDLS_RESTRICT A, const int A_stride, const int r, T record) noexcept
	Copy a row of the matrix to the first n entries of an exchange record of the workspace.

TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr void	load_row (const int n, T TDLS_RESTRICT A, const int A_stride, const int r, const T record) noexcept
	Copy the first n entries of an exchange record of the workspace to a row of the matrix, the converse of save_row.

template<bool fuse_rhs, typename Sync >
TDLS_EXEC_CHECK_DISABLE TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr void	physical_elimination_step (const int n, const int i, const int tx, const int threads, T TDLS_RESTRICT A, const int A_stride, T(&rB)[rows_per_thread], int(&origin)[rows_per_thread], T work, int &linfo, Sync &sync) noexcept(detail::nothrow_sync< Sync >)
	One column of the factorization under physical row interchanges, as in the compile-time solver: the row at position k is row k of the matrix, held by slot k / threads of thread k % threads.

template<bool fuse_rhs, typename Sync >
TDLS_EXEC_CHECK_DISABLE TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr int	eliminate (const int n, const int tx, const int threads, T TDLS_RESTRICT A, const int A_stride, T(&rB)[rows_per_thread], int(&rpiv)[rows_per_thread], T work, Sync &sync) noexcept(detail::nothrow_sync< Sync >)
	Factorization of the rows of the group, in place.

template<typename Sync >
TDLS_EXEC_CHECK_DISABLE TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr void	forward_pass (const int n, const int tx, const int threads, const T TDLS_RESTRICT A, const int A_stride, T(&rB)[rows_per_thread], const int(&rowid)[rows_per_thread], T work, Sync &sync) noexcept(detail::nothrow_sync< Sync >)
	Forward pass: L y = P b on the given row positions, y overwriting the right-hand-side entries of the thread.

template<typename Sync >
TDLS_EXEC_CHECK_DISABLE TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr void	backward_pass (const int n, const int tx, const int threads, const T TDLS_RESTRICT A, const int A_stride, T(&rB)[rows_per_thread], const int(&rowid)[rows_per_thread], T work, Sync &sync) noexcept(detail::nothrow_sync< Sync >)
	Backward pass: U x = y on the given row positions, the forward-reduced right-hand side y in the entries of the thread on entry, its solution entries on exit.

TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr int	row_at (const T *rows, const int k) noexcept
	Index of the row of S at position k: read from the published positions under logical row interchanges, k itself under physical ones. The indices travel as values of T, exact since the offset bounds keep n far below the mantissa range of every scalar type.

template<bool backward_only, typename Sync >
TDLS_EXEC_CHECK_DISABLE TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr void	transposed_passes (const int n, const int tx, const int threads, const T TDLS_RESTRICT A, const int A_stride, T(&rB)[rows_per_thread], const T rows, T *buf, Sync &sync) noexcept(detail::nothrow_sync< Sync >)
	Forward then backward pass of S^T x = b: b in the entries of the thread on entry, w at the entries of the same positions on exit.

template<bool backward_only, typename Sync >
TDLS_EXEC_CHECK_DISABLE TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr void	substitution (const int n, const int tx, const int threads, const T TDLS_RESTRICT A, const int A_stride, T(&rB)[rows_per_thread], const int(&rpiv)[rows_per_thread], T work, Sync &sync) noexcept(detail::nothrow_sync< Sync >)
	Substitution from the factored rows, the right-hand side in the entries of the thread on entry, the solution entries tx + K * threads on exit: L y = P b then U x = y under the column-major layout, U^T z = b, L^T w = z and x = P^T w under the row-major one.

TDLS_EXEC_CHECK_DISABLE TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr auto	make_sync (const int n, T *work) noexcept
	The barrier deduced for the group of the calling thread.

template<typename Sync = tdls::AutoSync>
TDLS_EXEC_CHECK_DISABLE TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr bool	factorize (const int n, const int tx, T TDLS_RESTRICT A, const int A_stride, int TDLS_RESTRICT piv, const int piv_stride, T *work, Sync &&sync=Sync{}) noexcept(detail::nothrow_sync< Sync >)
	In-place LU factorization with partial pivoting.

template<typename Sync = tdls::AutoSync>
TDLS_EXEC_CHECK_DISABLE TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr void	substitute (const int n, const int tx, const T TDLS_RESTRICT A, const int A_stride, const int TDLS_RESTRICT piv, const int piv_stride, const T TDLS_RESTRICT b, T TDLS_RESTRICT x, const int rhs_stride, T *work, Sync &&sync=Sync{}) noexcept(detail::nothrow_sync< Sync >)
	Solve from a factorization produced by factorize (b and x distinct).

template<typename Sync = tdls::AutoSync>
TDLS_EXEC_CHECK_DISABLE TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr void	substitute_canonical (const int n, const int tx, const T TDLS_RESTRICT A, const int A_stride, const int TDLS_RESTRICT piv, const int piv_stride, const int col, T TDLS_RESTRICT x, const int rhs_stride, T work, Sync &&sync=Sync{}) noexcept(detail::nothrow_sync< Sync >)
	Solve with b = e_col generated on the fly: the consistent-tangent-operator path.

template<typename Sync = tdls::AutoSync>
TDLS_EXEC_CHECK_DISABLE TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr void	substitute_inplace (const int n, const int tx, const T TDLS_RESTRICT A, const int A_stride, const int TDLS_RESTRICT piv, const int piv_stride, T TDLS_RESTRICT x, const int rhs_stride, T work, Sync &&sync=Sync{}) noexcept(detail::nothrow_sync< Sync >)
	Solve in place from a factorization produced by factorize: x holds the right-hand side on entry and the solution on exit.

template<typename Sync = tdls::AutoSync>
TDLS_EXEC_CHECK_DISABLE TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr bool	solve (const int n, const int tx, T TDLS_RESTRICT A, const int A_stride, int TDLS_RESTRICT piv, const int piv_stride, const T TDLS_RESTRICT b, T TDLS_RESTRICT x, const int rhs_stride, T *work, Sync &&sync=Sync{}) noexcept(detail::nothrow_sync< Sync >)
	factorize + substitute in one call, the pivot entries staying with the threads in between.

template<typename Sync = tdls::AutoSync>
TDLS_EXEC_CHECK_DISABLE TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr bool	solve_inplace (const int n, const int tx, T TDLS_RESTRICT A, const int A_stride, int TDLS_RESTRICT piv, const int piv_stride, T TDLS_RESTRICT y, const int rhs_stride, T work, Sync &&sync=Sync{}) noexcept(detail::nothrow_sync< Sync >)
	Factorization with the forward substitution folded in: the original MAGMA kernel.

Static Public Attributes
static constexpr int	rows_per_thread = Config.rows_per_thread < 1 ? 1 : Config.rows_per_thread
	Row slots of each thread: Config.rows_per_thread. When n is smaller, one thread solves the system and its slots beyond n hold phantom rows. A value below 1, rejected above, is clamped to 1 so that the rejection stays the only diagnostic.

static constexpr T	relative_pivot_threshold = Config.relative_pivot_threshold
	Relative threshold of the pivot choice, read once from the configuration (see CooperativeLUppConfig::relative_pivot_threshold).

static constexpr T	singular_floor = Config.singular_floor
	Singularity floor, read once from the configuration (see CooperativeLUppConfig::singular_floor).

static constexpr bool	transposed = Config.layout == MatrixLayout::RowMajor
	Whether the solve uses the transpose of the factored matrix, as in the compile-time solver: S = A and S x = b under the column-major layout, S = A^T and S^T x = b under the row-major one.

Detailed Description

template<typename T, CooperativeLUppConfig< T > Config = CooperativeLUppConfig<T>{}>
struct tdls::CooperativeLUppSolverDynamic< T, Config >

Runtime-size dense LU factorization with partial pivoting shared by a group of threads, solving one n x n system per group.

All entry points are static, host- and device-callable, called by every thread of the group with the dimension n and its rank tx, and take raw pointers pre-offset by the caller with one runtime stride per array. Entry points:

factorize: S := P*L*U in place, pivot entries out (S = A column-major, A^T row-major)
substitute: x := A^-1 b from a factorization (b and x distinct)
substitute_canonical: idem with b = e_col (tangent-operator columns)
substitute_inplace: idem with b == x
solve: factorize + substitute
solve_inplace: factorize with the forward pass folded in, the original MAGMA kernel

The factored matrix and the pivot array follow the format of CooperativeLUppSolverStatic under the same configuration: a factorization produced here must be consumed by the substitution routines of this family.

Template Parameters

T	scalar type (float, double or long double)
Config	compile-time knobs, passed as a constexpr value: rows per thread, row interchanges, relative pivot threshold, singularity floor, matrix layout; see CooperativeLUppConfig (unroll_loops is ignored by this variant)

Member Function Documentation

◆ backward_pass()

template<typename T , CooperativeLUppConfig< T > Config = CooperativeLUppConfig<T>{}>

template<typename Sync >

TDLS_EXEC_CHECK_DISABLE TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr void tdls::CooperativeLUppSolverDynamic< T, Config >::backward_pass	(	const int	n,
		const int	tx,
		const int	threads,
		const T *TDLS_RESTRICT	A,
		const int	A_stride,
		T(&)	rB[rows_per_thread],
		const int(&)	rowid[rows_per_thread],
		T *	work,
		Sync &	sync )

inlinestaticconstexprnoexcept

Backward pass: U x = y on the given row positions, the forward-reduced right-hand side y in the entries of the thread on entry, its solution entries on exit.

Every thread computes the same x_i, and the owner of entry i keeps it in its own entries instead of writing it to the workspace that every thread reads in the same barrier interval.

Template Parameters

Sync	callable type of the barrier

Parameters

[in]	n	system dimension
[in]	tx	rank of the calling thread in its group
[in]	threads	threads of the group, threads_per_system(n)
[in]	A	factored matrix (caller-pre-offset)
[in]	A_stride	element stride of A
[in,out]	rB	y entries of the rows of the thread on entry, solution entries tx + K * threads on exit
[in]	rowid	position of each row of the thread in the pivoted order
[in]	work	workspace of the group
[in]	sync	barrier of the group

◆ eliminate()

template<typename T , CooperativeLUppConfig< T > Config = CooperativeLUppConfig<T>{}>

template<bool fuse_rhs, typename Sync >

TDLS_EXEC_CHECK_DISABLE TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr int tdls::CooperativeLUppSolverDynamic< T, Config >::eliminate	(	const int	n,
		const int	tx,
		const int	threads,
		T *TDLS_RESTRICT	A,
		const int	A_stride,
		T(&)	rB[rows_per_thread],
		int(&)	rpiv[rows_per_thread],
		T *	work,
		Sync &	sync )

inlinestaticnodiscardconstexprnoexcept

Factorization of the rows of the group, in place.

Template Parameters

fuse_rhs	apply the forward pass to the right-hand side as well (solve_inplace)
Sync	callable type of the barrier

Parameters

[in]	n	system dimension
[in]	tx	rank of the calling thread in its group
[in]	threads	threads of the group, threads_per_system(n)
[in,out]	A	matrix (caller-pre-offset)
[in]	A_stride	element stride of A
[in,out]	rB	right-hand-side entries (fuse_rhs only)
[in,out]	rpiv	pivot entry of each slot of the thread, initialized by init_piv
[in]	work	workspace of the group
[in]	sync	barrier of the group

Returns: 0, or 1 + the first column whose best pivot fell below singular_floor (MAGMA's linfo)

◆ factorize()

template<typename T , CooperativeLUppConfig< T > Config = CooperativeLUppConfig<T>{}>

template<typename Sync = tdls::AutoSync>

TDLS_EXEC_CHECK_DISABLE TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr bool tdls::CooperativeLUppSolverDynamic< T, Config >::factorize	(	const int	n,
		const int	tx,
		T *TDLS_RESTRICT	A,
		const int	A_stride,
		int *TDLS_RESTRICT	piv,
		const int	piv_stride,
		T *	work,
		Sync &&	sync = Sync{} )

inlinestaticnodiscardconstexprnoexcept

In-place LU factorization with partial pivoting.

Template Parameters

Sync	callable type of the barrier

Parameters

[in]	n	system dimension
[in]	tx	rank of the calling thread in its group
[in,out]	A	matrix, pre-offset by the caller; its factorization on exit
[in]	A_stride	element stride of A
[out]	piv	pivot entries (always caller-provided)
[in]	piv_stride	element stride of piv
[in]	work	workspace of workspace_size(n) elements, shared by the group
[in]	sync	barrier of the group, deduced by default (see tdls::AutoSync)

Returns: false on a singular matrix (factorization unspecified).

◆ forward_pass()

template<typename T , CooperativeLUppConfig< T > Config = CooperativeLUppConfig<T>{}>

template<typename Sync >

TDLS_EXEC_CHECK_DISABLE TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr void tdls::CooperativeLUppSolverDynamic< T, Config >::forward_pass	(	const int	n,
		const int	tx,
		const int	threads,
		const T *TDLS_RESTRICT	A,
		const int	A_stride,
		T(&)	rB[rows_per_thread],
		const int(&)	rowid[rows_per_thread],
		T *	work,
		Sync &	sync )

inlinestaticconstexprnoexcept

Forward pass: L y = P b on the given row positions, y overwriting the right-hand-side entries of the thread.

Template Parameters

Sync	callable type of the barrier

Parameters

[in]	n	system dimension
[in]	tx	rank of the calling thread in its group
[in]	threads	threads of the group, threads_per_system(n)
[in]	A	factored matrix (caller-pre-offset)
[in]	A_stride	element stride of A
[in,out]	rB	right-hand-side entries of the thread
[in]	rowid	position of each row of the thread in the pivoted order
[in]	work	workspace of the group
[in]	sync	barrier of the group

◆ init_piv()

template<typename T , CooperativeLUppConfig< T > Config = CooperativeLUppConfig<T>{}>

TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr void tdls::CooperativeLUppSolverDynamic< T, Config >::init_piv	(	const int	tx,
		const int	threads,
		int(&)	rpiv[rows_per_thread] )

inlinestaticconstexprnoexcept

Initial pivot entries: no row has moved yet, so the entry of each slot is the index of its row, phantom rows included (theirs stays at or above n). Under logical row interchanges the entry is the position of the row of the slot, under physical ones the original index of the row held by the slot: both start there.

Parameters

[in]	tx	rank of the calling thread in its group
[in]	threads	threads of the group, threads_per_system(n)
[out]	rpiv	pivot entry of each slot of the thread

◆ keeps_pivot()

template<typename T , CooperativeLUppConfig< T > Config = CooperativeLUppConfig<T>{}>

TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr bool tdls::CooperativeLUppSolverDynamic< T, Config >::keeps_pivot	(	const T	in_place,
		const T	column_max )

inlinestaticconstexprnoexcept

Relative threshold of the pivot choice: whether the row in place keeps the pivot (see CooperativeLUppConfig::relative_pivot_threshold).

Parameters

[in]	in_place	magnitude of the row in place in the column
[in]	column_max	largest magnitude of the column

Returns: true when the row in place keeps the pivot

◆ load_piv()

template<typename T , CooperativeLUppConfig< T > Config = CooperativeLUppConfig<T>{}>

TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr void tdls::CooperativeLUppSolverDynamic< T, Config >::load_piv	(	const int	n,
		const int	tx,
		const int	threads,
		const int *TDLS_RESTRICT	piv,
		const int	piv_stride,
		int(&)	rpiv[rows_per_thread] )

inlinestaticconstexprnoexcept

Load the pivot entries recorded by factorize.

Parameters

[in]	n	system dimension
[in]	tx	rank of the calling thread in its group
[in]	threads	threads of the group, threads_per_system(n)
[in]	piv	pivot entries (caller-pre-offset)
[in]	piv_stride	element stride of piv
[out]	rpiv	pivot entry of each slot of the thread

◆ load_rhs()

template<typename T , CooperativeLUppConfig< T > Config = CooperativeLUppConfig<T>{}>

TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr void tdls::CooperativeLUppSolverDynamic< T, Config >::load_rhs	(	const int	n,
		const int	tx,
		const int	threads,
		const T *TDLS_RESTRICT	b,
		const int	rhs_stride,
		T(&)	rB[rows_per_thread] )

inlinestaticconstexprnoexcept

Load the right-hand-side entries of the rows of the calling thread.

Parameters

[in]	n	system dimension
[in]	tx	rank of the calling thread in its group
[in]	threads	threads of the group, threads_per_system(n)
[in]	b	right-hand side (caller-pre-offset)
[in]	rhs_stride	element stride of b
[out]	rB	right-hand-side entries of the thread

◆ load_row()

template<typename T , CooperativeLUppConfig< T > Config = CooperativeLUppConfig<T>{}>

TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr void tdls::CooperativeLUppSolverDynamic< T, Config >::load_row	(	const int	n,
		T *TDLS_RESTRICT	A,
		const int	A_stride,
		const int	r,
		const T *	record )

inlinestaticconstexprnoexcept

Copy the first n entries of an exchange record of the workspace to a row of the matrix, the converse of save_row.

Parameters

[in]	n	system dimension
[in,out]	A	matrix (caller-pre-offset)
[in]	A_stride	element stride of A
[in]	r	row of the matrix
[in]	record	exchange record

◆ logical_elimination_step()

template<typename T , CooperativeLUppConfig< T > Config = CooperativeLUppConfig<T>{}>

template<bool fuse_rhs, typename Sync >

TDLS_EXEC_CHECK_DISABLE TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr void tdls::CooperativeLUppSolverDynamic< T, Config >::logical_elimination_step	(	const int	n,
		const int	i,
		const int	tx,
		const int	threads,
		T *TDLS_RESTRICT	A,
		const int	A_stride,
		T(&)	rB[rows_per_thread],
		int(&)	rowid[rows_per_thread],
		T *	sB,
		T *	sx,
		T *	dsx,
		int &	linfo,
		Sync &	sync )

inlinestaticconstexprnoexcept

One column of the factorization under logical row interchanges. With fuse_rhs, the forward pass of the right-hand side as in the compile-time solver: L y = P b under the column-major layout, U^T z = b under the row-major one.

Template Parameters

fuse_rhs	apply the forward pass to the right-hand side as well (solve_inplace)
Sync	callable type of the barrier

Parameters

[in]	n	system dimension
[in]	i	column of this step
[in]	tx	rank of the calling thread in its group
[in]	threads	threads of the group, threads_per_system(n)
[in,out]	A	matrix (caller-pre-offset)
[in]	A_stride	element stride of A
[in,out]	rB	right-hand-side entries (fuse_rhs only)
[in,out]	rowid	position of each row of the thread in the pivoted order
[in]	sB	workspace: broadcast slot of the right-hand-side entry of the step (fuse_rhs only)
[in]	sx	workspace: pivot row
[in]	dsx	workspace: magnitudes of the column
[in,out]	linfo	0, or 1 + the first column whose best pivot fell below singular_floor
[in]	sync	barrier of the group

◆ make_sync()

template<typename T , CooperativeLUppConfig< T > Config = CooperativeLUppConfig<T>{}>

TDLS_EXEC_CHECK_DISABLE TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr auto tdls::CooperativeLUppSolverDynamic< T, Config >::make_sync	(	const int	n,
		T *	work )

inlinestaticconstexprnoexcept

The barrier deduced for the group of the calling thread.

The entry points deduce it on every call when no barrier is passed. A caller that also needs the barrier for its own exchanges between the threads of the group builds it once with this function, calls it at will, and passes it to the entry points, which then use it as is. On GPU, every thread of the group must call this function together, as the entry points (see tdls::AutoSync).

Parameters

[in]	n	system dimension
[in]	work	workspace of the group

Returns: the deduced barrier, which does nothing for one thread per system

◆ physical_elimination_step()

template<typename T , CooperativeLUppConfig< T > Config = CooperativeLUppConfig<T>{}>

template<bool fuse_rhs, typename Sync >

TDLS_EXEC_CHECK_DISABLE TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr void tdls::CooperativeLUppSolverDynamic< T, Config >::physical_elimination_step	(	const int	n,
		const int	i,
		const int	tx,
		const int	threads,
		T *TDLS_RESTRICT	A,
		const int	A_stride,
		T(&)	rB[rows_per_thread],
		int(&)	origin[rows_per_thread],
		T *	work,
		int &	linfo,
		Sync &	sync )

inlinestaticconstexprnoexcept

One column of the factorization under physical row interchanges, as in the compile-time solver: the row at position k is row k of the matrix, held by slot k / threads of thread k % threads.

Template Parameters

fuse_rhs	apply the elimination to the right-hand side as well (the forward pass of solve_inplace)
Sync	callable type of the barrier

Parameters

[in]	n	system dimension
[in]	i	column of this step
[in]	tx	rank of the calling thread in its group
[in]	threads	threads of the group, threads_per_system(n)
[in,out]	A	matrix (caller-pre-offset)
[in]	A_stride	element stride of A
[in,out]	rB	right-hand-side entries (fuse_rhs only)
[in,out]	origin	original index of the row held by each slot
[in]	work	workspace of the group
[in,out]	linfo	0, or 1 + the first column whose best pivot fell below singular_floor
[in]	sync	barrier of the group

◆ row_at()

template<typename T , CooperativeLUppConfig< T > Config = CooperativeLUppConfig<T>{}>

TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr int tdls::CooperativeLUppSolverDynamic< T, Config >::row_at	(	const T *	rows,
		const int	k )

inlinestaticconstexprnoexcept

Index of the row of S at position k: read from the published positions under logical row interchanges, k itself under physical ones. The indices travel as values of T, exact since the offset bounds keep n far below the mantissa range of every scalar type.

Parameters

[in]	rows	row of S at each position (logical row interchanges)
[in]	k	position

Returns: the row of S at position k

◆ save_row()

template<typename T , CooperativeLUppConfig< T > Config = CooperativeLUppConfig<T>{}>

TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr void tdls::CooperativeLUppSolverDynamic< T, Config >::save_row	(	const int	n,
		const T *TDLS_RESTRICT	A,
		const int	A_stride,
		const int	r,
		T *	record )

inlinestaticconstexprnoexcept

Copy a row of the matrix to the first n entries of an exchange record of the workspace.

Parameters

[in]	n	system dimension
[in]	A	matrix (caller-pre-offset)
[in]	A_stride	element stride of A
[in]	r	row of the matrix
[out]	record	exchange record

◆ solve()

template<typename T , CooperativeLUppConfig< T > Config = CooperativeLUppConfig<T>{}>

template<typename Sync = tdls::AutoSync>

TDLS_EXEC_CHECK_DISABLE TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr bool tdls::CooperativeLUppSolverDynamic< T, Config >::solve	(	const int	n,
		const int	tx,
		T *TDLS_RESTRICT	A,
		const int	A_stride,
		int *TDLS_RESTRICT	piv,
		const int	piv_stride,
		const T *TDLS_RESTRICT	b,
		T *TDLS_RESTRICT	x,
		const int	rhs_stride,
		T *	work,
		Sync &&	sync = Sync{} )

inlinestaticnodiscardconstexprnoexcept

factorize + substitute in one call, the pivot entries staying with the threads in between.

The barrier sequence does not depend on the verdict: a singular matrix is substituted as well, and x is then unspecified.

Template Parameters

Sync	callable type of the barrier

Parameters

[in]	n	system dimension
[in]	tx	rank of the calling thread in its group
[in,out]	A	on entry the matrix, pre-offset by the caller; on exit its factorization (usable for further substitute* calls)
[in]	A_stride	element stride of A
[out]	piv	pivot entries (always caller-provided)
[in]	piv_stride	element stride of piv
[in]	b	right-hand side, in original order
[out]	x	solution
[in]	rhs_stride	element stride of b and x
[in]	work	workspace of workspace_size(n) elements, shared by the group
[in]	sync	barrier of the group, deduced by default (see tdls::AutoSync)

Returns: false on a singular matrix (x unspecified).

◆ solve_inplace()

template<typename T , CooperativeLUppConfig< T > Config = CooperativeLUppConfig<T>{}>

template<typename Sync = tdls::AutoSync>

TDLS_EXEC_CHECK_DISABLE TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr bool tdls::CooperativeLUppSolverDynamic< T, Config >::solve_inplace	(	const int	n,
		const int	tx,
		T *TDLS_RESTRICT	A,
		const int	A_stride,
		int *TDLS_RESTRICT	piv,
		const int	piv_stride,
		T *TDLS_RESTRICT	y,
		const int	rhs_stride,
		T *	work,
		Sync &&	sync = Sync{} )

inlinestaticnodiscardconstexprnoexcept

Factorization with the forward substitution folded in: the original MAGMA kernel.

y holds the unpermuted right-hand side on entry and the solution on exit. The result is bitwise-identical to factorize + substitute_inplace. The barrier sequence does not depend on the verdict: a singular matrix is substituted as well, and y is then unspecified.

Template Parameters

Sync	callable type of the barrier

Parameters

[in]	n	system dimension
[in]	tx	rank of the calling thread in its group
[in,out]	A	on entry the matrix, pre-offset by the caller; on exit its factorization
[in]	A_stride	element stride of A
[out]	piv	pivot entries (always caller-provided)
[in]	piv_stride	element stride of piv
[in,out]	y	right-hand side on entry, solution on exit
[in]	rhs_stride	element stride of y
[in]	work	workspace of workspace_size(n) elements, shared by the group
[in]	sync	barrier of the group, deduced by default (see tdls::AutoSync)

Returns: false on a singular matrix (y unspecified).

◆ store_piv()

template<typename T , CooperativeLUppConfig< T > Config = CooperativeLUppConfig<T>{}>

TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr void tdls::CooperativeLUppSolverDynamic< T, Config >::store_piv	(	const int	n,
		const int	tx,
		const int	threads,
		int *TDLS_RESTRICT	piv,
		const int	piv_stride,
		const int(&)	rpiv[rows_per_thread] )

inlinestaticconstexprnoexcept

Record the pivot entries of the calling thread.

Parameters

[in]	n	system dimension
[in]	tx	rank of the calling thread in its group
[in]	threads	threads of the group, threads_per_system(n)
[out]	piv	pivot entries (caller-pre-offset)
[in]	piv_stride	element stride of piv
[in]	rpiv	pivot entry of each slot of the thread

◆ store_solution()

template<typename T , CooperativeLUppConfig< T > Config = CooperativeLUppConfig<T>{}>

TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr void tdls::CooperativeLUppSolverDynamic< T, Config >::store_solution	(	const int	n,
		const int	tx,
		const int	threads,
		T *TDLS_RESTRICT	x,
		const int	rhs_stride,
		const T(&)	rB[rows_per_thread] )

inlinestaticconstexprnoexcept

Store the solution entries held by the calling thread.

Parameters

[in]	n	system dimension
[in]	tx	rank of the calling thread in its group
[in]	threads	threads of the group, threads_per_system(n)
[out]	x	solution (caller-pre-offset)
[in]	rhs_stride	element stride of x
[in]	rB	solution entries of the thread

◆ substitute()

template<typename T , CooperativeLUppConfig< T > Config = CooperativeLUppConfig<T>{}>

template<typename Sync = tdls::AutoSync>

TDLS_EXEC_CHECK_DISABLE TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr void tdls::CooperativeLUppSolverDynamic< T, Config >::substitute	(	const int	n,
		const int	tx,
		const T *TDLS_RESTRICT	A,
		const int	A_stride,
		const int *TDLS_RESTRICT	piv,
		const int	piv_stride,
		const T *TDLS_RESTRICT	b,
		T *TDLS_RESTRICT	x,
		const int	rhs_stride,
		T *	work,
		Sync &&	sync = Sync{} )

inlinestaticconstexprnoexcept

Solve from a factorization produced by factorize (b and x distinct).

Template Parameters

Sync	callable type of the barrier

Parameters

[in]	n	system dimension
[in]	tx	rank of the calling thread in its group
[in]	A	factored matrix
[in]	A_stride	element stride of A
[in]	piv	pivot entries produced by factorize
[in]	piv_stride	element stride of piv
[in]	b	right-hand side, in original order
[out]	x	solution
[in]	rhs_stride	element stride of b and x
[in]	work	workspace of workspace_size(n) elements, shared by the group
[in]	sync	barrier of the group, deduced by default (see tdls::AutoSync)

◆ substitute_canonical()

template<typename T , CooperativeLUppConfig< T > Config = CooperativeLUppConfig<T>{}>

template<typename Sync = tdls::AutoSync>

TDLS_EXEC_CHECK_DISABLE TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr void tdls::CooperativeLUppSolverDynamic< T, Config >::substitute_canonical	(	const int	n,
		const int	tx,
		const T *TDLS_RESTRICT	A,
		const int	A_stride,
		const int *TDLS_RESTRICT	piv,
		const int	piv_stride,
		const int	col,
		T *TDLS_RESTRICT	x,
		const int	rhs_stride,
		T *	work,
		Sync &&	sync = Sync{} )

inlinestaticconstexprnoexcept

Solve with b = e_col generated on the fly: the consistent-tangent-operator path.

Template Parameters

Sync	callable type of the barrier

Parameters

[in]	n	system dimension
[in]	tx	rank of the calling thread in its group
[in]	A	factored matrix
[in]	A_stride	element stride of A
[in]	piv	pivot entries produced by factorize
[in]	piv_stride	element stride of piv
[in]	col	index of the canonical column e_col
[out]	x	solution
[in]	rhs_stride	element stride of x
[in]	work	workspace of workspace_size(n) elements, shared by the group
[in]	sync	barrier of the group, deduced by default (see tdls::AutoSync)

◆ substitute_inplace()

template<typename T , CooperativeLUppConfig< T > Config = CooperativeLUppConfig<T>{}>

template<typename Sync = tdls::AutoSync>

TDLS_EXEC_CHECK_DISABLE TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr void tdls::CooperativeLUppSolverDynamic< T, Config >::substitute_inplace	(	const int	n,
		const int	tx,
		const T *TDLS_RESTRICT	A,
		const int	A_stride,
		const int *TDLS_RESTRICT	piv,
		const int	piv_stride,
		T *TDLS_RESTRICT	x,
		const int	rhs_stride,
		T *	work,
		Sync &&	sync = Sync{} )

inlinestaticconstexprnoexcept

Solve in place from a factorization produced by factorize: x holds the right-hand side on entry and the solution on exit.

Each thread reads and writes only the entries of its own rows, the same set before and after, so the in-place form needs no copy.

Template Parameters

Sync	callable type of the barrier

Parameters

[in]	n	system dimension
[in]	tx	rank of the calling thread in its group
[in]	A	factored matrix
[in]	A_stride	element stride of A
[in]	piv	pivot entries produced by factorize
[in]	piv_stride	element stride of piv
[in,out]	x	right-hand side on entry, solution on exit
[in]	rhs_stride	element stride of x
[in]	work	workspace of workspace_size(n) elements, shared by the group
[in]	sync	barrier of the group, deduced by default (see tdls::AutoSync)

◆ substitution()

template<typename T , CooperativeLUppConfig< T > Config = CooperativeLUppConfig<T>{}>

template<bool backward_only, typename Sync >

TDLS_EXEC_CHECK_DISABLE TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr void tdls::CooperativeLUppSolverDynamic< T, Config >::substitution	(	const int	n,
		const int	tx,
		const int	threads,
		const T *TDLS_RESTRICT	A,
		const int	A_stride,
		T(&)	rB[rows_per_thread],
		const int(&)	rpiv[rows_per_thread],
		T *	work,
		Sync &	sync )

inlinestaticconstexprnoexcept

Substitution from the factored rows, the right-hand side in the entries of the thread on entry, the solution entries tx + K * threads on exit: L y = P b then U x = y under the column-major layout, U^T z = b, L^T w = z and x = P^T w under the row-major one.

Template Parameters

backward_only	skip the forward pass, folded into the factorization (solve_inplace)
Sync	callable type of the barrier

Parameters

[in]	n	system dimension
[in]	tx	rank of the calling thread in its group
[in]	threads	threads of the group, threads_per_system(n)
[in]	A	factored matrix (caller-pre-offset)
[in]	A_stride	element stride of A
[in,out]	rB	right-hand-side entries of the thread on entry (forward-reduced with backward_only), solution entries on exit
[in]	rpiv	pivot entry of each slot of the thread
[in]	work	workspace of the group
[in]	sync	barrier of the group

◆ threads_per_system()

template<typename T , CooperativeLUppConfig< T > Config = CooperativeLUppConfig<T>{}>

TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr int tdls::CooperativeLUppSolverDynamic< T, Config >::threads_per_system ( const int n )

inlinestaticconstexprnoexcept

Threads solving one system of dimension n: ceil(n / rows_per_thread).

Parameters

[in] n system dimension

Returns: the number of threads of a group

◆ transposed_passes()

template<typename T , CooperativeLUppConfig< T > Config = CooperativeLUppConfig<T>{}>

template<bool backward_only, typename Sync >

TDLS_EXEC_CHECK_DISABLE TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr void tdls::CooperativeLUppSolverDynamic< T, Config >::transposed_passes	(	const int	n,
		const int	tx,
		const int	threads,
		const T *TDLS_RESTRICT	A,
		const int	A_stride,
		T(&)	rB[rows_per_thread],
		const T *	rows,
		T *	buf,
		Sync &	sync )

inlinestaticconstexprnoexcept

Forward then backward pass of S^T x = b: b in the entries of the thread on entry, w at the entries of the same positions on exit.

Forward, U^T z = b: every thread loads U(i, c) for its entries c > i, and U(i, i), before the barrier; the owner of entry i publishes b'(i) and keeps z_i in its place. Backward, L^T w = z: every entry c < k loads L(k, c) before the barrier; the owner of entry k publishes w_k. Position 0 updates no entry in the backward pass: its step is skipped, and the buffer parity is shifted by one, so that the first backward step does not write the buffer read by the last forward step.

Template Parameters

backward_only	skip the forward pass, folded into the factorization (solve_inplace)
Sync	callable type of the barrier

Parameters

[in]	n	system dimension
[in]	tx	rank of the calling thread in its group
[in]	threads	threads of the group, threads_per_system(n)
[in]	A	factored matrix (caller-pre-offset)
[in]	A_stride	element stride of A
[in,out]	rB	entries tx + K * threads
[in]	rows	workspace: row of S at each position
[in]	buf	workspace: double-buffered broadcast value
[in]	sync	barrier of the group

◆ workspace_size()

template<typename T , CooperativeLUppConfig< T > Config = CooperativeLUppConfig<T>{}>

TDLS_HOST_DEVICE static TDLS_FORCE_INLINE_GPU constexpr int tdls::CooperativeLUppSolverDynamic< T, Config >::workspace_size ( const int n )

inlinestaticconstexprnoexcept

Elements of the workspace shared by the threads of a group: the two elements of the deduced CPU barrier, then 3 * n under logical row interchanges, 2 * n + 2 * threads_per_system(n) + 5 under physical ones.

Parameters

[in] n system dimension

Returns: the number of elements of the workspace

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

include/tdls/solvers/cooperative_lupp/solver_dynamic.hpp

Static Public Member Functions

Static Public Attributes

Detailed Description

Member Function Documentation

◆ backward_pass()

◆ eliminate()

◆ factorize()

◆ forward_pass()

◆ init_piv()

◆ keeps_pivot()

◆ load_piv()

◆ load_rhs()

◆ load_row()

◆ logical_elimination_step()

◆ make_sync()

◆ physical_elimination_step()

◆ row_at()

◆ save_row()

◆ solve()

◆ solve_inplace()

◆ store_piv()

◆ store_solution()

◆ substitute()

◆ substitute_canonical()

◆ substitute_inplace()

◆ substitution()

◆ threads_per_system()

◆ transposed_passes()

◆ workspace_size()