Die in dieser Arbeit vorgestellte Kompositionsmethode beschäftigt sich damit, bestimmte Aufgabenstellungen aus dem Bereich der Berechnung von Graphenkenngrößen und Grapheninvarianten in endlichen ungerichteten Graphen und Hypergraphen in ein einheitliches Schema einzuordnen und so die Umsetzung in Algorithmen zu erleichtern. Dabei werden zwei Hauptziele verfolgt. Zum einen soll die Menge der mit der Methode lösbaren Aufgaben möglichst groß sein, und zum anderen sollen die entstandenen Algorithmen tatsächliche Berechnungen in einigen Netzen praxisrelevanter Größe ermöglichen. Die Kompositionsmethode belegt mit ihren Zielen somit den Bereich zwischen zwei Extremen der Algorithmenentwicklung: Auf der einen Seite steht die Erzeugung von Spezialalgorithmen, die oft so stark an bestimmte Eigenschaften der zu berechnenden Größen gekoppelt sind, dass eine Anpassung an leicht veränderte Aufgabenstellungen nur schwer möglich ist bzw. unter Umständen der Entwicklung eines völlig neuen Algorithmus gleichkommt; auf der anderen Seite stehen die allgemeingültigen Ansätze, deren Umsetzung häufig zu Algorithmen führt, die bereits für sehr kleine Netze nicht mehr praktisch durchführbar sind. Die gestellten Ziele werden durch eine Formalisierung der Aufgabenstellungen erreicht, deren Ergebnisse direkt in Algorithmen umgesetzt werden können. Dabei müssen jeweils nur wenige aufgabenspezifische Details formuliert werden, die anschließend in einen von der konkreten Aufgabe unabhängigen Rahmenalgorithmus eingebunden werden. Ein solches Verfahren ist aus Sicht eines Anwenders aus der Praxis besonders interessant, da der Rahmenalgorithmus nur ein einziges Mal implementiert werden muss und somit bei wiederholter Verwendung der Methode der Entwicklungsaufwand für die erzeugten Kompositionsalgorithmen erheblich sinkt. Bislang wurden mit Hilfe der Kompositionsmethode zirka dreißig Problemstellungen von der Berechnung chromatischer Invarianten über das Zählen von Hamiltonkreisen bis hin zur Bestimmung von Zuverlässigkeitskenngrößen von stochastischen Netzen bearbeitet. Die von der Methode erzeugten Algorithmen sind dabei in aller Regel nicht optimal in Bezug auf Laufzeit und Speicherbedarf. Dieser Nachteil wird allerdings durch den extrem geringen Entwicklungsaufwand und durch die Anwendbarkeit der Methode auf neue Aufgabenstellungen, für die noch keine Spezialalgorithmen existieren, kompensiert. Besonders bei der Berechnung bestimmter Zuverlässigkeitskenngrößen sowie bei der Lösung von #P-vollständigen Abzählproblemen können die Kompositionsalgorithmen aber auch aktuelle Spezialalgorithmen übertreffen.

Ein zentrales Problem der quantitativen Texturanalyse ist die numerische Inversion der eindimensionalen Radontransformation auf der Lie--Gruppe SO(3) aller Rotationen im dreidimensionalen euklidischen Raum. In der vorliegenden Dissertation wird die Lösbarkeit und Eindeutigkeit dieses inversen Problems untersucht und Fehlerabschätzungen unter Berücksichtigung unvollständiger und fehlerbehafteter Daten hergeleitet. Weiterhin wird ein Algorithmus zur Lösung des inversen Problems vorgeschlagen, welcher auf einer Diskretisierung mittels radialer Basisfunktionen basiert und schnelle Fouriermethoden auf der Kugel und der Lie-Gruppe SO(3) benutzt. In numerischen Tests wird gezeigt, dass der Algorithmus für die Rekonstruktion scharfer Texturen aus Beugungsdaten gemessen auf einem hochauflösenden, ungleichmäßigen Messraster geeignet ist.

