Algorithms and Parallel Computing

20.1 INTRODUCTION

Solving systems of linear equations is found in almost all areas of engineering and scientific applications. A system of linear equations is generally expressed in matrix form as

(20.1)

where A is the system matrix, which is an n × n matrix, x is the unknown vector of n components, and b is a vector of constants. Techniques for solving linear systems could be direct or iterative. Direct techniques are appropriate for small systems (small values of n) where computational errors will be small. Iterative techniques are more appropriate for large systems where an assumed solution is refined after each iteration while suppressing computational noise. Table 20.1 summarizes the different direct and indirect techniques used to solve linear systems. Reference 129 explains in detail how such techniques are used.

Table 20.1 Direct and Indirect Techniques Used to Solve Linear Systems

Direct techniques	Comment
Forward substitution	System matrix lower triangular
Back substitution	System matrix upper triangular
LU factorization	Convert system matrix to equivalent triangular system. L is lower triangular matrix and U is upper triangular matrix.
Gaussian elimination	Convert system matrix to equivalent triangular system
LDMt factorization	Convert system matrix to three special matrices. L is lower triangular matrix, D is diagonal matrix, and M is a Gaussian transformation matrix such that ...