Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The Convolution Theorem 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.

The same thing can be done for convolutions in the quotient ring Z/pZ via the analogous Number Theoretic Transform.

Does this procedure generalize to other algebraic structures? Arbitrary rings? Semirings? Fast convolutions over the semiring (min,+) would be particularly useful.

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.

share|improve this question
    
Pontryagin duality (en.wikipedia.org/wiki/Pontryagin_duality) allows you to do the same thing over any locally compact abelian group. Note that the ring structure is irrelevant to the definition of convolution. –  Qiaochu Yuan Dec 31 '09 at 6:39
3  
I think it's the ring of complex numbers that Adam wants to replace, rather than the domain of the functions. –  Reid Barton Dec 31 '09 at 6:41
    
Does 'On Fast Multiplication of Polynomials Over Arbitrary Algebras': citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.570 Work for you? –  Thomas Dybdahl Ahle Nov 26 '13 at 17:35
add comment

3 Answers

up vote 13 down vote accepted

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 $(\oplus,\otimes)$ convolution 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.)

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.

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

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

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

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

share|improve this answer
add comment

You can do infimal convolution 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.

share|improve this answer
add comment

Look to the Chinese remainder theorem over rings. The discrete Fourier transform is just one example.

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 $\left[a_{n-1}\ a_{n-2}\ \ldots\ a_0\right]$ is equivalent to evaluating the polynomial $\sum^{(n-1)}_{j=0}a_jx^k $ at $\alpha^k$ for $k=0,1,\ldots, (k-1)$: \[\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}\] and the inverse DFT can be equated to (or easily derived from) Lagrangian interpolation.

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 $\left\{(\alpha_k,\beta_k),\ k=0,1,\ldots,(n-1)\right\}$ 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)}$: \[\begin{array}{rl}f(x)&\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)\\ &\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}\] 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.

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.

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

What the Chinese remainder theorem is really giving you is an isomorphism between the factor rings \[R/\bigcap_{k=0}^{n-1}I_k\cong \bigotimes_{k=0}^{n-1}R/I_k\] where $I_k<R$ 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 $I_k=p_k\mathbb{Z}$ 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.

share|improve this answer
    
All of this sounds very interesting. I'd love to be able to read your post well. Is there any chance of getting the tex working? –  Thomas Dybdahl Ahle Dec 10 '13 at 0:28
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.