Geometry-Analysis Based Algebraic Multigrid Methods And Applications

Multigrid methods are by far the most efficient methods for solving large scale algebraic systems arising from discretizations of partial differential equations. Roughly speaking, these methods can be developed though two approaches: geometric approach and algebraic approach. The purpose of this work is to develop multigrid methods by combining both geometric and algebraic approaches, which may be known as algebraic multigrid(AMG) methods based on geometric and analytic information.This dissertation consists of two parts. In the first part, by combining advantages of both geometric and algebraic multigrid methods, some robust multigrid methods are constructed for two kinds of finite element equations, one is the high order Lagrangian finite element equation for which AMG is often not very efficient; another is a condensed finite element system on criss-cross grids where the corresponding coarse spaces can not be made nested easily. By an effective use of geometric information and analytic properties of underlying differential equations and finite element spaces, many algebraic features can be exploited for developing new coarsening techniques and new interpolation operators. The new method overcomes the difficulty for properly controlling the degrees of freedom of the coarse spaces in the usual AMG methods. Numerical results show that our algebraic multigrid algorithm is substantially better than many usual algebraic multigrid algorithms. Furthermore, by using a new theoretical approach, namely the Xu-Zikatanov identity, a rigorous convergence analysis of our algebraic multigrid method is given. In addition, based on an algebraic multigrid method of linear finite elements, a robust preconditioned conjugate gradient method is presented and analyzed for the discrete systems of high order Lagrangian finite elements. These new ideas of hybrid multigrid and theoretical analysis provided in this work can be extended to more general cases.In the second part, algebraic multigrid methods are applied to solve two kinds of discrete systems arising from practical applications. First a block preconditioned conjugate gradient method (BPCG) and a class of algebraic multigrid methods are developed and studied for some discrete mathematical models for lattice block materials. Numerical experiments show that the new AMG methods converge uniformly with respect to the size of problem and also to some crucial parameters. Such a uniform convergence of the BPCG algorithm is further theoretically justified properly by...