research-article

Algorithm 932: PANG: Software for nonmatching grid projections in 2D and 3D with linear complexity

Authors:

Martin J. Gander,

Caroline JaphetAuthors Info & Claims

ACM Transactions on Mathematical Software (TOMS), Volume 40, Issue 1

Article No.: 6, Pages 1 - 25

https://doi.org/10.1145/2513109.2513115

Published: 03 October 2013 Publication History

Abstract

We design and analyze an algorithm with linear complexity to perform projections between 2D and 3D nonmatching grids. This algorithm, named the PANG algorithm, is based on an advancing front technique and neighboring information. Its implementation is surprisingly short, and we give the entire Matlab code. For computing the intersections, we use a direct and numerically robust approach. We show numerical experiments both for 2D and 3D grids, which illustrate the optimal complexity and negligible overhead of the algorithm. An outline of this algorithm has already been presented in a short proceedings paper of the 18th International Conference on Domain Decomposition Methods (see Gander and Japhet [2008]).

Supplementary Material

ZIP File (932.zip)

Software for PANG: Software for nonmatching grid projections in 2D and 3D with linear complexity

Download
19.87 KB

References

[1]

Bastian, P., Buse, G., and Sander, O. 2010. Infrastructure for the coupling of Dune grids. In Proceedings of ENUMATH, G. Kreiss, P. Lötstedt, A. Møalqvist, and M. Neytcheva, Eds., Springer, Berlin, 107--114.

[2]

Belgacem, F. B. and Maday, Y. 1999. Coupling spectral and finite elements for second order elliptic three-dimensional equations. SIAM J. Numer. Anal. 36, 4, 1234--1263.

Digital Library

[3]

Belgacem, F. B. 1999. The mortar finite element method with Lagrange multipliers. Numer. Math. 84, 2, 173--197.

[4]

Bennequin, D., Gander, M., and Halpern, L. 2009. A homographic best approximation problem with application to optimized Schwarz waveform relaxation. Math. Comp. 78, 185--223.

[5]

Bernardi, C., Maday, Y., and Patera, A. T. 1993. Domain decomposition by the mortar element method. In Asymptotic and Numerical Methods for Partial Differential Equations with Critical Parameters, H. K. and M. Garbey, Eds., Vol. 384, N.A.T.O. ASI, Kluwer Academic Publishers, Dordrecht, Netherlands, 269--286.

[6]

Bernardi, C., Maday, Y., and Patera, A. T. 1994. A new nonconforming approach to domain decomposition: The mortar element method. In Collège de France Seminar, H. Brezis and J.-L. Lions, Eds., Pitman, London, UK.

[7]

Braess, D. and Dahmen, W. 1998. Stability estimates of the mortar finite element method for 3-dimensional problems. East-West J. Numer. Math. 6, 4, 249--263.

[8]

Brezzi, F., Lions, J.-L., and Pironneau, O. 2001. Analysis of a Chimera method. C.R. Math. Acad. Sci. Paris 332, 7, 655--660.

[9]

Brune, P., Knepley, M., and Scot, L. 2013. Unstructured geometric multigrid in two and three dimensions on complex and graded meshes. SIAM J. Sci. Comput.

[10]

DUNE. 2010. Distributed and unified numerics environment. www.dune-project.org/modules/dune-grid-glue/.

[11]

Flemisch, B., Kaltenbacher, M., and Wohlmuth, B. I. 2006. Elasto-acoustic and acoustic-acoustic coupling on nonmatching grids. Int. J. Num. Meth. Eng. 67, 13, 1791--1810.

[12]

Gander, M., Halpern, L., and Kern, M. 2007. Schwarz waveform relaxation method for advection--diffusion--reaction problems with discontinuous coefficients and non-matching grids. In Decomposition Methods in Science and Engineering XVI, O. Widlund and D. Keyes, Eds., Lecture Notes in Computational Science and Engineering, vol. 55, Springer, Berlin, Germany, 916--920.

[13]

Gander, M. and Japhet, C. 2008. An algorithm for non-matching grid projections with linear complexity. In Proceedings of the 18th International Domain Decomposition Conference, M. Bercovier, M. J. Gander, D. Keyes, and O. Widlund, Eds., Lecture Notes in Computational Science and Engineering, Springer, Berlin, Germany.

[14]

Gander, M., Japhet, C., Maday, Y., and Nataf, F. 2005. A new cement to glue nonconforming grids with robin interface conditions: The finite element case. In Proceedings of the 15th International Domain Decomposition Conference. R. Kornhuber, R. H. W. Hoppe, J. Périaux, O. Pironneau, O. B. Widlund, and J. Xu, Eds., Lecture Notes in Computational Science and Engineering, vol. 40, Springer, Berlin, Germany, 259--266.

[15]

Gander, M. J. 1997. Overlapping Schwarz for parabolic problems. In Proceedings of Ninth International Conference on Domain Decomposition Methods. P. E. Bjørstad, M. Espedal, and D. Keyes, Eds., 97--104.

