\documentclass[11pt]{article} 
\usepackage[T1]{fontenc}
\usepackage{amsmath}
\usepackage{amsxtra}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{enumerate}
\usepackage{graphicx}
\usepackage{url}
\usepackage{color,hyperref}
\hypersetup{colorlinks,breaklinks,
             linkcolor=blue,urlcolor=blue,
           anchorcolor=blue,citecolor=blue}

\usepackage[margin=3cm]{geometry}

\usepackage{preamble}

\begin{document}

\section*{Math 5467 -- Homework 3}
\thispagestyle{empty}

\subsection*{Instructions:}

\begin{itemize}
\item  Complete the problems below, and submit your solutions by uploading them to your shared Google form for HW3.
\item If you use LaTeX to write up your solutions, upload them as a pdf file. Students who use LaTeX to write up their solutions will receive bonus points on the homework assignment.
\item If you choose to write your solutions and scan them, please either use a real scanner, or use a smartphone app that allows scanning with you smartphone camera. It is not acceptable to submit images of your solutions, as these can be hard to read.
\end{itemize}


\subsection*{Problems:}

\begin{enumerate}
\item (Split-Radix FFT) Assume $n\geq 4$ is a power of $2$ and let $f\in \lz$. Define $f_e \in \l(\Z_{\frac{n}{2}})$, and $f_{o,1},f_{o,2}\in \l(\Z_{\frac{n}{4}})$ by
\[f_e(k) = f(2k), \ \  f_{o,1}(k) = f(4k+1), \  \text{ and } \  f_{o,2}(k) = f(4k+3).\]
\begin{enumerate}[(i)]
\item Show that
\begin{equation}\label{eq:radixsplit}
\D_n f(\ell) = \D_{\frac{n}{2}}f_e(\ell) + e^{-2\pi i \ell/n}\D_{\frac{n}{4}} f_{o,1}(\ell) + e^{-2\pi i 3\ell/n}\D_{\frac{n}{4}} f_{o,2}(\ell).
\end{equation}
\item  The FFT algorithm based on the 3-way split in \eqref{eq:radixsplit} is called the split-radix FFT algorithm. There are a lot of redundant computations in \eqref{eq:radixsplit}, and these must be accounted for in order to realize the improved complexity of the split-radix FFT. Show that
\begin{align*}
\D_n f(\ell) &= \D_{\frac{n}{2}}f_e(\ell) + \phantom{i}(e^{-2\pi i \ell/n}\D_{\frac{n}{4}} f_{o,1}(\ell) + e^{-2\pi i 3\ell/n}\D_{\frac{n}{4}} f_{o,2}(\ell)),\\
\D_n f(\ell+\tfrac{n}{2}) &= \D_{\frac{n}{2}}f_e(\ell) - \phantom{i}(e^{-2\pi i \ell/n}\D_{\frac{n}{4}} f_{o,1}(\ell) + e^{-2\pi i 3\ell/n}\D_{\frac{n}{4}} f_{o,2}(\ell)),\\
\D_n f(\ell+\tfrac{n}{4}) &= \D_{\frac{n}{2}}f_e(\ell+\tfrac{n}{4}) - i(e^{-2\pi i \ell/n}\D_{\frac{n}{4}} f_{o,1}(\ell) - e^{-2\pi i 3\ell/n}\D_{\frac{n}{4}} f_{o,2}(\ell)),\\
\D_n f(\ell+\tfrac{3n}{4}) &= \D_{\frac{n}{2}}f_e(\ell+\tfrac{n}{4}) +i(e^{-2\pi i \ell/n}\D_{\frac{n}{4}} f_{o,1}(\ell) - e^{-2\pi i 3\ell/n}\D_{\frac{n}{4}} f_{o,2}(\ell)),
\end{align*}
for $0 \leq \ell \leq \frac{n}{4}-1$. This gives all the outputs of $\D f(\ell)$ and reduces the number of multiplications and additions required. 
\item Explain how the observations in Part (ii) allow you to compute $\D_n f$ from $\D_{\frac{n}{2}} f_e$, $\D_{\frac{n}{4}}f_{o,1}$ and $\D_{\frac{n}{4}}f_{o,2}$ using $6n$ real operations. [Note, multiplications with $\pm 1$ or $\pm i$ do not count, since they amount to negation of real or imaginary parts, which can be absorbed into the next operation by changing it from addition to subtraction or vice versa]

