Matrix Factorizations and Direct Solution of Linear Systems 51-5 the basis of errors that are made in the initial representation.Additional errors made in the course of the computation can hardly be expected to improve this situation. 51.2 Triangular Linear Systems Syseamsofieroquatiosorw时iahthotmnosnmennlforometntnci识 Such may be an be solved w. tems are e the for of lin they often constitute an interm Definitions: = r an upper triangular matrix (ti=0 for i>j)or a Facts:Hig02],[GV96] 1.[GV96,pp.88-90 Algorithm 1:Row-wise forward substitution for solving lower triangular system Input:L=[∈R"xn with(为=0fork<jb∈R Output:solution vector x ER"that satisfies Lx b x1←-b1/011 for k=2 ton 工k←(k-Lk.1k-1·工1k-1)/k.内 Algorithm 2:Column-wise back substitution for solving upper triangular system Input:U =ue nxn with =0 for k>i: for k=n down to 2 in steps of-1, 工k←b/ukk b1:k-1+b1:k-1-kU1:k-1.k x1←b/u1,1 2.Algorithm 1 involves as a core calculation dot products of portions of coefficient matrix rows with portions of the emerging solution vector.This can incur a performance penalty for large n from accumulation of dot products using a scalar recurrence.A "column-wise"reformulation may have better performance for large n.Algorithm 2 is such a "column-wise"formulation for upper triangular systems. 3.An efficient and reliable implementation for the solution of triangular systems is offered as part of the standard BLAs software library in xTRSz (see Chapter 92), where x=S,D,C,or Z according to whether data are single or double precision real,or single or double precision complex floating point numbers,respectively,and z=V or M according to whether a single system of equations is to be solved or multiple systems (sharing the same coefficient matrix)are to be solved,respectively. Matrix Factorizations and Direct Solution of Linear Systems 51-5 the basis of errors that are made in the initial representation. Additional errors made in the course of the computation can hardly be expected to improve this situation. 51.2 Triangular Linear Systems Systems of linear equations for which the unknowns may be solved for one at a time in sequence may be reordered to produce linear systems with triangular coefficient matrices. Such systems can be solved both with remarkable accuracy and remarkable efficiency. Tri￾angular systems are the archetype for easily solvable systems of linear equations. As such, they often constitute an intermediate goal in strategies for solving linear systems. Definitions: A linear system of equations Tx = b with T ∈ C n×n (representing n equations in n unknowns) is a triangular system if T = [tij] is either an upper triangular matrix (tij = 0 for i > j) or a lower triangular matrix (tij = 0 for i < j). Facts: [Hig02], [GV96] 1. [GV96, pp. 88–90] Algorithm 1: Row-wise forward substitution for solving lower triangular system Input: L = [`ij] ∈ R n×n with `kj = 0 for k < j; b ∈ R n Output: solution vector x ∈ R n that satisfies Lx = b x1 ← b1/`1,1 for k = 2 to n xk ← (bk − Lk,1:k−1 · x1:k−1)/`k,k Algorithm 2: Column-wise back substitution for solving upper triangular system Input: U = [uij] ∈ R n×n with ukj = 0 for k > j; b ∈ R n Output: solution vector x ∈ R n that satisfies Ux = b for k = n down to 2 in steps of −1, xk ← bk/uk,k b1:k−1 ← b1:k−1 − xkU1:k−1,k x1 ← b1/u1,1 2. Algorithm 1 involves as a core calculation dot products of portions of coefficient matrix rows with portions of the emerging solution vector. This can incur a performance penalty for large n from accumulation of dot products using a scalar recurrence. A “column-wise” reformulation may have better performance for large n. Algorithm 2 is such a “column-wise” formulation for upper triangular systems. 3. An efficient and reliable implementation for the solution of triangular systems is offered as part of the standard blas software library in xTRSz (see Chapter 92), where x=S, D, C, or Z according to whether data are single or double precision real, or single or double precision complex floating point numbers, respectively, and z=V or M according to whether a single system of equations is to be solved or multiple systems (sharing the same coefficient matrix) are to be solved, respectively