HFSS15: Direct Matrix Solver

Direct methods obtain an exact solution to the following linear system of equation

(1)

where A is a matrix, b a right hand side and x the solution. A matrix solver using a direct method is called a direct matrix solver.

The most widely known direct method is Gaussian elimination, which uses elementary matrix operations to compute the solution. Most other direct solution techniques are either a variant of Gaussian elimination or are based upon a particular factorization of the equations that will allow an exact computation. One of the most commonly used such techniques is the LU decomposition, which is introduced below.

LU decomposition is both a factorization approach and closely related to Gaussian elimination. It is based upon the assumption that A can be decomposed into a product of two matrices or factors.

(2)

where L is a lower triangular matrix (has elements only on the diagonal and below) and U is an upper triangular matrix (has elements only on the diagonal and above).

With the help of (2), we can equivalently solve (1) by first solving for y such that

(3)

then solving for x such that

(4)

The advantage of decomposition (2) is that the solution of triangular set of equations (3) and (4) is quite trivial. Namely, they can be solved directly by forward substitution and by backward substitution respectively. Furthermore, the factors in (2) are computed only once and can be reused in (3) and (4) for different right hand sides.

In LU decomposition, the major storage is for matrix A, factor L and factor U. The major operation is the decomposition (2), which is roughly equivalent to a matrix-matrix multiplication; while the operation in (3) and (4) combined, is equivalent to a matrix-vector multiplication. The total computational cost is S+mT with S>>T in general, where S is the number of operations for decomposition (2), m the number of right hand sides, and T the number of operations for both forward substitution and for backward substitution.

Direct methods are best used for solving system matrix equations with moderate size or with a large number of right hand sides. As the system to be solved becomes larger, the overhead associated with the more complicated iterative methods becomes less of an issue, and the iterative methods should outperform the direct methods. For sparse systems, the use of direct methods is complicated by the possible introduction of more nonzero entries (fill-in) such that the L and U factors become much denser than the original matrix A.