Computing Cardinality of Sumsets using Convolutions and FFTExplaining why FFT is faster than DFT for the...
Word for something that's always reliable, but never the best?
Other than edits for international editions, did Harry Potter and the Philosopher's Stone receive errata?
How does resistance convert voltage to current?
How do I narratively explain how in-game circumstances do not mechanically allow a PC to instantly kill an NPC?
How do I add a strong "onion flavor" to the biryani (in restaurant style)?
Is the fingering of thirds flexible or do I have to follow the rules?
Why are mages sometimes played bot instead of traditional ADCs?
What would be some possible ways of escaping higher gravity planets?
Why is Shelob considered evil?
Buying a "Used" Router
Create linguistic diagram (in TikZ?)
Should a new user just default to LinearModelFit (vs Fit)
How do dictionaries source attestation?
"Starve to death" Vs. "Starve to the point of death"
Why do single electrical receptacles exist?
Insecure private-key encryption
What is the draw frequency for 3 consecutive games (same players; amateur level)?
Does the US government have any planning in place to ensure there's no shortages of food, fuel, steel and other commodities?
Was there a pre-determined arrangement for the division of Germany in case it surrendered before any Soviet forces entered its territory?
What can I do to encourage my players to use their consumables?
How to align the top of the text with the top of a figure produced by tikz in minipage
How to put text above column in minipage?
How can I prevent an oracle who can see into the past from knowing everything that has happened?
Can me and my friend spend the summer in Canada (6 weeks) at 16 years old without an adult?
Computing Cardinality of Sumsets using Convolutions and FFT
Explaining why FFT is faster than DFT for the general public?FFT-less $O(nlog n)$ algorithm for pairwise sumsComputing set difference between two large setsWhat is the reason that is FFT multiplication slower than other methods for small N?Computing cross-correlation of different size vectors using FFTWhat is the complexity of the problem of computing the cardinality of the union of many (finite) and small sets?Computing Hamming Distance Between Binary VectorsNecessity of convolution operations for product of two polynomials via brute force methodHardness of approximating Minimum Cardinality Exact CoverObtaining Max-Weight Matching from Max-Weight-Max-Cardinality Matching?
$begingroup$
I read somewhere that you can compute the cardinality of sumsets by computing the convolutions of the characteristic vectors of the given sets, and that this can be done efficiently using Fast Fourier Transform. How would this work?
algorithms
asked 3 hours ago
Arnaud AvondetArnaud Avondet
62
New contributor
Arnaud Avondet is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
I read somewhere that you can compute the cardinality of sumsets by computing the convolutions of the characteristic vectors of the given sets, and that this can be done efficiently using Fast Fourier Transform. How would this work?
algorithms
asked 3 hours ago
Arnaud AvondetArnaud Avondet
62
New contributor
Arnaud Avondet is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
I read somewhere that you can compute the cardinality of sumsets by computing the convolutions of the characteristic vectors of the given sets, and that this can be done efficiently using Fast Fourier Transform. How would this work?
algorithms
asked 3 hours ago
Arnaud AvondetArnaud Avondet
62
New contributor
Arnaud Avondet is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
I read somewhere that you can compute the cardinality of sumsets by computing the convolutions of the characteristic vectors of the given sets, and that this can be done efficiently using Fast Fourier Transform. How would this work?
algorithms
algorithms
asked 3 hours ago
Arnaud AvondetArnaud Avondet
62
New contributor
Arnaud Avondet is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 3 hours ago
Arnaud AvondetArnaud Avondet
62
New contributor
Arnaud Avondet is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 3 hours ago
Arnaud AvondetArnaud Avondet
62
New contributor
Arnaud Avondet is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 3 hours ago
Arnaud AvondetArnaud Avondet
62
asked 3 hours ago
Arnaud AvondetArnaud Avondet
62
62
New contributor
Arnaud Avondet is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Arnaud Avondet is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Arnaud Avondet is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Here is a sketch of the main ideas. Let $S,T subseteq mathbb{N}$ be two multisets of non-negative integers, and define $S+T$ to be the multiset
$$S+T = {s+t mid s in S, t in T}.$$
Let $chi_S$ represent the characteristic vector of a set $S$. Then
$$chi_{S+T} = chi_S * chi_T,$$
where $*$ is a convolution operator.
The Fourier transform $mathcal{F}$ has the property that
$$mathcal{F}(f*g) = mathcal{F}(f) times mathcal{F}(g),$$
where $times$ represents pointwise multiplication of functions. Therefore,
$$mathcal{F}(chi_{S+T}) = mathcal{F}(chi_S) times mathcal{F}(chi_T),$$
and in particular,
$$chi_{S+T} = mathcal{F}^{-1}(mathcal{F}(chi_S) times mathcal{F}(chi_T)).$$
This gives us a method to compute $S+T$. We can compute the characteristic vector $chi_{S+T}$ for the multiset $S+T$ by computing $mathcal{F}(chi_S)$, the Fourier transform of the characteristic vector for $S$, and $mathcal{F}(g)$; multiplying them; and then applying the inverse Fourier transform to the result. Each of these steps can be implemented efficiently using the Fast Fourier transform. The end result will be $chi_{S+T}$, from which we can reconstruct $S+T$ or its cardinality.
The overall running time will be $O(n log n)$, where $n$ is an upper bound on the largest element of $S,T$.
answered 2 hours ago
D.W.♦D.W.
99.6k12121286
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "419"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Arnaud Avondet is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f104817%2fcomputing-cardinality-of-sumsets-using-convolutions-and-fft%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Here is a sketch of the main ideas. Let $S,T subseteq mathbb{N}$ be two multisets of non-negative integers, and define $S+T$ to be the multiset
$$S+T = {s+t mid s in S, t in T}.$$
Let $chi_S$ represent the characteristic vector of a set $S$. Then
$$chi_{S+T} = chi_S * chi_T,$$
where $*$ is a convolution operator.
The Fourier transform $mathcal{F}$ has the property that
$$mathcal{F}(f*g) = mathcal{F}(f) times mathcal{F}(g),$$
where $times$ represents pointwise multiplication of functions. Therefore,
$$mathcal{F}(chi_{S+T}) = mathcal{F}(chi_S) times mathcal{F}(chi_T),$$
and in particular,
$$chi_{S+T} = mathcal{F}^{-1}(mathcal{F}(chi_S) times mathcal{F}(chi_T)).$$
This gives us a method to compute $S+T$. We can compute the characteristic vector $chi_{S+T}$ for the multiset $S+T$ by computing $mathcal{F}(chi_S)$, the Fourier transform of the characteristic vector for $S$, and $mathcal{F}(g)$; multiplying them; and then applying the inverse Fourier transform to the result. Each of these steps can be implemented efficiently using the Fast Fourier transform. The end result will be $chi_{S+T}$, from which we can reconstruct $S+T$ or its cardinality.
The overall running time will be $O(n log n)$, where $n$ is an upper bound on the largest element of $S,T$.
answered 2 hours ago
D.W.♦D.W.
99.6k12121286
$endgroup$
add a comment |
$begingroup$
Here is a sketch of the main ideas. Let $S,T subseteq mathbb{N}$ be two multisets of non-negative integers, and define $S+T$ to be the multiset
$$S+T = {s+t mid s in S, t in T}.$$
Let $chi_S$ represent the characteristic vector of a set $S$. Then
$$chi_{S+T} = chi_S * chi_T,$$
where $*$ is a convolution operator.
The Fourier transform $mathcal{F}$ has the property that
$$mathcal{F}(f*g) = mathcal{F}(f) times mathcal{F}(g),$$
where $times$ represents pointwise multiplication of functions. Therefore,
$$mathcal{F}(chi_{S+T}) = mathcal{F}(chi_S) times mathcal{F}(chi_T),$$
and in particular,
$$chi_{S+T} = mathcal{F}^{-1}(mathcal{F}(chi_S) times mathcal{F}(chi_T)).$$
This gives us a method to compute $S+T$. We can compute the characteristic vector $chi_{S+T}$ for the multiset $S+T$ by computing $mathcal{F}(chi_S)$, the Fourier transform of the characteristic vector for $S$, and $mathcal{F}(g)$; multiplying them; and then applying the inverse Fourier transform to the result. Each of these steps can be implemented efficiently using the Fast Fourier transform. The end result will be $chi_{S+T}$, from which we can reconstruct $S+T$ or its cardinality.
The overall running time will be $O(n log n)$, where $n$ is an upper bound on the largest element of $S,T$.
answered 2 hours ago
D.W.♦D.W.
99.6k12121286
$endgroup$
add a comment |
$begingroup$
Here is a sketch of the main ideas. Let $S,T subseteq mathbb{N}$ be two multisets of non-negative integers, and define $S+T$ to be the multiset
$$S+T = {s+t mid s in S, t in T}.$$
Let $chi_S$ represent the characteristic vector of a set $S$. Then
$$chi_{S+T} = chi_S * chi_T,$$
where $*$ is a convolution operator.
The Fourier transform $mathcal{F}$ has the property that
$$mathcal{F}(f*g) = mathcal{F}(f) times mathcal{F}(g),$$
where $times$ represents pointwise multiplication of functions. Therefore,
$$mathcal{F}(chi_{S+T}) = mathcal{F}(chi_S) times mathcal{F}(chi_T),$$
and in particular,
$$chi_{S+T} = mathcal{F}^{-1}(mathcal{F}(chi_S) times mathcal{F}(chi_T)).$$
This gives us a method to compute $S+T$. We can compute the characteristic vector $chi_{S+T}$ for the multiset $S+T$ by computing $mathcal{F}(chi_S)$, the Fourier transform of the characteristic vector for $S$, and $mathcal{F}(g)$; multiplying them; and then applying the inverse Fourier transform to the result. Each of these steps can be implemented efficiently using the Fast Fourier transform. The end result will be $chi_{S+T}$, from which we can reconstruct $S+T$ or its cardinality.
The overall running time will be $O(n log n)$, where $n$ is an upper bound on the largest element of $S,T$.
answered 2 hours ago
D.W.♦D.W.
99.6k12121286
$endgroup$
Here is a sketch of the main ideas. Let $S,T subseteq mathbb{N}$ be two multisets of non-negative integers, and define $S+T$ to be the multiset
$$S+T = {s+t mid s in S, t in T}.$$
Let $chi_S$ represent the characteristic vector of a set $S$. Then
$$chi_{S+T} = chi_S * chi_T,$$
where $*$ is a convolution operator.
The Fourier transform $mathcal{F}$ has the property that
$$mathcal{F}(f*g) = mathcal{F}(f) times mathcal{F}(g),$$
where $times$ represents pointwise multiplication of functions. Therefore,
$$mathcal{F}(chi_{S+T}) = mathcal{F}(chi_S) times mathcal{F}(chi_T),$$
and in particular,
$$chi_{S+T} = mathcal{F}^{-1}(mathcal{F}(chi_S) times mathcal{F}(chi_T)).$$
This gives us a method to compute $S+T$. We can compute the characteristic vector $chi_{S+T}$ for the multiset $S+T$ by computing $mathcal{F}(chi_S)$, the Fourier transform of the characteristic vector for $S$, and $mathcal{F}(g)$; multiplying them; and then applying the inverse Fourier transform to the result. Each of these steps can be implemented efficiently using the Fast Fourier transform. The end result will be $chi_{S+T}$, from which we can reconstruct $S+T$ or its cardinality.
The overall running time will be $O(n log n)$, where $n$ is an upper bound on the largest element of $S,T$.
answered 2 hours ago
D.W.♦D.W.
99.6k12121286
answered 2 hours ago
D.W.♦D.W.
99.6k12121286
answered 2 hours ago
D.W.♦D.W.
99.6k12121286
answered 2 hours ago
D.W.♦D.W.
99.6k12121286
99.6k12121286
add a comment |
add a comment |
Arnaud Avondet is a new contributor. Be nice, and check out our Code of Conduct.
Arnaud Avondet is a new contributor. Be nice, and check out our Code of Conduct.
Arnaud Avondet is a new contributor. Be nice, and check out our Code of Conduct.
Arnaud Avondet is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Computer Science Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f104817%2fcomputing-cardinality-of-sumsets-using-convolutions-and-fft%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
