Mixing
Calculate $Av^{rightarrow}$ using FFT
$begingroup$
Given a vector $v^{rightarrow} = (v_0,v_1, ... v_{n-1})$
And given the matrix A =
$(a_0, a_1 ... a_{n-1})$
$(a_{n-1}, a_0,...., a_{n-2})$
$(a_{n-2}, a_{n-1}, a_0,...., a_{n-3})$
.....
$(a_1, ..., a_{n-2}, a_{n-1}, a_0)$
Each row of the matrix is a circular movement of the row above one column to the right.
I need to calculate $Acdot v^rightarrow$ in $Theta(ncdot lg n)$ complexity
I understand that the result is in the form of the following vector.
The naive approach will take me $theta(n^2)$. In order to that in the required complexity I know that FFT can come handy. But how do I define the polynomials that the algorithm will use? I saw a friend's solution but could not quite understand it. I really want an explanation to this problem and hopefully I will understand the basic concept of how to approach such problems.
fourier-transform fast-fourier-transform
asked Jan 29 at 17:58
S. PeterS. Peter
580310
$endgroup$
add a comment |
$begingroup$
Given a vector $v^{rightarrow} = (v_0,v_1, ... v_{n-1})$
And given the matrix A =
$(a_0, a_1 ... a_{n-1})$
$(a_{n-1}, a_0,...., a_{n-2})$
$(a_{n-2}, a_{n-1}, a_0,...., a_{n-3})$
.....
$(a_1, ..., a_{n-2}, a_{n-1}, a_0)$
Each row of the matrix is a circular movement of the row above one column to the right.
I need to calculate $Acdot v^rightarrow$ in $Theta(ncdot lg n)$ complexity
I understand that the result is in the form of the following vector.
The naive approach will take me $theta(n^2)$. In order to that in the required complexity I know that FFT can come handy. But how do I define the polynomials that the algorithm will use? I saw a friend's solution but could not quite understand it. I really want an explanation to this problem and hopefully I will understand the basic concept of how to approach such problems.
fourier-transform fast-fourier-transform
asked Jan 29 at 17:58
S. PeterS. Peter
580310
$endgroup$
add a comment |
$begingroup$
Given a vector $v^{rightarrow} = (v_0,v_1, ... v_{n-1})$
And given the matrix A =
$(a_0, a_1 ... a_{n-1})$
$(a_{n-1}, a_0,...., a_{n-2})$
$(a_{n-2}, a_{n-1}, a_0,...., a_{n-3})$
.....
$(a_1, ..., a_{n-2}, a_{n-1}, a_0)$
Each row of the matrix is a circular movement of the row above one column to the right.
I need to calculate $Acdot v^rightarrow$ in $Theta(ncdot lg n)$ complexity
I understand that the result is in the form of the following vector.
The naive approach will take me $theta(n^2)$. In order to that in the required complexity I know that FFT can come handy. But how do I define the polynomials that the algorithm will use? I saw a friend's solution but could not quite understand it. I really want an explanation to this problem and hopefully I will understand the basic concept of how to approach such problems.
fourier-transform fast-fourier-transform
asked Jan 29 at 17:58
S. PeterS. Peter
580310
$endgroup$
Given a vector $v^{rightarrow} = (v_0,v_1, ... v_{n-1})$
And given the matrix A =
$(a_0, a_1 ... a_{n-1})$
$(a_{n-1}, a_0,...., a_{n-2})$
$(a_{n-2}, a_{n-1}, a_0,...., a_{n-3})$
.....
$(a_1, ..., a_{n-2}, a_{n-1}, a_0)$
Each row of the matrix is a circular movement of the row above one column to the right.
I need to calculate $Acdot v^rightarrow$ in $Theta(ncdot lg n)$ complexity
I understand that the result is in the form of the following vector.
The naive approach will take me $theta(n^2)$. In order to that in the required complexity I know that FFT can come handy. But how do I define the polynomials that the algorithm will use? I saw a friend's solution but could not quite understand it. I really want an explanation to this problem and hopefully I will understand the basic concept of how to approach such problems.
fourier-transform fast-fourier-transform
fourier-transform fast-fourier-transform
asked Jan 29 at 17:58
S. PeterS. Peter
580310
asked Jan 29 at 17:58
S. PeterS. Peter
580310
asked Jan 29 at 17:58
S. PeterS. Peter
580310
asked Jan 29 at 17:58
S. PeterS. Peter
580310
asked Jan 29 at 17:58
S. PeterS. Peter
580310
580310
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Let $b=(b_0,...b_{n-1})$ with $b_i=a_{n-i}$ where the indices are taken modulo $n$ (reversing the order of the $a_i$'s makes it easier to bring up convolutions, see below).
Matrix $A$ has a special structure, which makes it amenable to fast computations. More precisely, it is a convolution matrix, which means that when you apply it to a vector $v$, the resulting vector is the convolution of $b$ with $v$:
$$(A_v)_i=(b circledast v)_i =sum_{j}b_{i-j}v_j =sum_{j}a_{j-i}v_jtext { (all indices modulo } n text{)}$$
The Discrete Fourier Transform $mathcal F$ maps a vector in $mathbb R^n$ to another vector in $mathbb R^n$ . It has the nice property of transforming a convolution into a component-wise product, that is:
$$left(mathcal F(b circledast v)right)_i=(mathcal F(b))_i(mathcal F(v))_i$$
So once transformed by the Fourier transform, the resultof applying $A$ to $v$ can be computed in only $mathcal O(n)$ operations (component-wise multiplications).
What's more, the Discrete Fourier transform, and its inverse, can be computed efficiently using the FFT algorithm, in $mathcal O(nlog(n)$.
So this means that to compute $Av$, you can apply the following efficient algorithm:
- First, precompute the discrete Fourier transform $mathcal F(b)$ of $b$ via the FFT. It's a one-time operation.
- For any vector $v$,
- compute its discrete Fourier transform $mathcal F(v)$ viat the FFT,
- multiply, component-by-component, $mathcal F(v)$ with $mathcal F(b)$
- Apply the inverse discrete Fourier transform (via the FFT) to the resulting vector.
For every vector $v$, this algorithm takes $mathcal O(nlog(n)) + mathcal O(n)+mathcal O(nlog(n))=mathcal O(nlog(n))$ operations, instead of the normal $mathcal O(n^2)$.
answered Jan 29 at 18:54
Stefan LafonStefan Lafon
3,005212
$endgroup$
$begingroup$
I understand the explanations regarding the run time complextiy of the algorithm, but could you perhaps show more into details the process fo the convolution calculation and the FFT in this problem? This is what my understanding is lacking and I can't really understand it from other explanations i read
$endgroup$
– S. Peter
Jan 29 at 20:02
add a comment |
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: "69"
};
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: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
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
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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%2fmath.stackexchange.com%2fquestions%2f3092515%2fcalculate-av-rightarrow-using-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$
Let $b=(b_0,...b_{n-1})$ with $b_i=a_{n-i}$ where the indices are taken modulo $n$ (reversing the order of the $a_i$'s makes it easier to bring up convolutions, see below).
Matrix $A$ has a special structure, which makes it amenable to fast computations. More precisely, it is a convolution matrix, which means that when you apply it to a vector $v$, the resulting vector is the convolution of $b$ with $v$:
$$(A_v)_i=(b circledast v)_i =sum_{j}b_{i-j}v_j =sum_{j}a_{j-i}v_jtext { (all indices modulo } n text{)}$$
The Discrete Fourier Transform $mathcal F$ maps a vector in $mathbb R^n$ to another vector in $mathbb R^n$ . It has the nice property of transforming a convolution into a component-wise product, that is:
$$left(mathcal F(b circledast v)right)_i=(mathcal F(b))_i(mathcal F(v))_i$$
So once transformed by the Fourier transform, the resultof applying $A$ to $v$ can be computed in only $mathcal O(n)$ operations (component-wise multiplications).
What's more, the Discrete Fourier transform, and its inverse, can be computed efficiently using the FFT algorithm, in $mathcal O(nlog(n)$.
So this means that to compute $Av$, you can apply the following efficient algorithm:
- First, precompute the discrete Fourier transform $mathcal F(b)$ of $b$ via the FFT. It's a one-time operation.
- For any vector $v$,
- compute its discrete Fourier transform $mathcal F(v)$ viat the FFT,
- multiply, component-by-component, $mathcal F(v)$ with $mathcal F(b)$
- Apply the inverse discrete Fourier transform (via the FFT) to the resulting vector.
For every vector $v$, this algorithm takes $mathcal O(nlog(n)) + mathcal O(n)+mathcal O(nlog(n))=mathcal O(nlog(n))$ operations, instead of the normal $mathcal O(n^2)$.
answered Jan 29 at 18:54
Stefan LafonStefan Lafon
3,005212
$endgroup$
$begingroup$
I understand the explanations regarding the run time complextiy of the algorithm, but could you perhaps show more into details the process fo the convolution calculation and the FFT in this problem? This is what my understanding is lacking and I can't really understand it from other explanations i read
$endgroup$
– S. Peter
Jan 29 at 20:02
add a comment |
$begingroup$
Let $b=(b_0,...b_{n-1})$ with $b_i=a_{n-i}$ where the indices are taken modulo $n$ (reversing the order of the $a_i$'s makes it easier to bring up convolutions, see below).
Matrix $A$ has a special structure, which makes it amenable to fast computations. More precisely, it is a convolution matrix, which means that when you apply it to a vector $v$, the resulting vector is the convolution of $b$ with $v$:
$$(A_v)_i=(b circledast v)_i =sum_{j}b_{i-j}v_j =sum_{j}a_{j-i}v_jtext { (all indices modulo } n text{)}$$
The Discrete Fourier Transform $mathcal F$ maps a vector in $mathbb R^n$ to another vector in $mathbb R^n$ . It has the nice property of transforming a convolution into a component-wise product, that is:
$$left(mathcal F(b circledast v)right)_i=(mathcal F(b))_i(mathcal F(v))_i$$
So once transformed by the Fourier transform, the resultof applying $A$ to $v$ can be computed in only $mathcal O(n)$ operations (component-wise multiplications).
What's more, the Discrete Fourier transform, and its inverse, can be computed efficiently using the FFT algorithm, in $mathcal O(nlog(n)$.
So this means that to compute $Av$, you can apply the following efficient algorithm:
- First, precompute the discrete Fourier transform $mathcal F(b)$ of $b$ via the FFT. It's a one-time operation.
- For any vector $v$,
- compute its discrete Fourier transform $mathcal F(v)$ viat the FFT,
- multiply, component-by-component, $mathcal F(v)$ with $mathcal F(b)$
- Apply the inverse discrete Fourier transform (via the FFT) to the resulting vector.
For every vector $v$, this algorithm takes $mathcal O(nlog(n)) + mathcal O(n)+mathcal O(nlog(n))=mathcal O(nlog(n))$ operations, instead of the normal $mathcal O(n^2)$.
answered Jan 29 at 18:54
Stefan LafonStefan Lafon
3,005212
$endgroup$
$begingroup$
I understand the explanations regarding the run time complextiy of the algorithm, but could you perhaps show more into details the process fo the convolution calculation and the FFT in this problem? This is what my understanding is lacking and I can't really understand it from other explanations i read
$endgroup$
– S. Peter
Jan 29 at 20:02
add a comment |
$begingroup$
Let $b=(b_0,...b_{n-1})$ with $b_i=a_{n-i}$ where the indices are taken modulo $n$ (reversing the order of the $a_i$'s makes it easier to bring up convolutions, see below).
Matrix $A$ has a special structure, which makes it amenable to fast computations. More precisely, it is a convolution matrix, which means that when you apply it to a vector $v$, the resulting vector is the convolution of $b$ with $v$:
$$(A_v)_i=(b circledast v)_i =sum_{j}b_{i-j}v_j =sum_{j}a_{j-i}v_jtext { (all indices modulo } n text{)}$$
The Discrete Fourier Transform $mathcal F$ maps a vector in $mathbb R^n$ to another vector in $mathbb R^n$ . It has the nice property of transforming a convolution into a component-wise product, that is:
$$left(mathcal F(b circledast v)right)_i=(mathcal F(b))_i(mathcal F(v))_i$$
So once transformed by the Fourier transform, the resultof applying $A$ to $v$ can be computed in only $mathcal O(n)$ operations (component-wise multiplications).
What's more, the Discrete Fourier transform, and its inverse, can be computed efficiently using the FFT algorithm, in $mathcal O(nlog(n)$.
So this means that to compute $Av$, you can apply the following efficient algorithm:
- First, precompute the discrete Fourier transform $mathcal F(b)$ of $b$ via the FFT. It's a one-time operation.
- For any vector $v$,
- compute its discrete Fourier transform $mathcal F(v)$ viat the FFT,
- multiply, component-by-component, $mathcal F(v)$ with $mathcal F(b)$
- Apply the inverse discrete Fourier transform (via the FFT) to the resulting vector.
For every vector $v$, this algorithm takes $mathcal O(nlog(n)) + mathcal O(n)+mathcal O(nlog(n))=mathcal O(nlog(n))$ operations, instead of the normal $mathcal O(n^2)$.
answered Jan 29 at 18:54
Stefan LafonStefan Lafon
3,005212
$endgroup$
Let $b=(b_0,...b_{n-1})$ with $b_i=a_{n-i}$ where the indices are taken modulo $n$ (reversing the order of the $a_i$'s makes it easier to bring up convolutions, see below).
Matrix $A$ has a special structure, which makes it amenable to fast computations. More precisely, it is a convolution matrix, which means that when you apply it to a vector $v$, the resulting vector is the convolution of $b$ with $v$:
$$(A_v)_i=(b circledast v)_i =sum_{j}b_{i-j}v_j =sum_{j}a_{j-i}v_jtext { (all indices modulo } n text{)}$$
The Discrete Fourier Transform $mathcal F$ maps a vector in $mathbb R^n$ to another vector in $mathbb R^n$ . It has the nice property of transforming a convolution into a component-wise product, that is:
$$left(mathcal F(b circledast v)right)_i=(mathcal F(b))_i(mathcal F(v))_i$$
So once transformed by the Fourier transform, the resultof applying $A$ to $v$ can be computed in only $mathcal O(n)$ operations (component-wise multiplications).
What's more, the Discrete Fourier transform, and its inverse, can be computed efficiently using the FFT algorithm, in $mathcal O(nlog(n)$.
So this means that to compute $Av$, you can apply the following efficient algorithm:
- First, precompute the discrete Fourier transform $mathcal F(b)$ of $b$ via the FFT. It's a one-time operation.
- For any vector $v$,
- compute its discrete Fourier transform $mathcal F(v)$ viat the FFT,
- multiply, component-by-component, $mathcal F(v)$ with $mathcal F(b)$
- Apply the inverse discrete Fourier transform (via the FFT) to the resulting vector.
For every vector $v$, this algorithm takes $mathcal O(nlog(n)) + mathcal O(n)+mathcal O(nlog(n))=mathcal O(nlog(n))$ operations, instead of the normal $mathcal O(n^2)$.
answered Jan 29 at 18:54
Stefan LafonStefan Lafon
3,005212
answered Jan 29 at 18:54
Stefan LafonStefan Lafon
3,005212
answered Jan 29 at 18:54
Stefan LafonStefan Lafon
3,005212
answered Jan 29 at 18:54
Stefan LafonStefan Lafon
3,005212
3,005212
$begingroup$
I understand the explanations regarding the run time complextiy of the algorithm, but could you perhaps show more into details the process fo the convolution calculation and the FFT in this problem? This is what my understanding is lacking and I can't really understand it from other explanations i read
$endgroup$
– S. Peter
Jan 29 at 20:02
add a comment |
$begingroup$
I understand the explanations regarding the run time complextiy of the algorithm, but could you perhaps show more into details the process fo the convolution calculation and the FFT in this problem? This is what my understanding is lacking and I can't really understand it from other explanations i read
$endgroup$
– S. Peter
Jan 29 at 20:02
$begingroup$
I understand the explanations regarding the run time complextiy of the algorithm, but could you perhaps show more into details the process fo the convolution calculation and the FFT in this problem? This is what my understanding is lacking and I can't really understand it from other explanations i read
$endgroup$
– S. Peter
Jan 29 at 20:02
$begingroup$
I understand the explanations regarding the run time complextiy of the algorithm, but could you perhaps show more into details the process fo the convolution calculation and the FFT in this problem? This is what my understanding is lacking and I can't really understand it from other explanations i read
$endgroup$
– S. Peter
Jan 29 at 20:02
add a comment |
Thanks for contributing an answer to Mathematics 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%2fmath.stackexchange.com%2fquestions%2f3092515%2fcalculate-av-rightarrow-using-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
