We propose and analyze three multilevel iterative solvers of both domain decomposition and multigrid type. All of these methods are algebraic, allowing almost or fully black-box implementation. Their development was motivated by the need to solve large algebraic systems of equations resulting from finite element discretizations of self-adjoint, second order uniformly elliptic problems on unstructured three-dimensional meshes. Two of the methods discussed perform a simple, but effective domain decomposition as a part of the solving process. This allows for a remarkable adaptivity, where the decomposition is generated depending on the difficulty of the problem without requiring an input of a different decomposition. We focus on achieving robustness features that allow using the new methods as a replacement of direct solvers for solving these systems. The new methods are superior in terms of computational complexity and storage requirements. On serial architectures, the asymptotic computational complexity of these methods for solving 3D problems is shown to be in the range of $O(n^{7/6})$ and $O(n^{49/33})$. The methods all benefit from implementation on modern parallel architectures which can reduce the computational complexity to $O(n^{7/6})$ for all three methods. The theoretical results are accompanied by computational experiments confirming the theoretically predicted convergence properties and suggesting the potential of the methods for solving a wider variety of problems than those % the ones covered by the current theory.

Contributed October 24, 1997.