\section{Implementation of submeshes}%
\label{S:submesh_implementation}%
\label{S:tracemesh_implementation}%
\idx{submeshes!implementation}
\idx{tracemeshes!implementation}

The concepts and motivations behind submeshes in \ALBERTA were already
introduced in \secref{book:S:Submeshes}. Shortly, a submesh or slave
mesh (maybe better ``trace-mesh'') of a given $d$-dimensional master
mesh is a collection of certain $d-1$-dimensional subsimplices that
should be refined and coarsened in a conforming way to the master
mesh. For parametric master meshes, all submeshes should also be
parametric.

The philosophy of submeshes is that their use should not involve major
changes of data structures nor excessive overhead in memory or CPU
time as a price for their features. We first describe how to allocate
and use submeshes. The ideas of how refining and coarsening work for
submeshes is described later.

\subsection{Allocating submeshes}%
\label{S:alloc_submesh}%
\idx{submeshes!allocation}

Submeshes are \ALBERTA \code{MESH} objects with some special properties.
The user defines a submesh by selecting certain subsimplices of 
macro elements. The mechanism uses a callback method similar to the case 
of node projections, refer \secref{S:node_projections}. 
\fdx{get_submesh()@{\code{get\_submesh()}}}
\bv\begin{verbatim}
MESH *get_submesh(MESH *, const char *,
                  int (*)(MESH *, MACRO_EL *, int, void *), void *);
\end{verbatim}\ev
\code{get\_submesh(master, name, binding\_method, data)} allocates a submesh 
with the identifier \code{name} of the given \code{master}. The binding method
is a callback function which is called by \ALBERTA for each macro element and 
each vertex/edge/face in 1d/2d/3d.

Given the \code{master} mesh,
a macro element \code{mel}, a vertex/edge/face \code{face}, and arbitrary 
user \code{data}, this function should return \true if the subface is 
to be part of the submesh and \false otherwise. An example is shown below.
The argument \code{data} is passed to the callback and may contain arbitrary
user data.

Calling this function will return the complete submesh. More than one
submesh may be defined. If the master mesh is already refined, then
the submesh will automatically be refined to maintain the conformity
property \mathref{book:E:conforming_submesh} on page
\pageref{book:E:conforming_submesh}. If the master mesh used projection of
nodes, then the node projection is inherited by the slave mesh and
automatically initialized in such a way that all submesh vertices
undergo the same projection as the master vertices.

If the master 
mesh is a parametric mesh (or is later defined to be one), then the parametric
structure is inherited in a straight forward manner to the submesh, a 
mechanism which is only implemented for \code{use\_lagrange\_parametric}. This 
implies that the submesh elements will also be described by element 
transformations of the same polynomial degree as for the master mesh, and that 
the shape of submesh elements matches the shape of curved master mash 
subsimplices.

The numbering of vertices on the macro triangulation of the submesh is done 
in such a way as to always guarantee matching refinement edges of submesh
and master mesh. Furthermore, the orientation of the submesh elements for 
2d submeshes follows a right hand rule for the outward pointing unit normal 
of the master macro element, see Figure \figref{F:submesh_numbering_3d}.

\begin{figure}[htbp]
\centering
\includegraphics{EPS/submesh_numbering_3d}
\caption[Trace-meshes, numbering of subsimplices]{Local vertex
  numbering of the 2d subsimplices of a 3d element of type 0 and
  positive orientation. The 2d submesh numbering depends on type and
  orientation of the master elements.}
\label{F:submesh_numbering_3d}
\end{figure}

The connection of submesh and master mesh is described internally using two
special \code{DOF\_PTR\_VEC}s. One of these, called \code{master\_binding},
is based on the submesh and contains pointers from slave elements into 
master elements. To be precise, each \code{CENTER} DOF of this vector
is a pointer to the master \code{EL} structure describing the element along 
which the submesh element lies. 

