More Web Proxy on the site http://driver.im/

research-article

Quasi-matrix-free Hybrid Multigrid on Dynamically Adaptive Cartesian Grids

Authors:

Marion Weinzierl,

Tobias WeinzierlAuthors Info & Claims

ACM Transactions on Mathematical Software (TOMS), Volume 44, Issue 3

Article No.: 32, Pages 1 - 44

https://doi.org/10.1145/3165280

Published: 06 February 2018 Publication History

Abstract

We present a family of spacetree-based multigrid realizations using the tree’s multiscale nature to derive coarse grids. They align with matrix-free geometric multigrid solvers as they never assemble the system matrices, which is cumbersome for dynamically adaptive grids and full multigrid. The most sophisticated realizations use BoxMG to construct operator-dependent prolongation and restriction in combination with Galerkin/Petrov-Galerkin coarse-grid operators. This yields robust solvers for nontrivial elliptic problems. We embed the algebraic, problem-dependent, and grid-dependent multigrid operators as stencils into the grid and evaluate all matrix-vector products in situ throughout the grid traversals. Such an approach is not literally matrix-free as the grid carries the matrix. We propose to switch to a hierarchical representation of all operators. Only differences of algebraic operators to their geometric counterparts are held. These hierarchical differences can be stored and exchanged with small memory footprint. Our realizations support arbitrary dynamically adaptive grids while they vertically integrate the multilevel operations through spacetree linearization. This yields good memory access characteristics, while standard colouring of mesh entities with domain decomposition allows us to use parallel many-core clusters. All realization ingredients are detailed such that they can be used by other codes.

References

[1]

M. F. Adams, J. Brown, M. Knepley, and R. Samtaney. 2016. Segmental refinement: A multigrid technique for data locality. SIAM J. Sci. Comput. 38, 4 (2016), C426--C440.

[2]

Advanced Scientific Computing Advisory Committee (ASCAC) Subcommittee. 2010. The Opportunities and Challenges of Exascale Computing. (2010). Retrieved from https://science.energy.gov/&sim;/media/ascr/ascac/pdf/reports/Exascale_subcomm ittee_report.pdf.

[3]

A. AlOnazi, G. S. Markomanolis, and D. Keyes. 2017. Asynchronous task-based parallelization of algebraic multigrid. In Proceedings of the Platform for Advanced Scientific Computing Conference (PASC’17). ACM, 5:1--5:11.

Digital Library

[4]

M. Bader. 2013. Space-Filling Curves—An Introduction with Applications in Scientific Computing. Texts in Computational Science and Engineering, Vol. 9. Springer-Verlag.

Digital Library

[5]

M. Bader, S. Schraufstetter, C. A. Vigh, and J. Behrens. 2008. Memory efficient adaptive mesh generation and implementation of multigrid algorithms using sierpinski curves. Int. J. Comput. Sci. Eng. 4, 1 (2008), 12--21.

Digital Library

[6]

A. B. Baker, R. D. Falgout, T. V. Kolev, and U. Meier Yang. 2011. Multigrid smoothers for ultraparallel computing. SIAM J. Sci. Comput. 33, 5 (2011), 2864--2887.

Digital Library

[7]

S. Balay and others. 2016. PETSc Web page. Retrieved from http://www.mcs.anl.gov/petsc.

[8]

P. Bastian, W. Hackbusch, and G. Wittum. 1998. Additive and multiplicative multi-grid: A comparison. Computing 60, 4 (1998), 345--364.

Digital Library

[9]

A. Behie and P. A. Forsyth, Jr. 1983. Multi-grid solution of three-dimensional problems with discontinuous coefficients. Appl. Math. Comput. 13, 3--4 (1983), 229--240.

Digital Library

[10]

A. Brandt. 1977. Multi-level adaptive solutions to boundary-value problems. Math. Comput. 31 (1977), 333--390.

[11]

A. Brandt and O. E. Livne. 2011. Multigrid techniques—1984 guide with applications to fluid dynamics. Classics in Applied Mathematics, 67, SIAM.

[12]