[16]

Gander, M. J., Halpern, L., and Nataf, F. 1999. Optimal convergence for overlapping and nonoverlapping Schwarz waveform relaxation. In Proceedings of 11th International Conference of Domain Decomposition Methods. C.-H. Lai, P. Bjørstad, M. Cross, and O. Widlund, Eds.

[17]

Glowinski, R., He, J., Lozinski, A., Rappaz, J., and Wagner, J. 2005. Finite element approximation of multi-scale elliptic problems using patches of elements. Numer. Math. 101, 4, 663--687.

Digital Library

[18]

Greiner, G. and Hormann, K. 1998. Efficient clipping of arbitrary polygons. ACM Trans. Graph. 17, 2, 71--83.

Digital Library

[19]

Halpern, L., Japhet, C., and Szeftel, J. 2010. Discontinuous Galerkin and nonconforming in time optimized Schwarz waveform relaxation. In Domain Decomposition Methods in Science and Engineering XIX, Y. Huang, R. Kornhuber, O. Widlund, and J. Xu, Eds., Lecture Notes in Computational Science and Engineering, vol. 78, Springer, Berlin, Germany, 133--140.

[20]

Hecht, F. 2012. Freefem++. www.freefem.org/ff++/index.htm.

[21]

Jain, A. 2007. Efficient parallel algorithm for overlaying surface meshes. Ph.D. thesis, College of Computing, Georgia Institute of Technology.

[22]

Jiao, X. and Heath, M. T. 2004. Common-refinement-based data transfer between non-matching meshes in multiphysics simulations. Int. J. Num. Meths. Eng. 61, 2402--2427.

[23]

Jiao, X. M. 2001. Data transfer and interface propagation in multicomponent simulations. Ph.D. thesis, University of Illinois at Urbana-Champaign.

Digital Library

[24]

Kamga, J.-B. A. and Pironneau, O. 2007. Numerical zoom for multiscale problems with an application to nuclear waste disposal. J. Comput. Phys. 224, 403--413.

Digital Library

[25]

Lee, P., Yang, C.-H., and Yang, J.-R. 2004. Fast algorithms for computing self-avoiding walks and mesh intersections over unstructured meshes. Adv. Eng. Soft. 35, 61--73.

Digital Library

[26]

Löhner, R. 2001. Applied CFD Techniques: An Introduction Based on Finite Element Methods. Wiley, Chichester, UK.

[27]

Martin, V. 2005. An optimized Schwarz waveform relaxation method for unsteady convection diffusion equation. Appl. Numer. Math. 52, 4, 401--428.

Digital Library

[28]

Meakin, R. L. 1991. A new method for establishing intergrid communication among systems of overset grids. In Proceedings of the 10^th AIAA Computational Fluid Dynamics Conference. 662--671.

[29]

MPCCI. 2013. Metalmapper for integrated Design Workflows - Mapping of Manufacturing and CFD Simulations Results to Crash and NVH Calculations. www.mpcci.de/.

[30]

Picasso, M., Rappaz, J., and Rezzonico, V. 2008. Multiscale algorithm with patches of finite elements. Comm. Num. Meth. Eng. 24, 6, 477--491.

[31]

Plimpton, S., Hendrickson, B., and Stewart, J. 1998. A parallel rendezvous algorithm for interpolation between multiple grids. In Proceedings of the ACM/IEEE Conference on Supercomputing. IEEE Computer Society, Los Alamitos, CA, 8.

Digital Library

[32]

Shewchuk, J. R. 1997. Adaptive precision floating-point arithmetic and fast robust geometric predicates. Comput. Geom. 18, 3, 305--363.

[33]

Steger, J. L., Dougherty, F. C., and Benek, J. A. 1983. A chimera grid scheme, advances in grid generation. In Advances in Grid Generation, K. Ghia and U. Ghia, Eds., FED, vol. 5, ASME, New York, NY, 59--69.

[34]

Weiler, K. and Atherton, P. 1977. Hidden surface removal using polygon area sorting. In Proceedings of the 4th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH). ACM, New York, NY, 214--222.

Digital Library

Cited By

Sasidharan AEvans KSchenk O(2024)Parallel Algorithms for Intersection ComputationProceedings of the Platform for Advanced Scientific Computing Conference10.1145/3659914.3659929(1-11)Online publication date: 3-Jun-2024
https://dl.acm.org/doi/10.1145/3659914.3659929
Cao YHoang THuynh P(2024)Monolithic and local time-stepping decoupled algorithms for transport problems in fractured porous mediaIMA Journal of Numerical Analysis10.1093/imanum/drae005Online publication date: 3-Apr-2024
https://doi.org/10.1093/imanum/drae005
Gómez-Molina PSanz-Lorenzo LCarpio J(2024)A stable conservative Lagrange-Galerkin scheme to pure convection equations with mesh intersectionJournal of Computational Physics10.1016/j.jcp.2023.112625497(112625)Online publication date: Jan-2024
https://doi.org/10.1016/j.jcp.2023.112625
Show More Cited By

