خوارزمية تحويل فورييه السريع للعوامل الأولية

الموسوعة الحرة

خوارزمية التحليل إلى العوامل الأولية (PFA) ، والتي تُعرف أيضًا بخوارزمية جود-توماس (1958/1963)، هي خوارزمية تحويل فورييه سريع (FFT) تُعيد صياغة تحويل فورييه المنفصل (DFT) ذي الحجم N = N₁N₂ كتحويل فورييه منفصل ثنائي الأبعاد N₁ × N₂ ، ولكن فقط في حالة كون N₁ و N₂ أوليين فيما بينهما . ويمكن بعد ذلك حساب هذه التحويلات الأصغر ذات الحجم N₁ و N₂ بتطبيق خوارزمية PFA بشكل متكرر أو باستخدام خوارزمية FFT أخرى .

لا ينبغي الخلط بين خوارزمية PFA وتعميم خوارزمية Cooley-Tukey الشائعة ذات الأساس المختلط ، والتي تقسم بدورها تحويل فورييه المنفصل (DFT) بحجم N = N₁N₂ إلى تحويلات أصغر بحجم N₁ و N₂ . يمكن للخوارزمية الأخيرة استخدام أي عوامل (ليس بالضرورة أولية فيما بينها)، ولكن يعيبها أنها تتطلب عمليات ضرب إضافية بجذور الوحدة تُسمى عوامل التدوير ، بالإضافة إلى التحويلات الأصغر. من ناحية أخرى، تعيب خوارزمية PFA أنها تعمل فقط مع العوامل الأولية فيما بينها (أي أنها غير مجدية مع أحجام قوى العدد اثنين ) وأنها تتطلب إعادة فهرسة أكثر تعقيدًا للبيانات بناءً على تماثلات المجموعة الجمعية . مع ذلك، تجدر الإشارة إلى أنه يمكن دمج خوارزمية PFA مع خوارزمية Cooley-Tukey ذات الأساس المختلط، حيث تقوم الأولى بتحليل N إلى مكونات أولية فيما بينها، بينما تتعامل الثانية مع العوامل المتكررة.

ترتبط خوارزمية PFA ارتباطًا وثيقًا بخوارزمية Winograd FFT المتداخلة ، حيث تُجري الأخيرة تحويل N1 × N2 المُفكك باستخدام تقنيات التفاف ثنائية الأبعاد أكثر تطورًا. ولذلك، تُطلق بعض الأبحاث القديمة على خوارزمية Winograd اسم PFA FFT .

(على الرغم من أن خوارزمية PFA تختلف عن خوارزمية كولي-توكي، فقد استشهد كولي وتوكي بعمل جود عام 1958 على خوارزمية PFA كمصدر إلهام في ورقتهم البحثية عام 1965، وكان هناك في البداية بعض الالتباس حول ما إذا كانت الخوارزميتان مختلفتين. في الواقع، كان هذا العمل هو العمل الوحيد السابق في مجال تحويل فورييه السريع الذي استشهدوا به، لأنهم لم يكونوا على دراية آنذاك بالبحث السابق الذي أجراه جاوس وآخرون.)

الخوارزمية

يتركأ(x){\displaystyle a(x)}ليكن متعدد الحدود وωن{\displaystyle \omega _{n}}كن مديرًان{\displaystyle n}الجذر النوني للوحدة . نُعرّف تحويل فورييه المنفصل لـأ(x){\displaystyle a(x)}كما هو الحالن{\displaystyle n}-مترابطة بيانية(أ^ج)=(أ(ωنج)){\displaystyle ({\hat {a}}_{j})=(a(\omega _{n}^{j}))}. بعبارة أخرى، أ^ج=∑أنا=0ن-1أأناωنأناج للجميع ج=0،1،...،ن-1.{\displaystyle {\hat {a}}_{j}=\sum _{i=0}^{n-1}a_{i}\omega _{n}^{ij}\quad {\text{ for all }}j=0,1,\dots ,n-1.}

لتبسيط الأمر، نرمز إلى التحويل بـDFTωن{\displaystyle {\text{DFT}}_{\omega _{n}}}.

تعتمد طريقة PFA على تحليل العوامل الأولية المشتركة لـن=∏د=0د-1ند{\textstyle n=\prod _{d=0}^{D-1}n_{d}}وينعطفDFTωن{\displaystyle {\text{DFT}}_{\omega _{n}}}داخل⨂دDFTωند{\textstyle \bigotimes _{d}{\text{DFT}}_{\omega _{n_{d}}}}لبعض الخياراتωند{\displaystyle \omega _{n_{d}}}هذا هو المكان⨂{\textstyle \bigotimes }هو حاصل الضرب الموتري .

رسم الخرائط بناءً على نظرية الأشعة السينية

