Finite element methods with hierarchical WEB-splines

Abstract

Piecewise polynomial approximations are fundamental to geometric modeling, computer graphics, and finite element methods. The classical finite element method uses low order piecewise polynomials defined on polygonal domains. The domains are discretized into simple polygons called the mesh. These polygons might be triangles, quadrilaterals, etc., for two-dimensional domains, and tetrahedra, hexahedra, etc., for three-dimensional domains. Meshing is often the most timeconsuming process in finite element methods. In classical two-dimensional finite element methods, the basis functions are usually hat functions defined on triangulations. Another possible selection of a finite element basis in two dimensions are tensor product b-splines.

Bivariate B-splines are piecewise polynomials of degree n with support having (n+1)² cells. The domain is discretized via a uniform grid. Relevant are those b-splines for which the support intersects the domain. To keep the support of a relevant B-spline within the domain, we multiply it by a weight function. The weight function is positive in the interior of the domain and vanishes on the boundary and outside of the domain. The resulting weighted B-splines conform to homogeneous boundary conditions. They satisfy the usual properties of a finite element basis.

The insertion of new knots into the grid is not a good adaptive strategy because of the global effect of knot insertion.Instead, hierarchical refinement is very effective for tensor product splines. It permits the change of control points and subsequent editing of fine details in some parts while keeping the other parts unaffected. For programming, a data structure is required that not only keeps track of the refinement but also stores the information about the discretization of the domain. Moreover, algorithms for assembling and solving the finite element system are needed. In this thesis, we have developed such adaptive schemes with weighted B-splines and implemented them in MATLAB with an appropriate data structure.

We proposed two different adaptive schemes for the selection of the sequence of subdomains characterizing the refinement. The first scheme uses a predefined and strongly nested domain sequence, appropriate, e.g., near a reentrant corner of the domain. For strongly nested domains, the distance between the boundary of the subdomain with grid width h and the subdomain with grid width h/2 is ≥ (2n+1)h. For such a domain sequence, an error estimate can be obtained.

The second adaptive scheme is an automatic refinement process.The refinement is determined by comparing the B-spline coefficients of an approximation with those of an approximation obtained by refining all subdomains.The hierarchical refinement is then based on the regions where the difference between the coefficients exceeds a given tolerance. Both adaptive schemes yield convergence of the hierarchical approximations. The adaptive schemes are tested by solving Poisson's problem on domains with reentrant corners with refinement in the neighborhood of the geometric singularity.

Stückweise polynomiale Approximationen spielen in der Geometrischen Modellierung, Computer graphik und bei Finite-Elemente-Methoden eine fundamentale Rolle. Klassische Finite-Elemente-Verfahren benutzen stückweise Polynome niedriger Ordnung auf polygonalen Gebieten. Die Gebiete werden in einfache Polygone, das so genannte Netz, zerlegt. Diese Polygone können für zweidimensionale Gebiete beispielsweise Dreiecke oder Vierecke sein, für dreidimensionale Gebie-te Tetraeder oder Hexaeder. Die Netzgenerierung ist oft der zeitaufwändigste Prozess in der Finite-Elemente-Methode. In der klassischen Finite-Elemente-Methode sind die Basisfunktionen in zwei Dimensionen meist auf Triangulierungen definierte Hut-Funktionen.Eine andere mögliche Wahl einer bivariaten Finite-Elemente-Basis sind Tensor-Produkt-B-Splines.

Bivariate B-Splines sind stückweise Polynome vom Grad n mit einem Träger, bestehend aus (n+1)² Gitterzellen. Das Gebiet wird durch ein uniformes Gitter diskretisiert. Relevant sind diejenigen B-Splines, deren Träger das Gebiet schneidet. Um den Träger eines relevanten B-Splines auf das Gebiet einzuschränken, wird er mit einer Gewichtsfunktion multipliziert. Die Gewichtsfunktion ist im Innern des Gebietes positiv und verschwindet auf dem Rand und außerhalb des Gebietes. Die resultierenden gewichteten B-Splines erfüllen homogene Randbedingungen. Sie besitzen die üblichen Eigenschaften einer Finite-Elemente-Basis.

Das Einfügen neuer Knoten in das Gitter ist keine gute adaptive Strategie aufgrund der globalen Auswirkung des Knoteneinfügens.Stattdessen ist eine hierarchische Verfeinerung für Tensorprodukt-Splines sehr effektiv. Sie erlaubt eine lokale Änderung von Kontrollpunkten mit anschließender Modifikation kleiner Details in einigen Bereichen, ohne dabei andere Bereiche zu beeinflussen. Zur Programmierung ist eine Datenstruktur notwendig, die sowohl die Verfeinerung beschreibt als auch die Diskretisierung des Gebietes berücksichtigt. Des Weiteren werden Algorithmen zur Aufstellung und Lösung des Finite-Elemente-Systems benötigt. In dieser Dissertation wurden solche adaptive Verfahren für gewichtete B-Splines entwickelt und mit einer entsprechenden Datenstruktur in MATLB implementiert.

Es wurden zwei verschiedene adaptive Schemata für die Auswahl der Folge der Teilgebiete, die die Verfeinerung beschreiben, vorgeschlagen. Das erste Schema benutzt eine vorab definierte stark geschachtelte Gebietsfolge, wie sie beispielsweisein der Umgebung einer einspringenden Ecke sinnvoll ist. Für eine stark geschachtelte Gebietsfolge ist der Abstand zwischen dem Rand des Gebiets mit Gitterweite h und dem Gebiet mit Gitterweite h/2 ≥ (2n+1)h. Für eine solche Gebietsfolge kann eine Fehlerabschätzung gezeigt werden.

Das zweite adaptive Schema ist ein automatischer Unterteilungsprozess. Die Unterteilung wird durch Vergleich der B-Spline-Koeffizienten einer Approximation mit denen einer Approximation, die durch Unterteilung aller Teilgebiete entsteht, bestimmt. Die hierarchische Unterteilung basiert dann auf den Bereichen, bei denen die Differenz zwischen den Koeffizienten eine vorgegebene Toleranz überschreitet. Für beide adaptiven Schemata erhält man Konvergenz der hierarchischen Approximationen. Die adaptiven Schemata wurden für das Poisson-Problem auf Gebieten mit einspringenden Ecken mit Verfeinerung in der Umgebung der geometrischen Singularität getestet.