×

A numerical investigation of Schwarz domain decomposition techniques for elliptic problems on unstructured grids. (English) Zbl 1017.65524

Summary: We consider a parallel implementation of the additive two-level Schwarz domain decomposition technique. The procedure is applied to elliptic problems on general unstructured grids of triangles and tetrahedra. A symmetric, positive-definite system of linear equations results from the discretization of the differential equations by a standard finite-element technique and it is solved with a parallel conjugate gradient (CG) algorithm preconditioned by Schwarz domain decomposition. The two-level scheme is obtained by augmenting the preconditioning system by a coarse grid operator constructed by employing an agglomeration-type algebraic procedure. The algorithm adopts an overlap of just a single layer of elements, in order to simplify the data-structure management involved in the domain decomposition and in the matrix-times-vector operation for the parallel conjugate gradient. Numerical experiments have been carried out to show the effectiveness of the procedure and they, in turn, show how even such a simple coarse grid operator is able to improve the scalability of the algorithm.

MSC:

65N55 Multigrid methods; domain decomposition for boundary value problems involving PDEs
76M10 Finite element methods applied to problems in fluid mechanics
76M25 Other numerical methods (fluid mechanics) (MSC2010)

Software:

ITSOL; ILUT; SPARSKIT
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bjorstad, P. E.; Skogen, M.: Domain decomposition algorithms of Schwarz type, designed for massively parallel computers. Fifth international symposium on domain decomposition methods for partial differential equations (1992) · Zbl 0770.65078
[2] Chan, T. F.; Smith, B.; Zou, J.: Overlapping Schwarz methods on unstructured meshes using non-matching coarse grids. Technical report 94-8 (February, 1994) · Zbl 0879.65082
[3] Chan, T. F.; Mathew, T. P.: Domain decomposition algorithms. Acta numerica, 61-143 (1994) · Zbl 0809.65112
[4] Chan, T. F.; Zou, J.: A convergence theory of multilevel additive Schwarz methods on unstructured meshes. Technical report 95-16 (March, 1995)
[5] also Ultracomputer Note 131.
[6] Dryja, M.; Wildlund, O. B.: Some domain decomposition algorithms for elliptic problems. Iterative methods for large linear systems, 273-291 (1989)
[7] Dryja, M.; Wildlund, O. B.: Domain decomposition algorithms with small overlap. Technical report 606 (May, 1992)
[8] Hendrickson, B.; Leland, R.: An improved spectral graph partitioning algorithm for mapping parallel computations. Technical report SAND92-1460 (September, 1992) · Zbl 0816.68093
[9] Hendrickson, B.; Leland, R.: Multidimensional spectral load balancing. Technical report SAND93-0074 (January, 1993)
[10] Hendrickson, B.; Leland, R.: A multilevel algorithm for partitioning graphs. Technical report SAND93-1301 (October, 1993) · Zbl 0816.68093
[11] Karypis, G.; Kumar, V.: Analysis of multilevel graph partitioning. Technical report 95-037 (June, 1995)
[12] Karypis, G.; Kumar, V.: A fast and high quality multilevel scheme for partitioning irregular graphs. Technical report 95-035 (June, 1995)
[13] Keyes, D. E.; Saad, Y.; Truhlar, D. G.: Domain-based parallelism and problem decomposition methods in computational science and engineering. (1995) · Zbl 0829.00009
[14] Koobus, B.; Lallemand, M. H.; Dervieux, A.: Unstructured volume-agglomeration MG: solution of the Poisson equation. Rapport de recherche RR-1496 (June, 1993) · Zbl 0794.76068
[15] Lallemand, M. H.; Steve, H.; Dervieux, A.: Unstructured multigridding by volume agglomeration: current status. Computers and fluids 21, No. 3, 397-433 (1992) · Zbl 0753.76136
[16] Saad, Y.: ILUT: A dual threshold incomplete ILU factorization. Technical report 92-38 (1992) · Zbl 0838.65026
[17] Saad, Y.: SPARSKIT: A basic tool kit for sparse matrix computations. Users mannual (June, 1994)
[18] Schwarz, H. A.: 2nd edn. Gesammelte mathematishe abhandlungen. Gesammelte mathematishe abhandlungen 2, 133-143 (1890)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.