\item  Show that part (iii) implies that the  number of real operations taken by the split-radix FFT, denoted again as $A_n$, satisfies the recursion
\[A_n = A_{\frac{n}{2}} + 2A_{\frac{n}{4}} + 6n.\]
Explain why $A_1=0$ and $A_2=4$.  Use this to show that $A_n \leq 4n\log_2n$. [Hint: Define $B_n=A_n - 4n\log_2 n$ and show that $B_n$ satisfies   $$B_n = B_{\frac{n}{2}} + 2B_{\frac{n}{4}}$$ with $B_1=0$ and $B_2=-4$.  Use this to argue that $B_n\leq 0$ for all power-of-two $n$.] [Note: If one is more careful about redundant computations (there are additional multiplications with $\pm 1$ or $\pm i$ that can be skipped), then the complexity of the split-radix FFT algorithm is actually $4n\log_2n - 6n + 8$ real operations].
\end{enumerate}

\item Discrete derivatives (difference quotients) can be interpreted as convolutions. Complete the following exercises. 
\begin{enumerate}[(i)]
\item For $f\in \lz$ define the backward difference 
\[\nabla^- f(k) = f(k) - f(k-1).\]
Find $g\in \lz$ so that $\nabla^- f = g*f$ and use the DFT convolution property $\D (g*f) = \D g \D f$ to show that $\D (\nabla^{-}f)(k) = (1-\omega^{-k})\D f(k)$, where $\omega = e^{2\pi i /n}$.
\item For $f\in \lz$ define the forward difference 
\[\nabla^+ f(k) = f(k+1) - f(k).\]
Find $g\in \lz$ so that $\nabla^+ f = g*f$ use this to show that $\D (\nabla^{+}f)(k) = (\omega^k - 1)\D f(k)$.
\item For $f\in \lz$ define the centered difference by
\[\nabla f(k) = \frac{1}{2}(\nabla^- f(k) + \nabla^+ f(k)) = \frac{1}{2}(f(k+1) - f(k-1)).\]
Use parts (i) and (ii) to show that 
\[\D (\nabla f)(k) = \frac{1}{2}(\omega^k - \omega^{-k})\D f(k) =i\sin(2\pi k/n)\D f(k).\]
\item For $f \in \lz$, define the discrete Laplacian as
\[\Delta f(k) = \nabla^+\nabla^-f(k) = f(k+1) - 2f(k) + f(k-1).\]
Use parts (i) and (ii) to show that 
\[\D (\Delta f)(k) = (\omega^k +\omega^{-k} - 2)\D f(k) =2(\cos(2\pi k /n)-1)\D f(k).\qedhere\]
\end{enumerate}
\item Consider the Poisson equation
\begin{equation}\label{eq:poisson}
\Delta u = f \ \ \text{ on } \ \Z_n.
\end{equation}
The source term $f\in \lz$ is given, and $u\in \lz$ is the unknown we wish to solve for. The discrete Laplacian $\Delta$ is defined in Problem 2. Use the DFT and the results from Problem 2 to derive a solution formula for $u$ using one forward transform $\D$ and one inverse transform $\D^{-1}$. Is there a condition you need to place on $\D f$ for your solution formula to make sense? [Hint: Take the DFT of both sides of \eqref{eq:poisson}, solve for $\D u$, and then apply the inverse DFT $\D^{-1}$. Be careful not to divide by zero when you solve for $\D u$.]
\item Let $n\geq 1$ be odd. Show that for $t\not\in \Z$ we have
\[\frac{1}{n}\sum_{k=-\frac{n-1}{2}}^{\frac{n-1}{2}} e^{2\pi i kt} = \frac{\sinc(nt)}{\sinc(t)}.\]
What happens when $t\in \Z$? Here, $\sinc$ is the normalized sinc function $\sinc(t) = \frac{\sin(\pi t)}{\pi t}$.
\end{enumerate}
\end{document}

