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.

Export metadata

Metadaten
Author:Oliver Wienand
URN:urn:nbn:de:hbz:386-kluedo-27467
Publisher:Wipprecht Stiftung
Place of publication:Frankfurt am Main
Advisor:Gert-Martin Greuel
Document Type:Doctoral Thesis
Language of publication:English
Date of Publication (online):2011/09/23
Date of first Publication:2011/09/21
Publishing Institution:Technische Universität Kaiserslautern
Granting Institution:Technische Universität Kaiserslautern
Acceptance Date of the Thesis:2011/07/01
Date of the Publication (Server):2011/09/27
Tag:Order; Rank test; Standard basis
GND Keyword:Mathematik
Page Number:153
Faculties / Organisational entities:Kaiserslautern - Fachbereich Mathematik
CCS-Classification (computer science):I. Computing Methodologies / I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION (REVISED) / I.1.2 Algorithms (F.2.1-2)
DDC-Cassification:5 Naturwissenschaften und Mathematik / 510 Mathematik
MSC-Classification (mathematics):05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Axx Enumerative combinatorics For enumeration in graph theory, see 05C30 / 05A05 Permutations, words, matrices
05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Axx Enumerative combinatorics For enumeration in graph theory, see 05C30 / 05A19 Combinatorial identities, bijective combinatorics
05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Cxx Graph theory (For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15) / 05C30 Enumeration in graph theory
06-XX ORDER, LATTICES, ORDERED ALGEBRAIC STRUCTURES [See also 18B35] / 06Axx Ordered sets / 06A06 Partial order, general
06-XX ORDER, LATTICES, ORDERED ALGEBRAIC STRUCTURES [See also 18B35] / 06Dxx Distributive lattices / 06D99 None of the above, but in this section
13-XX COMMUTATIVE RINGS AND ALGEBRAS / 13Pxx Computational aspects and applications [See also 14Qxx, 68W30] / 13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
13-XX COMMUTATIVE RINGS AND ALGEBRAS / 13Pxx Computational aspects and applications [See also 14Qxx, 68W30] / 13P25 Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.)
62-XX STATISTICS / 62Gxx Nonparametric inference / 62G86 Nonparametric inference and fuzziness
Licence (German):Standard gemäß KLUEDO-Leitlinien vom 27.05.2011