Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $S$ be a set of integers. $|S|=n$.

Can we find the product $\prod_{a,b\in S} a+b$ faster than naively add all pairs then multiply them one by one? By faster, I mean use less than $O(n^2)$ arithmetic operations.

If it's possible, can that algorithm work for any commutative semiring?

share|improve this question
    
You might be better off at cs.stackexchange.com or cstheory.stackexchange.com . If you do cross-post, add a link here too. –  user55085 Feb 15 '13 at 11:25
add comment

2 Answers

up vote 1 down vote accepted

Well, a repeated product is best done by recursively splitting the set of terms in half*, computing the products in each half, then multiplying the result, but only if the products become big enough that fast multiplication algorithms become relevant.

Of course, this is the same number of arithmetic operations either way. But it is still computational work overall.

*: half is best computed by total size of the numbers rather than simply how many


We could construct the polynomial

$$ f(x) = \prod_{s \in S} (x + s) $$

(keep in mind my advice about repeated products when computing this product!)

Now, the product you seek to compute is

$$ \prod_{s \in S} f(s) $$

The set of values $\{ f(s) | s \in S \}$ could be computed by a fast "multipoint evaluation" algorithm.


Recall that the resultant $\mathop{\text{Res}}(g(x),h(x))$ of two monic polynomials is the product

$$ \prod (\alpha - \beta) $$

where $\alpha$ and $\beta$ range over the roots of $g(x)$ and $h(x)$ respectively. So we could also compute the product by

$$ \mathop{\text{Res}}(f(x), f(-x)) $$


I haven't attempted to compute the time complexity of these algorithms. I expect the resultant to be the best of the methods I describe both in terms of time complexity and number of arithmetic operations.

All of these techniques can be adapted directly, I think, to any commutative ring. I know very little about computational algebra in semirings, but I find it very plausible the middle algorithm would only require a little bit of adaptation (although I'd be worried about the existence of fast polynomial multiplication algorithms), and a little bit plausible that there is a variation on resultants that would work.

share|improve this answer
    
If I'm not mistaken, the middle one would use $O(n \log n)$ arithmetic operations. I can't find anything on how many arithmetic operations are required to find the resultant of a polynomial. I'm not familiar with computational algebra, but it seems it's quite difficult to find time complexity analysis of algorithms and express it in a way so CS people would understand... –  Chao Xu Feb 15 '13 at 9:17
add comment

Couldn't you count the exponents for each of the elements of S? Assuming the different cases where the pairwise sums are symmetric a + b and b + a being counted twice or once, you could calculate the exponents for each of the elements of s, and then using fast exponentiation for each of the elements, and construct the sum of the terms.

You might also get extra mileage out of factoring the elements into powers of generators, if that is possible in the objects you describe.

share|improve this answer
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.