The second vector, called \code{slave\_binding}, is based on the
master mesh and points in the opposite direction. It maps
\code{VERTEX}/\code{EDGE}/\code{FACE} DOFs of the master element to
the \code{EL} structures of the slaves. If no slave element lies along
the \code{VERTEX}/\code{EDGE}/\code{FACE} then the pointer is
\nil. Figure \figref{F:slave_binding} illustrates this.

\begin{figure}[htbp]
\centering
\includegraphics[scale=0.75]{EPS/sm_dpv_2d}
\caption[Trace-meshes, 1d slave-elements]{2d master triangle with
  submesh intervals on all sides. Left: vector \code{slave\_binding}
  connecting \code{EDGE} DOFs to slave elements.  Right: vector
  \code{master\_binding} connecting \code{CENTER} DOFs to master
  elements.}
\label{F:slave_binding}
\end{figure}

Both vectors have their \code{refine\_interpol} and \code{coarse\_restrict} 
entries set to special internal routines. These routines automatically 
take care of updating the submesh during refinement and coarsening, which 
is useful since mesh changes are most easily done simultaneously on 
refinement or coarsening patches. This is described in more detail below.

Submeshes can be disconnected from the master mesh using the function
\fdx{unchain_submesh()@{\code{unchain\_submesh()}}}
\bv\begin{verbatim}
void unchain_submesh(MESH *slave);
\end{verbatim}\ev
This function deletes the connection between master mesh and submesh. It does 
\emph{not} delete the submesh. After doing this, the submesh and master mesh 
are entirely independent and separate \code{MESH} objects for \ALBERTA and 
may be refined and coarsened independently.

\subsection{Routines for submeshes}%
\label{S:tools_submesh}%
\idx{submeshes!tools}

The following tools are available for submeshes:
\fdx{read_submesh()@{\code{read\_submesh()}}}
\fdx{read_submesh_xdr()@{\code{read\_submesh\_xdr()}}}
\fdx{get_bndry_submesh()@{\code{get\_bndry\_submesh()}}}
\fdx{get_bndry_submesh_by_type()@{\code{get\_bndry\_submesh\_by\_type()}}}
\fdx{get_bndry_submesh_by_segment()@{\code{get\_bndry\_submesh\_by\_segment()}}}
\fdx{read_bndry_submesh()@{\code{read\_bndry\_submesh()}}}
\fdx{read_bndry_submesh_xdr()@{\code{read\_bndry\_submesh\_xdr()}}}
\fdx{read_bndry_submesh_by_type()@{\code{read\_bndry\_submesh\_by\_type()}}}
\fdx{read_bndry_submesh_by_type_xdr()@{\code{read\_bndry\_submesh\_by\_type\_xdr()}}}
\fdx{read_bndry_submesh_by_segment()@{\code{read\_bndry\_submesh\_by\_segment()}}}
\fdx{read_bndry_submesh_by_segment_xdr()@{\code{read\_bndry\_submesh\_by\_segment\_xdr()}}}
\fdx{trace_dof_real_vec()@{\code{trace\_dof\_real\_vec()}}}
\fdx{trace_dof_real_d_vec()@{\code{trace\_dof\_real\_d\_vec()}}}
\fdx{get_slave_dof_mapping()@{\code{get\_slave\_dof\_mapping()}}}
\fdx{get_master()@{\code{get\_master()}}}
\fdx{get_slave_el()@{\code{get\_slave\_el()}}}
\fdx{fill_slave_el_info()@{\code{get\_slave\_el\_info()}}}
\fdx{fill_master_el_info()@{\code{get\_master\_el\_info()}}}
\fdx{trace_to_bulk_coords()@{\code{trace\_to\_bulk\_coords()}}}
\fdx{trace_to_bulk_coords_dim()@{\code{trace\_to\_bulk\_coords\_dim()}}}
\fdx{trace_to_bulk_coords_0d()@{\code{trace\_to\_bulk\_coords\_0d()}}}
\fdx{trace_to_bulk_coords_1d()@{\code{trace\_to\_bulk\_coords\_1d()}}}
\fdx{trace_to_bulk_coords_2d()@{\code{trace\_to\_bulk\_coords\_2d()}}}
\fdx{bulk_to_trace_coords()@{\code{bulk\_to\_trace\_coords()}}}
\fdx{bulk_to_trace_coords_dim()@{\code{bulk\_to\_trace\_coords\_dim()}}}
\fdx{bulk_to_trace_coords_0d()@{\code{bulk\_to\_trace\_coords\_0d()}}}
\fdx{bulk_to_trace_coords_1d()@{\code{bulk\_to\_trace\_coords\_1d()}}}
\fdx{bulk_to_trace_coords_2d()@{\code{bulk\_to\_trace\_coords\_2d()}}}
\fdx{get_master_dof_indices()@{\code{get\_master\_dof\_indices()}}}
\fdx{get_master_bound()@{\code{get\_master\_bound()}}}
\fdx{trace_dof_real_vec()@{\code{trace\_dof\_real\_vec()}}}
\fdx{trace_dof_real_d_vec()@{\code{trace\_dof\_real\_d\_vec()}}}
\fdx{trace_dof_int_vec()@{\code{trace\_dof\_int\_vec()}}}
\fdx{trace_dof_dof_vec()@{\code{trace\_dof\_dof\_vec()}}}
\fdx{trace_int_dof_vec()@{\code{trace\_int\_dof\_vec()}}}
\fdx{trace_dof_uchar_vec()@{\code{trace\_dof\_uchar\_vec()}}}
\fdx{trace_dof_schar_vec()@{\code{trace\_dof\_schar\_vec()}}}
\fdx{trace_dof_ptr_vec()@{\code{trace\_dof\_ptr\_vec()}}}
\fdx{update_master_matrix()@{\code{update\_master\_matrix()}}}
\fdx{update_master_real_vec()@{\code{update\_master\_real\_vec()}}}
\fdx{update_master_real_d_vec()@{\code{update\_master\_real\_d\_vec()}}}
\bv\begin{verbatim}
MESH *read_submesh(MESH *master,
                   const char *slave_filename,
                   int (*binding_method)(MESH *master, MACRO_EL *el,
                                         int face, void *data),
                   NODE_PROJECTION *(*)(MESH *, MACRO_EL *, int),
                   void *data);
MESH *read_submesh_xdr(MESH *master,
                       const char *slave_filename,
                       int (*binding_method)(MESH *master, MACRO_EL *el,
                                             int face, void *data),
                       NODE_PROJECTION *(*)(MESH *, MACRO_EL *, int),
                       void *data);
MESH *get_bndry_submesh(MESH *master, const char *name);
MESH *get_bndry_submesh_by_type(MESH *master, const char *name,
                                BNDRY_TYPE type);
MESH *get_bndry_submesh_by_segment(MESH *master, const char *name,
                                   BNDRY_FLAGS segment);
MESH *read_bndry_submesh(MESH *master, const char *slave_filename);
MESH *read_bndry_submesh_xdr(MESH *master, const char *slave_filename);
MESH *read_bndry_submesh_by_type(MESH *master,
				 const char *slave_filename, BNDRY_TYPE type);
MESH *read_bndry_submesh_by_type_xdr(MESH *master,
				     const char *slave_filename,
                                     BNDRY_TYPE type);
MESH *read_bndry_submesh_by_segment(MESH *master,
				    const char *slave_filename,
                                    BNDRY_FLAGS segment);
MESH *read_bndry_submesh_by_segment_xdr(MESH *master,
				       const char *slave_filename,
                                       BNDRY_FLAGS segment);

void get_slave_dof_mapping(const FE_SPACE *m_fe_space, DOF_INT_VEC *s_map);
MESH *get_master(MESH *slave);
const DOF *get_master_dof_indices(const EL_INFO *s_el_info,
				  const FE_SPACE *m_fe_space,
				  DOF *result);
