My task asks me to check whether there is a common element in two sets $\{x_1,x_2,...,x_n\}$, $\{y_1,y_2,...,y_n\}$ with $x_i,y_i\in\mathbb{N}$ using the Fast Fourier Transform (FFT).
(I'm aware that there is a simple $O(n\log(n))$ algorithm to solve this problem using sorting and binary search.)
The tasks hints that we should consider the following product to solve the problem:
$$
\prod_{1\leq i,j \leq n} (x_i-y_j)
$$
The product is obviously zero if there is a common element, but I am still not sure how I could compute it faster via FFT.
I know how to use FFT to multiply polynomials efficiently, but somehow I seem to overlook something.
$\begingroup$
$\endgroup$
4
-
3$\begingroup$ I think the product that is zero if and only if there is a common element would be $\prod_{1\leq i,j\leq n}(x_i-y_j)$. This is equal to to the product $\prod_{i=1}^{n}p(x_i)$, where $p(x)=\prod_{j=1}^{n}(x-y_j)$. $\endgroup$– NotDijkstraJul 5, 2020 at 2:38
-
$\begingroup$ sorry, you are right $\endgroup$– plshelpJul 5, 2020 at 11:17
-
1$\begingroup$ @NotDijkstra: in fact, you can compute $p(x)$ as a polynomial using divide-and-conquer + FFT multiplication. After that, you need to evaluate $p$ in $n$ points. It is also a classical problem (so called multi-point evaluation) that can be solved in $O(n \log^2 n)$ time using FFT multiplication. Of course, this method is very arcane and slow compared to simple $O(n \log n)$ binary-search based solution, but I think this is exactly what plshelp is looking for. $\endgroup$– Kaban-5Jul 5, 2020 at 21:09
-
$\begingroup$ thanks i think that's the algorithm i was searching for $\endgroup$– plshelpJul 6, 2020 at 11:55
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
This one is a bit esoteric, but:
$$ \prod_{1\leq i,j \leq n} (x_i-y_j) $$
Could be decomposed to (as noted by @NotDijkstra)
$$ \prod_{i=1}^{n} p(x_i) $$ where $$ p (x) = \prod_{j=1}^{n} (x - y_j) $$
reduces to a polynomial with roots $y_i$. Coefficients of this polynomial could be computed with FFT, see https://arxiv.org/pdf/1608.01357.pdf. It could be done even faster using divide and conquer strategy - recursively split the formula into two polynomials and multiply them with FFT (see answers).
Polynomial representation in its turn would allow fast exponentiation of x, or even multi-point evaluation
Although, I don't see any advantages over traditional approach in terms of speed or complexity except if it's implemented on specialised ASICs/FPGAs/GPUs.
-
$\begingroup$ Interesting paper, however the runtime is $nN+O(n\log(n))$ and the author writes that N*n is $O(n^2)$. The idea to split the problem up is still a good start i think. $\endgroup$– plshelpJul 5, 2020 at 20:58
-
$\begingroup$ It seems like $p(x)$ polynomial could be evaluated on X in n log n using FFT - cecm.sfu.ca/CAG/theses/justine.pdf. But I couldn’t find a fast way to compute coefficients. So it’s still $n^2$. $\endgroup$– dk14Jul 5, 2020 at 22:18
-
$\begingroup$ @plshelp actually: stackoverflow.com/questions/28465398/… $\endgroup$– dk14Jul 5, 2020 at 22:24
$\begingroup$
$\endgroup$
It seems you want to use Vandermand's matrix.
Let's say the arrays have unique values in each of them(remember we need distinct values of \begin{equation} (x_k) 's \end{equation} for k=1,...len(array1)+len(array2) to work for the property of "Uniqueness of interpolating polynomial") and we know the fact that at least one of them is common in the two arrays.
Now combine the arrays and calculate Determinant of Vandermand's Matrix which had to be nonsingular if all the x's and y's combined were distinct. Since we know there is a common element, the determinant of Vandermand's matrix must be 0, i.e, \begin{equation} \\\prod_{0<=j<k<=2n-1}(x_k-x_j)=0\\ \end{equation}
I wouldn't call it an efficient algorithm because solving the eqn using LU decomposition algorithms provides us with time complexity of O($n^3$) while even a faster algorithm like Lagrange's Formula would only get us to O($n^2$).
