There are two general schemes for solving linear systems:
- Direct Elimination Methods, and
- Iterative Methods.
All the direct methods are, in some sense, based on the standard Gauss Elimination technique, which systematically applies row operations to transform the original system of equations into a form that is easier to solve. This section overviews the LU Decomposition method which, although functionally equivalent to the Gauss Elimination method, does provide some additional flexibility for computer implementation. Thus, the LU decomposition method is often the preferred direct solution method for low to medium sized systems (usually less than 200-300 equations).
For large systems, iterative methods (instead of direct elimination methods) are almost always used. This switch is required from accuracy considerations (related to round-off errors), from memory limitations for physical storage of the equation constants, from considerations for treating nonlinear problems, and from overall efficiency concerns. There are several specific iterative schemes that are in common use, but most methods build upon the base of the Gauss-Seidel method, usually with some acceleration scheme to help convergence. Thus, our focus in this brief overview is first on the basic Gauss Seidel scheme and on the use of Successive Over Relaxation (SOR) to help accelerate convergence.
We also give a short tutorial to the multigrid and conjugate gradient methods for solving 2D and 3D problems effectively.