Back

In browsing the state of the art I came across two interesting things. The first is the software package lolremez (https://github.com/samhocevar/lolremez) that implements polynomial (and rational polynomial $f(x) / g(x)$) function approximation using the so-called Remez algorithm. After building it (https://github.com/samhocevar/lolremez/issues/27) it seems to work rather well. The author also wrote a Wiki on the GitHub project with a bunch of tips for using the API to do special things like round the coefficients to easily-representable numbers, or enforce odd-function symmetry (https://github.com/samhocevar/lolremez/wiki/Tutorial-3-of-5:-changing-variables-for-simpler-polynomials#odd-and-even-functions) in the approximation.

Lolremez outputs the approximated polynomial's coefficients in Horner (https://en.wikipedia.org/wiki/Horner%27s_method) evaluation format. Horner's method is bad for me, or at least non-optimal, because it does not optimize for the number of multiplication operations, which is a bottleneck in FHE. Instead, there's a nice technique from the computational matrix algebra world called Paterson-Stockmeyer (https://en.wikipedia.org/wiki/Polynomial_evaluation#Matrix_polynomials) that reduces the number of (non-scalar) multiplications from $O(n)$ to $O(\sqrt{n})$. This is what most FHE people use by default, as far as I can tell.

So I wrote a little Python CLI to convert lolremez output to coefficient form. It uses `python-fire` and `sympy` to do the hard work.

(Code omitted for brevity. See: https://www.jeremykun.com/shortform/2024-05-06-1018/)

The second interesting thing is how FHE researchers have adapted Remez to FHE specifically. This paper of Joon-Woo Lee, Eunsang Lee, Yongwoo Lee, Young-Sik Kim, and Jong-Seon No (https://eprint.iacr.org/2020/552) develops a "multi-interval" Remez method that jointly optimizes over multiple disjoint intervals of approximation. This is useful for approximating something like a sign function that has a discontinuity at zero (though you can do it in lolremez using odd-function symmetry tricks). The authors use the multi-interval method with $[-1, -\varepsilon] \cup [\varepsilon, 1]$ for small $\varepsilon > 0$ to approximate sign. There is an implementation (https://github.com/tuneinsight/lattigo/blob/4cce9a48c1daaa2dd122921822f5ad70cd444156/he/hefloat/minimax_composite_polynomial.go#L124) of this algorithm in the lattigo (https://github.com/tuneinsight/lattigo) library, which is also the project that tipped me off about Paterson-Stockmeyer. Kudos to Jean-Philippe Bossuat, its primary author, for making so much useful knowledge public and easy to find.