שאלת מבחן באלגוריתמים - האוניברסיטה הפתוחה 2021 - התמרת פורייה מהירה

**הנחיות:** אסור להשתמש באלגוריתם של Strassen; הניחו שכל פעולה אריתמטית (חיבור/חיסור/כפל/חילוק/השוואה של מספרים) מתבצעת בזמן קבוע. **(א)** ברצוננו להפיק תחזית מזג-אוויר **למחרתיים**, עבור $n$ אתרים. לכל אתר $1\le k\le n$ נתונות שלוש מטריצות: $A_k$ מסדר $n\times\log n$ (מצב מזג-האוויר היום), $B_k$ מסדר $\log n\times n$ (השינוי מהיום למחר, כך ש-$C_k:=A_k\cdot B_k$ הוא מזג-האוויר מחר), ו-$D_k$ מסדר $n\times\sqrt n$ (השינוי ממחר למחרתיים, כך שמזג-האוויר במחרתיים הוא $C_k\cdot D_k$). הציגו אלגוריתם יעיל ככל האפשר לחישוב מזג-האוויר במחרתיים בכל האתרים. **(ב)** הציגו אלגוריתם לחישוב המכפלה $A\cdot E$ של שתי מטריצות $n\times n$, אם $A$ מקיימת שכל שורה בה היא הזזה מחזורית של השורה הראשונה (מטריצה **מחזורית/circulant**): אם השורה הראשונה היא $(a_0,a_1,\dots,a_{n-1})$, אזי שורה $t$ היא $(a_{n-t+1},\dots,a_n,a_0,a_1,\dots,a_{n-t})$. נדרש זמן $o(n^3)$ (רק אלגוריתם, ללא הוכחה).

רמז: בסעיף (א) שימו לב שכפל מטריצות אסוציאטיבי — האם **סדר** ביצוע המכפלות משנה את העלות כאן, בהינתן שהמימדים אינם שווים? בסעיף (ב) התבוננו במכפלה של המטריצה בעמודה בודדת ושאלו איזו פעולה מוכרת זו בדיוק.

פתרון: **(א)** נחשב לפי סדר הכפל $A_k\cdot(B_k\cdot D_k)$ (אסוציאטיביות): - $\widetilde{C}_k:=B_k\cdot D_k$: מכפלת $(\log n\times n)\cdot(n\times\sqrt n)$ בזמן $\Theta(\log n\cdot n\cdot\sqrt n)=\Theta(n^{3/2}\log n)$; התוצאה מסדר $\log n\times\sqrt n$. - $A_k\cdot\widetilde{C}_k$: מכפלת $(n\times\log n)\cdot(\log n\times\sqrt n)$ בזמן $\Theta(n\cdot\log n\cdot\sqrt n)=\Theta(n^{3/2}\log n)$. לכל אתר $\Theta(n^{3/2}\log n)$, ולכל $n$ האתרים סה"כ **$\Theta(n^{5/2}\log n)$**. (הסדר ההפוך $(A_k B_k)D_k$ היה עולה $\Theta(n^{5/2})$ לאתר, כלומר $\Theta(n^{7/2})$ סה"כ.) **(ב)** כל **עמודה** של $A\cdot E$ היא **קונבולוציה מעגלית** של השורה הראשונה $(a_0,a_{n-1},\dots,a_1)$ עם העמודה המתאימה של $E$ (שכן $A$ מחזורית). קונבולוציה מעגלית מחושבת ב-FFT: 0. חשב $\text{FFT}$ של (השורה הראשונה של) $A$. 1. לכל עמודה $i$ של $E$: חשב $\text{FFT}$ של העמודה, כפול איבר-איבר בתוצאת שלב 0, ובצע $\text{iFFT}$ — זו העמודה ה-$i$ של $A\cdot E$. 2. החזר את $A\cdot E$. **זמן ריצה:** $n$ ביצועים של FFT/iFFT, כל אחד $\Theta(n\log n)$, סה"כ $\Theta(n^2\log n)=o(n^3)$.