We present a method for determining the reduced Gröbner basis with respect to a given admissible term order of order type ! of the intersection ideal of an infinite sequence of polynomial ideals. As an application we discuss the Lagrange type interpolation on algebraic sets and the 'approximation' of the ideal I of an algebraic set by zero dimensional ideals, whose affine Hilbert functions converge towards the affine Hilbert function of I.

No description available.

We introduce the notion of nested distance desert automata as a joint generalization and further development of distance automata and desert automata. We show that limitedness of nested distance desert automata is PSPACE-complete. As an application, we show that it is decidable in 22O(n2) space whether the language accepted by an n-state non-deterministic automaton is of a star height less than a given integer h (concerning rational expressions with union, concatenation and iteration). We also show some decidability results for some substitution problems for recognizable languages.

Following the mechanisms, where the coarse geometric properties of a space with bounded geometry can induce properties on the related coarse (boundary) groupoid and vice versa, we prove that a sequence of bounded degree graphs being hyperfinite is equivalent to the equivalence relation induced by the coarse boundary groupoid associated to this sequence being hyperfinite. Even more, we introduce a coarse and weaker notion of Property A in a sequence of graphs, called Property A on average, that also turns out to be equivalent to the hyperfiniteness of a sequence of bounded degree graphs. Furthermore, we show that if the coarse boundary groupoid is topologically a-T-menable, then the related sequence of bounded degree graphs is asymptotically coarsely embeddable into a Hilbert space. In the measurable case, we also have the asymptotic coarse embeddability of the sequence of graphs after discarding small subgraphs along the sequence and looking at this new sequence of graphs with the induced length metric of original graph. Afterwards those result are applicable to sofic groups. When we take the sequence of graphs to be a sofic approximation of an amenable discrete finitely generated sofic group, we know that this sequence is hyperfinte, has property A on average and property almost-A. If the group is a-T-menable then the sequence of graphs is weakly asymptotically coarsely embeddable into a Hilbert space.

This thesis studies two Markov processes describing the evolution of a system of many interacting random components. These processes undergo an absorbing-state phase transition, i.e., as one variates the parameter values, the process exhibits a transition from a convergence regime to one of the absorbing-states to an active regime. In Chapter 2 we study Activated Random Walk, which is an interacting particle system where the particles can be of two types and their number is conserved. Firstly, we provide a new lower bound for the critical density on Z as a function of the jump distribution and of the sleeping rate and we prove that the critical density is not a constant function of the jump distribution. Secondly, we prove that on Zd in the case of biased jump distribution the critical density is strictly less than one, provided that the sleeping rate is small enough. This answers a question that has been asked by Dickman, Rolla, Sidoravicius [9, 28] in the case of biased jump distribution. Our results have been presented in [33]. In Chapter 3 we study a class of probabilistic cellular automata which are related by a natural coupling to a special type of oriented percolation model. Firstly, we consider the process on a finite torus of size n, which is ergodic for any parameter value. By employing dynamic-renormalization techniques, we prove that the average absorption time grows exponentially (resp. logarithmically) with n when the model on Z is in the active (resp. absorbing) regime. This answers a question that has been asked by Toom [37]. Secondly, we study how the neighbourhood of the model affects the critical probability for the process on Z. We provide a lower bound for the critical probability as a function of the neighbourhood and we show that our estimates are sharp by comparing them with our numerical estimates. Our results have been presented in [34, 35].

The paper describes a storage scheme for sparse symmetric or nonsymmetric matrices which has been developed and used for many years at the Technical University of Chemnitz. An overview of existing library subroutines using such matrices is included.

In this paper, we investigate the question of the spectrally equivalence of the so- called Pseudo-Laplacian to the usual discrete Laplacian in order to use hierarchical preconditioners for this more complicate matrix. The spectral equivalence is shown to be equivalent to a Brezzi-type inequality, which is fulfilled for the finite element spaces considered here.

The paper mainly describes the user interface of some graphical visualization tools for parallel finite element applications in 2D (layer problems, deformation problems, fluid dynamics). There are presented some examples of various methods to display the numerical results.