H.-J. Bungartz, W. Eckhardt, T. Weinzierl, and C. Zenger. 2010. A precompiler to reduce the memory footprint of multiscale PDE solvers in C++. Future Gen. Comput. Syst. 26, 1 (2010), 175--182.

Digital Library

[13]

C. Burstedde, L. C. Wilcox, and O. Ghattas. 2011. p4est: Scalable algorithms for parallel adaptive mesh refinement on forests of octrees. SIAM J. Sci. Comput. 33, 3 (2011), 1103--1133.

Digital Library

[14]

D. E. Charrier and T. Weinzierl. 2017. An experience report on (auto-)tuning of mesh-based PDE solvers on shared memory systems. In Proceedings of the Conference on Parallel Processing and Applied Mathematics (PPAM’17), R. Wyrzykowski, J. Dongarra, K. Karczewski, and J. Wasniewski (Eds.). (accepted).

[15]

A. J. Cleary et al. 2000. Robustness and scalability of algebraic multigrid. SIAM J. Sci. Comput. 21, 5 (2000), 1886--1908.

Digital Library

[16]

J. E. Dendy. 1982. Black box multigrid. J. Comput. Phys. 48, 3 (1982), 366--386.

[17]

J. E. Dendy. 1983. Black box multigrid for nonsymmetric problems. Appl. Math. Comput. 13, 3--4 (1983), 261--283.

Digital Library

[18]

J. E. Dendy. 1987. Two multigrid methods for three-dimensional problems with discontinuous and anisotropic coefficients. SIAM J. Sci. Statist. Comput. 8, 5 (1987), 673--685.

[19]

J. E. Dendy. 1988. Black box multigrid for periodic and singular problems. Appl. Math. Comput. 25, 1 (1988), 1--10.

Digital Library

[20]

J. E. Dendy and J. D. Moulton. 2010. Black box multigrid with coarsening by a factor of three. Numer. Lin. Alg. Appl. 17 (2010), 577--598.

[21]

J. Dongarra et al. 2016. A Proposed API for Batched Basic Linear Algebra Subprograms. Technical Report 2016.25. University of Manchester. Retrieved from http://eprints.ma.man.ac.uk/2464/1/covered/MIMS\ep2016\25.pdf.

[22]

J. Dongarra, J. Hittinger, et al. 2014. Applied Mathematics Research for Exascale Computing. Technical Report. DOE ASCR Exascale Mathematics Working Group: Retrieved from http://www.netlib.org/utk/people/JackDongarra/PAPERS/doe-exascale-math-report.pdf.

[23]

W. Eckhardt, R. Glas, D. Korzh, S. Wallner, and T. Weinzierl. 2016. On-the-fly memory compression for multibody algorithms. In Proceedings of the International Conference on Parallel Computing (ParCo’15), G. R. Joubert, H. Leather, M. Parsons, F. Peters, and M. Sawyer (Eds.), Vol. 27. IOS Press, 421--430.

[24]

W. Eckhardt and T. Weinzierl. 2010. A blocking strategy on multicore architectures for dynamically adaptive PDE solvers. In Proceedings of the Conference on Parallel Processing and Applied Mathematics (PPAM’09) (LNCS), R. Wyrzykowski, J. Dongarra, K. Karczewski, and J. Wasniewski (Eds.), Vol. 6068. Springer-Verlag, 567--575.

Digital Library

[25]

C. Feichtinger, S. Donath, H. Köstler, J. Götz, and U. Rüde. 2011. WaLBerla: HPC software design for computational engineering simulations. J. Comput. Sci. 2, 2 (2011), 105--112.

[26]

P. Ghysels and W. Vanroose. 2015. Modeling the performance of geometric multigrid stencils on multicore computer architectures. SIAM J. Sci. Comput. 37, 2 (2015), C194--C216.

[27]

B. Gmeiner, H. Köstler, M. Stürmer, and U. Rüde. 2014. Parallel multigrid on hierarchical hybrid grids: A performance study on current high performance computing clusters. Concurr. Comput.: Pract. Exper. 26, 1 (2014), 217--240.

