Metadata-Version: 2.4
Name: polyinv
Version: 0.2.0
Summary: Discover minimal canonical polynomial invariants from noisy data
Author-email: Tesfay Zemuy Gebrekidan <tzemuy13@gmail.com>
License-Expression: MIT
Project-URL: Homepage, https://github.com/TesfayZ/polyinv
Project-URL: Repository, https://github.com/TesfayZ/polyinv
Project-URL: Documentation, https://github.com/TesfayZ/polyinv#readme
Project-URL: Issues, https://github.com/TesfayZ/polyinv/issues
Classifier: Programming Language :: Python :: 3
Classifier: Operating System :: OS Independent
Classifier: Topic :: Scientific/Engineering :: Mathematics
Classifier: Intended Audience :: Science/Research
Requires-Python: >=3.9
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: numpy>=1.24
Requires-Dist: scipy>=1.10
Requires-Dist: sympy>=1.12
Requires-Dist: scikit-learn>=1.2
Requires-Dist: pandas>=2.0
Provides-Extra: dev
Requires-Dist: pytest; extra == "dev"
Requires-Dist: black; extra == "dev"
Requires-Dist: mypy; extra == "dev"
Dynamic: license-file

# polyinv – Discover Minimal Canonical Polynomial Invariants from Noisy Data

