Prime-factor FFT algorithm - Revision history

Quondum: rm title case; fmt; fixing weirdness of $not being on its own line in Brave browser$

2025-04-06T00:58:57Z

rm title case; fmt; fixing weirdness of <math display="block"> not being on its own line in Brave browser

Citation bot: Add: bibcode, doi. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:FFT algorithms | #UCB_Category 15/17

2024-12-29T15:16:18Z

Add: bibcode, doi. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:FFT algorithms | #UCB_Category 15/17

← Previous revision		Revision as of 15:16, 29 December 2024
Line 63:		Line 63:
	==References==		==References==
	{{refbegin}}		{{refbegin}}
	*{{cite journal \|first=I. J. \|last=Good \|title=The interaction algorithm and practical Fourier analysis \|journal=Journal of the Royal Statistical Society, Series B \|volume=20 \|issue=2 \|pages=361–372 \|year=1958 \|jstor=2983896 }} Addendum, ''ibid.'' '''22''' (2), 373-375 (1960) {{JSTOR\|2984108}}.		*{{cite journal \|first=I. J. \|last=Good \|title=The interaction algorithm and practical Fourier analysis \|journal=Journal of the Royal Statistical Society, Series B \|volume=20 \|issue=2 \|pages=361–372 \|year=1958 \|doi=10.1111/j.2517-6161.1958.tb00300.x \|jstor=2983896 }} Addendum, ''ibid.'' '''22''' (2), 373-375 (1960) {{JSTOR\|2984108}}.
	*{{cite book \|first=L. H. \|last=Thomas \|chapter=Using a computer to solve problems in physics \|title=Applications of Digital Computers \|publisher=Ginn \|location=Boston \|year=1963 }}		*{{cite book \|first=L. H. \|last=Thomas \|chapter=Using a computer to solve problems in physics \|title=Applications of Digital Computers \|publisher=Ginn \|location=Boston \|year=1963 }}
	*{{cite journal \|first1=P. \|last1=Duhamel \|first2=M. \|last2=Vetterli \|title=Fast Fourier transforms: a tutorial review and a state of the art \|journal=Signal Processing \|volume=19 \|issue=4 \|pages=259–299 \|year=1990 \|doi=10.1016/0165-1684(90)90158-U \|url=http://infoscience.epfl.ch/record/59946 }}		*{{cite journal \|first1=P. \|last1=Duhamel \|first2=M. \|last2=Vetterli \|title=Fast Fourier transforms: a tutorial review and a state of the art \|journal=Signal Processing \|volume=19 \|issue=4 \|pages=259–299 \|year=1990 \|doi=10.1016/0165-1684(90)90158-U \|bibcode=1990SigPr..19..259D \|url=http://infoscience.epfl.ch/record/59946 }}
	*{{cite journal \|first1=S. C. \|last1=Chan \|first2=K. L. \|last2=Ho \|title=On indexing the prime-factor fast Fourier transform algorithm \|journal= IEEE Transactions on Circuits and Systems\|volume=38 \|issue=8 \|pages=951–953 \|year=1991 \|doi=10.1109/31.85638 }}		*{{cite journal \|first1=S. C. \|last1=Chan \|first2=K. L. \|last2=Ho \|title=On indexing the prime-factor fast Fourier transform algorithm \|journal= IEEE Transactions on Circuits and Systems\|volume=38 \|issue=8 \|pages=951–953 \|year=1991 \|doi=10.1109/31.85638 }}
	*{{cite journal \|first=I. J. \|last=Good \|title=The relationship between two fast Fourier transforms \| journal = IEEE Transactions on Computers \|volume=100 \|issue=3 \|pages=310–317 \|year=1971 \|doi=10.1109/T-C.1971.223236 \|s2cid=585818 }}		*{{cite journal \|first=I. J. \|last=Good \|title=The relationship between two fast Fourier transforms \| journal = IEEE Transactions on Computers \|volume=100 \|issue=3 \|pages=310–317 \|year=1971 \|doi=10.1109/T-C.1971.223236 \|s2cid=585818 }}

Synapse554: /* Algorithm */

2024-08-15T15:14:19Z

Algorithm

← Previous revision		Revision as of 15:14, 15 August 2024
Line 10:		Line 10:

	==Algorithm==		==Algorithm==
	Let <math>a(x)</math> a polynomial and <math>\omega_n</math> a [[Principal root of unity\|principal <math>n</math>th root of unity]]. We define the DFT of <math>a(x)</math> as the <math>n</math>-tuple <math>(\hat{a}_j) = (a(\omega_n^j)) </math>.		Let <math>a(x)</math> be a polynomial and <math>\omega_n</math> be a [[Principal root of unity\|principal <math>n</math>-th root of unity]]. We define the DFT of <math>a(x)</math> as the <math>n</math>-tuple <math>(\hat{a}_j) = (a(\omega_n^j)) </math>.
	In other words,		In other words,
	<math display="block">\hat{a}_j = \sum_{i=0}^{n-1} a_i \omega_n^{ij} \quad \text{ for all } j = 0, 1, \dots, n - 1.</math>		<math display="block">\hat{a}_j = \sum_{i=0}^{n-1} a_i \omega_n^{ij} \quad \text{ for all } j = 0, 1, \dots, n - 1.</math>

Philipnelson99: Reverted edits by 142.181.177.25 (talk) (HG) (3.4.12)

2024-03-18T20:46:47Z

Reverted edits by 142.181.177.25 (talk) (HG) (3.4.12)

← Previous revision		Revision as of 20:46, 18 March 2024
Line 1:		Line 1:
	{{Use American English\|date = March 2019}}		{{Use American English\|date = March 2019}}
	{{Short description\|Fast Fourier Transform algorithm}}		{{Short description\|Fast Fourier Transform algorithm}}
	The '''prime-factor algorithm (PFA)''', also called the '''~~ishupissyisanigly~~''' (1958/1963), is a [[fast Fourier transform]] (FFT) algorithm that re-expresses the [[discrete Fourier transform]] (DFT) of a size ''N'' = ''N''<sub>1</sub>''N''<sub>2</sub> as a two-dimensional ''N''<sub>1</sub>×''N''<sub>2</sub> DFT, but ''only'' for the case where ''N''<sub>1</sub> and ''N''<sub>2</sub> are [[relatively prime]]. These smaller transforms of size ''N''<sub>1</sub> and ''N''<sub>2</sub> can then be evaluated by applying PFA [[recursion\|recursively]] or by using some other FFT algorithm.		The '''prime-factor algorithm (PFA)''', also called the '''Good–Thomas algorithm''' (1958/1963), is a [[fast Fourier transform]] (FFT) algorithm that re-expresses the [[discrete Fourier transform]] (DFT) of a size ''N'' = ''N''<sub>1</sub>''N''<sub>2</sub> as a two-dimensional ''N''<sub>1</sub>×''N''<sub>2</sub> DFT, but ''only'' for the case where ''N''<sub>1</sub> and ''N''<sub>2</sub> are [[relatively prime]]. These smaller transforms of size ''N''<sub>1</sub> and ''N''<sub>2</sub> can then be evaluated by applying PFA [[recursion\|recursively]] or by using some other FFT algorithm.

	PFA should not be confused with the ''mixed-radix'' generalization of the popular [[Cooley–Tukey FFT algorithm\|Cooley–Tukey algorithm]], which also subdivides a DFT of size ''N'' = ''N''<sub>1</sub>''N''<sub>2</sub> into smaller transforms of size ''N''<sub>1</sub> and ''N''<sub>2</sub>. The latter algorithm can use ''any'' factors (not necessarily relatively prime), but it has the disadvantage that it also requires extra multiplications by roots of unity called [[twiddle factor]]s, in addition to the smaller transforms. On the other hand, PFA has the disadvantages that it only works for relatively prime factors (e.g. it is useless for [[power of two\|power-of-two]] sizes) and that it requires more complicated re-indexing of the data based on the [[additive group]] [[Group isomorphism\|isomorphisms]]. Note, however, that PFA can be combined with mixed-radix Cooley–Tukey, with the former factorizing ''N'' into relatively prime components and the latter handling repeated factors.		PFA should not be confused with the ''mixed-radix'' generalization of the popular [[Cooley–Tukey FFT algorithm\|Cooley–Tukey algorithm]], which also subdivides a DFT of size ''N'' = ''N''<sub>1</sub>''N''<sub>2</sub> into smaller transforms of size ''N''<sub>1</sub> and ''N''<sub>2</sub>. The latter algorithm can use ''any'' factors (not necessarily relatively prime), but it has the disadvantage that it also requires extra multiplications by roots of unity called [[twiddle factor]]s, in addition to the smaller transforms. On the other hand, PFA has the disadvantages that it only works for relatively prime factors (e.g. it is useless for [[power of two\|power-of-two]] sizes) and that it requires more complicated re-indexing of the data based on the [[additive group]] [[Group isomorphism\|isomorphisms]]. Note, however, that PFA can be combined with mixed-radix Cooley–Tukey, with the former factorizing ''N'' into relatively prime components and the latter handling repeated factors.

142.181.177.25 at 20:46, 18 March 2024

2024-03-18T20:46:41Z

← Previous revision		Revision as of 20:46, 18 March 2024
Line 1:		Line 1:
	{{Use American English\|date = March 2019}}		{{Use American English\|date = March 2019}}
	{{Short description\|Fast Fourier Transform algorithm}}		{{Short description\|Fast Fourier Transform algorithm}}
	The '''prime-factor algorithm (PFA)''', also called the '''~~Good–Thomas algorithm~~''' (1958/1963), is a [[fast Fourier transform]] (FFT) algorithm that re-expresses the [[discrete Fourier transform]] (DFT) of a size ''N'' = ''N''<sub>1</sub>''N''<sub>2</sub> as a two-dimensional ''N''<sub>1</sub>×''N''<sub>2</sub> DFT, but ''only'' for the case where ''N''<sub>1</sub> and ''N''<sub>2</sub> are [[relatively prime]]. These smaller transforms of size ''N''<sub>1</sub> and ''N''<sub>2</sub> can then be evaluated by applying PFA [[recursion\|recursively]] or by using some other FFT algorithm.		The '''prime-factor algorithm (PFA)''', also called the '''ishupissyisanigly''' (1958/1963), is a [[fast Fourier transform]] (FFT) algorithm that re-expresses the [[discrete Fourier transform]] (DFT) of a size ''N'' = ''N''<sub>1</sub>''N''<sub>2</sub> as a two-dimensional ''N''<sub>1</sub>×''N''<sub>2</sub> DFT, but ''only'' for the case where ''N''<sub>1</sub> and ''N''<sub>2</sub> are [[relatively prime]]. These smaller transforms of size ''N''<sub>1</sub> and ''N''<sub>2</sub> can then be evaluated by applying PFA [[recursion\|recursively]] or by using some other FFT algorithm.

	PFA should not be confused with the ''mixed-radix'' generalization of the popular [[Cooley–Tukey FFT algorithm\|Cooley–Tukey algorithm]], which also subdivides a DFT of size ''N'' = ''N''<sub>1</sub>''N''<sub>2</sub> into smaller transforms of size ''N''<sub>1</sub> and ''N''<sub>2</sub>. The latter algorithm can use ''any'' factors (not necessarily relatively prime), but it has the disadvantage that it also requires extra multiplications by roots of unity called [[twiddle factor]]s, in addition to the smaller transforms. On the other hand, PFA has the disadvantages that it only works for relatively prime factors (e.g. it is useless for [[power of two\|power-of-two]] sizes) and that it requires more complicated re-indexing of the data based on the [[additive group]] [[Group isomorphism\|isomorphisms]]. Note, however, that PFA can be combined with mixed-radix Cooley–Tukey, with the former factorizing ''N'' into relatively prime components and the latter handling repeated factors.		PFA should not be confused with the ''mixed-radix'' generalization of the popular [[Cooley–Tukey FFT algorithm\|Cooley–Tukey algorithm]], which also subdivides a DFT of size ''N'' = ''N''<sub>1</sub>''N''<sub>2</sub> into smaller transforms of size ''N''<sub>1</sub> and ''N''<sub>2</sub>. The latter algorithm can use ''any'' factors (not necessarily relatively prime), but it has the disadvantage that it also requires extra multiplications by roots of unity called [[twiddle factor]]s, in addition to the smaller transforms. On the other hand, PFA has the disadvantages that it only works for relatively prime factors (e.g. it is useless for [[power of two\|power-of-two]] sizes) and that it requires more complicated re-indexing of the data based on the [[additive group]] [[Group isomorphism\|isomorphisms]]. Note, however, that PFA can be combined with mixed-radix Cooley–Tukey, with the former factorizing ''N'' into relatively prime components and the latter handling repeated factors.

Philipnelson99: Reverted edits by 142.181.177.25 (talk) (HG) (3.4.12)

2024-03-18T20:46:09Z

Reverted edits by 142.181.177.25 (talk) (HG) (3.4.12)

← Previous revision		Revision as of 20:46, 18 March 2024
Line 1:		Line 1:
	{{Use American English\|date = March 2019}}		{{Use American English\|date = March 2019}}
	{{Short description\|Fast Fourier Transform algorithm}}		{{Short description\|Fast Fourier Transform algorithm}}
	The '''prime-factor algorithm (PFA)''', also called the '''~~ishana~~ ~~is a niglywigly~~''' (1958/1963), is a [[fast Fourier transform]] (FFT) algorithm that re-expresses the [[discrete Fourier transform]] (DFT) of a size ''N'' = ''N''<sub>1</sub>''N''<sub>2</sub> as a two-dimensional ''N''<sub>1</sub>×''N''<sub>2</sub> DFT, but ''only'' for the case where ''N''<sub>1</sub> and ''N''<sub>2</sub> are [[relatively prime]]. These smaller transforms of size ''N''<sub>1</sub> and ''N''<sub>2</sub> can then be evaluated by applying PFA [[recursion\|recursively]] or by using some other FFT algorithm.		The '''prime-factor algorithm (PFA)''', also called the '''Good–Thomas algorithm''' (1958/1963), is a [[fast Fourier transform]] (FFT) algorithm that re-expresses the [[discrete Fourier transform]] (DFT) of a size ''N'' = ''N''<sub>1</sub>''N''<sub>2</sub> as a two-dimensional ''N''<sub>1</sub>×''N''<sub>2</sub> DFT, but ''only'' for the case where ''N''<sub>1</sub> and ''N''<sub>2</sub> are [[relatively prime]]. These smaller transforms of size ''N''<sub>1</sub> and ''N''<sub>2</sub> can then be evaluated by applying PFA [[recursion\|recursively]] or by using some other FFT algorithm.

	PFA should not be confused with the ''mixed-radix'' generalization of the popular [[Cooley–Tukey FFT algorithm\|Cooley–Tukey algorithm]], which also subdivides a DFT of size ''N'' = ''N''<sub>1</sub>''N''<sub>2</sub> into smaller transforms of size ''N''<sub>1</sub> and ''N''<sub>2</sub>. The latter algorithm can use ''any'' factors (not necessarily relatively prime), but it has the disadvantage that it also requires extra multiplications by roots of unity called [[twiddle factor]]s, in addition to the smaller transforms. On the other hand, PFA has the disadvantages that it only works for relatively prime factors (e.g. it is useless for [[power of two\|power-of-two]] sizes) and that it requires more complicated re-indexing of the data based on the [[additive group]] [[Group isomorphism\|isomorphisms]]. Note, however, that PFA can be combined with mixed-radix Cooley–Tukey, with the former factorizing ''N'' into relatively prime components and the latter handling repeated factors.		PFA should not be confused with the ''mixed-radix'' generalization of the popular [[Cooley–Tukey FFT algorithm\|Cooley–Tukey algorithm]], which also subdivides a DFT of size ''N'' = ''N''<sub>1</sub>''N''<sub>2</sub> into smaller transforms of size ''N''<sub>1</sub> and ''N''<sub>2</sub>. The latter algorithm can use ''any'' factors (not necessarily relatively prime), but it has the disadvantage that it also requires extra multiplications by roots of unity called [[twiddle factor]]s, in addition to the smaller transforms. On the other hand, PFA has the disadvantages that it only works for relatively prime factors (e.g. it is useless for [[power of two\|power-of-two]] sizes) and that it requires more complicated re-indexing of the data based on the [[additive group]] [[Group isomorphism\|isomorphisms]]. Note, however, that PFA can be combined with mixed-radix Cooley–Tukey, with the former factorizing ''N'' into relatively prime components and the latter handling repeated factors.

142.181.177.25 at 20:46, 18 March 2024

2024-03-18T20:46:02Z

← Previous revision		Revision as of 20:46, 18 March 2024
Line 1:		Line 1:
	{{Use American English\|date = March 2019}}		{{Use American English\|date = March 2019}}
	{{Short description\|Fast Fourier Transform algorithm}}		{{Short description\|Fast Fourier Transform algorithm}}
	The '''prime-factor algorithm (PFA)''', also called the '''~~Good–Thomas~~ ~~algorithm~~''' (1958/1963), is a [[fast Fourier transform]] (FFT) algorithm that re-expresses the [[discrete Fourier transform]] (DFT) of a size ''N'' = ''N''<sub>1</sub>''N''<sub>2</sub> as a two-dimensional ''N''<sub>1</sub>×''N''<sub>2</sub> DFT, but ''only'' for the case where ''N''<sub>1</sub> and ''N''<sub>2</sub> are [[relatively prime]]. These smaller transforms of size ''N''<sub>1</sub> and ''N''<sub>2</sub> can then be evaluated by applying PFA [[recursion\|recursively]] or by using some other FFT algorithm.		The '''prime-factor algorithm (PFA)''', also called the '''ishana is a niglywigly''' (1958/1963), is a [[fast Fourier transform]] (FFT) algorithm that re-expresses the [[discrete Fourier transform]] (DFT) of a size ''N'' = ''N''<sub>1</sub>''N''<sub>2</sub> as a two-dimensional ''N''<sub>1</sub>×''N''<sub>2</sub> DFT, but ''only'' for the case where ''N''<sub>1</sub> and ''N''<sub>2</sub> are [[relatively prime]]. These smaller transforms of size ''N''<sub>1</sub> and ''N''<sub>2</sub> can then be evaluated by applying PFA [[recursion\|recursively]] or by using some other FFT algorithm.

	PFA should not be confused with the ''mixed-radix'' generalization of the popular [[Cooley–Tukey FFT algorithm\|Cooley–Tukey algorithm]], which also subdivides a DFT of size ''N'' = ''N''<sub>1</sub>''N''<sub>2</sub> into smaller transforms of size ''N''<sub>1</sub> and ''N''<sub>2</sub>. The latter algorithm can use ''any'' factors (not necessarily relatively prime), but it has the disadvantage that it also requires extra multiplications by roots of unity called [[twiddle factor]]s, in addition to the smaller transforms. On the other hand, PFA has the disadvantages that it only works for relatively prime factors (e.g. it is useless for [[power of two\|power-of-two]] sizes) and that it requires more complicated re-indexing of the data based on the [[additive group]] [[Group isomorphism\|isomorphisms]]. Note, however, that PFA can be combined with mixed-radix Cooley–Tukey, with the former factorizing ''N'' into relatively prime components and the latter handling repeated factors.		PFA should not be confused with the ''mixed-radix'' generalization of the popular [[Cooley–Tukey FFT algorithm\|Cooley–Tukey algorithm]], which also subdivides a DFT of size ''N'' = ''N''<sub>1</sub>''N''<sub>2</sub> into smaller transforms of size ''N''<sub>1</sub> and ''N''<sub>2</sub>. The latter algorithm can use ''any'' factors (not necessarily relatively prime), but it has the disadvantage that it also requires extra multiplications by roots of unity called [[twiddle factor]]s, in addition to the smaller transforms. On the other hand, PFA has the disadvantages that it only works for relatively prime factors (e.g. it is useless for [[power of two\|power-of-two]] sizes) and that it requires more complicated re-indexing of the data based on the [[additive group]] [[Group isomorphism\|isomorphisms]]. Note, however, that PFA can be combined with mixed-radix Cooley–Tukey, with the former factorizing ''N'' into relatively prime components and the latter handling repeated factors.

137.248.70.5: /* Mapping Based on CRT */

2024-03-07T11:07:14Z

Mapping Based on CRT

← Previous revision		Revision as of 11:07, 7 March 2024
Line 28:		Line 28:
	Finally, define <math>a_{i_0, \dots, i_{D - 1}} = a_{\sum_{d = 0}^{D - 1} i_d e_d}</math> and <math>\hat{a}_{j_0, \dots, j_{D - 1}} = \hat{a}_{\sum_{d = 0}^{D - 1} j_d e_d}</math>,		Finally, define <math>a_{i_0, \dots, i_{D - 1}} = a_{\sum_{d = 0}^{D - 1} i_d e_d}</math> and <math>\hat{a}_{j_0, \dots, j_{D - 1}} = \hat{a}_{\sum_{d = 0}^{D - 1} j_d e_d}</math>,
	we have		we have
	<math display="block">\hat{a}_{j_0, \dots, j_{D - 1}} = \sum_{i_0 = 0}^{n_0 - 1} \cdots \sum_{i_{D - 1}}^{n_{D - 1} - 1} a_{i_0, \dots, i_{D - 1}} \prod_{d = 0}^{D - 1} \omega_{n_d}^{i_d j_d} .</math>		<math display="block">\hat{a}_{j_0, \dots, j_{D - 1}} = \sum_{i_0 = 0}^{n_0 - 1} \cdots \sum_{i_{D - 1}=0}^{n_{D - 1} - 1} a_{i_0, \dots, i_{D - 1}} \prod_{d = 0}^{D - 1} \omega_{n_d}^{i_d j_d} .</math>
	Therefore, we have the multi-dimensional DFT, <math>\otimes_{d = 0}^{D - 1} \text{DFT}_{\omega_{n_d}}</math>.		Therefore, we have the multi-dimensional DFT, <math>\otimes_{d = 0}^{D - 1} \text{DFT}_{\omega_{n_d}}</math>.

137.248.70.5: /* Mapping Based on CRT */

2024-03-07T11:00:20Z

Mapping Based on CRT

← Previous revision		Revision as of 11:00, 7 March 2024
Line 25:		Line 25:
	\sum_{i = 0}^{n - 1} a_i \left( \prod_{d = 0}^{D - 1} \omega_{n_d} \right)^{ij} =		\sum_{i = 0}^{n - 1} a_i \left( \prod_{d = 0}^{D - 1} \omega_{n_d} \right)^{ij} =
	\sum_{i = 0}^{n - 1} a_i \prod_{d = 0}^{D - 1} \omega_{n_d}^{ (i \bmod n_d) (j \bmod n_d)} =		\sum_{i = 0}^{n - 1} a_i \prod_{d = 0}^{D - 1} \omega_{n_d}^{ (i \bmod n_d) (j \bmod n_d)} =
	\sum_{i_0 = 0}^{n_0 - 1} \cdots \sum_{i_{D - 1}}^{n_{D - 1} - 1} a_{\sum_{d = 0}^{D - 1} e_d i_d} \prod_{d = 0}^{D - 1} \omega_{n_d}^{i_d (j \bmod n_d)} .</math>		\sum_{i_0 = 0}^{n_0 - 1} \cdots \sum_{i_{D - 1} = 0}^{n_{D - 1} - 1} a_{\sum_{d = 0}^{D - 1} e_d i_d} \prod_{d = 0}^{D - 1} \omega_{n_d}^{i_d (j \bmod n_d)} .</math>
	Finally, define <math>a_{i_0, \dots, i_{D - 1}} = a_{\sum_{d = 0}^{D - 1} i_d e_d}</math> and <math>\hat{a}_{j_0, \dots, j_{D - 1}} = \hat{a}_{\sum_{d = 0}^{D - 1} j_d e_d}</math>,		Finally, define <math>a_{i_0, \dots, i_{D - 1}} = a_{\sum_{d = 0}^{D - 1} i_d e_d}</math> and <math>\hat{a}_{j_0, \dots, j_{D - 1}} = \hat{a}_{\sum_{d = 0}^{D - 1} j_d e_d}</math>,
	we have		we have

2601:647:6300:1070:59A4:D25D:994F:8792: Fixing typo in modulo (q_d -> n_d) for CRT map

2024-03-03T05:05:38Z

Fixing typo in modulo (q_d -> n_d) for CRT map

← Previous revision		Revision as of 05:05, 3 March 2024
Line 19:		Line 19:
	=== Mapping Based on CRT ===		=== Mapping Based on CRT ===

	For a coprime factorization <math display="inline">n = \prod_{d = 0}^{D - 1} n_d</math>, we have the [[Chinese remainder theorem\|Chinese remainder map]] <math>m \mapsto (m \bmod ~~q_d~~)</math> from <math>\mathbb{Z}_{n}</math> to <math display="inline">\prod_{d = 0}^{D - 1} \mathbb{Z}_{n_d} </math> with <math display="inline">(m_d) \mapsto \sum_{d = 0}^{D - 1} e_d m_d</math> as its inverse where <math>e_d</math>'s are the [[central idempotent\|central orthogonal idempotent elements]] with <math display="inline">\sum_{d = 0}^{D - 1} e_d = 1 \pmod{n}</math>.		For a coprime factorization <math display="inline">n = \prod_{d = 0}^{D - 1} n_d</math>, we have the [[Chinese remainder theorem\|Chinese remainder map]] <math>m \mapsto (m \bmod n_d)</math> from <math>\mathbb{Z}_{n}</math> to <math display="inline">\prod_{d = 0}^{D - 1} \mathbb{Z}_{n_d} </math> with <math display="inline">(m_d) \mapsto \sum_{d = 0}^{D - 1} e_d m_d</math> as its inverse where <math>e_d</math>'s are the [[central idempotent\|central orthogonal idempotent elements]] with <math display="inline">\sum_{d = 0}^{D - 1} e_d = 1 \pmod{n}</math>.
	Choosing <math>\omega_{n_d} = \omega_n^{e_d}</math> (therefore, <math display="inline">\prod_{d = 0}^{D - 1} \omega_{n_d} = \omega_n^{\sum_{d = 0}^{D - 1} e_d} = \omega_n</math>), we rewrite <math>\text{DFT}_{\omega_n}</math> as follows:		Choosing <math>\omega_{n_d} = \omega_n^{e_d}</math> (therefore, <math display="inline">\prod_{d = 0}^{D - 1} \omega_{n_d} = \omega_n^{\sum_{d = 0}^{D - 1} e_d} = \omega_n</math>), we rewrite <math>\text{DFT}_{\omega_n}</math> as follows:
	<math display="block">\hat{a}_j =		<math display="block">\hat{a}_j =

← Previous revision		Revision as of 15:16, 29 December 2024
Line 63:		Line 63:
	==References==		==References==
	{{refbegin}}		{{refbegin}}
	*{{cite journal \|first=I. J. \|last=Good \|title=The interaction algorithm and practical Fourier analysis \|journal=Journal of the Royal Statistical Society, Series B \|volume=20 \|issue=2 \|pages=361–372 \|year=1958 \|jstor=2983896 }} Addendum, ''ibid.'' '''22''' (2), 373-375 (1960) {{JSTOR\|2984108}}.		*{{cite journal \|first=I. J. \|last=Good \|title=The interaction algorithm and practical Fourier analysis \|journal=Journal of the Royal Statistical Society, Series B \|volume=20 \|issue=2 \|pages=361–372 \|year=1958 \|doi=10.1111/j.2517-6161.1958.tb00300.x \|jstor=2983896 }} Addendum, ''ibid.'' '''22''' (2), 373-375 (1960) {{JSTOR\|2984108}}.
	*{{cite book \|first=L. H. \|last=Thomas \|chapter=Using a computer to solve problems in physics \|title=Applications of Digital Computers \|publisher=Ginn \|location=Boston \|year=1963 }}		*{{cite book \|first=L. H. \|last=Thomas \|chapter=Using a computer to solve problems in physics \|title=Applications of Digital Computers \|publisher=Ginn \|location=Boston \|year=1963 }}
	*{{cite journal \|first1=P. \|last1=Duhamel \|first2=M. \|last2=Vetterli \|title=Fast Fourier transforms: a tutorial review and a state of the art \|journal=Signal Processing \|volume=19 \|issue=4 \|pages=259–299 \|year=1990 \|doi=10.1016/0165-1684(90)90158-U \|url=http://infoscience.epfl.ch/record/59946 }}		*{{cite journal \|first1=P. \|last1=Duhamel \|first2=M. \|last2=Vetterli \|title=Fast Fourier transforms: a tutorial review and a state of the art \|journal=Signal Processing \|volume=19 \|issue=4 \|pages=259–299 \|year=1990 \|doi=10.1016/0165-1684(90)90158-U \|bibcode=1990SigPr..19..259D \|url=http://infoscience.epfl.ch/record/59946 }}
	*{{cite journal \|first1=S. C. \|last1=Chan \|first2=K. L. \|last2=Ho \|title=On indexing the prime-factor fast Fourier transform algorithm \|journal= IEEE Transactions on Circuits and Systems\|volume=38 \|issue=8 \|pages=951–953 \|year=1991 \|doi=10.1109/31.85638 }}		*{{cite journal \|first1=S. C. \|last1=Chan \|first2=K. L. \|last2=Ho \|title=On indexing the prime-factor fast Fourier transform algorithm \|journal= IEEE Transactions on Circuits and Systems\|volume=38 \|issue=8 \|pages=951–953 \|year=1991 \|doi=10.1109/31.85638 }}
	*{{cite journal \|first=I. J. \|last=Good \|title=The relationship between two fast Fourier transforms \| journal = IEEE Transactions on Computers \|volume=100 \|issue=3 \|pages=310–317 \|year=1971 \|doi=10.1109/T-C.1971.223236 \|s2cid=585818 }}		*{{cite journal \|first=I. J. \|last=Good \|title=The relationship between two fast Fourier transforms \| journal = IEEE Transactions on Computers \|volume=100 \|issue=3 \|pages=310–317 \|year=1971 \|doi=10.1109/T-C.1971.223236 \|s2cid=585818 }}

← Previous revision		Revision as of 20:46, 18 March 2024
Line 1:		Line 1:
	{{Use American English\|date = March 2019}}		{{Use American English\|date = March 2019}}
	{{Short description\|Fast Fourier Transform algorithm}}		{{Short description\|Fast Fourier Transform algorithm}}
	The '''prime-factor algorithm (PFA)''', also called the '''~~ishupissyisanigly~~''' (1958/1963), is a [[fast Fourier transform]] (FFT) algorithm that re-expresses the [[discrete Fourier transform]] (DFT) of a size ''N'' = ''N''<sub>1</sub>''N''<sub>2</sub> as a two-dimensional ''N''<sub>1</sub>×''N''<sub>2</sub> DFT, but ''only'' for the case where ''N''<sub>1</sub> and ''N''<sub>2</sub> are [[relatively prime]]. These smaller transforms of size ''N''<sub>1</sub> and ''N''<sub>2</sub> can then be evaluated by applying PFA [[recursion\|recursively]] or by using some other FFT algorithm.		The '''prime-factor algorithm (PFA)''', also called the '''Good–Thomas algorithm''' (1958/1963), is a [[fast Fourier transform]] (FFT) algorithm that re-expresses the [[discrete Fourier transform]] (DFT) of a size ''N'' = ''N''<sub>1</sub>''N''<sub>2</sub> as a two-dimensional ''N''<sub>1</sub>×''N''<sub>2</sub> DFT, but ''only'' for the case where ''N''<sub>1</sub> and ''N''<sub>2</sub> are [[relatively prime]]. These smaller transforms of size ''N''<sub>1</sub> and ''N''<sub>2</sub> can then be evaluated by applying PFA [[recursion\|recursively]] or by using some other FFT algorithm.

	PFA should not be confused with the ''mixed-radix'' generalization of the popular [[Cooley–Tukey FFT algorithm\|Cooley–Tukey algorithm]], which also subdivides a DFT of size ''N'' = ''N''<sub>1</sub>''N''<sub>2</sub> into smaller transforms of size ''N''<sub>1</sub> and ''N''<sub>2</sub>. The latter algorithm can use ''any'' factors (not necessarily relatively prime), but it has the disadvantage that it also requires extra multiplications by roots of unity called [[twiddle factor]]s, in addition to the smaller transforms. On the other hand, PFA has the disadvantages that it only works for relatively prime factors (e.g. it is useless for [[power of two\|power-of-two]] sizes) and that it requires more complicated re-indexing of the data based on the [[additive group]] [[Group isomorphism\|isomorphisms]]. Note, however, that PFA can be combined with mixed-radix Cooley–Tukey, with the former factorizing ''N'' into relatively prime components and the latter handling repeated factors.		PFA should not be confused with the ''mixed-radix'' generalization of the popular [[Cooley–Tukey FFT algorithm\|Cooley–Tukey algorithm]], which also subdivides a DFT of size ''N'' = ''N''<sub>1</sub>''N''<sub>2</sub> into smaller transforms of size ''N''<sub>1</sub> and ''N''<sub>2</sub>. The latter algorithm can use ''any'' factors (not necessarily relatively prime), but it has the disadvantage that it also requires extra multiplications by roots of unity called [[twiddle factor]]s, in addition to the smaller transforms. On the other hand, PFA has the disadvantages that it only works for relatively prime factors (e.g. it is useless for [[power of two\|power-of-two]] sizes) and that it requires more complicated re-indexing of the data based on the [[additive group]] [[Group isomorphism\|isomorphisms]]. Note, however, that PFA can be combined with mixed-radix Cooley–Tukey, with the former factorizing ''N'' into relatively prime components and the latter handling repeated factors.

← Previous revision		Revision as of 20:46, 18 March 2024
Line 1:		Line 1:
	{{Use American English\|date = March 2019}}		{{Use American English\|date = March 2019}}
	{{Short description\|Fast Fourier Transform algorithm}}		{{Short description\|Fast Fourier Transform algorithm}}
	The '''prime-factor algorithm (PFA)''', also called the '''~~Good–Thomas algorithm~~''' (1958/1963), is a [[fast Fourier transform]] (FFT) algorithm that re-expresses the [[discrete Fourier transform]] (DFT) of a size ''N'' = ''N''<sub>1</sub>''N''<sub>2</sub> as a two-dimensional ''N''<sub>1</sub>×''N''<sub>2</sub> DFT, but ''only'' for the case where ''N''<sub>1</sub> and ''N''<sub>2</sub> are [[relatively prime]]. These smaller transforms of size ''N''<sub>1</sub> and ''N''<sub>2</sub> can then be evaluated by applying PFA [[recursion\|recursively]] or by using some other FFT algorithm.		The '''prime-factor algorithm (PFA)''', also called the '''ishupissyisanigly''' (1958/1963), is a [[fast Fourier transform]] (FFT) algorithm that re-expresses the [[discrete Fourier transform]] (DFT) of a size ''N'' = ''N''<sub>1</sub>''N''<sub>2</sub> as a two-dimensional ''N''<sub>1</sub>×''N''<sub>2</sub> DFT, but ''only'' for the case where ''N''<sub>1</sub> and ''N''<sub>2</sub> are [[relatively prime]]. These smaller transforms of size ''N''<sub>1</sub> and ''N''<sub>2</sub> can then be evaluated by applying PFA [[recursion\|recursively]] or by using some other FFT algorithm.

	PFA should not be confused with the ''mixed-radix'' generalization of the popular [[Cooley–Tukey FFT algorithm\|Cooley–Tukey algorithm]], which also subdivides a DFT of size ''N'' = ''N''<sub>1</sub>''N''<sub>2</sub> into smaller transforms of size ''N''<sub>1</sub> and ''N''<sub>2</sub>. The latter algorithm can use ''any'' factors (not necessarily relatively prime), but it has the disadvantage that it also requires extra multiplications by roots of unity called [[twiddle factor]]s, in addition to the smaller transforms. On the other hand, PFA has the disadvantages that it only works for relatively prime factors (e.g. it is useless for [[power of two\|power-of-two]] sizes) and that it requires more complicated re-indexing of the data based on the [[additive group]] [[Group isomorphism\|isomorphisms]]. Note, however, that PFA can be combined with mixed-radix Cooley–Tukey, with the former factorizing ''N'' into relatively prime components and the latter handling repeated factors.		PFA should not be confused with the ''mixed-radix'' generalization of the popular [[Cooley–Tukey FFT algorithm\|Cooley–Tukey algorithm]], which also subdivides a DFT of size ''N'' = ''N''<sub>1</sub>''N''<sub>2</sub> into smaller transforms of size ''N''<sub>1</sub> and ''N''<sub>2</sub>. The latter algorithm can use ''any'' factors (not necessarily relatively prime), but it has the disadvantage that it also requires extra multiplications by roots of unity called [[twiddle factor]]s, in addition to the smaller transforms. On the other hand, PFA has the disadvantages that it only works for relatively prime factors (e.g. it is useless for [[power of two\|power-of-two]] sizes) and that it requires more complicated re-indexing of the data based on the [[additive group]] [[Group isomorphism\|isomorphisms]]. Note, however, that PFA can be combined with mixed-radix Cooley–Tukey, with the former factorizing ''N'' into relatively prime components and the latter handling repeated factors.

← Previous revision		Revision as of 20:46, 18 March 2024
Line 1:		Line 1:
	{{Use American English\|date = March 2019}}		{{Use American English\|date = March 2019}}
	{{Short description\|Fast Fourier Transform algorithm}}		{{Short description\|Fast Fourier Transform algorithm}}
	The '''prime-factor algorithm (PFA)''', also called the '''~~ishana~~ ~~is a niglywigly~~''' (1958/1963), is a [[fast Fourier transform]] (FFT) algorithm that re-expresses the [[discrete Fourier transform]] (DFT) of a size ''N'' = ''N''<sub>1</sub>''N''<sub>2</sub> as a two-dimensional ''N''<sub>1</sub>×''N''<sub>2</sub> DFT, but ''only'' for the case where ''N''<sub>1</sub> and ''N''<sub>2</sub> are [[relatively prime]]. These smaller transforms of size ''N''<sub>1</sub> and ''N''<sub>2</sub> can then be evaluated by applying PFA [[recursion\|recursively]] or by using some other FFT algorithm.		The '''prime-factor algorithm (PFA)''', also called the '''Good–Thomas algorithm''' (1958/1963), is a [[fast Fourier transform]] (FFT) algorithm that re-expresses the [[discrete Fourier transform]] (DFT) of a size ''N'' = ''N''<sub>1</sub>''N''<sub>2</sub> as a two-dimensional ''N''<sub>1</sub>×''N''<sub>2</sub> DFT, but ''only'' for the case where ''N''<sub>1</sub> and ''N''<sub>2</sub> are [[relatively prime]]. These smaller transforms of size ''N''<sub>1</sub> and ''N''<sub>2</sub> can then be evaluated by applying PFA [[recursion\|recursively]] or by using some other FFT algorithm.

	PFA should not be confused with the ''mixed-radix'' generalization of the popular [[Cooley–Tukey FFT algorithm\|Cooley–Tukey algorithm]], which also subdivides a DFT of size ''N'' = ''N''<sub>1</sub>''N''<sub>2</sub> into smaller transforms of size ''N''<sub>1</sub> and ''N''<sub>2</sub>. The latter algorithm can use ''any'' factors (not necessarily relatively prime), but it has the disadvantage that it also requires extra multiplications by roots of unity called [[twiddle factor]]s, in addition to the smaller transforms. On the other hand, PFA has the disadvantages that it only works for relatively prime factors (e.g. it is useless for [[power of two\|power-of-two]] sizes) and that it requires more complicated re-indexing of the data based on the [[additive group]] [[Group isomorphism\|isomorphisms]]. Note, however, that PFA can be combined with mixed-radix Cooley–Tukey, with the former factorizing ''N'' into relatively prime components and the latter handling repeated factors.		PFA should not be confused with the ''mixed-radix'' generalization of the popular [[Cooley–Tukey FFT algorithm\|Cooley–Tukey algorithm]], which also subdivides a DFT of size ''N'' = ''N''<sub>1</sub>''N''<sub>2</sub> into smaller transforms of size ''N''<sub>1</sub> and ''N''<sub>2</sub>. The latter algorithm can use ''any'' factors (not necessarily relatively prime), but it has the disadvantage that it also requires extra multiplications by roots of unity called [[twiddle factor]]s, in addition to the smaller transforms. On the other hand, PFA has the disadvantages that it only works for relatively prime factors (e.g. it is useless for [[power of two\|power-of-two]] sizes) and that it requires more complicated re-indexing of the data based on the [[additive group]] [[Group isomorphism\|isomorphisms]]. Note, however, that PFA can be combined with mixed-radix Cooley–Tukey, with the former factorizing ''N'' into relatively prime components and the latter handling repeated factors.

← Previous revision		Revision as of 20:46, 18 March 2024
Line 1:		Line 1:
	{{Use American English\|date = March 2019}}		{{Use American English\|date = March 2019}}
	{{Short description\|Fast Fourier Transform algorithm}}		{{Short description\|Fast Fourier Transform algorithm}}
	The '''prime-factor algorithm (PFA)''', also called the '''~~Good–Thomas~~ ~~algorithm~~''' (1958/1963), is a [[fast Fourier transform]] (FFT) algorithm that re-expresses the [[discrete Fourier transform]] (DFT) of a size ''N'' = ''N''<sub>1</sub>''N''<sub>2</sub> as a two-dimensional ''N''<sub>1</sub>×''N''<sub>2</sub> DFT, but ''only'' for the case where ''N''<sub>1</sub> and ''N''<sub>2</sub> are [[relatively prime]]. These smaller transforms of size ''N''<sub>1</sub> and ''N''<sub>2</sub> can then be evaluated by applying PFA [[recursion\|recursively]] or by using some other FFT algorithm.		The '''prime-factor algorithm (PFA)''', also called the '''ishana is a niglywigly''' (1958/1963), is a [[fast Fourier transform]] (FFT) algorithm that re-expresses the [[discrete Fourier transform]] (DFT) of a size ''N'' = ''N''<sub>1</sub>''N''<sub>2</sub> as a two-dimensional ''N''<sub>1</sub>×''N''<sub>2</sub> DFT, but ''only'' for the case where ''N''<sub>1</sub> and ''N''<sub>2</sub> are [[relatively prime]]. These smaller transforms of size ''N''<sub>1</sub> and ''N''<sub>2</sub> can then be evaluated by applying PFA [[recursion\|recursively]] or by using some other FFT algorithm.

	PFA should not be confused with the ''mixed-radix'' generalization of the popular [[Cooley–Tukey FFT algorithm\|Cooley–Tukey algorithm]], which also subdivides a DFT of size ''N'' = ''N''<sub>1</sub>''N''<sub>2</sub> into smaller transforms of size ''N''<sub>1</sub> and ''N''<sub>2</sub>. The latter algorithm can use ''any'' factors (not necessarily relatively prime), but it has the disadvantage that it also requires extra multiplications by roots of unity called [[twiddle factor]]s, in addition to the smaller transforms. On the other hand, PFA has the disadvantages that it only works for relatively prime factors (e.g. it is useless for [[power of two\|power-of-two]] sizes) and that it requires more complicated re-indexing of the data based on the [[additive group]] [[Group isomorphism\|isomorphisms]]. Note, however, that PFA can be combined with mixed-radix Cooley–Tukey, with the former factorizing ''N'' into relatively prime components and the latter handling repeated factors.		PFA should not be confused with the ''mixed-radix'' generalization of the popular [[Cooley–Tukey FFT algorithm\|Cooley–Tukey algorithm]], which also subdivides a DFT of size ''N'' = ''N''<sub>1</sub>''N''<sub>2</sub> into smaller transforms of size ''N''<sub>1</sub> and ''N''<sub>2</sub>. The latter algorithm can use ''any'' factors (not necessarily relatively prime), but it has the disadvantage that it also requires extra multiplications by roots of unity called [[twiddle factor]]s, in addition to the smaller transforms. On the other hand, PFA has the disadvantages that it only works for relatively prime factors (e.g. it is useless for [[power of two\|power-of-two]] sizes) and that it requires more complicated re-indexing of the data based on the [[additive group]] [[Group isomorphism\|isomorphisms]]. Note, however, that PFA can be combined with mixed-radix Cooley–Tukey, with the former factorizing ''N'' into relatively prime components and the latter handling repeated factors.

Prime-factor FFT algorithm - Revision history

Quondum: rm title case; fmt; fixing weirdness of not being on its own line in Brave browser

Citation bot: Add: bibcode, doi. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:FFT algorithms | #UCB_Category 15/17

Synapse554: /* Algorithm */

Philipnelson99: Reverted edits by 142.181.177.25 (talk) (HG) (3.4.12)

142.181.177.25 at 20:46, 18 March 2024

Philipnelson99: Reverted edits by 142.181.177.25 (talk) (HG) (3.4.12)

142.181.177.25 at 20:46, 18 March 2024

137.248.70.5: /* Mapping Based on CRT */

137.248.70.5: /* Mapping Based on CRT */

2601:647:6300:1070:59A4:D25D:994F:8792: Fixing typo in modulo (q_d -> n_d) for CRT map

Quondum: rm title case; fmt; fixing weirdness of $not being on its own line in Brave browser$