[28]

B. Gmeiner, U. Rüde, H. Stengel, C. Waluga, and B. Wohlmuth. 2015. Towards textbook efficiency for parallel multigrid. Numer. Math. Theory Methods Appl. 8 (2015), 22--46. Issue 01.

[29]

M. Griebel. 1990. Zur Lösung von Finite-Differenzen- und Finite-Element-Gleichungen mittels der Hiearchischen-Transformations-Mehrgitter-Methode. PhD thesis. TU München.

[30]

M. Griebel. 1994. Multilevelmethoden als Iterationsverfahren über Erzeugendensystemen. Habilitation Thesis. TU München.

[31]

M. Griebel and G. Zumbusch. 1999. Parallel multigrid in an adaptive PDE solver based on hashing and space-filling curves. Parallel Comput. 25, 7 (July 1999), 827--843.

Digital Library

[32]

L. B. Hart, S. F. McCormick, A. O’Gallagher, and J. W. Thomas. 1986. The fast adaptive composite-grid method (FAC): Algorithms for advanced computers. Appl. Math. Comput. 19, 1--4 (1986), 103--126.

Digital Library

[33]

T. Huckle. 2008. Compact fourier analysis for designing multigrid methods. SIAM J. Sci. Comput. 31, 1 (2008), 644--666.

Digital Library

[34]

J. King, T. Gilray, R. M. Kirby, and M. Might. 2016. Dynamic sparse-matrix allocation on GPUs. In Proceedings of ISC High Performance 2016. 61--80.

[35]

C. Lu, X. Jiao, and N. M. Missirlis. 2014. A hybrid geometric + algebraic multigrid method with semi-iterative smoothers. Numer. Lin. Alg. Appl. 21, 2 (2014), 221--238.

[36]

S. P. MacLachlan, J. D. Moulton, and T. P. Chartier. 2012. Robust and adaptive multigrid methods: Comparing structured and algebraic approaches. Numer. Lin. Alg. Appl. 19, 2 (2012), 389--413.

[37]

T. Malas, G. Hager, H. Ltaief, and D. Keyes. 2015. Multi-dimensional intra-tile parallelization for memory-starved stencil computations. CoRR abs/1510.04995 (2015).

[38]

J. D. McCalpin. 1995. Memory bandwidth and machine balance in current high performance computers. IEEE Computer Society Technical Committee on Computer Architecture (TCCA) Newsletter (1995), 19--25.

[39]

S. F. McCormick. 1989. Multilevel Adaptive Methods for Partial Differential Equations. SIAM.

Digital Library

[40]

M. Mehl, T. Weinzierl, and C. Zenger. 2006. A cache-oblivious self-adaptive full multigrid method. Numer. Lin. Alg. Appl. 13, 2--3 (2006), 275--291.

[41]

J. D. Moulton, J. E. Dendy, and J. M. Hyman. 1998. The black box multigrid numerical homogenization algorithm. J. Comput. Phys. 142, 1 (1998), 80--108.

Digital Library

[42]

B. Reps and T. Weinzierl. 2017. A complex additive geometric multigrid solver for the Helmholtz equations on spacetrees. ACM Trans. Math. Software 44, 1 (2017), 2:1--2:36.

Digital Library

[43]

J. Rudi, A. C. I. Malossi, T. Isaac, G. Stadler, M. Gurnis, P. W. J. Staar, Y. Ineichen, C. Bekas, A. Curioni, and O. Ghattas. 2015. An extreme-scale implicit solver for complex PDEs: Highly heterogeneous flow in earth’s mantle. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC’15). ACM, New York, NY, 5:1--5:12.

Digital Library

[44]

R. S. Sampath, S. S. Adavani, H. Sundar, I. Lashuk, and G. Biros. 2008. Dendro: Parallel algorithms for multigrid and AMR methods on 2:1 balanced octrees. In Proceedings of the 2008 ACM/IEEE Conference on Supercomputing (SC’08). IEEE Press, Piscataway, NJ, 18:1--18:12.

Digital Library