Index Terms

Algorithm 932: PANG: Software for nonmatching grid projections in 2D and 3D with linear complexity

Recommendations

Modified Berlekamp-Massey Algorithm for Approximating the k-Error Linear Complexity of Binary Sequences
Cryptography and Coding
Abstract
Some cryptographical applications use pseudorandom sequences and require that the sequences are secure in the sense that they cannot be recovered by only knowing a small amount of consecutive terms. Such sequences should therefore have a large ...
Modified Berlekamp-Massey algorithm for approximating the k-error linear complexity of binary sequences
Cryptography and Coding'07: Proceedings of the 11th IMA international conference on Cryptography and coding

Some cryptographical applications use pseudorandom sequences and require that the sequences are secure in the sense that they cannot be recovered by only knowing a small amount of consecutive terms. Such sequences should therefore have a large linear ...
Computing the linear complexity for sequences with characteristic polynomial fv

We present several generalisations of the Games---Chan algorithm. For a fixed monic irreducible polynomial f we consider the sequences s that have as a characteristic polynomial a power of f. We propose an algorithm for computing the linear complexity ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Mathematical Software

ACM Transactions on Mathematical Software Volume 40, Issue 1

September 2013

165 pages

ISSN:0098-3500

EISSN:1557-7295

DOI:10.1145/2513109

Issue’s Table of Contents

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 October 2013

Accepted: 01 March 2013

Revised: 01 January 2013

Received: 01 April 2012

Published in TOMS Volume 40, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Agence Nationale de la Recherche

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

28
Total Citations
View Citations
266
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)1

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Sasidharan AEvans KSchenk O(2024)Parallel Algorithms for Intersection ComputationProceedings of the Platform for Advanced Scientific Computing Conference10.1145/3659914.3659929(1-11)Online publication date: 3-Jun-2024
https://dl.acm.org/doi/10.1145/3659914.3659929
Cao YHoang THuynh P(2024)Monolithic and local time-stepping decoupled algorithms for transport problems in fractured porous mediaIMA Journal of Numerical Analysis10.1093/imanum/drae005Online publication date: 3-Apr-2024
https://doi.org/10.1093/imanum/drae005
Gómez-Molina PSanz-Lorenzo LCarpio J(2024)A stable conservative Lagrange-Galerkin scheme to pure convection equations with mesh intersectionJournal of Computational Physics10.1016/j.jcp.2023.112625497(112625)Online publication date: Jan-2024
https://doi.org/10.1016/j.jcp.2023.112625
van’t Wout E(2024)The boundary element method for acoustic transmission with nonconforming gridsJournal of Computational and Applied Mathematics10.1016/j.cam.2024.115838(115838)Online publication date: Feb-2024
https://doi.org/10.1016/j.cam.2024.115838
Antolin PBuffa ACirillo E(2023)Region Extraction in Mesh IntersectionComputer-Aided Design10.1016/j.cad.2022.103448156(103448)Online publication date: Mar-2023
https://doi.org/10.1016/j.cad.2022.103448
Huynh PCao YHoang T(2023)Fast and Accuracy-Preserving Domain Decomposition Methods for Reduced Fracture Models with Nonconforming Time GridsJournal of Scientific Computing10.1007/s10915-023-02251-096:1Online publication date: 29-May-2023
https://dl.acm.org/doi/10.1007/s10915-023-02251-0
Mahadevan VGuerra JJiao XKuberry PLi YUllrich PMarsico DJacob RBochev PJones P(2022)Metrics for Intercomparison of Remapping Algorithms (MIRA) protocol applied to Earth system modelsGeoscientific Model Development10.5194/gmd-15-6601-202215:17(6601-6635)Online publication date: 2-Sep-2022
https://doi.org/10.5194/gmd-15-6601-2022
Mccoid CGander M(2022)A Provably Robust Algorithm for Triangle-triangle Intersections in Floating-point ArithmeticACM Transactions on Mathematical Software10.1145/351326448:2(1-30)Online publication date: 26-May-2022
https://dl.acm.org/doi/10.1145/3513264
Hoang T(2022)Fully implicit local time-stepping methods for advection-diffusion problems in mixed formulationsComputers & Mathematics with Applications10.1016/j.camwa.2022.05.022118:C(248-264)Online publication date: 15-Jul-2022
https://dl.acm.org/doi/10.1016/j.camwa.2022.05.022
Moro FCodecasa L(2021)Domain Decomposition With Non-Conforming Polyhedral GridsIEEE Access10.1109/ACCESS.2020.30471539(1465-1481)Online publication date: 2021
https://doi.org/10.1109/ACCESS.2020.3047153
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents