A numerical study on Neumann-Neumann methods for hp approximations on geometrically refined boundary layer meshes II. Three-dimensional problems

Andrea Toselli; Xavier Vasseur

ESAIM: Mathematical Modelling and Numerical Analysis (2006)

  • Volume: 40, Issue: 1, page 99-122
  • ISSN: 0764-583X

Abstract

top
In this paper, we present extensive numerical tests showing the performance and robustness of a Balancing Neumann-Neumann method for the solution of algebraic linear systems arising from hp finite element approximations of scalar elliptic problems on geometrically refined boundary layer meshes in three dimensions. The numerical results are in good agreement with the theoretical bound for the condition number of the preconditioned operator derived in [Toselli and Vasseur, IMA J. Numer. Anal.24 (2004) 123–156]. They confirm that the condition numbers are independent of the aspect ratio of the mesh and of potentially large jumps of the coefficients. Good results are also obtained for certain singularly perturbed problems. The condition numbers only grow polylogarithmically with the polynomial degree, as in the case of p approximations on shape-regular meshes [Pavarino, RAIRO: Modél. Math. Anal. Numér.31 (1997) 471–493]. This paper follows [Toselli and Vasseur, Comput. Methods Appl. Mech. Engrg.192 (2003) 4551–4579] on two dimensional problems.

How to cite

top

Toselli, Andrea, and Vasseur, Xavier. "A numerical study on Neumann-Neumann methods for hp approximations on geometrically refined boundary layer meshes II. Three-dimensional problems." ESAIM: Mathematical Modelling and Numerical Analysis 40.1 (2006): 99-122. <http://eudml.org/doc/249695>.

