Barycentric Interpolation

Do not index

Special thanks to Alistair Stewart for the helpful discussions

In this research article, I review the barycentric interpolation method as a more efficient form for working with Lagrange bases especially when paired with nth roots of unity.

First we define as the product of terms:

Next we define the barycentric weight as:

Such that the Lagrange base can be written as:

This works because:

(The term in the numerator and denominator both cancel out)

Where is the Kronecker delta function. And so our new Lagrange polynomial becomes:

Since is a common term we can factor it out such that we have:

This form allows us to precompute and only have to compute the individual barycentric weights for each -th term. This gives us a much better complexity than the naive Lagrange interpolation polynomial.

Equation is also known as the “First form of the barycentric interpolation formula”.

But we’re not done, we need to re-write the barycentric weight as a function, rather than an expression. Notice that we can rewrite as:

Where is the derivative of . In order to understand how we arrived at this derivative expression, Let’s examine an example for

In order to compute the derivative of this function we leverage the product rule:

Thus the derivative becomes:

Evaluating the derivative at gives us:

From observing how the derivative behaves at other coordinates , we can generalise the derivative as:

So we see now how our barycentric weight can be re-written as a function of :

nth Roots of Unity

Another optimisation we can make here is to reduce the computation time for the terms and to be logarithmic, by leveraging the th roots of unity. The th Roots of unity are simply the solutions to the equation:

For example, the solutions to the equation at , are . This is because, . At , we run into a problem, the first two solutions are & same as before, but other what two numbers raised to will give us ? Well logically that would be and but there are no solutions for this expression in the real numbers. Instead, they are referred to as and , imaginary units which lie in the complex plane. Usually we’d be working in finite fields or cyclic groups where there are indeed solutions to these expressions. The fundamental theorem of algebra states that any th degree polynomial has roots. What this means is that we can factor the equation above into the form:

Where is some primitive root of unity such that . This primitive root of unity has an order , that is to say that generates a multiplicative group of order . It's worth noting that this group is an Abelian group. Equation is also referred to as the Zero or Vanishing Polynomial. We can show this is true by recalling basic group theory, for any positive integer :

So this means equation will “vanish” on all powers of . Finally, the barycentric weight, is just the derivative of equation :

So our new Lagrange base becomes:

References

Barycentric Lagrange Interpolation