does the "convolution theorem" apply to weaker algebraic structures? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T23:35:18Z http://mathoverflow.net/feeds/question/10237 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/10237/does-the-convolution-theorem-apply-to-weaker-algebraic-structures does the "convolution theorem" apply to weaker algebraic structures? Adam 2009-12-31T06:28:51Z 2010-02-04T23:19:48Z <p>The <a href="http://mathworld.wolfram.com/ConvolutionTheorem.html%20%22Convolution%20Theorem%22" rel="nofollow">Convolution Theorem</a> is often exploited to compute the convolution of two sequences efficiently: take the (discrete) Fourier transform of each sequence, multiply them, and then perform the inverse transform on the result.</p> <p>The same thing can be done for convolutions in the quotient ring Z/pZ via the analogous <a href="http://mathworld.wolfram.com/NumberTheoreticTransform.html" rel="nofollow">Number Theoretic Transform</a>.</p> <p>Does this procedure generalize to other algebraic structures? Arbitrary rings? Semirings? Fast convolutions over the semiring (min,+) would be particularly useful.</p> <p>I'm led to suspect this because both sorting and FFT can be computed using the same butterfly-like network with simple operations like "min", "max", "+", and "*" at the nodes of the network, and sorting can be thought of as a kind of convolution.</p> http://mathoverflow.net/questions/10237/does-the-convolution-theorem-apply-to-weaker-algebraic-structures/11606#11606 Answer by Ryan Williams for does the "convolution theorem" apply to weaker algebraic structures? Ryan Williams 2010-01-13T02:12:15Z 2010-01-13T02:12:15Z <p>In general, it is a major open question in discrete algorithms as to which algebraic structures admit fast convolution algorithms and which do not. (To be concrete, I define the <em>$(\oplus,\otimes)$ convolution</em> of two $n$-vectors $[x_0,\ldots,x_{n-1}]$ and $[y_0,\ldots,y_{n-1}]$, to be the vector $[z_0,\ldots,z_{n-1}]$ with $$z_k = (x_0 \otimes y_k) \oplus (x_1 \otimes y_{k-1}) \oplus \cdots \oplus (x_k \otimes y_0).$$ Here, $\otimes$ and $\oplus$ are the multiplication and addition operations of some underlying semiring.) </p> <p>For any $\otimes$ and $\oplus$, the convolution can be computed trivially in $O(n^2)$ operations. As you note, when $\otimes = \times$, $\oplus = +$, and we work over the integers, this convolution can be done efficiently, in $O(n \log n)$ operations. </p> <p>But for more complex operations, we do not know efficient algorithms, and we do not know good lower bounds. The best algorithm for $(\min,+)$ convolution is $O(n^2/\log n)$ operations, due to Chan. See</p> <blockquote> <p>David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Perouz Taslakian: Necklaces, Convolutions, and X + Y. ESA 2006: 160-171</p> </blockquote> <p>A substantially subquadratic algorithm for $(\min,+)$ convolution would (to my knowledge) imply a subcubic algorithm all-pairs shortest paths in general graphs, a longstanding open problem. The above reference also gives a $O(n^2 (\log \log n)^2/\log n)$ algorithm for a "(median,+) convolution".</p> <p>The situation is subtle. It's not clear when convolution over a semiring is easy and when it's hard. For instance, the $(\min,\max)$ convolution <em>can</em> be computed in subquadratic time: I believe that $O(n^{3/2} \log n)$ operations suffice. This can be obtained from adapting the $(\min,\max)$ matrix multiplication algorithm in my work with Vassilevska and Yuster on all-pairs bottleneck paths. Basically you reduce the problem to computing $\sqrt{n}$ instances of a $(+,\times)$ ring convolution.</p> http://mathoverflow.net/questions/10237/does-the-convolution-theorem-apply-to-weaker-algebraic-structures/14199#14199 Answer by A. Johnston for does the "convolution theorem" apply to weaker algebraic structures? A. Johnston 2010-02-04T22:43:41Z 2010-02-04T22:43:41Z <p>Look to the Chinese remainder theorem over rings. The discrete Fourier transform is just one example.</p> <p>The discrete Fourier transform over a field $\mathbb{F}$ (for example $\mathbb{C}$ or $\mathbb{F}_{q}$) using an $n^{th}$ primitive root of unity $\alpha$ (in $\mathbb{C}$, $\alpha=e^{2\pi i/n}$) of a vector <code>$\left[a_{n-1}\ a_{n-2}\ \ldots\ a_0\right]$</code> is equivalent to evaluating the polynomial <code>$\sum^{(n-1)}_{j=0}a_jx^k$</code> at $\alpha^k$ for $k=0,1,\ldots, (k-1)$: <code>$\mathcal{F}\left( \sum^{(n-1)}_{j=0}a_jx^k\right)= \left[\sum^{(n-1)}_{j=0}a_j(\alpha^k)^j\right]_{j=0}^{n-1}$</code> and the inverse DFT can be equated to (or easily derived from) Lagrangian interpolation. </p> <p>Interpolation is a special case of the Chinese remainder theorem over $\mathbb{F}[x]$. Reducing a polynomial $f(x)$ modulo $(x-\alpha)$ is identical to evaluating $f(x)$ at $\alpha$ ($x\equiv \alpha \bmod{(x-\alpha)}$). Interpolation of the set of distinct points <code>$\left\{(\alpha_k,\beta_k),\ k=0,1,\ldots,(n-1)\right\}$</code> is equivalent to finding the polynomial $f(x)\in \mathbb{F}[x]/\left(\prod_{k=0}^{n-1}(x-\alpha_k)\right)\mathbb{F}[x]$ such that $f(x)\equiv \beta_k\bmod{(x-\alpha_k)}$: <code>$\begin{array}{rl}f(x)&amp;\equiv\sum_{k=0}^{n-1}\left(\prod_{j\neq k}(x-\alpha_j)\right)\left(\left(\prod_{j\neq k}(x-\alpha_j)\right)^{-1}\beta_k\bmod{(x-\alpha_k)}\right)\\ &amp;\equiv \sum_{k=0}^{n-1}\left(\frac{\prod_{j\neq k}(x-\alpha_j)}{\prod_{j\neq k}(\alpha_k-\alpha_j)}\right)\beta_k \bmod{\prod_{k=0}^{n-1}(x-\alpha_k)}\end{array}$</code> The second line of that equation, minus the mod, is the Lagrangian interpolation formula. The mod just means that any polynomial of the form $f(x)+h(x)\prod_{k=0}^{n-1}(x-\alpha_k)$, where $h(x)$ is any polynomial over $\mathbb{F}$, will pass through these same points. </p> <p>For the DFT the final modulus product is $\prod_{k=0}^{n-1}(x-\alpha^n)=(x^n-1)$ and polynomial multiplication modulo $(x^n-1)$ is equivalent to the convolution of two $n$ long vectors. </p> <p>The butterfly effect of the FFT comes from using a $2^n$-th primitive root of unity, $\alpha$. A similar effect (though not as elegant) can be achieved using $3^n$-th primitive roots of unity (or any other $p^n$) and combining specified sets of three ($p$).</p> <p>What the Chinese remainder theorem is really giving you is an isomorphism between the factor rings <code>$R/\bigcap_{k=0}^{n-1}I_k\cong \bigotimes_{k=0}^{n-1}R/I_k$</code> where <code>$I_k&lt;R$</code> are ideals in $R$ with special properties. If $R$ is a Euclidian domain, such as $\mathbb{Z}$ or $\mathbb{F}[x]$, these special properties amount to the ideals being generated by relatively prime elements. For example over $\mathbb{Z}$ the ideals would look like <code>$I_k=p_k\mathbb{Z}$</code> with $GCD(p_k,p_j)=1$ for all distinct pairs of $(k,j)$, and the intersection of the ideals would be $\bigcap I_k=\left(\prod p_k\right)\mathbb{Z}$. Any operations which done modulo the product can be performed in parallel modulo each factor. </p> http://mathoverflow.net/questions/10237/does-the-convolution-theorem-apply-to-weaker-algebraic-structures/14204#14204 Answer by Dan Piponi for does the "convolution theorem" apply to weaker algebraic structures? Dan Piponi 2010-02-04T23:19:48Z 2010-02-04T23:19:48Z <p>You can do <a href="http://en.wikipedia.org/wiki/Legendre_transformation#Infimal_convolution" rel="nofollow">infimal convolution</a> using the Legendre transform. You can certainly implement a reasonably fast algorithm for infimal convolution of convex piecewise linear functions though I don't know about the fastest known algorithms that don't use the Legendre transform. The Legendre transform is also called the Fenchel conjugate in optimisation papers so that's another good term to google on.</p>