Hierarchical bases give conjugate gradient type methods a multigrid speed of convergence

摘要

The interesting properties of the discretization matrices arising in the finite element solution of plane elliptic boundary value problems when using hierarchical bases are described. The condition numbers of these discretization matrices grow only quadratically in the number of refinement levels, contrary to the exponential growth found with nodal bases. Furthermore it is easily possible to compute the product of such a discretization matrix with a given coefficient vector. We show how these results can be used to solve the discretized problem in O(n log n) computer operations, where n is the number of unknowns. Special emphasis is layed on the refinement structures used in R. E. Bank's PLTMG package, which have not been treated in the author's previous papers.