لتحليل الأعداد الأولية فيما بينهان=∏د=0د-1ند{\displaystyle \textstyle n=\prod _{d=0}^{D-1}n_{d}}لدينا خريطة البقايا الصينيةم↦(متعديلند){\displaystyle m\mapsto (m{\bmod {n}}_{d})}منZن{\displaystyle \mathbb {Z} _{n}}ل∏د=0د-1Zند{\textstyle \prod _{d=0}^{D-1}\mathbb {Z} _{n_{d}}}مع(مد)↦∑د=0د-1هـدمد{\textstyle (m_{d})\mapsto \sum _{d=0}^{D-1}e_{d}m_{d}}كمعكوسها حيثهـد{\displaystyle e_{d}}' s هي العناصر المركزية المتعامدة المتساوية القوة مع∑د=0د-1هـد=1(تعديلن){\textstyle \sum _{d=0}^{D-1}e_{d}=1{\pmod {n}}}اختيارωند=ωنهـد{\displaystyle \omega _{n_{d}}=\omega _{n}^{e_{d}}}(لذلك، ⁠∏د=0د-1ωند=ωن∑د=0د-1هـد=ωن{\displaystyle \prod _{d=0}^{D-1}\omega _{n_{d}}=\omega _{n}^{\sum _{d=0}^{D-1}e_{d}}=\omega _{n}}) ، نعيد كتابةDFTωن{\displaystyle {\text{DFT}}_{\omega _{n}}}على النحو التالي:

أ^ج=∑أنا=0ن-1أأناωنأناج=∑أنا=0ن-1أأنا(∏د=0د-1ωند)أناج=∑أنا=0ن-1أأنا∏د=0د-1ωند(أناتعديلند)(جتعديلند)=∑أنا0=0ن0-1⋯∑أناد-1=0ند-1-1أ∑د=0د-1هـدأناد∏د=0د-1ωندأناد(جتعديلند).{\displaystyle {\hat {a}}_{j}=\sum _{i=0}^{n-1}a_{i}\omega _{n}^{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}=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})}.}

وأخيرًا، حددأأنا0،...،أناد-1=أ∑د=0د-1أنادهـد{\displaystyle a_{i_{0},\dots ,i_{D-1}}=a_{\sum _{d=0}^{D-1}i_{d}e_{d}}}و​أ^ج0،...،جد-1=أ^∑د=0د-1جدهـد{\displaystyle {\hat {a}}_{j_{0},\dots ,j_{D-1}}={\hat {a}}_{\sum _{d=0}^{D-1}j_{d}e_{d}}}لدينا​

أ^ج0،...،جد-1=∑أنا0=0ن0-1⋯∑أناد-1=0ند-1-1أأنا0،...،أناد-1∏د=0د-1ωندأنادجد.{\displaystyle {\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}}.}

لذلك، لدينا تحويل فورييه المنفصل متعدد الأبعاد ،⊗د=0د-1DFTωند{\displaystyle \textstyle \otimes _{d=0}^{D-1}{\text{DFT}}_{\omega _{n_{d}}}}⁠ .

كتماثلات جبرية

يمكن صياغة PFA بطريقة عالية المستوى من حيث التشاكلات الجبرية . نتذكر أولاً أنه بالنسبة لحلقة تبديليةR{\displaystyle R}وتماثل المجموعة منجي{\displaystyle G}إلى​∏دجيد{\displaystyle \textstyle \prod _{d}G_{d}}لدينا التشاكل الجبري التالي

R[جي]≅⨂دR[جيد]،{\displaystyle R[G]\cong \bigotimes _{d}R[G_{d}],}

أين⨂{\displaystyle \bigotimes }يشير إلى حاصل الضرب الموتري للجبر .

لنرى كيف تعمل اتفاقية الحماية الشخصية، نختارجي=(Zن،+،0){\displaystyle G=(\mathbb {Z} _{n},+,0)}وجيد=(Zند،+،0){\displaystyle G_{d}=(\mathbb {Z} _{n_{d}},+,0)}نحدد أيضًا المجموعات الجمعية .R[جي]{\displaystyle R[G]}مثلR[x]⟨xن-1⟩{\textstyle {\frac {R[x]}{\langle x^{n}-1\rangle }}}وR[جيد]{\displaystyle R[G_{d}]}كما​R[xد]⟨xدند-1⟩{\displaystyle \textstyle {\frac {R[x_{d}]}{\langle x_{d}^{n_{d}}-1\rangle }}}. اختيارη=أ↦(أتعديلند){\displaystyle \eta =a\mapsto (a{\bmod {n}}_{d})}باعتبارها تماثل المجموعةجي≅∏دجيد{\displaystyle \textstyle G\cong \prod _{d}G_{d}}لدينا تماثل جبريη*:R[جي]≅⨂دR[جيد]{\textstyle \eta ^{*}:R[G]\cong \bigotimes _{d}R[G_{d}]}أو بدلاً من ذلك،

