or
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up
Syntax | Example | Reference | |
---|---|---|---|
# Header | Header | 基本排版 | |
- Unordered List |
|
||
1. Ordered List |
|
||
- [ ] Todo List |
|
||
> Blockquote | Blockquote |
||
**Bold font** | Bold font | ||
*Italics font* | Italics font | ||
~~Strikethrough~~ | |||
19^th^ | 19th | ||
H~2~O | H2O | ||
++Inserted text++ | Inserted text | ||
==Marked text== | Marked text | ||
[link text](https:// "title") | Link | ||
 | Image | ||
`Code` | Code |
在筆記中貼入程式碼 | |
```javascript var i = 0; ``` |
|
||
:smile: | ![]() |
Emoji list | |
{%youtube youtube_id %} | Externals | ||
$L^aT_eX$ | LaTeX | ||
:::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Do you want to remove this version name and description?
Syncing
xxxxxxxxxx
Dividing In Lagrange basis when one of the points is zero - Generalised
Reference
The formulas were derived by reading the following academic article here
Problem
In the multipoint protocol, we had a polynomial of the form:
\[ g(X) = r^0 \frac{f_0(X) - y_0}{X-z_0} + r^1 \frac{f_1(X) - y_1}{X-z_1} + \ldots +r^{m-1} \frac{f_{m-1}(X) - y_{m-1}}{X-z_{m-1}} \]
In our context, \(z_i\) is an element in the domain, so naively we cannot compute this division in lagrange form. We also do not want to use monomial form, as we would need to interpolate our polynomials, which is exp
Simplifying the problem:
We have \(\frac{f(X)}{g(X)} = \frac{f(X)}{X - x_m} = \sum_{i=0}^{d-1} {f_i\frac{\mathcal{L_i(X)}}{X - x_m}}\)
In what follows, we re-derive all of the necessary formulas that will allows us to divide by a linear polynomial that vanishes on the domain in lagrange basis, where the domain can be arbitrary.
Lagrange polynomial
We briefly restate the formula for a lagrange polynomial:
\[ \mathcal{L_i}(X) = \prod_{j \neq i, j = 0}\frac{X -x_j}{x_i - x_j} \]
First form of the barycentric interpolation formula
We introduce the polynomial \(A(X) = (X - x_0)(X - x_1)...(X-x_n)\).
We also introduce the derivative of \(A'(X) = \sum_{j=0}^{d-1}\prod_{i \neq j}(X - x_i)\) .
In general this derivative does not have a succinct/sparse form. We do however have a succinct form if the domain is the roots of unity!
Now note that \(A'(x_j) = \prod_{i=0,i \neq j}(x_j - x_i)\)
We can use \(A\) and \(A'\) to re-define our lagrange polynomial as :
\[ \mathcal{L_i}(X) = \frac{A(X)}{A'(x_i) (X - x_i)} \]
The first barycentric form for a polynomial \(f(X)\) can now be defined as :
\[ f(X) = \sum_{i=0}^{d-1}{\frac{A(X)}{A'(x_i) (X - x_i)} f_i} \]
Remarks
Re-defining the quotient
Note that our original problem was that the polynomial:
\[\sum_{i=0}^{d-1} {f_i\frac{\mathcal{L_i(X)}}{X - x_m}}\]
Had a \(X - x_m\) term in the denominator. We will use the first barycentric form as a way to get rid of this.
First we rewrite \(\frac{\mathcal{L_i(X)}}{X - x_m}\) using the first form:
\[ \frac{\mathcal{L_i}(X)}{X - x_m} = \frac{A(X)}{A'(x_i) (X - x_i)(X-x_m)} \]
We then note that:
\[ A(X) = \mathcal{L_m}(X) \cdot A'(x_m) \cdot (X - x_m) \]
We can hence plug this into our previous equation:
\[ \frac{\mathcal{L_i}(X)}{X - x_m} = \frac{\mathcal{L_m}(X) \cdot A'(x_m) \cdot (X - x_m)}{A'(x_i) (X - x_i)(X-x_m)} \]
Simplifying since we have a \(X - x_m\) in the numerator and denominator:
\[ \frac{\mathcal{L_i}(X)}{X - x_m} = \frac{A'(x_m) \cdot \mathcal{L_m}(X) }{A'(x_i)\cdot (X - x_i)} \]
We have now re-defined \(q(X)\) to not include \(X-x_m\) !
We now summarise and state that:
\[ q(X) = \sum_{i=0}^{d-1} f_i \frac{\mathcal{L_i}(X)}{X - x_m} = f_i \frac{A'(x_m) \cdot \mathcal{L_m}(X) }{A'(x_i)\cdot (X - x_i)} \]
Explicit formulas for each case
Computing \(q_m\)
When dealing with the point which vanishes on zero, the above formula becomes:
\[ q_m = q(x_m) = \sum_{i=0}^{d-1}\frac{A'(x_m)}{A'(x_i)} \frac{f_i}{x_m - x_i} \]
Computing \(q_j\)
For the case that the evaluation does not vanish on the domain, we can use the original formula.
For all \(j \neq m\)
\[ q_j = q(x_j) = \sum_{i=0}^{d-1} f_i \frac{\mathcal{L_i}(x_j)}{x_j - x_m} \]
We note that the terms of the sum are zero, except for when \(i=j\) from the definition of the lagrange polynomial , hence we can simplify this to be:
\[ q_j = \frac{f_j}{x_j - x_m} \]
Optimisations
If we use the formulas as shown above, \(q_m\) will take \(d\) steps due to the sum, and \(q_j\) will take \(d-1\) steps. We describe a way to reduce this complexity in the code.
1. Rewrite \(q_m\) in terms of \(q_j\)
Note that if we multiply \(q_m\) by \(\frac{-1}{-1}\) we get:
\[ q_m = q(x_m) = -\sum_{i=0}^{d-1}\frac{A'(x_m)}{A'(x_i)} \frac{f_i}{x_i - x_m} \]
We can now substite in \(q_i\)
\[ q_m = q(x_m) = -\sum_{i=0}^{d-1}\frac{A'(x_m)}{A'(x_i)} q_i \]
2. Removing field inversions in \(q_j\)
Note that \(q_j\) has a division which is many times more expensive than a field multiplication. We now show a way to precompute in such a way that we do not need to invert elements.
Again note that:
\[ q_j = \frac{f_j}{x_j - x_m} \]
The expensive division occurs here \(\frac{1}{x_j-x_m}\). In our particular case, we note that the domain is the discrete interval \([0,255]\) this means we need only to precompute \(\frac{1}{x_i}\) for \(x_i \in [-255, 255]\). This is 510 values, so we would store \(510 * 32 = 16Kb\). If this is too much space, one could halve the storage by not storing the negated points.
How would I lookup and store these values in practice?
First we imagine that we have stored the values in an array as such:
\([\frac{1}{1}, \frac{1}{2}, \frac{1}{3}, \frac{1}{4}... \frac{1}{255},\frac{1}{-1},\frac{1}{-2},...\frac{1}{-255}]\)
We first note that we can easily get from \(\frac{1}{k}\) to \(\frac{1}{-k}\) in the array by jumping forward 255 indices. Our strategy will be to find \(\frac{1}{k}\) then jump to \(\frac{1}{-k}\) if we need to.
Example
We want to compute \(\frac{1}{0 - 255}\).
3. Precompute \(\frac{A'(x_m)}{A'(x_i)}\)
For our case, we will need to store precomputed values, if we want to efficiently compute \(q_m\) in \(O(d)\) steps, and to also avoid inversions.
The strategy is that, we precompute \(A'(x_i)\) and \(\frac{1}{A'(x_i)}\). Given that we have 256 points in the domain. This will cost us \(256 * 2 * 32 \text{ bytes} = 16kB\).
How would I lookup and store these values in practice?
Similar to the previous optimisation, we store \(A'(x_i)\) in an array as such:
\([A'(0), A'(1), A'(2), A'(3)... A'(255),\frac{1}{A'(0)},\frac{1}{A'(1)},\frac{1}{A'(2)},...\frac{1}{A'(255)}]\)
Example
We want to compute \(\frac{A'(0)}{A'(5)}\)
In general:
Evaluate polynomial in evaluation form on a point outside of the domain
Suppose \(z\) is a point outside of the domain.
\[ f(z) = \sum_{i=0}^{d-1}f_i\mathcal{L_i}(z) = \sum_{i=0}^{d-1}{\frac{A(z)}{A'(x_i) (z - x_i)} f_i} = A(z)\sum_{i=0}^{d-1}\frac{f_i}{A'(x_i)(z-x_i)} \]
Optimising: