# What is meant by “operations”?

In this paper, on page 243, we have

$$d_{jk} = \frac{a_j}{a_k(x_j - x_k)}$$

where $$a_k = \prod_{l = 0;l\neq k}^{N}(x_k-x_l)$$

Now, $a_k$ requires evaluating N multiplications. Why does the author say, "$N^2$ operations are required to compute $a_j$"?

• $a_l$ has two different free indices in the first equation you show, therefore for calculating $d_{ij}$ it requires $N^2$ operations – Kbzon Jul 28 '16 at 11:59
• Ok, I am asking about $a_j$, the author says that calculating (just) $a_k$ we require $N^2$ operations. From what I can see, If $a_k$ takes $N$ operations then indeed $d_{ij}$ takes $N^2$ operations as you say, but I am struggling to see how the author says that, to compute $a_j$, $N^2$ operations are requested. From the formula for $a_j$ we only require $N$ subtractions and $N$ multiplications, thus $O(N)$. – user21030 Jul 29 '16 at 16:23
• @Kbzon this is not correct, for $d_{i,j}$ you compute $a_j$ in $N$ operations, $a_k$ in $N$ operations and $x_j-x_k$ in constant. Then you just have to multiply/divide in constant. Makes $2N$ operations for one $d_{i,j}$ and $2N^3$ for the complete Matrix, yet the authors say the Matrix takes $4N^4$, which should be just wrong. Only because it is peer-reviewed it does not mean it has to be right. – Jan Hackenberg Aug 14 '16 at 22:37

Of course you are right, $a_k$ requires N multiplications, it's obvious. It does not involve $d_{jk}$...

[EDITED because of my inattention] I suspect "operations" here means multiplies and inverses only, neglecting subtractions $x_j-x_k$.

Taking a look at the paper, I see Eq. (2.8):

$$\phi_{N+1}(x) = \prod_{l=0}^N (x-x_l)\,.$$ Then, [Eq. (2.9)] $$\phi'_{N+1}(x) = \sum_{k=0}^{N}\prod_{l=0,l\neq k}^N (x-x_l)$$ and so [Eq. (2.10)] $$\phi'_{N+1}(x_k) = a_k \,.$$

For each $a_k$, $N$ multiplies are required. Could one interpret the assertion globally, on all $a_j$? Indeed, the paper evaluate $4N^2$ operations for the whole matrix $D$. What if one only counts multiplies or inverses? Back in 1989, it was not uncommon to forget adds and subtractions in complexity. In Eq. 2.12a, they evaluate off-diagonal elements: $$\frac{a_j}{a_k(x_j-x_k)}$$ with "another $2N^2$ operations". Once the $a_j$ are computed, this seems sound: $1$ product and $1$ divide for each pair of $(j,k)$, $j\neq k$. Then they count $N^2$ for the diagonal elements $$\sum_{l=0,l\neq k}^{N}\frac{1}{x_k-x_l}\,,$$ ie $N$ inverses for each of the diagonal elements, about $N^2$ total.

• in 2.9 the sum vanishes for a fixed k right? I was thinking a lot in this direction too, but I guess the topic's creator's formula is right? – Jan Hackenberg Aug 15 '16 at 13:28
• @Jan Hackenberg I did not pay enough attention. Wouldn't it be $N?^2$ for all the $a_j$? – Laurent Duval Aug 15 '16 at 13:49
• @Jan Hackenberg I may be very tired, but where do they mention $N^4$? – Laurent Duval Aug 15 '16 at 15:16
• just 3rd or 4th sentence after formula 2.12b. The longer I think, the more I think that one should really look if in 1989 a multiplication was considered a basic operation. From my feeling it should still be, but computers were dinosaurs in this time right? – Jan Hackenberg Aug 15 '16 at 15:48
• Maybe you are not the only one tired ;) – Jan Hackenberg Aug 15 '16 at 19:06