mainpage.doc

// SPDX-FileCopyrightInfo: Copyright © DUNE Project contributors, see file LICENSE.md in module root
// SPDX-License-Identifier: LGPL-2.1-or-later
/*! \mainpage UG-4.0 Reference Manual
 *
 *       
 * \section intro Introduction
 *
 * This is the introduction.
 *
 * \section mods Modules
 *
<ul>
  <li> \ref ug </li> 
  <ul>
    <li> \ref dev </li>
    <li> \ref dom </li>
    <ul>
      <li> \ref std </li>
    </ul>
    <li> \ref gm </li>
    <li> \ref graphics </li>
    <li> \ref low </li>
    <li> \ref np </li>
    <li> \ref ui </li>
  </ul>
</ul>
 

\section chapter2 Overview of UGs data structures

This page will give an overview of the data types defined in UG 
that are used to represent meshes and geometries. All data types discussed here are 
defined in the header file gm.h of the grid manager module.
A description of the individual data types can be found in 
separate pages for each data type. UGs data structure is very flexible
and covers two- and threedimensional elements and a general sparse
matrix structure. You can have different numbers of degrees of freedom 
in nodes, edges, sides
and elements of a three-dimensional mesh. Therefore the data structure
can be used e.g. also for non-conforming or mixed finite element discretizations.
To structure the data you can group vectors by using BLOCKVECTORs; this
yields blockmatrices too.

UGs refinement module can refine and coarsen a given mesh structure. In
order to do that it needs a complete description of the geometry of the
domain. For full flexibility, the geometry is defined by patches, which are
mappings from a d-1 dimensional parameter space to d dimensional euclidean space.

If we imagine a three-dimensional mesh we can identify a hierarchy of 
geometrical objects like `elements, sides, edges` and `nodes`.
By element we mean just a simple geometric shape like
a triangle, a quadrilateral, a tetrahedron or a hexahedron. In our notation the element
does not include the number of degrees of freedom or the definition of the shape functions
as it is common in the Finite Element context. A side is meant to be a face of an element, that
is a d-1 dimensional object if we have a mesh in d dimensions (d=2,3). An edge is a connection
of two nodes, i.~e. a one-dimensional object and a node is a point in space (as far as geometry
is concerned). Note that in two space dimensions sides coincide with edges, or we can say that
a side consists of one edge and two nodes in that case.

The TeX version of this page contains a graphical representation of the data 
structure.

Size limitations of the data structure are described in a separate page LIMITS.

All data types have names with uppercase letters. Now we give a brief description
of all data types for which a separate page is provided.

. DOMAIN - Structure that describes a two- or threedimensional domain.

. BOUNDARY_SEGMENT - A DOMAIN is constructed from several BOUNDARY_SEGMENT objects.
UG can handle also `internal` boundaries, e.g. for material interfaces.

. PROBLEM - Stores references to user defined coefficient functions. The purpose
of these functions depends on the problem class library. A problem corresponds 
to a DOMAIN and provides a BOUNDARY_CONDITION for each BOUNDARY_SEGMENT
besides the coefficient functions. There may be several problems defined on a domain.

. BOUNDARY_CONDITION - For each BOUNDARY_SEGMENT a corresponding BOUNDARY_CONDITION
object must be allocated.

. FORMAT - This structure parametrizes the data structure. The format determines
the layout of the sparse matrix data structure and how it is determined from
the mesh data. 

. ELEMENT - UGs data structure is element oriented, so this is the basic data
type from which other objects can be reached locally. The variable element
concept allows several element types (e.g. triangles and quadrilaterals) in one mesh.
Elements give you access to the corresponding nodes and to neighboring elements.

. NODE - Corners of the elements are described by the NODE structure. Only the
information that is different per level is stored here. E.g. geometric information 
for a node e.g. is stored only once in a VERTEX object. Several NODE objects share
share one VERTEX if they are at the same position on different levels.

. VERTEX - Geometric data of a NODE. This contains x,y (,z), i.e global
coordinates, the position in the coarser grid level (local coordinates) and
boundary information if the node is on the boundary (see VSEGMENT).

. LINK - The mesh structure implies a neighbor relationship on the NODE
objects (the `mesh graph`). 
Since the mesh is unstructured a linked list must be used to provide
references to all neighbors. The LINK data type forms that list and each
LINK object represents one neighbor.

. EDGE - The LINK structure represents a directed edge of the mesh graph from
some node `a` to node `b`. The LINK from node `b` to node `a` must always exist
since the neighbor relation is symmetric and therefore the two LINK objects
are combined to form an (undirected) EDGE object.

. GEOM_OBJECT - This is an union of ELEMENT, NODE and EDGE, the basic
geometric objects.

. VECTOR - This structure is part of UGs sparse matrix data structure. Degrees
of freedom (and additional values) associated with `one geometric object` 
(ELEMENT, NODE, EDGE and also sides in 3D for which there is no extra data type)  
are stored in a VECTOR object. In each VECTOR starts a list of MATRIX objects
representing the rows of the global stiffness matrix corresponding to all
degrees of freedom in the VECTOR.

. MATRIX - Contains all matrix entries coupling the degrees of freedom
in two VECTOR objects. MATRIX objects come in pairs connecting two
VECTOR objects in both directions. If the VECTOR objects are identical (which is
the case for diagonal entries) then there is only one MATRIX.
The graph induced by the MATRIX-VECTOR
structure is completely independent from the mesh graph represented by the
LINK-NODE structure.

. CONNECTION - The two (or one, s.a.) MATRIX objects connecting two VECTOR objects
are combined to a CONNECTION object. This is similar to the combination of two
LINK objects in an EDGE.

. GRID - All objects allocated on one grid level can be accessed via the
GRID structure.

. MULTIGRID - Several grid levels are combined to form a MULTIGRID structure.
It also provides access to the data structure parameters (FORMAT), the
geometry (DOMAIN) and the problem description (PROBLEM). The MULTIGRID
structure is basically an environment item (see ENVIRONMENT). Several
MULTIGRID objects can be handled simultaneously by the grid manager module.

`IMPORTANT:` The access to all components of the data types is realized with
macros. Through the use of macros the data structure can be changed without
changing the code that uses it. 

\sa

LIMITS, all data types mentioned above.

.p DataStructure.eps
.cb
Graphical representation of the data structure with references.
.ce


\section LIMITS Constants defining limitations of the data structure

There are some constants defining limitations of the data structure.
They are explained here. The actual value of the definition should
be extracted from the source code via the uggrep shell script
provided with UG.

`In file gm.h`

. MAXLEVEL - Maximum number of grid levels allowed in MULTIGRID.

. MAXOBJECTS - Maximum number of different objects in free list.

. MAX_SIDES_OF_ELEM - Maximum number of sides of an element (of any type).

. MAX_EDGES_OF_ELEM - Maximum number of edges of an element (of any type).

. MAX_CORNERS_OF_ELEM - Maximum number of corners of an element (of any type).

. MAX_EDGES_OF_SIDE - Maximum number of edges per side.

. MAX_CORNERS_OF_SIDE - Maximum number of corners per side.

. MAX_CORNERS_OF_EDGE - Maximum number of corners per edge (is always 2).

. MAX_SIDES_OF_EDGE - In 3D two sides always have on edge in common.

. MAX_SONS - Maximum number of sons per element.

. MAXMATRICES - Maximum number of MATRIX types with different size.

. MAXCONNECTIONS - Maximum number of different CONNECTION types.

. MSIZEMAX - Maximum size of a MATRIX object in bytes.

. NO_OF_ELEM_MAX - Maximum number of elements touching the same edge.

`In file switch.h`

. MAXVECTORS - Maximum number of different VECTOR types.

\section REFINEMENT The interface to the grid refinement module

The interface to the grid refinement will change in the near future.
Therefore only a rudimentary documentation is provided.

UGs local refinement capability is element oriented, i.e. the
error estimator (part of the problem class) selects all or
part of the elements for refinement. To that end the error
estimator calls the function

\verbatim
INT MarkForRefinement (ELEMENT *theElement, INT rule, INT side);
\endverbatim

where rule is one of the following rules

\verbatim
NO_REFINEMENT
COPY     
RED    
BLUE  
BISECTION_1 
BISECTION_2_Q 
BISECTION_2_T1
BISECTION_2_T2
BISECTION_3 
UNREFINE 
\endverbatim

and side is some orientation necessary for those rules
that are not invariant under rotation (e.g. the edge to bisect).
The RED rule selects standard isotropic refinement independent
of the element type. Triangles are subdivided in four triangles
by connecting the edge midpoints, quadrilaterals are subdivided
by connecting edge midpoints with the centroid and tetrahedral
elements are subdivided using the refinement strategy of J. Bey.
For RED refinement the side information is arbitrary.

The MarkForRefinement function may only be called for those elements
where 

\verbatim
INT EstimateHere (ELEMENT *theElement);
\endverbatim

returns true. EstimateHere is true for the leave elements of the element
hierarchy, i.e. those elements that are not further refined. Care
must be taken when the estimator for an element needs also information
on the solution in neighboring elements (see e.g. the implementation
of the error estimator in the diff2d package). 

After the desired elements have been tagged for refinement the refine
of the UG command language is used to actually refine the elements.

\subsection Example Example2

The following function selects all (possible) elements in a MULTIGRID for refinement and
returns the number of elements selected for refinement.

\verbatim
static INT MarkAll (MULTIGRID *theMG)
{
    GRID *theGrid;
    ELEMENT *theElement;
    int k,j;
    INT cnt;

    // get number of levels
    j = TOPLEVEL(theMG);

    // cnt will hold the number elements to be refined 
    cnt = 0;

    // mark elements
    for (k=0; k<=j; k++)
    {
        theGrid = GRID_ON_LEVEL(theMG,k);
        for (theElement=FIRSTELEMENT(theGrid); theElement!=NULL; theElement=SUCCE(theElement))
            if (EstimateHere(theElement))
            {
                cnt++;
                MarkForRefinement(theElement,RED,0);
            }
    }

    // return cnt
    return(cnt);
}
\endverbatim

\sa

MarkForRefinement(), EstimateHere(), refine()

REFERENCES:

[1] J. Bey: Tetrahedral Grid Refinement. To be published in Computing.

[2] J. Bey: AGM^3D Manual. Technical Report, Universität Tübingen, 1994.

[3] R.E. Bank, A.H. Sherman, A. Weiser: Refinement Algorithms and Data
Structures for Regular Local Mesh Refinement. In: Scientific Computing,
IMACS, North-Holland, Amsterdam, 1983.

 */