Elimination and Counting via Thomas Decomposition

• Applicant: Professor Dr. Wilhelm Plesken
• Subject Area: Mathematics
• Term: from 2010 to 2014
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 171336561

• Final Report Year: 2014

Final Report Abstract

The goal of this project was to study the triangulation algorithm of J. M. Thomas within a modern framework of commutative algebra, algebraic geometry, and differential algebra. This decomposition algorithm decomposes algebraic and differential equations disjointly into so-called simple systems. As first objective, both the implementations of the algebraic and differential algorithms were optimized. For the algebraic case, the algorithms were adapted to positive characteristic and can now also compute so-called comprehensive decompositions. The Thomas decomposition allows to define and compute the counting polynomial of a constructible set in affine or projective space and of toric varieties. This polynomial is a very fine description of the size of a constructible set; in fact, it contains enough information to decide whether two constructible sets contained in each other are equal. The counting polynomial was studied abstractly and could be characterized axiomatically. It generalizes the dimension and Euler characteristic as a description of a constructible set. In some cases, the counting polynomial can be used to count the number of solutions of a polynomial system over a finite field. Among the applications are codes and matroids. In the case of differential systems, Kolchin's dimension polynomial describes the number of coefficients which can generically be chosen freely in a power series solution. The dimension polynomial was extended from prime differential ideals to simple systems. Thereby, the dimension polynomial and other invariants it implies, like Cartan characters or Einstein's strength, were made fully algorithmic. The differential counting polynomial was introduced as a generalization of the differential dimension polynomial to describe the solution set of a system of differential equations in a more detailed way. It is strong enough to decide equality for solution sets of differential equations under mild additional assumptions. However, its computation could be shown not to be algorithmic. Thus, at best one can hope for a collection of methods to compute the differential counting polynomial of many important classes of systems of differential equations. Such methods could be described for several classes of interesting systems of differential equations. To the surprise of the investigators, examples of differential equations could be found with infinite exceptional sets in their solution set. As a further important application of the Thomas decomposition, differential elimination was studied. The Thomas decomposition sets itself apart from other algorithms in differential algebra because it leads to disjoint decompositions, which was fundamental to many examples, e.g. parametric system-theoretic examples with applications to control theory.

Publications

• Thomas decomposition of algebraic and differential systems. In Proceedings of the 12th international conference on Computer algebra in scientific computing, Springer Lecture Notes in Computer Science Volume 6244, pages 31–54, 2010
  T. Bächler, V. P. Gerdt, M. Lange-Hegermann, and D. Robertz
  
• An axiomatic setup for algorithmic homological algebra and an alternative approach to localization. J. Algebra Appl., 10(2):269–293, 2011
  Mohamed Barakat and Markus Lange-Hegermann
  
• Localizeringforhomalg: localize commutative rings at maximal ideals. ACM Commun. Comput. Algebra, 44:201–204, January 2011
  Mohamed Barakat and Markus Lange-Hegermann
  
• Thomas decomposition and its applications. ACM Commun. Comput. Algebra, 44(3/4):91–92, January 2011
  T. Bächler, V. P. Gerdt, M. Lange-Hegermann, W. Plesken, and D. Robertz
  
• Algorithmic Thomas decomposition of algebraic and differential systems. J. Symbolic Comput., 47(10):1233–1266, 2012
  T. Bächler, V. P. Gerdt, M. Lange-Hegermann, and D. Robertz
  
• Formal Algorithmic Elimination for PDEs. Habilitationsschrift, Faculty of Mathematics, Computer Science and Natural Sciences, RWTH Aachen University, 2012
  D. Robertz
  
• On the Extcomputability of Serre quotient categories. Journal of Algebra, 2012
  Mohamed Barakat and Markus Lange-Hegermann
  
• Computing ext in serre quotient categories. In Mini-Workshop: Constructive homological algebra with applications to coherent sheaves and control theory, number 25 in Oberwolfach Reports, pages 1508–1511. MFO, Oberwolfach, 2013
  Mohamed Barakat and Markus Lange-Hegermann
  
• Numerical flux functions for Reynolds-averaged Navier-Stokes and kω turbulence model computations with a line-preconditioned p-multigrid discontinuous Galerkin solver. International Journal for Numerical Methods in Fluids, 71:1055–1072, June 2013
  M. Wallraff, T. Leicht, and M. Lange-Hegermann
  
• On monads of exact reflective localizations of Abelian categories. Homology, Homotopy and Applications, 15(2):145–151, 2013
  Mohamed Barakat and Markus Lange-Hegermann
  
• Thomas decomposition of parametric nonlinear control systems. In proceedings of the IFAC Joint conference, pages 296–301, 2013
  M. Lange-Hegermann and D. Robertz
  
• Characterizing Serre quotients with no section functor and applications to coherent sheaves. Appl. Categor. Struct., 22(3):457–466, 2014
  Mohamed Barakat and Markus Lange-Hegermann
  
• Counting polynomials for linear codes, hyperplane arrangements, and matroids. Documenta Math., 19(9):247– 284, 2014
  W. Plesken and T. Bächler
  
• Counting Solutions of Algebraic Systems via Triangular Decomposition. PhD thesis, RWTH Aachen, Germany, 2014
  T. Bächler
  
• Counting Solutions of Differential Equations. PhD thesis, RWTH Aachen, Germany, 2014
  M. Lange-Hegermann