The numerical solution of partial differential equations and integral equations in modeling various physical phenomena often requires the solution of large sparse or structured systems of linear algebraic equations. The direct solution of these linear systems using Gaussian elimination is prohibitively expensive in terms of both time and storage, so iterative methods are used. These do not require storage of the matrix but only the ability to perform matrix-vector multiplications. An important area of research is to find efficient iterative methods that require only a small number of matrix-vector multiplications and a small amount of additional work to compute a good approximate solution to the linear system. Sometimes the techniques used in solving linear systems are applicable in other areas as well, such as computing eigenvalues and computing various matrix functions such as the resolvent and the matrix exponential.
Recent progress has been made in understanding the behavior of the conjugate gradient method and the minimal residual method for symmetric linear systems in finite precision arithmetic. It is shown that these methods behave like the exact algorithms applied to a larger linear system whose eigenvalues all lie in tiny intervals about the eigenvalues of the given matrix. This same analysis shows why the Lanczos algorithm can be used effectively to compute the matrix exponential.
Current work deals with nonsymmetric problems. One interesting problem is to describe the behavior of iterative methods for nonsymmetric linear systems in terms of some characteristic properties of the coefficient matrix. Eigenvalues are not the answer in the nonnormal case. Another open problem is to find an iterative method using a short recurrence that generates a near optimal approximate solution to the linear system at each step. The conjugate gradient and minimal residual methods do this for symmetric problems, but it is not known if such a method exists for nonsymmetric matrices.For more details, see the references: