×

Data-sparse algebraic multigrid methods for large scale boundary element equations. (English) Zbl 1073.65135

Summary: This paper presents new algebraic multigrid (AMG) preconditioners for data-sparse boundary element matrices arising from the adaptive cross approximation (ACA) to dense boundary element matrices. Here we mainly consider the single layer potential integral equation, resulting from the direct boundary integral formulation of the interior, or exterior Dirichlet boundary value problems for the Laplace equation in two, or three spatial dimensions, as the most interesting boundary integral equation.
The standard collocation, or Galerkin boundary element discretizations lead to fully populated system matrices which require \(O(N_{h}^2)\) of storage units and cause the same complexity for a single matrix-by-vector multiplication, where \(N_h\) denotes the number of boundary unknowns. Data-sparse matrix approximation schemes such as ACA reduce this complexity to an almost linear behavior in \(N_h\). Since the single layer potential operator is a pseudo-differential operator of the order -1, the resulting boundary element matrices have large condition numbers on fine meshes. Iterative solvers dramatically suffer from this property for growing \(N_h\).
Our AMG-preconditioners avoid the increase of the iteration numbers and result in almost optimal solvers with respect to the total complexity. This behavior is confirmed by our numerical experiments. Let us mention that our AMG-preconditioners use only single grid information provided by the ACA system matrix and by the usual mesh data on the finest level anyway. Similar results are valid for the hypersingular integral operator that is easier to handle since it is a pseudo-differential operator of the order +1.

MSC:

65N38 Boundary element methods for boundary value problems involving PDEs
65N55 Multigrid methods; domain decomposition for boundary value problems involving PDEs
35J05 Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation
65F35 Numerical computation of matrix norms, conditioning, scaling

Software:

