4
$\begingroup$

There are $n$ charges placed on the x-axis at points $1,2,3,\dots,n$. We need to calculate the force on each charge by every other charge. I need the exact force. Charges can be arbitrary. Inputs are the charges possibly in the form of an array. Force is defined in the usual physical way.

I know an $O(n^2)$ algorithm to do the task. However, it can be done in $O(n\log n)$.

I have read about FFT, but I don't know how to apply it here. I know that we can multiply two degree $n$ polynomials in $O(n\log n)$. This problem is similar to that problem. Any help will be appreciated.

$\endgroup$
0
2
$\begingroup$

Suppose that the charges are $q_1,\ldots,q_n$. You need to calculate, for all $i$, $$ F_i = q_i \sum_{j>i} \frac{q_j}{(i-j)^2} - q_i \sum_{j<i} \frac{q_j}{(i-j)^2}. $$ In matrix form, we get $$ \begin{bmatrix} F_1/q_1 \\ F_2/q_2 \\ \vdots \\ F_n/q_n \end{bmatrix} = \begin{bmatrix} 0 & 1 & \frac{1}{4} & \frac{1}{9} & \cdots & \frac{1}{(n-1)^2} \\ -1 & 0 & 1 & \frac{1}{4} & \cdots & \frac{1}{(n-2)^2} \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ \frac{-1}{(n-1)^2} & \frac{-1}{(n-2)^2} & \frac{-1}{(n-3)^2} & \frac{-1}{(n-4)^2} & \cdots & 0 \end{bmatrix} \begin{bmatrix} q_1 \\ q_2 \\ \vdots \\ q_n \end{bmatrix} $$ What the FFT allows us to do is to quickly multiply by a circulant matrix. In order to obtain a circulant matrix, all you have to do is add $n-1$ dummy coordinates: $$ \begin{bmatrix} F_1/q_1 \\ F_2/q_2 \\ \vdots \\ F_n/q_n \\ \ast \\ \vdots \\ \ast \end{bmatrix} = \begin{bmatrix} 0 & 1 & \frac{1}{4} & \frac{1}{9} & \cdots & \frac{1}{(n-1)^2} & \frac{-1}{(n-1)^2} & \cdots & -1 \\ -1 & 0 & 1 & \frac{1}{4} & \cdots & \frac{1}{(n-2)^2} & \frac{1}{(n-1)^2} & \cdots & \frac{-1}{4} \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\ \frac{-1}{(n-1)^2} & \frac{-1}{(n-2)^2} & \frac{-1}{(n-3)^2} & \frac{-1}{(n-4)^2} & \cdots & 0 & 1 & \cdots & \frac{1}{(n-1)^2} \\ \frac{1}{(n-1)^2} & \frac{-1}{(n-1)^2} & \frac{-1}{(n-2)^2} & \frac{-1}{(n-3)^2} & \cdots & -1 & 0 & \cdots & \frac{1}{(n-2)^2} \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\ 1 & \frac{1}{4} & \frac{1}{9} & \frac{1}{16} & \cdots & \frac{-1}{(n-1)^2} & \frac{-1}{(n-2)^2} & \cdots & 0 \end{bmatrix} \begin{bmatrix} q_1 \\ q_2 \\ \vdots \\ q_n \\ 0 \\ \vdots \\ 0 \end{bmatrix} $$ We don't really care about the $n-1$ asterisked entries. The new matrix is $(2n-1)\times(2n-1)$, and so FFT still runs in $O(n\log n)$. Of course, if your FFT works only for powers of 2, you need an extra padding step.

$\endgroup$

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.