Barycentric Interpolation

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.
profile photo
Seun Lanlege
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”.
Polynomial interpolation breathing
Polynomial interpolation breathing
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:


Related posts
post image
In this research article, I review the Cooley-Tukey FFT as a faster alternative than the naive approach for computing DFTs of lengths that are not a power of 2, but have highly composite factors.
post image
In this research article, I present a protocol for efficiently verifying the Ethereum Beacon chain's Casper FFG consensus proofs using a SNARK based scheme.
post image
Polynomial commitment schemes are the foundational cryptographic primitive for things like computational integrity proofs (aka (ZK-)SNARKs) and verkle tries (a more efficient alternative to merkle-patricia tries). In this article ...
Powered by Notaku