Optimal solvers for fourth-order PDEs discretized on unstructured grids

This paper provides a class of optimal algorithms for the linear algebraic systems arising from direct finite element discretization of the fourth-order equation with different boundary conditions on any polygonal domains that are partitioned by unstructured grids. Several preconditioners are presented, and the preconditioned conjugate gradient methods applied with these preconditioners are proved to converge uniformly with respect to the size of the linear systems. As a result, for the first time in the literature, it is rigorously proved in this paper that a discretized finite element system for fourth-order PDEs on an unstructured grid of size N can be solved within O(N log N) operations. One main ingredient in constructing these optimal preconditioners is a mixed-form discretization of the fourth-order problem. Such a mixed-form discretization often leads to an approximation of the original solution that is either suboptimal or divergent, but it nevertheless provides optimal preconditioners for the direct finite element problem. It is further shown that the implementation of the preconditioners can be reduced to the solution of several discrete Poisson equations. Consequently, the existing optimal or nearly optimal solver, such as geometric or algebraic multigrid methods, for Poisson equations will lead to a nearly optimal solver for the discrete fourth-order system. A number of nonstandard Sobolev spaces and their discretizations defined on the boundary of polygonal domains are carefully studied and used for the analysis of these preconditioners. Numerical examples are also provided to confirm the theory developed in the paper. © 2014 Societ y for Industrial and Applied Mathematics.