Implementation details

Current implementation

LolRemez implements the Remez algorithm.

For more information about the algorithm, the Wikipedia article has some useful information, but I found the documentation from the Boost library’s implementation to be a lot better.

It is built of the following bricks:

• An arbitrary precision number (bignum) implementation, provided by Lol Engine.
• A linear system solver; I use simple Gaussian elimination because this part of the process is not a bottleneck.
• An extrema-finding algorithm; I use successive parabolic interpolation for now, but may be switching to Brent’s method later.
• A root-finding algorithm; I use the midpoint algorithm for now (experiments with regula falsi have not been conclusive yet)

Further work

Bignum multiplication is the #1 bottleneck in LolRemez. It could be improved using Karatsuba multiplication but that’s a pretty difficult task.

One big limitation with LolRemez is that, when working with float variables, converting the minimax polynomial’s coefficients to float does not necessarily provide the best possible polynomial. The presentation Polynomial approximation and floating-point numbers (Chevillard) are a good starting point to understand why and also what we can do to improve LolRemez.

Another challenge is approximating higher dimension functions. The paper An extension of ChebFun to two dimensions (Townsend, Trefethen) pointed me to a method for finding good 2D polynomial approximations.