3
$\begingroup$

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.

$\endgroup$
  • 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$ – NotDijkstra Jul 5 at 2:38
  • $\begingroup$ sorry, you are right $\endgroup$ – plshelp Jul 5 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-5 Jul 5 at 21:09
  • $\begingroup$ thanks i think that's the algorithm i was searching for $\endgroup$ – plshelp Jul 6 at 11:55
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\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$ – plshelp Jul 5 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$ – dk14 Jul 5 at 22:18
  • $\begingroup$ @plshelp actually: stackoverflow.com/questions/28465398/… $\endgroup$ – dk14 Jul 5 at 22:24
0
$\begingroup$

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$).

| cite | improve this answer | |
$\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.