[45]

M. Schreiber, T. Weinzierl, and H.-J. Bungartz. 2013. Cluster optimization and parallelization of simulations with dynamically adaptive grids. In Proceedings Euro-Par 2013 (Lecture Notes in Computer Science), F. Wolf, B. Mohr, and D. an Mey (Eds.), Vol. 8097. Springer-Verlag, Berlin, 484--496.

Digital Library

[46]

T. Scott. 1985. Multi-grid methods for oil reservoir simulation in two and three dimensions. J. Comput. Phys. 59, 2 (1985), 290--307.

[47]

Y. Shapira. 2003. Matrix-Based Multigrid. Kluwer.

[48]

K. Stüben. 2001. Appendix A: An introduction to algebraic multigrid. In Multigrid, U. Trottenberg, C. W. Oosterlee, and A. Schüller (Eds.). Elsevier Science Inc.

[49]

H. Sundar, G. Biros, C. Burstedde, J. Rudi, O. Ghattas, and G. Stadler. 2012. Parallel geometric-algebraic multigrid on unstructured forests of octrees. In Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis (SC’12). IEEE Computer Society Press, Los Alamitos, CA, 43:1--43:11.

Digital Library

[50]

H. Sundar, R. S. Sampath, and G. Biros. 2008. Bottom-up construction and 2:1 balance refinement of linear octrees in parallel. SIAM J. Sci. Comput. 30, 5 (2008), 2675--2708.

Digital Library

[51]

E. Treister and I. Yavneh. 2010. Square and stretch multigrid for stochastic matrix eigenproblems. Numer. Lin. Alg. Appl. 17, 2–3 (2010), 229--251.

[52]

U. Trottenberg, C. W. Oosterlee, and A. Schüller. 2001. Multigrid. Academic Press.

Digital Library

[53]

M. Weinzierl. 2013. Hybrid Geometric-Algebraic Matrix-Free Multigrid on Spacetrees. PhD Thesis. TU München.

[54]

T. Weinzierl. 2009. A Framework for Parallel PDE Solvers on Multiscale Adaptive Cartesian Grids. Verlag Dr. Hut.

[55]

T. Weinzierl. 2017. The Peano software—Parallel, automaton-based, dynamically adaptive grid traversals. Technical Report. arXiv:1506.04496.

[56]

T. Weinzierl et al. 2012. Peano—a Framework for PDE Solvers on Spacetree Grids. Retrieved from http://www.peano-framework.orgwww.peano-framework.org.

[57]

T. Weinzierl, M. Bader, K. Unterweger, and R. Wittmann. 2014. Block fusion on dynamically adaptive spacetree grids for shallow water waves. Parallel Process. Lett. 24, 3 (2014), 1441006.

[58]

T. Weinzierl and M. Mehl. 2011. Peano -- A traversal and storage scheme for octree-like adaptive cartesian multiscale grids. SIAM J. Sci. Comput. 33, 5 (2011), 2732--2760.

Digital Library

[59]

R. Wienands and H. Köstler. 2010. A practical framework for the construction of prolongation operators for multigrid based on canonical basis functions. Comput. Visual. Sci. 13 (2010), 207--220. Issue 5.

Digital Library

[60]

I. Yavneh. 1998. Coarse-grid correction for nonelliptic and singular perturbation problems. SIAM J. Sci. Comput. 19, 5 (1998), 1682--1699.

Digital Library

[61]

I. Yavneh and M. Weinzierl. 2012. Nonsymmetric black box multigrid with coarsening by three. Numer. Lin. Alg. Appl. 19, 2 (2012), 246--262.

Cited By

