Algorithms for Symbolic Computation and their Applications - Standard Bases over Rings and Rank Tests in Statistics

In the first part of the thesis we develop the theory of standard bases in free modules over (localized) polynomial rings. Given that linear equations are solvable in the coefficients of the polynomials, we introduce an algorithm to compute standard bases with respect to arbitrary (module) monomial orderings. Moreover, we take special care to principal ideal rings, allowing zero divisors. For these rings we design modified algorithms which are new and much faster than the general ones. These algorithms were motivated by current limitations in formal verification of microelectronic System-on-Chip designs. We show that our novel approach using computational algebra is able to overcome these limitations in important classes of applications coming from industrial challenges. The second part is based on research in collaboration with Jason Morton, Bernd Sturmfels and Anne Shiu. We devise a general method to describe and compute a certain class of rank tests motivated by statistics. The class of rank tests may loosely be described as being based on computing the number of linear extensions to given partial orders. In order to apply these tests to actual data we developed two algorithms and used our implementations to apply the methodology to gene expression data created at the Stowers Institute for Medical Research. The dataset is concerned with the development of the vertebra. Our rankings proved valuable to the biologists.Im ersten Teil der Dissertation wird die Theorie der Standardbasen in freien Moduln über (lokalisierten) Polynomialringen entwickelt. Falls lineare Gleichungen in den Koeffizienten der Polynome lösbar sind, entwickeln wir Algorithmen um Standardbasen bezüglich beliebiger (Modul-) Monomordnungen zu berechnen. Weiterhin untersuchen wir den Fall von Hauptidealringen mit Nullteilern. Wir implementieren für diesen Fall modifizierte neue Algorithmen, welche deutlich performanter als die generischen sind. Die Implementierung wurde durch bestehende Restriktionen bei der Verifikation von System-on-Chip Layouts motiviert. Wir zeigen, dass die neue Herangehensweise mit Methoden der Computeralgebra bestehende Beschränkungen der industriellen Anwendung überwindet. Der zweite Teil basiert auf gemeinsamer Forschung mit Jason Morton, Bernd Sturmfels und Anne Shiu. Wir entwickeln eine allgemeine Methode um eine bestimmte Klasse von Ranktests zu beschreiben und zu berechnen. Diese Klasse kann vereinfacht durch Partialordnungen sowie die Berechnung ihrer linearen Erweiterungen beschrieben werden. Um die Tests in der Praxis anwenden zu können entwickeln wir zwei Algorithmen. Die Implementation wurde für die Bewertungen von Genexpressionsdaten genutzt, welche am Stowers Institute for Medical Research erhoben wurden. Der verwendete Datensatz dient der Untersuchung der Entwicklung der Wirbelsäule in Embryonen. Die Rangfolgen, welche von den Tests generiert wurden, waren hilfreich