MULTILEVEL ALGORITHMS CONSIDERED AS ITERATIVE METHODS ON SEMIDEFINITE SYSTEMS

For the representation of piecewise d-linear functions instead of the usual finite element basis, a generating system is introduced that contains the nodal basis functions of the finest level and of all coarser levels of discretization. This approach enables the author to work directly with multilevel decompositions of a function. For a partial differential equation, the Galerkin scheme based on this generating system results in a semidefinite matrix equation that has in the one-dimensional (1D) case only about twice, in the two-dimensional (2D) case about 4/3 times, and in the three-dimensional (3D) case about 8/7 times as many unknowns as the usual system. Furthermore, the semidefinite system possesses not just one, but many solutions. However, the unique solution of the usual definite finite element problem can be easily computed from every solution of the semidefinite problem. The author shows that modem multilevel algorithms can be considered as standard iterative methods over the semidefinite system. The conjugate gradient (CG) method for the semidefinite system is equivalent to the BPX- or MDS-preconditioned CG method for the linear system that arises from the usual finite element basis. The Gauss-Seidel iteration applied to the semidefinite system is equivalent to the multigrid (MG) method applied to the standard basis system. Consequently, the Gauss-Seidel-preconditioned CG method for the semidefinite system is equivalent to MG-CG for the standard basis system. This paper includes results of numerical experiments regarding the condition number and the convergence rates of different iterative methods for the semidefinite system.