interval-arithmetic

Python library for composable functions R^n -> R, symbolic differentiation, compiled evaluation, piecewise structure over axis-aligned boxes, Taylor polynomial approximation with rigorous error bounds, and interval queries via Taylor patchworks.

---

Installation

Requires Python <= 3.10.

From the project root:

pip install -r requirements.txt
pip install -e .

---

Running Tests

pytest

---

Benchmarking

Compare compile time vs query time across dimensions and functions.

python benchmark.py

---

Project Structure

interval-algebra/
├── pyproject.toml
├── requirements.txt
├── README.md                       # This file :)
├── src/
│   └── interval_algebra/
│       ├── __init__.py
│       ├── fn.py                   # symbolic functions
│       ├── ops.py                  # arithmetic and unary ops
│       ├── autodiff.py             # arbitrary degree differentiation
│       ├── compiled_fn.py          # tape-based compilation and derivative evaluation
│       ├── piecewise.py            # arbitrary region piecewise
│       ├── piecewise_grid.py       # piecewise functions on "boxy" regions (faster eval)
│       ├── taylor.py               # Taylor polynomial and remainder bounds
│       ├── taylor_patchwork.py     # constructs piecewise grid of Taylor expansions to spec
│       ├── interval.py             # per-patch caching, quadratic optimization, and interval queries
│       └── viz.py                  # 1D and 2D visualization utilities
├── tests/
│   ├── test_fn.py
│   ├── test_autodiff.py
│   ├── test_compiled_fn.py
│   ├── test_piecewise.py
│   ├── test_piecewise_grid.py
│   ├── test_taylor.py
│   ├── test_taylor_patchwork.py
│   ├── test_interval.py
└── examples/
    ├── viz_ex.py
    └── benchmark.py

API Overview

The core abstraction is Fn: a pure symbolic function R^n -> R built from:

• variables via vars(n)
• arithmetic operators: +, -, *, /, **
• unary methods: .sin(), .cos(), .exp(), .log(), etc...
• composition via f(g1, g2, ...)

From an Fn you can:

• differentiate symbolically to obtain new Fn objects
• compile to a CompiledFn with efficient evaluation and derivative tapes
• build Taylor polynomials and rigorous remainder bounds on regions
• build a patchwork of Taylor regions for global interval queries

Piecewise structure is supported by:

• PiecewiseFn: arbitrary regions represented as R^n -> bool
• PiecewiseGridFn: axis-aligned boxes for fast lookup and compilation

Taylor layer:

• TaylorApprox: Taylor polynomial at a given center + coefficients
• TaylorRegionApprox: polynomial + region box + proven error bound
• build_taylor_patchwork: recursively tiles a region to meet an error target
• query_box_minmax_quadratic: rigorous min/max on subregions for quadratic patches

Variables and Functions

from interval_algebra import vars

(x,) = vars(1)
f = x * x + x.sin()
f(2.0)

Derivatives

from interval_algebra import vars, differentiate_axis

(x,) = vars(1)
f = x * x + x.sin()

df = differentiate_axis(f, 0)
df(1.5)

Mixed Derivatives

from interval_algebra import vars, differentiate_multi

x, y = vars(2)
f = (x * x) * (y * y)

dxy = differentiate_multi(f, (1, 1))   # ∂²/(∂x ∂y)
dxy(2.0, 3.0)

---

Compilation (for evaluation + derivatives)

from interval_algebra import vars

(x,) = vars(1)
f = x ** 4 + x

cf = f.compile(max_order=2)
cf.eval((1.5,))
cf.deriv((1.5,), (1,))   # first derivative
cf.deriv((1.5,), (2,))   # second derivative
cf.all_derivs((1.5,))

---

Piecewise Structure

Arbitrary predicates

from interval_algebra import vars, piecewise

(x,) = vars(1)
f = piecewise([
    (lambda xs: xs[0] < 0, (-x).exp()),
    (lambda xs: xs[0] >= 0, x * x),
])

f(-2.0), f(1.0)

Box-based (grid) structure

from interval_algebra.piecewise_grid import box, closed_interval, piecewise_grid
from interval_algebra import vars

x, y = vars(2)

R1 = box(closed_interval(0, 1), closed_interval(0, 1))
R2 = box(closed_interval(1, 2), closed_interval(0, 1))

pw = piecewise_grid([
    (R1, x * y),
    (R2, x + y),
])

pw(0.5, 0.5), pw(1.5, 0.5)

---

Taylor Approximation

from interval_algebra import vars
from interval_algebra.taylor import taylor_approx

(x,) = vars(1)
f = x.exp()

TA = taylor_approx(f, center=(0.0,), order=4)
p = TA.as_fn()
p(0.2)

Remainder Bound on a Box

from interval_algebra.taylor import bound_taylor_error
from interval_algebra.piecewise_grid import box, closed_interval

B = box(closed_interval(-0.5, 0.5))
eps = bound_taylor_error(f, center=(0.0,), order=4, box=B)

---

Taylor Patchworks

Automatically tile a region into boxes with Taylor polynomials meeting an error target.

from interval_algebra import vars
from interval_algebra.piecewise_grid import box, closed_interval
from interval_algebra.taylor_patchwork import build_taylor_patchwork

(x,) = vars(1)
f = x * x + 0.1 * x.sin()

region = box(closed_interval(-2, 2))
pw = build_taylor_patchwork(
    fn=f,
    region=region,
    eps_target=0.05,
    mode="adaptive_order",   # or "fixed_order" for all taylor series of one order (slower)
    base_order=2,
    max_order=2,
)
len(pw.patches)

---

Interval Queries (Quadratic Patches)

For quadratic patches (order <= 2), we support exact optimization of the Taylor polynomial on sub-boxes, plus rigorous error inflation for the true function. Higher degrees are currently unsupported.

from interval_algebra.interval import (
    analyze_patchwork_extrema_quadratic,
    query_box_minmax_quadratic,
)
from interval_algebra.piecewise_grid import box, closed_interval

# Precompute extrema of each patch (caches H, g, c0 per patch)
pw_ext = analyze_patchwork_extrema_quadratic(pw)

# Query rigorous min/max of f on a smaller interval
Q = box(closed_interval(-1, 1))
res = query_box_minmax_quadratic(pw, Q, precomputed_extrema=pw_ext)

res.min_lower, res.max_upper
res.argmin_candidates, res.argmax_candidates

---

Visualization (1D/2D)

Optional helpers for exploring functions and patchworks.

from interval_algebra.viz import plot_1d_patchwork, plot_2d_patchwork

# fig, ax = plot_1d_patchwork(pw)               # 1D
# fig, ax = plot_2d_patchwork(pw_2d, kind="both")   # 2D surfaces

---