From a2355038333db44e2664f9b32d48e52e557973c1 Mon Sep 17 00:00:00 2001 From: Marc Fehling Date: Wed, 5 Jun 2019 13:20:36 +0200 Subject: [PATCH] Reviewed section on hp adaptivity. --- 9.1/paper.bib | 16 +++++++++++++ 9.1/paper.tex | 63 +++++++++++++++++++++++++++------------------------ 2 files changed, 50 insertions(+), 29 deletions(-) diff --git a/9.1/paper.bib b/9.1/paper.bib index 7c102ea..43a60eb 100644 --- a/9.1/paper.bib +++ b/9.1/paper.bib @@ -418,6 +418,22 @@ Collection of deal.II Manifold Wrappers for the OpenCASCADE Library}}, pages = {1103-1133}, year = 2011} +@Article{Burstedde2018, + author = {C. Burstedde}, + title = {Parallel tree algorithms for {AMR} and non-standard data access}, + journal = {arXiv e-prints}, + keywords = {Computer Science - Distributed, Parallel, and Cluster Computing, 65D18, 65M50, 65Y05, 68W10}, + year = 2018, + month = {Mar}, + eid = {arXiv:1803.08432}, + pages = {arXiv:1803.08432}, + archivePrefix = {arXiv}, + eprint = {1803.08432}, + primaryClass = {cs.DC}, + adsurl = {https://ui.adsabs.harvard.edu/abs/2018arXiv180308432B}, + adsnote = {Provided by the SAO/NASA Astrophysics Data System} +} + @Book{arpack, author = {R. B. Lehoucq and D. C. Sorensen and C. Yang}, title = {{ARPACK} users' guide: solution of large-scale eigenvalue problems with implicitly restarted Arnoldi methods}, diff --git a/9.1/paper.tex b/9.1/paper.tex index 4805aec..f897126 100644 --- a/9.1/paper.tex +++ b/9.1/paper.tex @@ -169,7 +169,7 @@ The major changes of this release are: Section~\ref{subsec:ad}), \item Dedicated support for symbolic algebra (see Section~\ref{subsec:sd}), - \item Full support for $hp$ adaptivity in parallel computations (see + \item Full support for $hp$~adaptivity in parallel computations (see Section~\ref{subsec:hp}), \item Interfaces to the HDF5 file format and libraries (see Section~\ref{subsec:hdf5}), @@ -378,10 +378,10 @@ use of a custom-generated \texttt{std::function} (so-called ``lambda'' optimizat compiling expressions using the LLVM JIT compiler. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\subsection{Full support for $hp$ adaptivity in parallel computations} +\subsection{Full support for $hp$~adaptivity in parallel computations} \label{subsec:hp} -\dealii{} has had support for $hp$ adaptive methods since around 2005 +\dealii{} has had support for $hp$~adaptive methods since around 2005 (documented in \cite{BangerthKayserHerold2007}) and for parallel computations on distributed meshes since around 2010 (see \cite{BangerthBursteddeHeisterKronbichler11}), but not for both at the @@ -389,8 +389,8 @@ same time. The challenges to combine these are related to a number of areas: \begin{enumerate} \item Data structures: The data structures necessary to store the - indices of degrees of freedom are necessarily substantially more - complicated for $hp$ algorithms than for the $h$-adaptive schemes + indices of degrees of freedom are substantially more + complicated for $hp$~algorithms than for the $h$~adaptive schemes that were already implemented. This is because the number of degrees of freedom per cell is now no longer constant. Furthermore, faces and edges may need to store more than one set of indices if @@ -403,20 +403,20 @@ areas: cells), and for which the data structures stored on different processors have to be reconciled. -\item Algorithms: Already for $h$ adaptive meshes, enumerating all - degrees of freedom on the global mesh is difficult, as evidenced by +\item Algorithms: Already for $h$~adaptive meshes, enumerating all + degrees of freedom uniquely on the global mesh is difficult, as evidenced by the complications of the algorithms shown in Section 3.1 of \cite{BangerthBursteddeHeisterKronbichler11}, which requires more than one page of text and is implemented in many hundreds of lines of code. - These difficulties are even more pronounced when using $hp$ - adaptivity. The main obstacle is the desire to unify the indices of - matching degrees of freedom on adjacent cells, such as the edge - degree of freedom of a $Q_2$ element with the middle one of - the three edge degrees of freedom of a $Q_4$ element on a - neighboring cell. Section 4.2 of - \cite{BangerthKayserHerold2007} discusses a sequential algorithm + These difficulties are even more pronounced when using $hp$~adaptivity. + The main obstacle is the desire to unify the indices of + matching degrees of freedom on adjacent cells whenever elements with + continuous polynomials are used. For example, the edge degree of freedom + of a $Q_2$~element has to be merged with the middle one of the three + edge degrees of freedom of a $Q_4$~element on a neighboring cell. + Section 4.2 of \cite{BangerthKayserHerold2007} discusses a sequential algorithm that eliminates one of these degrees of freedom in favor of another, but it introduces a ``master'' and a ``slave'' side of the interface. This is of no major consequence in sequential @@ -438,24 +438,26 @@ areas: \item Data transfer patterns: An important algorithm in parallel finite element methods is the exchange of information stored on cells during mesh repartitioning. This happens, for example, when - interpolating the solution from one mesh to the next, - adaptively-refined mesh; or when adapting the polynomial degrees + interpolating the solution from one mesh to the next + adaptively refined mesh; or when adapting the polynomial degrees associated with each cell and repartitioning in order to balance the computational cost of each processor's partition. When - using $h$ adaptive methods, the amount of data associated with each + using $h$~adaptive methods, the amount of data associated with each cell is fixed and the algorithms that implement the data transfer - are consequently relatively simple. On the other hand, in $hp$ - contexts, each cell may have a different number of unknowns + are consequently relatively simple. On the other hand, in $hp$~contexts, + each cell may have a different number of unknowns associated with it, and the algorithms that transfer the data are - substantially more complicated. Furthermore, the amount of data - associated with each cell may be large on cells with higher - polynomial degrees, and might profit from compression before - sending. - -\item Balancing computational cost: For $h$-adaptive algorithms, the + substantially more complicated. In order to implement those, we rely + on recent enhancements of the \pfrst~library (documented in + \cite{Burstedde2018}) to transfer data of variable size across + processors. Furthermore, the amount of data associated with each + cell may be large on cells with higher polynomial degrees, and + might profit from compression before sending. + +\item Balancing computational cost: For $h$~adaptive algorithms, the amount of work associated with each cell is essentially the same, both during the assembly of linear systems as well as during the - solver phase. For $hp$-adaptive methods, this is no longer the + solver phase. For $hp$~adaptive methods, this is no longer the case. Consequently, balancing the cost of work between different processors' partitions is no longer as easy as ensuring that every processor owns a roughly equal number of cells. Rather, one needs to @@ -463,7 +465,10 @@ areas: relative cost compared to some reference. To make things worse, the relative cost of assembly on a cell might not match the relative cost of the linear solver associated with this cell, leading to - difficult trade-offs in defining optimal weighting factors. + difficult trade-offs in defining optimal weighting factors. In this + release, we supplied the basic functionality to attach any amount + of weighting factors to cells, but users still have to find reasonable + weights for themselves. \end{enumerate} All of these issues have been addressed in the current release and are @@ -624,7 +629,7 @@ following: \begin{itemize} \item For geometric multigrid: \cite{Kanschat2004,JanssenKanschat2011,ClevengerHeisterKanschatKronbichler2019}; \item For distributed parallel computing: \cite{BangerthBursteddeHeisterKronbichler11}; - \item For $hp$ adaptivity: \cite{BangerthKayserHerold2007}; + \item For $hp$~adaptivity: \cite{BangerthKayserHerold2007}; \item For partition-of-unity (PUM) and enrichment methods of the finite element space: \cite{Davydov2016}; \item For matrix-free and fast assembly techniques: @@ -664,7 +669,7 @@ following: \item nanoflann \cite{nanoflann} \item NetCDF \cite{rew1990netcdf} \item OpenCASCADE \cite{opencascade-web-page} -\item p4est \cite{p4est} +\item p4est \cite{Burstedde2018,p4est} \item PETSc \cite{petsc-user-ref,petsc-web-page} \item ROL \cite{ridzal2014rapid} \item ScaLAPACK \cite{slug} -- 2.39.5