Author | Ploeg, A. van der |

Title | Preconditioning for sparse matrices with applications |

Conference/Journal | PhD-thesis, Rijks University Groningen |

Month | February |

Year | 1994 |

Abstract

In this thesis, we have considered the development of preconditioners for large sparse systems of linear equations Ax = b. Primarily, we have studied preconditioners based on incomplete decompositions.

In Chapter 1, we have shown that for many problems, conjugate gradient-like methods combined with a proper preconditioner perform significantly better than stationary iterative methods such as Jacobi, Gauss-Seidel and SOR. In Chapter 1 we also have considered some preconditioning techniques for matrices with a very regular sparsity pattern. When A is symmetric positive definite, it appeared that in most cases the system can be solved efficiently by the MICCG-method, in which the sparsity pattern of L+LT is the same as that of A. This regular sparsity pattern enables us to implement the MICCG-method efficiently on supercomputers, and to use the Eisenstat implementation for the matrix-vector multiplication.

When the coefficient matrix stems from a discretization of a steady convection-diffusion equation with dominating convective parts, both the robustness and efficiency of the preconditioner can be improved by allowing some extra fill-in in the factors L and U.

Of course, more analysis (e.g. rigorous convergence proof) and further optimization (e.g. choice of the drop tolerance and ordering of the unknowns) is needed. In the present method, the renumbering of the unknowns is based on a rectangular grid. An algorithm in which a similar renumbering is performed using only the sparsity pattern of A, so that it can be used in case of unstructured grids and irregular geometries, is worth further study. Also, more research is required to exploit the parallelism present in the algorithm,and to study the possibilities for using the ideas of Chapter 6 for solving the discretized incompressible Navier-Stokes equations.

In this thesis, we have considered the development of preconditioners for large sparse systems of linear equations Ax = b. Primarily, we have studied preconditioners based on incomplete decompositions.

In Chapter 1, we have shown that for many problems, conjugate gradient-like methods combined with a proper preconditioner perform significantly better than stationary iterative methods such as Jacobi, Gauss-Seidel and SOR. In Chapter 1 we also have considered some preconditioning techniques for matrices with a very regular sparsity pattern. When A is symmetric positive definite, it appeared that in most cases the system can be solved efficiently by the MICCG-method, in which the sparsity pattern of L+LT is the same as that of A. This regular sparsity pattern enables us to implement the MICCG-method efficiently on supercomputers, and to use the Eisenstat implementation for the matrix-vector multiplication.

When the coefficient matrix stems from a discretization of a steady convection-diffusion equation with dominating convective parts, both the robustness and efficiency of the preconditioner can be improved by allowing some extra fill-in in the factors L and U.

Of course, more analysis (e.g. rigorous convergence proof) and further optimization (e.g. choice of the drop tolerance and ordering of the unknowns) is needed. In the present method, the renumbering of the unknowns is based on a rectangular grid. An algorithm in which a similar renumbering is performed using only the sparsity pattern of A, so that it can be used in case of unstructured grids and irregular geometries, is worth further study. Also, more research is required to exploit the parallelism present in the algorithm,and to study the possibilities for using the ideas of Chapter 6 for solving the discretized incompressible Navier-Stokes equations.

Download File

PDF format, file size 0.8 MB.

PDF format, file size 0.8 MB.