void trace_dof_real_vec(DOF_REAL_VEC *svec, const DOF_REAL_VEC *mvec);
void trace_dof_real_d_vec(DOF_REAL_D_VEC *svec, const DOF_REAL_D_VEC *mvec);
void trace_dof_int_vec(DOF_INT_VEC *svec, const DOF_INT_VEC *mvec);
void trace_dof_dof_vec(DOF_DOF_VEC *svec, const DOF_DOF_VEC *mvec);
void trace_int_dof_vec(DOF_DOF_VEC *svec, const DOF_DOF_VEC *mvec);
void trace_dof_uchar_vec(DOF_UCHAR_VEC *svec, const DOF_UCHAR_VEC *mvec);
void trace_dof_schar_vec(DOF_SCHAR_VEC *svec, const DOF_UCHAR_VEC *mvec);
void trace_dof_ptr_vec(DOF_PTR_VEC *svec, const DOF_PTR_VEC *mvec);
void update_master_matrix(DOF_MATRIX *m_dof_matrix,
			  const EL_MATRIX_INFO *s_minfo);
void update_master_real_vec(DOF_REAL_VEC *m_drv,
                            const EL_VEC_INFO *s_vec_info);
void update_master_real_d_vec(DOF_REAL_D_VEC *m_drdv,
			      const EL_VEC_D_INFO *s_vec_info);
\end{verbatim}\ev
%%
\begin{compatibility}
  \label{compat:get_master_el}
  The functionality of the function \code{get\_master\_el()} has been
  shifted to the \hyperref[T:EL_INFO]{\code{EL\_INFO}} structure;
  information about the "master"-element is computed during
  mesh-traversal if requested by the \code{FILL\_MASTER\_INFO} and
  \code{FILL\_MASTER\_NEIGH} fill-flags (see also
  \secref{S:traverse}).
