2
$\begingroup$

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$"?

Improve this question
$\endgroup$
  • 4
    $\begingroup$ $a_l$ has two different free indices in the first equation you show, therefore for calculating $d_{ij}$ it requires $N^2$ operations $\endgroup$ – Kbzon Jul 28 '16 at 11:59
  • $\begingroup$ 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)$. $\endgroup$ – user21030 Jul 29 '16 at 16:23
  • $\begingroup$ @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. $\endgroup$ – Jan Hackenberg Aug 14 '16 at 22:37
-1
$\begingroup$

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

Improve this answer
$\endgroup$
1
$\begingroup$

[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.

Improve this answer
$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Jan Hackenberg Aug 15 '16 at 13:28
  • $\begingroup$ @Jan Hackenberg I did not pay enough attention. Wouldn't it be $N?^2$ for all the $a_j$? $\endgroup$ – Laurent Duval Aug 15 '16 at 13:49
  • $\begingroup$ @Jan Hackenberg I may be very tired, but where do they mention $N^4$? $\endgroup$ – Laurent Duval Aug 15 '16 at 15:16
  • $\begingroup$ 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? $\endgroup$ – Jan Hackenberg Aug 15 '16 at 15:48
  • 1
    $\begingroup$ Maybe you are not the only one tired ;) $\endgroup$ – Jan Hackenberg Aug 15 '16 at 19:06

Your Answer

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