May be solvers for the hp-version optimized? - "Optimal solver for Dirichlet problems on subdomains of decomposition in the domain decomposition method for hp-version"
Vadim Korneev
May 15, 2001, 1:30 p.m. T 857We are concerned with the complexity of the Dirichlet-Dirichlet DD (domain decomposition) solvers for systems of hp-version finite element algebraic equations. In general, it depends on the quality of the DD preconditioner, i.e., on the number of the outer iterations, and four major contributions at each iteration. These contributions are due to solving
- IDP - internal discrete Dirichlet problems on subdomains of decomposition,
- the interface problem related to the unknowns on the sides of the subdomains of decomposition,
- the global problem related to the unknowns at the vertices of subdomains of decomposition, and
- multiplication of vectors by the global finite element matrix.
Numerical experiments and apriori estimates show that the greatest contribution to the total computational work is related to solving IDP, if it is done by general direct methods. With 2) and 3) studied in our previous works, in this talk we show that, additionally, IDP solvers may be optimized. The starting point is the preconditioner for IDP suggested in our earlier works. It may be interpreted as the finite-difference five-point approximation on the uniform orthogonal grid for the second order elliptic operator with deteriorating coefficients in the reference square. For the first step, we simplify the preconditioner by means of decomposing the reference square in such rectangular subdomains, that in every of which the coefficients are replaced by constants without loss of the spectral equivalence. For the systems with the new preconditioner for the matrix, we suggest two types of fast solvers. One is exact and asymptotically almost optimal, i.e., optimal up to log p. It is is based on the transformation to the special basis, which in part is trigonometric. This solver employes subprocedures of 1D and 2D fast discrete Fourier transforms, the method of 1D "progonka" for the systems with three diagonal matrices and Gaussian elimination for the system of O((log p)^2) equations. Another is in part iterative and asymptotically optimal. It employes the same procedures as the exact solver, except that 2D fast discrete Fourier transforms on the subdomains of the decomposition of the reference square are replaced by more efficient multigrid methods. Combined with our previous results on the preconditioning of subproblems 2), 3), the suggested fast solvers for IDDP directly lead to the almost optimal and optimal, up to the operation 4), DD solver for hp-version systems of algebraic equations.
