Rational Function Arithmetic
Efficient arithmetic on multivariate rational functions arising in generating function computations.
- Suitable for
- Master's thesis
- Supervision
- Zafeirakis Zafeirakopoulos
A rational function is a ratio \(r = P/Q\) where \(P, Q \in \mathbb{Z}[x_1,\ldots,x_n]\) are multivariate polynomials. Rational functions are the natural output of Polyhedral Omega, Barvinok’s algorithm, and many combinatorial counting methods: the generating function
\[\sum_{k\geq 0} f(k)\,z^k = \frac{P(z)}{Q(z)}\]encodes a sequence \(f(k)\) (e.g., the number of integer points in a scaled polytope) as a ratio of polynomials.
Efficient arithmetic on these objects — addition, multiplication, reduction to lowest terms — is a bottleneck in large-scale computations.
Core operations
Canonical form. A rational function \(P/Q\) is in canonical form when \(\gcd(P,Q)=1\). Computing \(\gcd\) of multivariate polynomials requires a subresultant or modular GCD algorithm and is the dominant cost.
Addition. \(\dfrac{P_1}{Q_1} + \dfrac{P_2}{Q_2} = \dfrac{P_1 Q_2 + P_2 Q_1}{Q_1 Q_2}\), followed by GCD reduction. Computing \(\gcd(Q_1,Q_2)\) first gives a smaller common denominator and avoids unnecessary coefficient growth.
Partial fractions. Decompose \(P(z)/Q(z)\) into a sum of simpler fractions with irreducible-power denominators. Used to extract specific coefficients \([z^k]P/Q\) as closed-form expressions. See also the Partial Fraction Decomposition topic.
Sparse representation
Combinatorial generating functions are typically sparse: their numerators and denominators have far fewer nonzero terms than the dense worst case. A sparse representation — storing only nonzero monomials in a hash map or sorted list — dramatically reduces memory and computation. The challenge is avoiding quadratic blowup when multiplying two sparse polynomials with overlapping support.
Goal
Survey sparse multivariate polynomial representations, implement core rational function arithmetic (add, multiply, GCD-based reduce), and benchmark against existing CAS tools.
- Repo: alcyon-ratfun.jl
Milestones
| ID | Title |
|---|---|
| M1 | Data structures survey & prototype |
| M2 | Core arithmetic (add, mul, reduce) |
| M3 | Partial fraction decomposition |
| M4 | Benchmarks & final report |
Tasks
| ID | Title | Status |
|---|---|---|
| T1 | Survey sparse multivariate representations | todo |
| T2 | Implement multiplication kernels | todo |
| T3 | Sparse partial fraction pipeline | todo |
| T4 | Benchmarks + write-up | todo |
Deliverables
- Julia package with tests
- Benchmark against existing tools
- Short report (6–8 pages)
References
-
A. I. Barvinok. A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed. Mathematics of Operations Research, 19(4):769–779, 1994. DOI 10.1287/moor.19.4.769
-
M. Köppe and S. Verdoolaege. Computing Parametric Rational Generating Functions with a Primal Barvinok Algorithm. Electronic Journal of Combinatorics, 15(1), 2008. combinatorics.org