thgdalg.html

有限元学习研究用源代码(老外的),供科研人员参考

 In a regular geometry, the time for a call of f(k) may be
estimated by 1 / 0.
 

 At first, we consider the variant of the algorithm with 2
= 0. This can be done, because usually a variant with smaller
2 is more accurate and greater values of 2 will be used only
for the reason of time efficiency.

  <p>The time for the call of the lowest level simplices is estimated by
the previous lemma. The time required for creation and subdivision of
each simplex may be estimated by a constant. The number of steps in
the loop in each simplex may be estimated by the number of
intersections with the internal planes which is bounded because the
geometry is regular. That's why the time for a call of each simplex
excluding the call time for the sub-simplices may be estimated by a
constant.

  <p>The length of the intersection line may be estimated by1. For each refinement level k we subdivide this line into
2^k parts of length k there  k = 1 / 2^k  is
the size of a simplex of this level. The number of simplices
containing such a part is fixed by the dimension, and because of the
regularity the number of simplex calls on this level which is
necessary to travel along this part may be estimated by a
constant. Thus, the number of simplex calls in level k can be
estimated by 2^k. The sum over all levels from 0 to l = \log_2
(1 / 0) we can estimate with 2^{l+1} or
  1 / 0 .

Usually for the time of the special algorithm for the size 2 we
obtain a better estimate as  2 / 0 . This allows to
obtain a better estimate for higher values of 2. For example,
if we can estimate this call by a constant, we can estimate the
resulting call time by  1 / 2 .

  <p>If the time required for calls of f(0) cannot be simply
estimated by a constant or this constant is too big, it may be
estimated by the time for a single call (the first) and the time for
calls of f(1) for the edge between the starting point and the point we
have to find.

  <p>Now let's estimate the overall time necessary for the geometry
description for a simple but typical application. Assume we have a
regular isotropic grid with n points in each direction in the
d-dimensional space. Assume we call at first f(0) with an optimal
starting point, that means in a distance of the edge length of the grid
g.  Assume also that we call f(k) only for simplices with
corners at grid points and with minimal size (bounded by
g). Assume also that the geometry is regular enough so that for
distances of order g it may be approximated by planes at least if we
want to define the number of intersections.

Consider a regular refinement step with factor 2. Instead of a single
intersection of a k-side with a k-segment we have now 2^{d-k} such
intersections. The function f(k) may be called only if we have an
intersection of a (k-1)-segment for a side in the immediate
neighbourhood.  That's why the number of calls of f(k) can increase
only by a factor 2^{d-k+1}, the number of calls of f(0)
increases by the factor 2^d.  The time for each call will not
increase, it will even decrease because the distances will be later.
For the overall time of cogeometry calls we obtain the maximal factor
2^d --- the same as for the number of nodes. So, usually we have
the following

 The time required for cogeometry calls depends linearily on
the number of nodes.  

Another situation of interest is the usage of a grid of the same
density for the geometry description. This situation is typical for
time-dependent processes, if the grid of the previous step will be
used to define the new cogeometry. In this case, the two grids are
usually of the same refinement level. To find the time behaviour in
this case, we have to consider the refinement as of the new, as of the
old grid. The number of calls will increase by the factor 2^d. But
what can we say about the time for each call? Here we have to compare two
effects:

 
 <ul>
 <li> The length of the intersection line becomes smaller for each
call by the factor 2.
 
 <li> The time required for travelling a given distance on the line
becomes greater by the factor 2.
 
 </ul>


As the result, the time required for each call remains approximately
unchanged. Also in this situation we obtain approximately linear
behaviour.

  <p>These considerations also show that the time for calls of f(k)
for higher k is not relevant for greater number of nodes. It will be
relevant only for a small number of nodes, if many cells of the grid
have intersections with the boundary.

 
<h2><a NAME="gdalgconv">Topological Errors and Convexity </a></h2>


Another very interesting question for the cogemetry is the following:

 If we create a grid using the contravariant geometry description,
is it possible to guarantee that there will be no topological errors?
 

The answer to this question seems to be the greatest problem of the
contravariant geometry description:

  In general, it is not possible to avoid topological errors
without having any additional information.
 

Indeed, there may be very thin subregions inside a region. If we find
such a subregion depends on the grid density and accident. If the
subregion is so thin that no point of the finest grid will be inside,
we have no chance to detect that there is such a subregion.

 <p>Remark that this is a consequence of the possibility to define
cogeometries with an infinite number of regions and other cogeometries
with such infinite properties like Julia set's or the Mandelbrot
set. Such geometries obviously have to be simplified by any finite
grid.
 <p>On the other hand, this description shows that dangerous situations
have some special structure. We can classify such dangerous subregions
by a "codimension" which is simply the number of the "very thin
directions". For codimension 1, we have a crack.  For codimension 2 a
channel, for the maximal codimension an enclave. There may be also
segments of higher codimension which may be dangerous. They all have
some common properties:

 
 <ul>
 <li>They are small.
 
 <li>Their environment is highly non-convex.
 
 </ul>


This leads to two strategies to avoid errors:

 
 <ul>
 <li>Further refinement.
 
 <li>To remove highly non-convex situations using artificial
subdivision.
 
 </ul>


The first strategy may be used in problems where topological errors in
principle are not very dangerous if they are small enough. In the
second strategy, we simply subdivide the environment into parts. The
search operation for the additional boundaries and subboundaries
allows to detect the thin segment.

 <p>Let's show that this strategy is universal. In principle, we have
to consider only geometries which may be approximated by a grid. But a
grid may be considered as a subdivision of the segments into convex
parts. Now let's show that a geometry described only by convex
segments is not dangerous:

 There is a grid generation algorithm which allows to
define the cogeometry in a given region without topological errors (in
exact real arithmetics) for an arbitrary finite cogeometry consisting
only of convex segments.
 

 Let's describe this algorithm. We start with a simplicial grid
containing the region of interest. In the first step, we detect the
segment of all nodes of the grid by calls of f(0).
  <p> In the step k we detect the topology of the k-dimensional sides
of the simplices, based on the correct detection of the topology of
the sides. We use the function f(k) with all (k-1)-flags which have
been detected on the boundary of the side. If we obtain more than one
intersection point inside the side, we subdivide the side into
parts. For the boundary between the parts, the previous step allows to
define the geometry and topology correctly. This subdivision ends
caused by the finite number of segments and the trivial fact that in
general there may be only one intersection between a convex segment
and a simplex of related codimension. Caused by the convexity of the
segments, for every pair of flags we have found the line between them
will be in the same segment. At least, we define the segments as the
convex hull of all points of the segment we have found in the
algorithm (inclusive the boundary points).
  <p>It can be easily proved per induction over the dimension of the
sides and for each side dimension per induction over the dimension of
the segments that every point on a side may be described by a convex
linear combination of such points. The begin of induction over the
sides are the corners defined with f(0). The begin of induction on
each part of a side is the single intersection point on the side.  We
use the fact that a convex segment is planar and consider a line in
this segment and the side through a point. This line ends on a
boundary of the side or on a boundary point of the segment.  The
boundary point of the segment is part of a segment with lower
dimension. Thus, for above ends we obtain such a required linear
combination using the induction. That's why we obtain it also for our
point.
  <p>We have not considered here the case of degeneration. But the
geometry is defined by a finite number N of real numbers (the vertex
coordinates).  That's why, if in the algorithm we obtain a
degeneration, we can simply restart the algorithm with an irrational
modification of the initial values. At least after N such restarts
(every time with an irrational modification independent of the
previous) there will be no degeneracy. This proves the theorem.
 

In reality, it is not necessary to subdivide all segments into
approximately convex parts. Only small, very non-convex parts have to
be modified. Usually, if all details of the geometry are so big that
there will be some points of the grid inside, it is not necessary to make
such subdivisions.

 <p>Subdivisions may be useful also to obtain sharp edges and
corners. If we do not subdivide the faces of a boundary edge, the
position of the edge may not be detected. That means, the edge or the
corner will be rounded. To avoid this effect, we can subdivide the
boundary face into two parts with a boundary line between them. Now,
the previous algorithm easily detects the edge and computes
explicitly grid nodes on the boundary line. Subdividing the boundary
line by a vertex at the position of the corner also leads in this
algorithm to an explicit grid node at the corner.