\end{compatibility}
%%
Description of the individual functions:
\begin{descr}
  \kitem{read\_submesh(master,filename,binding\_method,init\_node\_proj,data)}
  This function must be used to read a submesh from disk which was
  previously saved by \code{write\_mesh()}, see
  \secref{S:file_formats}. Note that a \code{write\_mesh()} call using
  the master mesh does \emph{not} store submeshes as well. After this
  call the submesh is again connected with the master mesh. The
  \code{init\_node\_proj} must be the same function as originally
  passed to the master mesh. The \code{binding\_method} must also be
  the same function as used to define the submesh originally. The
  reason for passing these pointers again is that there is no way to
  store the C code describing these functions in a file.

  \kitem{read\_submesh\_xdr()} Analogous function for submeshes stored
  by \code{write\_mesh\_xdr()}.

  \kitem{get\_bndry\_submesh(master, name)} A convenience function, internally
  \code{get\_submesh()} is called with an appropriate
  \code{binding\_method} which turns all boundary simplices into a sub-mesh.

  \kitem{get\_bndry\_submesh\_by\_type(master, name, type)}  Like  the
  function above, but allows for the specification of a boundary type.
  See Section \ref{S:boundary}.

  \kitem{get\_bndry\_submesh\_by\_segment(master, name, segment)} Like
    the function above, but allows for the specification of a boundary
    type bit-mask.  See Section \ref{S:boundary}.

  \kitem{read\_bndry\_submesh(master, filename)}
  \kitem{read\_bndry\_submesh\_xdr(master, filename)}
  \kitem{read\_bndry\_submesh\_by\_type(master, filename, type)}
  \kitem{read\_bndry\_submesh\_by\_type\_xdr(master, filename, type)}
  \kitem{read\_bndry\_submesh\_by\_segment(master, filename, segment)}
  \kitem{read\_bndry\_submesh\_by\_segment\_xdr(master, filename, segment)}~\\
  Counterparts to \code{read\_submesh()} and
  \code{read\_submesh\_xdr()} to read back sub-meshes generated by
  \code{get\_bndry\_submesh()} and
  \code{get\_bndry\_submesh\_by\_type()}, respectively.

  \kitem{get\_slave\_dof\_mapping(m\_fe\_space, s\_map)} Fills the
  vector \code{s\_map} on the submesh with the corresponding DOF
  indices of the finite element space \code{m\_fe\_space} on the
  master mesh. This only works if \code{m\_fe\_space} and
  \code{s\_map->fe\_space} are Lagrange type spaces of equal degree.
  The master DOF indices are not updated during mesh changes, hence
  the use of a \code{DOF\_INT\_VEC}, see \secref{S:DOF_VEC}.

  \kitem{get\_master(slave)} returns the master mesh of \code{slave}.
  
 \kitem{fill\_slave\_el\_info(slv\_el\_info, el\_info, face, slave\_mesh)}
  Fills a \code{EL\_INFO} element descriptor refering to the slave mesh.

 \kitem{fill\_master\_el\_info(mst\_el\_info, el\_info, face, fill\_flags)}
  Fills a \code{EL\_INFO} element descriptor refering to the slave mesh.
  \code{fill\_flags} determines what kind of information is provided.

 \kitem{trace\_to\_bulk\_coords(result, lambda, el\_info)}
 \kitem{bulk\_to\_trace\_coords(result, lambda, el\_info)}
  Given local coordinates on either the master or the trace mesh
  construct the matching local coordinates for the
  peer-element. \code{el\_info} always refers to the lower-dimensional slave-mesh.

 \kitem{get\_master\_dof\_indices(result, s\_el\_info, m\_fe\_space)}
  Find the \code{DOF}s of \code{m\_fe\_space} -- a finite element
  space belonging to a master mesh -- belonging to the
  \code{s\_el\_info} -- an element descriptor for an element of the
  slave mesh. If \code{result} is not \nil, then it is used as storage
  for the \code{DOF}-indices and its address is returned. Otherwise
  the address of a static storage area is returned which holds the
  results until it is overwritten on the call to
  \code{get\_master\_dof\_indices()}.

 \kitem{get\_master\_bound(result, s\_el\_info, m\_fe\_space)}
  Same for the boundary classification.

  \kitem{trace\_<TYPE>\_vec(slave\_vec, master\_vec)} Implement
  discrete trace operators. The vector \code{slave\_vec} must be based
  on a submesh of the mesh defining \code{master\_vec}. The entries of
  \code{slave\_vec} are overwritten with values of \code{master\_vec}
  along the interface. The finite element spaces of \code{slace\_vec}
  and \code{master\_vec} must be compatible, i.e.
  \code{slave\_vec->fe\_space->bas\_fcts} must be the trace space
  \code{master\_vec->fe\_space->bas\_fcts->trace\_bas\_fcts}.
  \code{<TYPE>} is one of \{\code{dof\_real}, \code{dof\_real\_d},
  \code{dof\_int}, \code{dof\_dof}, \code{int\_dof},
  \code{dof\_schar}, \code{dof\_uchar}, \code{dof\_ptr}\}, i.e. there
  is a trace operation for all \code{DOF}-vector types.
%  These routines use interpolation and therefore
%  work for any finite element spaces.  If both vectors are contained
%  in Lagrange type spaces of equal degree then the values will be
%  exactly the same at the DOFs that coincide spatially.


%  \kitem{get\_master\_binding(slave)} returns the \code{DOF\_PTR\_VEC}
%  \code{master\_binding} described above.

