Introduction

The triangular solve with multiple right-hand sides has the form

B := A-1 B, B := A-T B, B := B A-1, or B := B A-T.

Here B is a general matrix of size m × n while A is an m × n upper or lower triangular matrix, as indicated by the letter U or L, respectively.

The name of the operation comes from the fact that in practice the inverse of the triangular matrix is not formed. Instead, the solution of the triangular system

A-1 X = B, A-T X = B, X A-1 = B, or X A-T = B.

is computed, where X overwrites the input matrix B. Furthermore, when one considers the equation

A-1 X = B ,

and bj and xj denote the jth columns of B and X , respectively, then

A-1 xj = bj .

This shows that for each column of B one needs to solve a triangular system (with a single right-hand side), which explains the "multiple right-hand sides" part of the name of the operation. A similar observation can be made for all cases of the operation.

Notice: In all these operations, the upper or lower triangular matrix is stored in the upper or lower triangular part of matrix A, respectively. The other part of the matrix may contain data, which is not used nor is it altered as part of the computation.