Abstract: Angenommen, wir haben eine natürliche Zahl n, und wir setzen n wiederholt auf eine zufällige Zahl zwischen 0 und n-1, solange bis wir Null erhalten. Was ist die erwartete Anzahl von Runden, bis das passiert? Während dieses Spiel noch einfach zu analysieren ist, gibt es andere, fast ebenso einfach zu beschreibende andere Spiele, deren asymptotisches Verhalten unbekannt ist. Im Vortrag möchte ich zeigen, was diese Spiele mit randomisierten Pivotregeln für die Simplexmethode zu tun haben, und warum solche Regeln einserseits so vielversprechend, andererseits aber auch so schwierig zu analysieren sind.
Abstract: For many years, the finite element method has been successfully applied by engineers in simulations. But such a method needs a tool as a prerequisite, which converts a CAD model into a finite element mesh model suitable for a numerical analysis. Therefore, various algorithms for the generation of meshes have been developed, mostly decomposing surfaces into triangles and solid bodies into tetrahedra. In many applications, however, quadrilateral and hexahedral meshes have numerical advantages. Recent years showed many research efforts and brought up several approaches, but up to now, hexahedral mesh generation for an arbitrary 3D solid is still a challenge. We propose a new method for constructing all-hexahedral finite element meshes. The key idea is to separate the mesh generation process into a combinatorial part, where an abstract cell complex of hexahedra is constructed from a surface mesh, and a geometric embedding part, where the exact positions of the mesh nodes are determined. The step-wise creation of the hex complex is guided by the cycle structure of the combinatorial dual of the surface mesh. Our method transforms the graph of the surface mesh iteratively by changing the dual cycle structure until we get the surface mesh of a single hexahedron. Starting with a single hexahedron and reversing the order of the graph transformations, each transformation step can be interpreted as adding one or more hexahedra to the so far created hex complex.