%  \kitem{get\_slave\_binding(slave)} returns the \code{DOF\_PTR\_VEC}
%  \code{slave\_binding} described above.
  \kitem{update\_master\_matrix(m\_dof\_matrix, s\_minfo)}
  \kitem{update\_master\_real\_vec(m\_drv, s\_vec\_info)}
  \kitem{update\_master\_real\_d\_vec(m\_drdv, s\_vec\_info)}~\\
  These functions take element-matrix descriptors \code{s\_minfo}
  designed for the slave-mesh and update a matrix for the master-mesh.
  This can, e.g., be used to assemble Robin boundary conditions and
  the like.
\end{descr}

\subsection{Refinement and coarsening of submeshes}%
\label{S:rc_submeshes}%
\idx{submeshes!refinement}%
\idx{submeshes!coarsening}

As explained above, submeshes and master meshes are automatically refined
and coarsened simultaneously to maintain matching nodes and edges. To 
guarantee this property we need to be careful in choosing the enumeration 
of vertices of the submesh. In the most complicated case of a 2d submesh of 
a 3d master mesh, the numbering of a slave element tied to a given face 
of a master tetrahedron depends on the master tetrahedron's 
orientation, type, and the face index. Figure \figref{F:submesh_numbering_3d}
demonstrates one given case. The 2d submesh triangles possess the property
that they are oriented in a right hand rule with the thumb pointing away
from the master element.

Any mesh, whether master mesh or submesh may be refined or coarsened by 
a call to the routines \code{refine()} or \code{coarsen}, see Sections
\ref{S:refinement_routines} and \ref{S:coarsening_routines} respectively.
As mentioned before, an entire hierarchy of submeshes from 3d down to 1d 
is possible. 

If a top-level master mesh is to be refined, then
the refinement algorithm is carried out as usual. The vector 
\code{slave\_binding} based on the top-level master mesh has an entry 
\code{refine\_interpol} set to a special internal routine. This routine
is called for each master refinement patch. It creates a corresponding 
submesh refinement patch for the submesh elements adjoining the master 
patch. The submesh patch is then refined (in the process calling in turn 
any \code{refine\_interpol}s of the submesh).

If a submesh is to be refined, \ALBERTA first transfers the refinement
markers of the submesh elements to the corresponding master elements
using \code{master\_binding}. Then \code{refine()} is called
recursively for the master mesh. Once we reach the top-level master
mesh we proceed as in the prior paragraph.  The submesh refinement
markers are reset during the refinement of the master meshes. The
diagram of \figref{F:submesh_refinement} describes this process.

\begin{figure}[htbp]
\centering
\includegraphics[scale=0.75]{EPS/submesh_refinement}
\caption{Modified refinement algorithm.}\label{F:submesh_refinement}
\end{figure}

Coarsening of master and submeshes works in much the same way. Note
that coarsening marks must be transferred to the master mesh to enable
any change --- this will overwrite refinement marks on the master mesh
elements along the interface! Furthermore, the master mesh receives
the same value of the coarsening mark as the slave mesh, which may not
be enough to guarantee the coarsening if the current refinement edge
of a master element does not lie along the interface with the submesh.

Another caveat is that the user should be careful when using other refinement 
interpolation or coarsening interpolation/restriction routines on the 
master mesh that perform certain operations using submeshes. The state of 
the submesh is undefined at the time of calling these routines.

To conclude, submeshes offer advantages in many calculations where
information based on surfaces or interfaces is necessary. The price of
using a submesh is the additional overhead of one \code{MESH}
structure plus the memory needed to store two \code{DOF\_PTR\_VEC}s
(and their respective DOF administration). The vector
\code{slave\_binding} is based on the master mesh, while the vector
\code{master\_binding} is based on the submesh. Both vector require
the feature \code{preserve\_coarse\_dofs}, see
\secref{S:basic_steps_rc} for details. Allocating submeshes once
the master mesh is strongly refined is to be avoided, since a DOF 
administration for new element nodes may have to be set up on the fly. This
can be expensive in terms of CPU time. The user should code the macro
triangulations in a way that the interface defining the submesh is 
easily accessible.





%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "alberta-man"
%%% End: