Unit 4.3 A new notation for presenting algorithms
We now introduce a notation, which we call the FLAME notation [5], for presenting algorithms that involve vectors that hides intricate indexing. Consider the algorithm on the left:
Compare it to the equivaluent algorithm to its right. The idea is that at the top of the loop the coefficients given by \(a_T \) have been used to partially compute \(\psi \text{.}\) Comparing to the algorithm to its right, this means that at the top of the loop
\begin{equation*}
\begin{array}{l}
\left.
\begin{array}{c}
\alpha_0 \\
\vdots \\
\alpha_{k-1}
\end{array}
\right\} a_T
\\ \hline
\left.
\begin{array}{c}
\alpha_k \\
\alpha_{k+1} \\
\vdots\\
\alpha_{n-1}
\end{array}
\right\} a_B.
\end{array}
\end{equation*}
In the current iteration, we need to compute with \(\alpha_k \) which is the top element of \(a_B \text{.}\) We expose that element by repartitioning
\begin{equation*}
\left( \begin{array}{c}
a_T \\ \hline
a_B
\end{array} \right)
\rightarrow
\left( \begin{array}{c}
a_0 \\ \hline
\alpha_1 \\
a_2
\end{array} \right).
\end{equation*}
Comparing to the algorithm to its right, this means that
\begin{equation*}
\begin{array}{l}
\left.
\begin{array}{c}
\alpha_0 \\
\vdots \\
\alpha_{k-1}
\end{array}
\right\} a_0
\\ \hline
\left.
{~~~} \alpha_{k} {~~~}
\right\} \alpha_1 \\
\left.
\begin{array}{c}
\alpha_{k+1} \\
\vdots\\
\alpha_{n-1}
\end{array}
\right\} a_2.
\end{array}
\end{equation*}
Notice that in our new notation, \(\alpha_1 \) equals the element of \(a \) wiith which we compute in this iteration. In the old notation, it is always the second element in the vector of coefficients. At the bottom of the loop, we add the top element of \(a_B\) to the bottom of \(a_T \text{:}\)
\begin{equation*}
\left( \begin{array}{c}
a_T \\ \hline
a_B
\end{array} \right)
\leftarrow
\left( \begin{array}{c}
a_0 \\
\alpha_1 \\ \hline
a_2
\end{array} \right).
\end{equation*}
In other words,
\begin{equation*}
\begin{array}{l}
\left.
\begin{array}{c}
\alpha_0 \\
\vdots \\
\alpha_{k-1} \\
\alpha_k
\end{array}
\right\} a_T
\\ \hline
\left.
\begin{array}{c}
\alpha_{k+1} \\
\vdots\\
\alpha_{n-1}
\end{array}
\right\} a_B.
\end{array}
\end{equation*}
With this, we hope the notation is relatively intuitive.