[![PyPI version](https://img.shields.io/pypi/v/polyinv)](https://pypi.org/project/polyinv/)
[![License: MIT](https://img.shields.io/badge/License-MIT-yellow.svg)](https://opensource.org/licenses/MIT)

**polyinv** is a Python package that recovers **minimal canonical polynomial invariants** from noisy numerical data. Given a set of observations (points in ℝⁿ), it returns the reduced Gröbner basis of the polynomial ideal that vanishes on the data, up to a specified degree and rational coefficient tolerance.

The algorithm is based on the paper:

> **Canonical Minimal Polynomial Invariants from Noisy Data via Adaptive Sparse Nullspace Recovery and Gröbner Basis**  
> Tesfay Zemuy Gebrekidan  
> [PDF](https://zenodo.org/records/21836794) · [Code](https://github.com/TesfayZ/srgb-csnp.git)

---

## Features

- **Unique canonical form** – returns the reduced Gröbner basis (grevlex order), guaranteed minimal and irredundant.
- **Handles multiple simultaneous invariants** – Combinatorial Sparse Nullspace Pursuit (CSNP) separates linearly mixed conservation laws.
- **Rationality prior** – prefers coefficients with low bit-cost (small integers and denominators) over spurious irrational fits.
- **Certified global search** – Branch-and-Bound with dominance pruning ensures optimality (Theorem 4.5).
- **Adaptive degree discovery** – automatically finds the polynomial degree via an MDL-based sweep (default maximum degree 10).
- **Noise-aware** – errors-in-variables correction, adaptive snap-rounding, and scale-relative residual thresholds.
- **Multiple input formats** – NumPy arrays, Pandas DataFrames, or CSV files.
- **Command-line interface** – discover invariants directly from the terminal.

---

## Installation

Install from PyPI:

```bash
pip install polyinv
```

Or install the latest development version:

```bash
git clone https://github.com/TesfayZ/polyinv
cd polyinv
pip install -e .
```

---

## Quick Start

```python
import numpy as np
from polyinv import discover

# Generate data on the unit circle
t = np.linspace(0, 2*np.pi, 500)
data = np.column_stack([np.cos(t), np.sin(t)])
var_names = ["x", "y"]

# Discover x² + y² − 1 = 0
result = discover(data, var_names=var_names, max_degree=2)

print(result.basis)
# [x**2 + y**2 - 1]

print(result.status)
# SUCCESS

print(result.certified)
# True
```

---

## Command-Line Interface

```bash
polyinv data.csv --vars x,y --max-degree 2 --format json
```

For all available options:

```bash
polyinv --help
```

---

## API Reference

```python
discover(
    data,
    var_names=None,
    *,
    noise_sigma=None,
    max_degree=None,
    D_max=10,
    max_denom=64,
    k_max=6,
    full_nullspace=False,
    use_bb=True,
    auto_escalate_denom=True,
    standardize=False,
    verbose=False,
)
```

Recovers the reduced Gröbner basis of the vanishing ideal.

### Parameters

| Parameter | Description |
|-----------|-------------|
| `data` | `np.ndarray`, `pd.DataFrame`, or CSV filename |
| `var_names` | Optional variable names |
| `noise_sigma` | Estimated noise standard deviation. If `None`, estimated from the SVD tail. |
| `max_degree` | Maximum polynomial degree. If omitted, adaptive search is used. |
| `D_max` | Upper bound for adaptive degree discovery (default `10`). |
| `max_denom` | Largest denominator allowed for rational coefficients (default `64`). |
| `k_max` | Maximum support size (default `6`). |
| `full_nullspace` | Enable full-nullspace deflation when multiple invariants are expected. |
| `use_bb` | Use Branch-and-Bound certification. |
| `auto_escalate_denom` | Retry using larger denominators if necessary. |
| `standardize` | Standardize variables before fitting. |
| `verbose` | Print progress information. |

### Returns

A `PolyInvResult` object containing:

| Attribute | Description |
|-----------|-------------|
| `basis` | Reduced Gröbner basis (SymPy expressions) |
| `status` | `"SUCCESS"`, `"ABSTAINED"`, or `"FAILED"` |
| `certified` | Whether exhaustive search certified optimality |
| `message` | Human-readable status |
| `elapsed` | Runtime in seconds |

Additional diagnostic information (support sets, rationality cost, etc.) is also available.

---

## Advanced Usage

### Using a Pre-built Design Matrix

```python
from polyinv._sr_gb import build_transition_difference_library

_, monomials, Phi = build_transition_difference_library(
    old_data,
    new_data,
    var_names,
    degree,
)

result = discover(
    None,
    var_names,
    degree=degree,
    monomials=monomials,
    Phi=Phi,
)
```

---

## How It Works

The algorithm proceeds through the following stages:

1. **Monomial Expansion**
   - Builds the polynomial feature library up to the selected degree.

2. **Numerical Nullspace Estimation**
   - Uses Singular Value Decomposition (SVD) to estimate the nullspace.

3. **Combinatorial Sparse Nullspace Pursuit (CSNP)**
   - Searches for sparse polynomial relations using the lexicographic objective:

   1. Rationality cost
   2. Sparsity

4. **Snap-Rounding**
   - Converts floating-point coefficients into exact rational numbers using adaptive tolerances.

5. **Algebraic Simplification**
   - Removes redundant factors and unnecessary higher-degree multiples.

6. **Gröbner Basis Canonicalisation**
   - Computes the reduced Gröbner basis over ℚ using graded reverse lexicographic order (grevlex).

The final output is a **unique minimal generating set** for the polynomial ideal that vanishes on the observed data.

---

## Citation

If you use **polyinv** or the underlying paper in your research, please cite both references separately:

### Software citation

```bibtex
@software{Gebrekidan2026polyinv,
  author       = {Tesfay Zemuy Gebrekidan},
  title        = {polyinv: Canonical Minimal Polynomial Invariant Computation Package - based on the paper - Canonical Minimal Polynomial Invariants from Noisy Data via Adaptive Sparse Nullspace Recovery and Gröbner Basis},
  year         = {2026},
  publisher    = {Zenodo},
  doi          = {10.5281/zenodo.21838053},
  url          = {https://doi.org/10.5281/zenodo.21838053},
}
```

### Paper citation

```bibtex
@misc{Gebrekidan2026srgb_csnp,
  author       = {Tesfay Zemuy Gebrekidan},
  title        = {Canonical Minimal Polynomial Invariants from Noisy Data via Adaptive Sparse Nullspace Recovery and Gröbner Basis},
  year         = {2026},
  publisher    = {Zenodo},
  doi          = {10.5281/zenodo.21836794},
  url          = {https://doi.org/10.5281/zenodo.21836794},
}
```

---

## License

This project is licensed under the **MIT License**. See the `LICENSE` file for details.

---

## Contributing

Bug reports, feature requests, and pull requests are welcome.

Please open an issue or submit a pull request on GitHub.

---

## Acknowledgements

This work builds upon ideas from the Sparse Identification of Nonlinear Dynamics (SINDy) and Approximate Vanishing Ideal (AVI) communities, and uses **SymPy** for symbolic algebra and Gröbner basis computations.