η*:R[x]⟨xن-1⟩≅⨂دR[xد]⟨xدند-1⟩.{\displaystyle \eta ^{*}:{\frac {R[x]}{\langle x^{n}-1\rangle }}\cong \bigotimes _{d}{\frac {R[x_{d}]}{\langle x_{d}^{n_{d}}-1\rangle }}.}

والآن لاحظ ذلكDFTωن{\displaystyle {\text{DFT}}_{\omega _{n}}}هو في الواقع تماثل جبري منR[x]⟨xن-1⟩{\textstyle {\frac {R[x]}{\langle x^{n}-1\rangle }}}ل∏أناR[x]⟨x-ωنأنا⟩{\textstyle \prod _{i}{\frac {R[x]}{\langle x-\omega _{n}^{i}\rangle }}}وكلDFTωند{\displaystyle {\text{DFT}}_{\omega _{n_{d}}}}هو تماثل جبري منR[x]⟨xدند-1⟩{\textstyle {\frac {R[x]}{\langle {x_{d}}^{n_{d}}-1\rangle }}}ل∏أنادR[xد]⟨xد-ωندأناد⟩{\textstyle \prod _{i_{d}}{\frac {R[x_{d}]}{\langle x_{d}-\omega _{n_{d}}^{i_{d}}\rangle }}}لدينا تماثل جبريη′{\displaystyle \eta '}من⨂د∏أنادR[xد]⟨xد-ωندأناد⟩{\textstyle \bigotimes _{d}\prod _{i_{d}}{\frac {R[x_{d}]}{\langle x_{d}-\omega _{n_{d}}^{i_{d}}\rangle }}}ل∏أناR[x]⟨x-ωنأنا⟩{\textstyle \prod _{i}{\frac {R[x]}{\langle x-\omega _{n}^{i}\rangle }}}ما تخبرنا به اتفاقية حماية الأداء هو أنDFTωن=η′∘⨂دDFTωند∘η*{\textstyle {\text{DFT}}_{\omega _{n}}=\eta '\circ \bigotimes _{d}{\text{DFT}}_{\omega _{n_{d}}}\circ \eta ^{*}}أينη*{\displaystyle \eta ^{*}}وη′{\displaystyle \eta '}إعادة الفهرسة بدون عمليات حسابية فعلية فيR{\displaystyle R}.

حساب عدد التحويلات متعددة الأبعاد

لاحظ أن شرط التحويلDFTωن{\displaystyle {\text{DFT}}_{\omega _{n}}}داخلη′∘⨂دDFTωند∘η*{\textstyle \eta '\circ \bigotimes _{d}{\text{DFT}}_{\omega _{n_{d}}}\circ \eta ^{*}}يعتمد على تماثل المجموعة الجمعية "أ"η{\displaystyle \eta }من(Zن،+،0){\displaystyle (\mathbb {Z} _{n},+,0)}إلى​∏د(Zند،+،0){\displaystyle \textstyle \prod _{d}(\mathbb {Z} _{n_{d}},+,0)}أي تماثل زمر جمعي سيفي بالغرض. لحساب عدد طرق التحويلDFTωن{\displaystyle {\text{DFT}}_{\omega _{n}}}إلى​η′∘⨂دDFTωند∘η*{\displaystyle \textstyle \eta '\circ \bigotimes _{d}{\text{DFT}}_{\omega _{n_{d}}}\circ \eta ^{*}}، كل ما نحتاجه هو حساب عدد التشاكلات الجمعية من(Zن،+،0){\displaystyle (\mathbb {Z} _{n},+,0)}ل∏د(Zند،+،0){\textstyle \prod _{d}(\mathbb {Z} _{n_{d}},+,0)}أو بديلًا عن ذلك ، عدد التشاكلات الذاتية للمجموعات الجمعية على(Zن،+،0){\displaystyle (\mathbb {Z} _{n},+,0)}منذ​(Zن،+،0){\displaystyle (\mathbb {Z} _{n},+,0)}إذا كانت دورية ، فيمكن كتابة أي تشاكل ذاتي على النحو التالي:1↦ز{\displaystyle 1\mapsto g}أينز{\displaystyle g}هو مولد لـ(Zن،+،0){\displaystyle (\mathbb {Z} _{n},+,0)}بحسب تعريف(Zن،+،0){\displaystyle (\mathbb {Z} _{n},+,0)}،​ز{\displaystyle g}'s هي بالضبط تلك الأعداد الأولية فيما بينها لـن{\displaystyle n}لذلك، يوجد بالضبطφ(ن){\displaystyle \varphi (n)}العديد من هذه الخرائط حيثφ{\displaystyle \varphi }هي دالة أويلر . وأصغر مثال عليها هون=6{\displaystyle n=6}أينφ(ن)=2{\displaystyle \varphi (n)=2}، مما يوضح الخريطتين الموجودتين في الأدبيات: "خريطة CRT" و"خريطة روريتانيا". [ 1 ]

انظر أيضاً

ملحوظات

مراجع