the auxiliary space solvers and their applications
Open Access
- Author:
- Wang, Lu
- Graduate Program:
- Mathematics
- Degree:
- Doctor of Philosophy
- Document Type:
- Dissertation
- Date of Defense:
- August 05, 2014
- Committee Members:
- Jinchao Xu, Dissertation Advisor/Co-Advisor
James Joseph Brannick, Committee Member
Ludmil Tomov Zikatanov, Committee Member
Chao Yang Wang, Special Member - Keywords:
- multigrid
auxiliary space
solver - Abstract:
- Developing efficient iterative methods and parallel algorithms for solving sparse linear sys- tems discretized from partial differential equations (PDEs) is still a challenging task in scien- tific computing and practical applications. Although many mathematically optimal solvers, such as the multigrid methods, have been analyzed and developed, the unfortunate reality is that these solvers have not been used much in practical applications. In order to narrow the gap between theory and practice, we develop, formulate, and analyze mathematically optimal solvers that are robust and easy to use in practice based on the methodology of Fast Auxiliary Space Preconditioning (FASP). We develop a multigrid method on unstructured shape-regular grids by the construction of an auxiliary coarse grid hierarchy on which the multigrid method can be applied by using the FASP technique. Such a construction is realized by a cluster tree which can be obtained in O(N log N ) operations for a grid of N nodes. This tree structure is used for the definition of the grid hierarchy from coarse to fine. For the constructed grid hierarchy, we prove that the condition number of the preconditioned system for an elliptic PDE is O(logN). Then, we present a new colored block Gauss-Seidel method for general unstructured grids. By constructing the auxiliary grid, we can aggregate the degree of freedoms in the same cells of the auxiliary girds into one block. By developing and a parallel coloring algorithm for the tree structure, a colored block Gauss-Seidel method can be applied with the aggregates serving as non-overlapping blocks. On the other hand, we also develop a new parallel unsmoothed aggregation algebraic multigrid method for the PDEs defined on an unstructured mesh from the auxiliary grid. It provides (nearly) optimal load balance and predictable communication patterns factors that make our new algorithm suitable for parallel computing. Furthermore, we extend the FASP techniques to saddle point and indefinite problems. Two auxiliary space preconditioners are presented. An abstract framework of the symmetric positive definite auxiliary preconditioner is presented so that the optimal multigrid method could be applied for the indefinite problem on the unstructured grid. We also numerically verify the optimality of the two preconditioners for the Stokes equations.