Charrier DHazelwood BWeinzierl T(2020)Enclave Tasking for DG Methods on Dynamically Adaptive MeshesSIAM Journal on Scientific Computing10.1137/19M127619442:3(C69-C96)Online publication date: 5-May-2020
https://doi.org/10.1137/19M1276194
Reinarz ACharrier DBader MBovard LDumbser MDuru KFambri FGabriel AGallard JKöppel SKrenz LRannabauer LRezzolla LSamfass PTavelli MWeinzierl T(2020)ExaHyPE: An engine for parallel dynamically adaptive simulations of wave problemsComputer Physics Communications10.1016/j.cpc.2020.107251(107251)Online publication date: Mar-2020
https://doi.org/10.1016/j.cpc.2020.107251
Murray CWeinzierl T(2020)Lazy Stencil Integration in Multigrid AlgorithmsParallel Processing and Applied Mathematics10.1007/978-3-030-43229-4_3(25-37)Online publication date: 19-Mar-2020
https://doi.org/10.1007/978-3-030-43229-4_3
Show More Cited By

Index Terms

Quasi-matrix-free Hybrid Multigrid on Dynamically Adaptive Cartesian Grids

Recommendations

Multigrid Methods on Adaptively Refined Grids

Using multigrid solvers in the adaptive finite element method yields a powerful tool for solving large-scale partial differential equations that exhibit localized features such as singularities or shocks. In addition to describing the basic method and ...
A Comparison of Algebraic Multigrid and Geometric Immersed Interface Multigrid Methods for Interface Problems

In [L. Adams and Z. Li, SIAM J. Sci. Comput., 24 (2002), pp. 463--479], a multigrid method was designed specifically for interface problems that have been discretized using the methods described in [L. Adams and Z. Li, SIAM J. Sci. Comput., 24 (2002), pp. ...
A Multigrid Method on Non-Graded Adaptive Octree and Quadtree Cartesian Grids

In order to develop efficient numerical methods for solving elliptic and parabolic problems where Dirichlet boundary conditions are imposed on irregular domains, Chen et al. (J. Sci. Comput. 31(1):19---60, 2007) presented a methodology that produces ...

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 44, Issue 3

September 2018

291 pages

ISSN:0098-3500

EISSN:1557-7295

DOI:10.1145/3175005

Editor:
Daniel Kressner
EPF Lausanne, Switzerland

Issue’s Table of Contents

Copyright © 2018 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: 06 February 2018

Accepted: 01 November 2017

Revised: 01 July 2017

Received: 01 November 2016

Published in TOMS Volume 44, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

European Unions Horizon 2020 research and innovation programme

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
153
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Charrier DHazelwood BWeinzierl T(2020)Enclave Tasking for DG Methods on Dynamically Adaptive MeshesSIAM Journal on Scientific Computing10.1137/19M127619442:3(C69-C96)Online publication date: 5-May-2020
https://doi.org/10.1137/19M1276194
Reinarz ACharrier DBader MBovard LDumbser MDuru KFambri FGabriel AGallard JKöppel SKrenz LRannabauer LRezzolla LSamfass PTavelli MWeinzierl T(2020)ExaHyPE: An engine for parallel dynamically adaptive simulations of wave problemsComputer Physics Communications10.1016/j.cpc.2020.107251(107251)Online publication date: Mar-2020
https://doi.org/10.1016/j.cpc.2020.107251
Murray CWeinzierl T(2020)Lazy Stencil Integration in Multigrid AlgorithmsParallel Processing and Applied Mathematics10.1007/978-3-030-43229-4_3(25-37)Online publication date: 19-Mar-2020
https://doi.org/10.1007/978-3-030-43229-4_3
Murray CWeinzierl T(2020)Stabilized asynchronous fast adaptive composite multigrid using additive dampingNumerical Linear Algebra with Applications10.1002/nla.232828:3Online publication date: 24-Aug-2020
https://doi.org/10.1002/nla.2328
Murray CWeinzierl T(2020)Delayed approximate matrix assembly in multigrid with dynamic precisionsConcurrency and Computation: Practice and Experience10.1002/cpe.594133:11Online publication date: 22-Jul-2020
https://doi.org/10.1002/cpe.5941
Weinzierl T(2019)The Peano Software—Parallel, Automaton-based, Dynamically Adaptive Grid TraversalsACM Transactions on Mathematical Software10.1145/331979745:2(1-41)Online publication date: 18-Apr-2019
https://dl.acm.org/doi/10.1145/3319797

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