Contents

Lower Triangular Solve with Multiple Right-hand Sides (Trsm_lln)
1. Definition
2. Theorems, Lemmas, and Corollaries
Algorithms

Lower Triangular Solve with Multiple Right-hand Sides (Trsm_lln)

Definition

Definition: Given a nonsingular LowerTriangularMatrix $L \in \Snxn$ and matrix $B \in \Rmxn$ , the lower triangular solve with multiple right-hand sides (lower Trsm) computes the solution of $ L X = B $ , where $L$ and $B$ are given and $X$ is to be computed.

The name of this operation comes for the observation that if $B$ and $X$ are partitioned by columns,

$$ B \rightarrow \defrowvector{b}{n} $ and $ X \rightarrow \defrowvector{x}{n} $,$

then

$\left( \begin{array}{c | c | c } L b_0 & \cdots & L b_{n-1} \end{array} \right) = \left( \begin{array}{c | c | c } x_0 & \cdots & x_{n-1} \end{array} \right)$

so that $L x_j = b_j $ . In other words, a lower triangular solve must be performed with every right-hand side column $ b_j $ .

Theorems, Lemmas, and Corollaries

Algorithms

$B \becomes L^{-1} B$ denotes the operation that overwrites right-hand side $B$ with the solution of $ L X = B $ . Let $\hat{B}$ denote the original contents of $ B $ .

Partitioned Matrix Expression

This operation has two PMEs:

PME 1

$\FlaTwoByOne { B_T } { B_B } = \FlaTwoByOne { X_T } { X_B } \wedge \left\{ \begin{array}{l} L_{TL} X_T = \hat{B}_T \\ L_{BR} X_B = \hat{B}_B - L_{BL} X_T \end{array} \right.$

Details.

PME 2

$\FlaOneByTwo{ B_L }{ B_R } = \FlaOneByTwo{ X_L }{ X_R } \wedge \left\{ \begin{array}{l} L X_L = \hat{B}_L \\ L X_R = \hat{B}_R \end{array} \right.$

Details.

Loop-invariants

The above PMEs allow for four different loop-invariants to be identified:

Invariant 1

$\FlaTwoByOne { B_T } { B_B } = \FlaTwoByOne { X_T } { \hat{B}_B } $ where $ L_{TL} X_T = \hat{B}_T$

Invariant 2

$\FlaTwoByOne { B_T } { B_B } = \FlaTwoByOne { X_T } { \hat{B}_B - L_{BL} X_T } $ where $ L_{TL} X_T = \hat{B}_T$

Invariant 3

$\FlaOneByTwo{ B_L }{ B_R } = \FlaOneByTwo{ X_L }{ \hat{B}_R } $ where $ L X_L = \hat{B}_L$

Invariant 4

$\FlaOneByTwo{ B_L }{ B_R } = \FlaOneByTwo{ \hat{B}_L }{ X_R } $ where $ L X_R = \hat{B}_R$

Algorithmic variants

Variant 1	unb	Derivation	Worksheet	Algorithm	FLAME@lab	FLAMEC
Variant 1	blk	Derivation	Worksheet	Algorithm	FLAME@lab	FLAMEC
Variant 2	unb	Derivation	Worksheet	Algorithm	FLAME@lab	FLAMEC
Variant 2	blk	Derivation	Worksheet	Algorithm	FLAME@lab	FLAMEC
Variant 3	unb	Derivation	Worksheet	Algorithm	FLAME@lab	FLAMEC
Variant 3	blk	Derivation	Worksheet	Algorithm	FLAME@lab	FLAMEC
Variant 4	unb	Derivation	Worksheet	Algorithm	FLAME@lab	FLAMEC
Variant 4	blk	Derivation	Worksheet	Algorithm	FLAME@lab	FLAMEC

Performance

Enlarge

Try it yourself

attachment:Trsm_lln_with_50.png

Figure 1: Performance of the different variants (unblocked and blocked) on an Intel Xeon (3.4GHz) processor. For these experiments, the block size ( $b$ in the algorithms, nb_alg in the FLAMEC code) was chosen to equal 128. The reference implementation Simple loops computes the operation with simple indexed loops.