@article{Toselli2006,
abstract = { In this paper, we present extensive numerical tests showing the performance and robustness of a Balancing Neumann-Neumann method for the solution of algebraic linear systems arising from hp finite element approximations of scalar elliptic problems on geometrically refined boundary layer meshes in three dimensions. The numerical results are in good agreement with the theoretical bound for the condition number of the preconditioned operator derived in [Toselli and Vasseur, IMA J. Numer. Anal.24 (2004) 123–156]. They confirm that the condition numbers are independent of the aspect ratio of the mesh and of potentially large jumps of the coefficients. Good results are also obtained for certain singularly perturbed problems. The condition numbers only grow polylogarithmically with the polynomial degree, as in the case of p approximations on shape-regular meshes [Pavarino, RAIRO: Modél. Math. Anal. Numér.31 (1997) 471–493]. This paper follows [Toselli and Vasseur, Comput. Methods Appl. Mech. Engrg.192 (2003) 4551–4579] on two dimensional problems. },
author = {Toselli, Andrea, Vasseur, Xavier},
journal = {ESAIM: Mathematical Modelling and Numerical Analysis},
keywords = {Domain decomposition; preconditioning; hp finite elements; spectral elements; anisotropic meshes.; domain decomposition; hp finite elements; anisotropic meshes; numerical examples; singular perturbation; balancing Neumann-Neumann method; condition number; performance; robustness},
language = {eng},
month = {2},
number = {1},
pages = {99-122},
publisher = {EDP Sciences},
title = {A numerical study on Neumann-Neumann methods for hp approximations on geometrically refined boundary layer meshes II. Three-dimensional problems},
url = {http://eudml.org/doc/249695},
volume = {40},
year = {2006},
}

TY - JOUR
AU - Toselli, Andrea
AU - Vasseur, Xavier
TI - A numerical study on Neumann-Neumann methods for hp approximations on geometrically refined boundary layer meshes II. Three-dimensional problems
JO - ESAIM: Mathematical Modelling and Numerical Analysis
DA - 2006/2//
PB - EDP Sciences
VL - 40
IS - 1
SP - 99
EP - 122
AB - In this paper, we present extensive numerical tests showing the performance and robustness of a Balancing Neumann-Neumann method for the solution of algebraic linear systems arising from hp finite element approximations of scalar elliptic problems on geometrically refined boundary layer meshes in three dimensions. The numerical results are in good agreement with the theoretical bound for the condition number of the preconditioned operator derived in [Toselli and Vasseur, IMA J. Numer. Anal.24 (2004) 123–156]. They confirm that the condition numbers are independent of the aspect ratio of the mesh and of potentially large jumps of the coefficients. Good results are also obtained for certain singularly perturbed problems. The condition numbers only grow polylogarithmically with the polynomial degree, as in the case of p approximations on shape-regular meshes [Pavarino, RAIRO: Modél. Math. Anal. Numér.31 (1997) 471–493]. This paper follows [Toselli and Vasseur, Comput. Methods Appl. Mech. Engrg.192 (2003) 4551–4579] on two dimensional problems.
LA - eng
KW - Domain decomposition; preconditioning; hp finite elements; spectral elements; anisotropic meshes.; domain decomposition; hp finite elements; anisotropic meshes; numerical examples; singular perturbation; balancing Neumann-Neumann method; condition number; performance; robustness
UR - http://eudml.org/doc/249695
ER -

References

top
  1. Y. Achdou, P. Le Tallec, F. Nataf and M. Vidrascu, A domain decomposition preconditioner for an advection-diffusion problem. Comput. Methods Appl Mech. Engrg.184 (2000) 145–170.  Zbl0979.76043
  2. M. Ainsworth, A preconditioner based on domain decomposition for hp–FE approximation on quasi–uniform meshes. SIAM J. Numer. Anal.33 (1996) 1358–1376.  Zbl0855.65044
  3. B. Andersson, U. Falk, I. Babuška and T. von Petersdorff, Reliable stress and fracture mechanics analysis of complex aircraft components using a hp–version FEM. Int. J. Numer. Meth. Eng.38 (1995) 2135–2163.  Zbl0834.73064
  4. O. Axelsson, Iterative Solution Methods. Cambridge University Press (1994).  Zbl0795.65014
  5. I. Babuška and B. Guo, Approximation properties of the hp–version of the finite element method. Comput. Methods Appl. Mech. Engrg.133 (1996) 319–346.  Zbl0882.65096
  6. R. Barrett, M. Berry, T.F. Chan, J. Demmel, J. Donato, J. Dongarra, V. Eijkhout, R. Pozo, C. Romine and H. Van der Vorst, Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, 2nd edition. SIAM, Philadelphia, PA (1994).  
  7. M. Benzi, Preconditioning techniques for large linear systems: a survey. J. Comput. Phys.182 (2002) 418–477.  Zbl1015.65018
  8. M. Benzi and M. Tuma, A parallel solver for large-scale Markov chains. Appl. Numer. Math.41 (2002) 135–153.  Zbl0997.65006
  9. C. Bernardi and Y. Maday, Spectral methods. In Handbook of Numerical Analysis, North-Holland, Amsterdam Vol. V, Part 2 (1997) 209–485.  
  10. S. Beuchler, Multigrid solver for the inner problem in domain decomposition methods for p-fem. SIAM J. Numer. Anal.40 (2002) 928–944.  Zbl1030.65125
  11. A. Björck, Numerical methods for least-squares problems. SIAM (1996).  Zbl0847.65023
  12. R. Bridson and W.-P. Tang, Refining an approximate inverse. J. Comput. Appl. Math.123 (2000) 293–306.  Zbl0982.65035
  13. P. Brown and H. Walker, GMRES on (nearly) singular systems. SIAM J. Matrix Anal. Appl.18 (1997) 37–51.  Zbl0876.65019
  14. W. Cecot, W. Rachowicz and L. Demkowicz, An hp-adaptive finite element method for electromagnetics. III. a three-dimensional infinite element for Maxwell's equations. Internat. J. Numer. Methods Engrg.57 (2003) 899–921.  Zbl1034.78017
  15. E. Chow, A priori sparsity patterns for parallel sparse approximate inverse preconditioners. SIAM J. Sci. Comput.21 (2000) 1804–1822.  Zbl0957.65023
  16. M. Dryja and O.B. Widlund, Schwarz methods of Neumann-Neumann type for three-dimensional elliptic finite element problems. Comm. Pure Appl. Math.48 (1995) 121–155.  Zbl0824.65106
  17. M. Dryja, M.V. Sarkis and O.B. Widlund, Multilevel Schwarz methods for elliptic problems with discontinuous coefficients in three dimensions. Numer. Math.72 (1996) 313–348.  Zbl0857.65131
  18. C. Farhat and F.-X. Roux, Implicit parallel processing in structural mechanics, in Computational Mechanics Advances, J. Tinsley Oden Ed. North-Holland 2 (1994) 1–124.  Zbl0805.73062
  19. C. Farhat and F.-X. Roux, A method of finite element tearing and interconnecting and its parallel solution algorithm. Int. J. Numer. Meth. Engng.32 (1991) 1205–1227.  Zbl0758.65075
  20. D.R. Fokkema, G.L.G. Sleijpen and H.A. Van der Vorst, Jacobi-Davidson style QR and QZ algorithms for the reduction of matrix pencils. SIAM J. Sci. Comput.20 (1998) 94–125.  Zbl0924.65027
  21. P. Frauenfelder and C. Lage, An object oriented software package for partial differential equations. ESAIM: M2AN36 (2002) 937–951.  Zbl1032.65128
  22. R. Geus, The Jacobi-Davidson algorithm for solving large sparse symmetric eigenvalue problems with application to the design of accelerator cavities. Ph.D. thesis, ETH, Zürich, Institut für Wissenschaftliches Rechnen (2002).  
  23. G. Golub and C. Van Loan, Matrix Computations. The John Hopkins University Press (1996). Third edition.  
  24. G. Golub and Q. Ye, Inexact preconditioned conjugate gradient method with inner-outer iterations. SIAM J. Sci. Comput.21 (1999) 1305–1320.  Zbl0955.65022
  25. M. Grote and T. Huckle, Parallel preconditioning with sparse approximate inverses. SIAM J. Sci. Comput.18 (1997) 838–853.  Zbl0872.65031
  26. W.Z. Gui and I. Babuška, The h-, p- and hp-version of the Finite Element Method in one dimension, I: The error analysis of the p-version, II: The error analysis of the h- and hp-version, III: The adaptive hp-version. Numer. Math.49 (1986) 577–683.  Zbl0614.65088
  27. B. Guo and W. Cao, Additive Schwarz methods for the hp version of the finite element method in two dimensions. SIAM J. Scientific Comput.18 (1997) 1267–1288.  Zbl0892.65072
  28. R. Henderson, Dynamic refinement algorithms for spectral element methods. Comput. Methods Appl. Mech. Engrg. 175 (1999) 395–411.  Zbl0927.76077
  29. I.C.F. Ipsen and C.D. Meyer, The idea behind Krylov methods. Amer. Math. Monthly105 (1998) 889–899.  Zbl0982.65034
  30. G.E. Karniadakis and S. Sherwin, Spectral/hp Element Methods for CFD. Oxford University Press (1999).  Zbl0954.76001
  31. V. Korneev, J.E. Flaherty, J.T. Oden and J. Fish, Additive Schwarz algorithms for solving hp-version finite element systems on triangular meshes. Appl. Numer. Math43 (2002) 399–421.  Zbl1018.65126
  32. V. Korneev, U. Langer and L.S. Xanthis, On fast domain decomposition solving procedures for hp-discretizations of 3d elliptic problems. Comput. Methods Appl. Math.3 (2003) 536–559.  Zbl1038.65133
  33. P. Le Tallec and A. Patra, Non–overlapping domain decomposition methods for adaptive hp approximations of the Stokes problem with discontinuous pressure fields. Comput. Methods Appl. Mech. Engrg.145 (1997) 361–379.  Zbl0891.76053
  34. J.W. Lottes and P.F. Fischer, Hybrid Multigrid/Schwarz algorithms for the spectral element method. Technical report, Mathematics and Computer Science Division, Argonne National Laboratory (January 2003).  Zbl1078.65570
  35. J. Mandel and M. Brezina, Balancing domain decomposition for problems with large jumps in coefficients. Math. Comp.65 (1996) 1387–1401.  Zbl0853.65129
  36. J.M. Melenk and C. Schwab, hp–FEM for reaction–diffusion equations. I: Robust exponential convergence. SIAM J. Numer. Anal.35 (1998) 1520–1557.  Zbl0972.65093
  37. M. Melenk, hp-finite element methods for singular perturbations. Springer Verlag. Lect. Notes Math.1796 (2002).  Zbl1021.65055
  38. P. Monk, Finite element methods for Maxwell's equations. Numerical Mathematics and Scientific Computation, The Clarendon Press Oxford University Press, New York, 2003.  Zbl1024.78009
  39. R. Nicolaides, Deflation of conjugate gradients with application to boundary value problems. SIAM J. Numer. Anal.24 (1987) 355–36.  Zbl0624.65028
  40. J.T. Oden, A. Patra and Y. Feng, Parallel domain decomposition solver for adaptive hp finite element methods. SIAM J. Numer. Anal.34 (1997) 2090–2118.  Zbl0890.65124
  41. L.F. Pavarino, Neumann-Neumann algorithms for spectral elements in three dimensions. RAIRO: Modél. Math. Anal. Numér.31 (1997) 471–493.  Zbl0881.65121
  42. L.F. Pavarino and O.B. Widlund, Balancing Neumann-Neumann algorithms for incompressible Navier-Stokes equations. Commun. Pure Appl. Math.55 (2002) 302–335.  Zbl1024.76025
  43. A. Quarteroni and A. Valli, Numerical Approximation of Partial Differential Equations. Springer-Verlag, Berlin (1994).  Zbl0803.65088
  44. J. Ruge and K. Stüben, Algebraic multigrid, in Multigrid Methods, S. Mc Cormick Ed. SIAM Philadelphia (1987) 73–130.  
  45. Y. Saad, A flexible inner-outer preconditioned GMRES algorithm. SIAM J. Sci. Comput.14 (1993) 461–469.  Zbl0780.65022
  46. Y. Saad and M. Schultz, GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear system. SIAM J. Sci. Statist. Comput.7 (1986) 856–869.  Zbl0599.65018
  47. Y. Saad and B. Suchomel, Arms: an algebraic recursive multilevel solver for general sparse linear systems. Numer. Linear Algebra Appl.9 (2002) 359–378.  Zbl1071.65001
  48. M.V. Sarkis, Schwarz Preconditioners for Elliptic Problems with Discontinuous Coefficients Using Conforming and Non-Conforming Elements. Ph.D. thesis, Courant Institute, New York University, September (1994). TR671, Department of Computer Science, New York University, URL: file://cs.nyu.edu/pub/tech-reports/tr671.ps.Z.  Zbl0884.65119
  49. D. Schötzau and C. Schwab, Time discretization of parabolic problems by the hp-version of the discontinuous Galerkin finite element method. SIAM J. Numer. Anal.38 (2000) 837–875.  Zbl0978.65091
  50. C. Schwab, p– and hp– Finite Element Methods. Oxford Science Publications (1998).  Zbl0910.73003
  51. C. Schwab and M. Suri, The p and hp version of the finite element method for problems with boundary layers. Math. Comp.65 (1996) 1403–1429.  Zbl0853.65115
  52. C. Schwab, M. Suri and C.A. Xenophontos, The hp–FEM for problems in mechanics with boundary layers. Comput. Methods Appl. Mech. Engrg.157 (1998) 311–333.  Zbl0959.74073
  53. B.F. Smith, P.E. Bjørstad and W.D. Gropp, Domain Decomposition: Parallel Multilevel Methods for Elliptic Partial Differential Equations. Cambridge University Press (1996).  Zbl0857.65126
  54. P. Solin, K. Segeth and I. Dolezel, Higher-order finite element methods. Studies in Advanced Mathematics, Chapman and Hall, 2004.  
  55. A. Toselli, FETI domain decomposition methods for scalar advection-diffusion problems.Comput. Methods Appl. Mech. Engrg.190 (2001) 5759–5776.  Zbl1017.76048
  56. A. Toselli and X. Vasseur, Domain decomposition methods of Neumann-Neumann type for hp-approximations on geometrically refined boundary layer meshes in two dimensions. Technical Report 02–15, Seminar für Angewandte Mathematik, ETH, Zürich (September 2002). Submitted to Numerische Mathematik.  Zbl1054.65117
  57. A. Toselli and X. Vasseur, A numerical study on Neumann-Neumann and FETI methods for hp-approximations on geometrically refined boundary layer meshes in two dimensions. Comput. Methods Appl. Mech. Engrg. 192 (2003) 4551–4579.  Zbl1054.65117
  58. A. Toselli and X. Vasseur, Domain decomposition methods of Neumann-Neumann type for hp-approximations on boundary layer meshes in three dimensions. IMA J. Numer. Anal.24 (2004) 123–156.  Zbl1048.65125
  59. A. Toselli and O. Widlund, Domain Decomposition methods – Algorithms and Theory. Springer Series on Computational Mathematics, Springer 34 (2004).  Zbl1069.65138
  60. U. Trottenberg, C. Oosterlee and A. Schüller, Multigrid. Academic Press, London (2000). Guest contribution by Klaus Stüben: “An Introduction to Algebraic Multigrid”.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.