Understanding the Computational Complexity of Mathematica's `CylindricalDecomposition`

Cylindrical decomposition is a crucial algorithm within symbolic computation, primarily used for quantifier elimination over real numbers. In Wolfram Mathematica, `CylindricalDecomposition` is an essential function that simplifies logical formulas involving inequalities over the real numbers. This article aims to delve into the computational complexity of this function, providing insight into its underlying mechanics, applications, and performance implications.

Cylindrical Algebraic Decomposition (CAD)

At the heart of `CylindricalDecomposition` lies the Cylindrical Algebraic Decomposition (CAD) algorithm, which partitions $\mathbb{R}^n$ into disjoint semi-algebraic sets. These "cylinders" correspond to simple, quantifier-free formulas. This decomposition makes it exceedingly useful for solving problems in real algebraic geometry and for simplifying multivariate polynomial systems with real coefficients.

Technical Explanation

Algorithm Overview

The CAD algorithm proceeds through the following high-level steps:

1. Projection: It reduces the problem from $n$ variables to $n-1$ variables by projecting the critical set of points (where the polynomial or their derivatives are zero) onto a lower-dimensional space.
2. Base Case Handling: For the univariate case (e.g., when $n=1$), it partitions the real line based on the roots of polynomials.
3. Lifting: It reconstructs the information from the lower-dimensional decomposition back into the original $n$-dimensional space to form "cylinders".

Complexity Analysis

The theoretical complexity of CAD, as first developed by Collins, can be daunting. It is doubly exponential in the number of variables. More formally, given a polynomial system of degree $d$ in $n$ variables, the complexity of cylindrical decomposition is often described as:

$$\mathcal{O}(d^{2^{\mathcal{O}(n)}})$$

While optimizations and heuristic methods can improve practical performance, the worst-case remains theoretically costly due to this double exponential dependence on the number of variables.

Example Application

Consider a simple system of inequalities:

• Number of Variables: The complexity grows doubly exponentially with the number of variables. • Polynomial Degree: The degree of input polynomials impacts the cost, as higher-degree polynomials necessitate more complex decomposition. • Optimization Techniques: Modern implementations, including those in Mathematica, use improvements like partial CAD, subtle variable orderings, and heuristic pruning to alleviate some computational burdens. • Variable Ordering: Intelligent choice of which variable to eliminate first can drastically reduce computation time. • Partial CAD: A refinement focuses only on the region of interest, potentially lowering complexity. • Parallel Computing: Leveraging modern computing infrastructure can help manage workload for larger systems.