Thomas Decomposition of Algebraic and Differential Systems

Thomas Bächler, Vladimir P. Gerdt, Markus Lange-Hegermann, Daniel RobertzCASC 2010 · OpenReview

TL;DR

This paper presents a novel algorithm for decomposing systems of algebraic and differential equations into "simple" subsystems. This decomposition is "disjoint," meaning the solution sets of the output subsystems do not overlap, which is a significant advantage over existing methods. The algorithm has been implemented in Maple and offers a powerful new tool for analyzing complex systems in mathematics and physics.

What Problem Does This Paper Address?

Solving systems of polynomial and differential equations is a fundamental challenge in many scientific disciplines. While methods like Gröbner bases exist, they can be computationally expensive. Triangular decomposition methods, particularly the THOMAS decomposition, offer an alternative by breaking down complex systems into simpler, more manageable parts. However, existing THOMAS decomposition algorithms often lack a "disjoint" decomposition, meaning the solution sets of the resulting subsystems can overlap, complicating interpretation. This paper addresses this by developing a new algorithm that guarantees a disjoint decomposition, ensuring that each part of the solution space is uniquely represented.

Methods

The core of this work is a new algorithmic version of the THOMAS decomposition. For algebraic systems, "simplicity" is defined by triangularity, square-freeness, and non-vanishing initials. For differential systems, the algorithm extends these properties to include "involutivity," a crucial concept in differential algebra. The algorithm iteratively processes systems, using subalgorithms like InitSplit, ResSplit, ResSplitGCD, and ResSplitDivide to split systems based on polynomial initials and resultants. These techniques ensure that the resulting subsystems meet the criteria for simplicity. The differential part of the algorithm builds upon the algebraic foundation by incorporating concepts from Janet division and differential algebra, using specialized reduction and insertion algorithms. The entire process is implemented in the MAPLE computer algebra system.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Disjoint Decomposition is Key: The primary innovation is the guarantee of a disjoint decomposition. This is a significant improvement over previous methods where solution sets could overlap, making it hard to isolate specific solution behaviors.
  • Bridging Algebraic and Differential: The paper elegantly extends the algebraic THOMAS decomposition to handle differential systems, leveraging Janet division and involutive bases to manage the infinite nature of differential variables.
  • "Simple" Systems as Building Blocks: The definition of "simple" systems (triangular, square-free, non-vanishing initials for algebraic; plus involutive for differential) provides a clear target for the decomposition process.
  • Algorithmic Elegance: The use of specialized splitting and reduction algorithms (InitSplit, ResSplit, etc.) demonstrates a systematic approach to achieving the desired decomposition properties.

Key Results

The paper presents a new algorithm for THOMAS decomposition that guarantees disjointness for both algebraic and differential systems. This algorithm has been implemented in MAPLE. While specific quantitative results (e.g., performance benchmarks against other algorithms) are not detailed in this excerpt, the core contribution is the algorithmic framework and its implementation, which provides a more robust and interpretable decomposition of complex systems. The paper includes an example of the Cole-Hopf transformation to illustrate the differential decomposition.

Limitations and Future Work

The authors acknowledge that proofs are omitted for compactness and will be published elsewhere. They also mention that further work will explore applications benefiting from simple systems and compare their implementation with other decomposition methods. The paper hints at future research on modeling differential fields and the use of these decomposition techniques in various scientific applications. The implementation details are discussed, but a comprehensive performance analysis is not presented in this excerpt.

Summary updated

Abstract

In this paper we consider disjoint decomposition of algebraic and non-linear partial differential systems of equations and inequations into so-called simple subsystems. We exploit Thomas decomposition ideas and develop them into a new algorithm. For algebraic systems simplicity means triangularity, squarefreeness and non-vanishing initials. For differential systems the algorithm provides not only algebraic simplicity but also involutivity. The algorithm has been implemented in Maple.
BibTeX
@inproceedings{bachler2010thomas,
  author = {Thomas Bächler and Vladimir P. Gerdt and Markus Lange-Hegermann and Daniel Robertz},
  title = {{Thomas Decomposition of Algebraic and Differential Systems}},
  booktitle = {CASC},
  year = {2010},
  url = {https://openreview.net/forum?id=RjWiu0UuSD},
}
Figure