# 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. 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”.
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

Related posts 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. 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. 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 ...