Embedding polynomial systems into vertically parametrised families: A case study on ODEbase

Basic Information

• Paper ID: 2501.00156
• Title: Embedding polynomial systems into vertically parametrised families: A case study on ODEbase
• Authors: Oliver Daisey, Yue Ren, Yuvraj Singh (Durham University)
• Classification: math.AG (Algebraic Geometry)
• Publication Date: December 30, 2024
• Paper Link: https://arxiv.org/abs/2501.00156

Abstract

Vertically parametrised polynomial systems constitute a special class of parametrised polynomial systems whose interesting algebraic information is encoded in their combinatorial structure. Given a fixed polynomial system, this paper empirically investigates what constitutes a good vertically parametrised polynomial system that generates it, and how to construct such systems. The study utilizes all polynomial systems from ODEbase as data, transcribing them into OSCAR-readable format, provided as the Julia package OscarODEbase.

Research Background and Motivation

Problem Context

1. Importance of Vertically Parametrised Systems: Vertically parametrised polynomial systems describe steady states in mass-action kinetics, with many interesting properties encoded in their (tropical) combinatorial structure, including:
   • Solution sets always possess the expected dimension and at least one smooth point
   • For the generic zero-dimensional case, both the generic number of complex solutions and lower bounds on positive solutions can be computed combinatorially via tropical geometry
   • Optimal homotopies can be constructed through tropical geometric combinatorics
2. Embedding Problem: Given a polynomial system F, how to find a "good" vertically parametrised system F̃ such that F = F̃_P for some parameter choice P
3. Practical Requirements: In applications such as biochemical reaction networks, it is necessary to embed concrete polynomial systems into parametrised families to leverage the favorable properties of vertically parametrised systems

Research Motivation

• Existing theory indicates that vertically parametrised systems possess good algebraic properties, but lacks practical guidance on constructing "good" embeddings
• ODEbase provides a large collection of real polynomial systems from biological systems, offering an ideal data source for empirical research
• There is a need to develop practical algorithms for constructing near-optimal embeddings

Core Contributions

1. Identified discriminative criteria for good embeddings: Through empirical study of systems in ODEbase, discovered that minimizing the number of distinct monomials is the primary characteristic distinguishing good embeddings
2. Proposed a greedy alignment algorithm: For the NP-hard problem of constructing good embeddings, developed a practical greedy algorithm
3. Developed the OscarODEbase.jl package: Converted 190 polynomial models from ODEbase into OSCAR-readable format, facilitating related research
4. Provided an empirical analysis framework: Established a scoring system for evaluating embedding quality and experimental methodology

Detailed Methodology

Task Definition

Input: Polynomial system F = {f₁, ..., fₖ} ⊆ Kx±
Output: Vertically parametrised system F̃ such that F = F̃_P for some parameter P, with F̃ possessing good algebraic properties
Objective: The generic root count of F̃ should match the solution count of F, reflecting the genericity of F̃

Core Concepts

Vertically Parametrised Systems

A vertically parametrised polynomial system F̃ = {f₁, ..., fₖ} ⊆ K[a]x± has the form:

fᵢ := Σⱼ₌₁ᵐ cᵢ,ⱼ aⱼ x^αⱼ

where S = {α₁, ..., αₘ} ⊆ Zⁿ, cᵢ,ⱼ ∈ K

Macaulay Matrix

For a polynomial system F, its Macaulay matrix is defined as:

Mac(F) := (cᵢ,ⱼ)ᵢ∈[k],ⱼ∈[m] ∈ K^(k×m)

Scoring System

The following scoring metrics were defined to evaluate embedding quality:

• S(F) := -M(F): Minimize total number of monomials
• S₀(F) := M₀(F): Maximize number of zero minors
• R₀(F) := M₀(F)/M(F): Proportion of zero minors
• S₀ⁿᵗ(F), R₀ⁿᵗ(F): Non-trivial zero minor-related metrics

Greedy Alignment Algorithm

For the optimal alignment problem (NP-hard), Algorithm 4.3 is proposed:

GreedyAlignment(S₁, ..., Sₖ):
1. Set v₁ := 0
2. For ℓ = 2 to k:
   Compute vℓ := argmin |⋃ᵢ₌₁ˡ(Sᵢ + vᵢ)|
3. Return aligned support sets

Experimental Setup

Dataset

• ODEbase: Contains 200 polynomial models of biochemical reaction networks
• Selection Criteria:
  • 51 systems from mass-action kinetics with toric solutions
  • 31 systems with 16 or fewer species (for detailed analysis)
  • 70 systems for algorithm performance evaluation

Evaluation Metrics

1. Success Rate: Proportion of cases where the original system outperforms perturbations on various scoring metrics
2. Approximation Ratio: Ratio of greedy algorithm results to optimal solutions
3. Monomial Count: Primary optimization objective

Experimental Design

1. Discriminative Criteria Experiment: For each system F, test whether its perturbations F' achieve higher scores
2. Algorithm Performance Experiment: Run greedy algorithm on random translations, comparing with original system

Experimental Results

Main Findings

Validity of Discriminative Criteria

Among 31 test systems, the number of cases where each scoring metric successfully identified the original system:

• S (monomial count): 28/31 (90.3%)
• S₀: 2/31 (6.5%)
• S₀ⁿᵗ: 9/31 (29.0%)
• R₀: 9/31 (29.0%)
• R₀ⁿᵗ: 2/31 (6.5%)

Algorithm Performance

In testing on 70 systems:

• 91% of cases: Average score over 10 runs within 1.149× of optimal
• Best score: Within 1.059× of optimal
• Algorithm demonstrates excellent performance, approaching optimal solutions

Case Studies

Example 2.6 demonstrates differences between embeddings:

I := ⟨x₁² + x₂² + x₁, x₁² + x₂² + 1⟩

Two different generating sets F and G lead to different generic root counts:

• ℓI = ℓIF,K(a) = 2 < 4 = ℓIG,K(b)

BIOMD0000000629 system shows that the original system is not always optimal, indicating problem complexity.

Experimental Observations

1. Minimizing monomial count is the most important criterion for identifying good embeddings
2. Multiple runs of the greedy algorithm significantly improve result quality
3. Original systems are usually but not always optimal, leaving room for improvement

Related Work

Theory of Vertically Parametrised Systems

• Feliu et al. FHP24a,FHP24b: Established dimension theory for vertically parametrised systems
• Helminck and Ren HR22: Computing generic root counts via tropical geometry
• Rose and Telek RT24: Lower bounds on positive solution counts

Polytope Alignment Problems

• de Berg et al. DDVST96: Optimal alignment of convex polytopes in 2D and 3D
• Ahn et al. ABS08,ACR13: Probabilistic algorithms for high-dimensional cases
• Fukuda and Uno FU07: Polynomial-time algorithm using ellipsoid method

Conclusions and Discussion

Main Conclusions

1. Minimizing monomial count is the key principle for constructing good vertically parametrised embeddings
2. Greedy algorithm performs well in practice, approaching optimal solutions
3. ODEbase systems provide a rich source of real data for research

Limitations

1. NP-hardness: The optimal embedding problem is theoretically difficult to solve exactly
2. Heuristic Methods: Greedy algorithm does not guarantee global optimality
3. Data Constraints: Only biological systems from ODEbase used, potential domain bias

Future Directions

1. Develop more precise approximation algorithms
2. Study polynomial systems from other application domains
3. Explore machine learning methods to predict good embeddings

In-Depth Evaluation

Strengths

1. Theory-Practice Integration: Applies abstract algebraic geometry theory to practical problems
2. Rigorous Empirical Methodology: Systematic experimentation using large-scale real data
3. High Practical Value: Provides usable software package and algorithms
4. Problem Significance: Addresses key issues in applications of vertically parametrised systems

Weaknesses

1. Limited Theoretical Analysis: Insufficient analysis of theoretical performance guarantees for greedy algorithm
2. Scoring System Limitations: Failed to find effective tiebreaker criteria
3. Computational Complexity: Algorithm may face memory constraints for large systems

Impact

1. Academic Contribution: Provides important guidance for practical applications of vertically parametrised systems
2. Software Contribution: OscarODEbase.jl package facilitates related research
3. Methodological Contribution: Establishes framework for evaluating embedding quality

Applicable Scenarios

1. Biochemical Reaction Networks: Analysis of mass-action kinetics systems
2. Algebraic Geometry Computation: Scenarios requiring exploitation of vertically parametrised system properties
3. Symbolic Computation: Parametric study of polynomial systems

References

The paper cites important works from multiple fields including algebraic geometry, tropical geometry, computational geometry, and symbolic computation, particularly:

• Foundational theory by Feliu, Henriksson, Pascual-Escudero on vertically parametrised systems
• Applications of tropical geometry by Helminck, Ren in root count computation
• Related literature on ODEbase database

Overall Assessment: This is a well-executed paper combining theory and practice, addressing important problems in the application of vertically parametrised polynomial systems. While there is room for improvement in theoretical analysis, its empirical methodology and practical value make it a valuable contribution to the field.