A black-box iterative solver based on a two-level Schwarz method (Q1969307)

The authors describe and investigate a black-box iterative solver for 2D and 3D elliptic problems with Dirichlet or Neumann boundary conditions, which problems are discretized on a general unstructured grid with P1 or Q1 elements. This is an algebraic two-grid method which can be interpreted as an overlapping multiplicative Schwarz method. The authors show convergence independent of \(h\) or \(H\) for this method. As input to the algorithm, only the stiffness matrix \(A\) and the right-hand vector are required. The second, coarse grid is then constructed (in a fashion remembering classical sparse matrix ordering techniques) automatically on the basis of the graph of \(A\). In cases where large neigbourhoods of unknowns are aggregated, a higher degree of the polynomial smoother is needed; for the (local) correction operators and the coarse grid equation, Cholesky decompositions are computed. The total operation count is estimated as \(O(n^{4/3})\) for 2D and \(O(n^{49/33})\) for 3D problems, using a serial computer; for a parallel computer the operation count estimate becomes yet better. The whole procedure is used as a preconditioner for conjugate gradients. Numerical results are reported for 3D elasticity problems with about 60000 unknowns and for scattering problems with up to about four millions of unknowns.