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!