Stanford 50: State of the Art and Future Directions of Computational Mathematics and Numerical Computing


  • March 30, 2007
  • 2:00 pm - 2:25 pm

Combining direct and iterative methods for the solution of large systems in different application areas

Iain Duff (Rutherford Appleton Laboratory)

We are concerned with the solution of sets of linear equations where the matrices are of very high order. We first discuss sparse direct methods and consider the size of problems that they can currently solve. We then discuss the limitations of such methods, where current research is going in moving these limitations, and how far we might expect to go with direct solvers in the near future.

This leads us to the conclusion that very large systems, by which we mean three dimensional problems in more than a million degrees of freedom, require the assistance of iterative methods in their solution. However, even the strongest advocates and developers of iterative methods recognize their limitations when solving difficult problems, that is problems that are poorly conditioned and/or very unstructured. It is now universally accepted that sophisticated preconditioners must be used in such instances.

A very standard and sometimes successful class of preconditioners are based on incomplete factorizations or sparse approximate inverses, but we very much want to exploit the powerful software that we have developed for sparse direct methods over a period of more than thirty years. We thus discuss various ways in which a symbiotic relationship can be developed between direct and iterative methods in order to solve problems that would be intractable for one class of methods alone. In these approaches, we will use a direct factorization on a "nearby'' problem or on a subproblem.

We then look at examples using this paradigm in four quite different application areas; the first solves a subproblem and the others a nearby problem using a direct method.

Stanford University Home Page