I'm working through Blahut's 'Fast Algorithms for Signal Processing'. Trying to develop an intuition for the Cook-Toom algorithm for convolutions as used by Lavin and Gray in their Winograd paper for convnets.

At page 151 (chapter 5.2), Blahut writes that the following is the final result of the Cook-Toom algorithm:


I'm a bit confused about why one has an $s(x)$ and then has an $s$ instead a few lines later like so:


But that is secondary. I'm guessing that's to do with us no longer treating $s$ as a polynomial after the inverse transform with $C$? But I though convolution was equivalent to polynomial multiplication. Still not entirely clear on that.

My main question is, how are the following Lagrange polynomials derived? For reference, the interpolation points are $\beta_0 = 0, \beta_1 = 1, \beta_2 = -1$:

$L_0 = -x^2 + 1,$

$L_1 = x^2 + x,$

$L_2 = x^2 - x.$

These are stated, but don't follow obviously from the rest of the text. My understanding of Lagrange polynomials is somewhat limited. Any clarification would be very much appreciated!


If you represent a second-order polynomial $s(x)$ with Lagrange polynomials $L_i(x)$ and interpolation points $\beta_i$, $i=0,1,2$, such that


then for the equality in $(1)$ to be satisfied, the polynomials $L_i(x)$ must have zeros at $x=\beta_j$, $j\neq i$, and they must equal $1$ at $x=\beta_i$. This completely determines the polynomials $L_i(x)$.

E.g., the polynomial $L_0(x)$ must have two zeros at $\beta_1=1$ and $\beta_2=-1$, respectively, and it must satisfy $L_0(\beta_0)=L_0(0)=1$. The latter condition just determines the scaling. This results in


The other polynomials can be derived in the same way.

Note that the polynomials $L_1(x)$ and $L_2(x)$ have a scaling factor of $\frac12$, which is later in the derivation absorbed in other constants for reasons of computational efficiency.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.