OSTBEM
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adams, R. A., Sobolev Spaces, Pure and Applied Mathematics (1975), Academic Press: Academic Press New York · Zbl 0186.19101
[2] M. Bebendorf, Effiziente numerische Lösung von Randintegralgleichungen unter Verwendung von Niedrigrang-Matrizen, Ph.D. Thesis, Universität Saarbrücken, 2000; M. Bebendorf, Effiziente numerische Lösung von Randintegralgleichungen unter Verwendung von Niedrigrang-Matrizen, Ph.D. Thesis, Universität Saarbrücken, 2000
[3] Bebendorf, M., Approximation of boundary element matrices, Numer. Math., 86, 565-589 (2000) · Zbl 0966.65094
[4] Bebendorf, M.; Rjasanov, S., Adaptive low-rank approximation of collocation matrices, Computing, 70, 1, 1-24 (2003) · Zbl 1068.41052
[5] Braess, D., Towards algebraic multigrid for elliptic problems of second order, Computing, 55, 379-393 (1995) · Zbl 0844.65088
[6] Bramble, J. H.; Leyk, Z.; Pasciak, J. E., The analysis of multigrid algorithms for pseudo-differential operators of order minus one, Math. Comp., 63, 208, 461-478 (1994) · Zbl 0812.65110
[7] Brandt, A., Algebraic multigrid theory: the symmetric case, Appl. Math. Comput., 19, 23-56 (1986) · Zbl 0616.65037
[8] Brandt, A., General highly accurate algebraic coarsening, Electron. Trans. Numer. Anal., 10, 1-20 (2000) · Zbl 0951.65096
[9] A. Brandt, S. McCormick, J.W. Ruge, Algebraic multigrid (AMG) for automatic multigrid solution with application to geodetic computations, Report, Inst. Comp. Studies Colorado State Univ., 1982; A. Brandt, S. McCormick, J.W. Ruge, Algebraic multigrid (AMG) for automatic multigrid solution with application to geodetic computations, Report, Inst. Comp. Studies Colorado State Univ., 1982
[10] Carrier, J.; Greengard, L.; Rokhlin, V., A fast adaptive multipole algorithm for particle simulations, SIAM J. Sci. Statist. Comput., 9, 4, 669-686 (1988) · Zbl 0656.65004
[11] Chen, G.; Zhou, J., Boundary Element Methods, Computational Mathematics and Applications (1992), Academic Press: Academic Press New York
[12] G. Haase, U. Langer, S. Reitzinger, J. Schöberl, A General Approach to Algebraic Multigrid, SFB-Report 00-33, Johannes Kepler University Linz, SFB Numerical and Symbolic Scientific Computing, http://www.sfb013.uni-linz.ac.at/ sfb/reports/2000/ps-files (2000); G. Haase, U. Langer, S. Reitzinger, J. Schöberl, A General Approach to Algebraic Multigrid, SFB-Report 00-33, Johannes Kepler University Linz, SFB Numerical and Symbolic Scientific Computing, http://www.sfb013.uni-linz.ac.at/ sfb/reports/2000/ps-files (2000)
[13] Hackbusch, W., A sparse matrix arithmetic based on \(H\)-matrices, Computing, 62, 2, 89-108 (1999) · Zbl 0927.65063
[14] Hackbusch, W., Multigrid Methods and Application (1985), Springer: Springer Berlin · Zbl 0577.65118
[15] Hackbusch, W.; Nowak, Z. P., On the fast matrix multiplication in the boundary element method by panel clustering, Numer. Math., 54, 4, 463-491 (1989) · Zbl 0641.65038
[16] Jung, M.; Langer, U., Applications of multilevel methods to practical problems, Surveys Math. Indust., 1, 217-257 (1991) · Zbl 0743.65031
[17] Kickinger, F., Algebraic multigrid for discrete elliptic second-order problems, (Hackbusch, W., Multigrid Methods V, Proceedings of the 5th European Multigrid Conference. Multigrid Methods V, Proceedings of the 5th European Multigrid Conference, Springer Lecture Notes in Computational Science and Engineering, vol. 3 (1998), Springer: Springer Berlin), 157-172 · Zbl 0926.65128
[18] Lage, C.; Schwab, C., Wavelet Galerkin algorithms for bondary integral equations, SIAM J. Sci. Comput., 20, 2195-2222 (1999) · Zbl 0943.65134
[19] Langer, U.; Pusch, D.; Reitzinger, S., Efficient preconditioners for boundary element matrices based on grey-box algebraic multigrid methods, Internat. J. Numer. Methods Engrg., 58, 13, 1937-1953 (2003) · Zbl 1035.65144
[20] U. Langer, W. Queck, Preconditioned Uzawa-type iterative methods for solving mixed finite element equations, 3/1987, Wissenschaftliche Schriftenreihe der TU Karl-Marx-Stadt, Karl-Marx-Stadt, 1987; U. Langer, W. Queck, Preconditioned Uzawa-type iterative methods for solving mixed finite element equations, 3/1987, Wissenschaftliche Schriftenreihe der TU Karl-Marx-Stadt, Karl-Marx-Stadt, 1987 · Zbl 0619.65052
[21] Langer, U.; Steinbach, O., Boundary element tearing and interconnecting methods, Computing, 71, 3, 205-228 (2003) · Zbl 1037.65123
[22] Meurant, G., Computer Solution of Large Linear Systems, (Studies in Mathematics and its Applications, vol. 28 (1999), Elsevier: Elsevier Amsterdam) · Zbl 0934.65032
[23] Reitzinger, S., Algebraic Multigrid Methods for Large Scale Finite Element Equations, Reihe C—Technik und Naturwissenschaften (2001), Universitätsverlag Rudolf Trauner: Universitätsverlag Rudolf Trauner Linz
[24] Rokhlin, V., Rapid solution of integral equations of classical potential theory, J. Comput. Phys., 60, 2, 187-207 (1985) · Zbl 0629.65122
[25] Ruge, J. W.; Stüben, K., Algebraic multigrid (AMG), (McCormick, S., Multigrid Methods. Multigrid Methods, Frontiers in Applied Mathematics, vol. 5 (1986), SIAM: SIAM Philadelphia, PA), 73-130
[26] Ruge, J. W.; Stüben, K., Efficient solution of finite difference and finite element equations, (Paddon, D.; Holstein, H., Multigrid Methods for Integral and Differential Equations, vol. 3 (1985), Clarendon: Clarendon Oxford), 169-212 · Zbl 0581.65072
[27] Steinbach, O., Numerische Näherungsverfahren für elliptische Randwertprobleme: Finite Elemente und Randelemente (2003), Teubner-Verlag: Teubner-Verlag Stuttgart · Zbl 1130.65001
[28] Steinbach, O., OSTBEM—A Boundary Element Software Package (2000), University of Stuttgart
[29] O. Steinbach, Gebietszerlegungsmethoden mit Randintegralgleichungen und effiziente numerische Lösungsverfahren für gemischte Randwertprobleme, Ph.D. Thesis, University of Stuttgart, 1996; O. Steinbach, Gebietszerlegungsmethoden mit Randintegralgleichungen und effiziente numerische Lösungsverfahren für gemischte Randwertprobleme, Ph.D. Thesis, University of Stuttgart, 1996 · Zbl 0863.65079
[30] Vanek, P.; Mandel, J.; Brezina, M., Algebraic multigrid by smoothed aggregation for second and fourth order elliptic problems, Computing, 56, 179-196 (1996) · Zbl 0851.65087
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.