next up previous [pdf]

Next: Numerical complexity and accuracy Up: Algorithm Previous: Butterfly structure

Fast butterfly algorithm

With the previously introduced low-rank approximations and the butterfly structure, we are ready to describe the fast algorithm. Our goal is to approximate $ \delta_t^{AB}$ , definition 21, so as to get $ u^B(\mathbf{x})$ , definition 19, by traversing the tree structure (Figure 2) from top to bottom on the $ X$ side, and from bottom to top on the $ K$ side. This can be done in five major steps. To avoid too much technical detail, we deliberately defer the complete derivation of the algorithm until the appendix, and only summarize here the final updating formulas for each step.

1. Initialization. At level $ l=0$ , let $ A$ be the root box of $ T_X$ . For each leaf box $ B\in T_K$ , construct the coefficients $ \{\delta_t^{AB}\}$ by

$\displaystyle \delta_t^{AB}=e^{-2\pi i \Phi(\mathbf{x}_0(A),\mathbf{k}_t^B)}\su...
...B(\mathbf{k}) e^{2\pi i \Phi(\mathbf{x}_0(A),\mathbf{k})}g(\mathbf{k}) \right).$ (23)

2. Recursion. At $ l=1,2,...,L/2$ , for each pair $ (A,B)$ , let $ A_p$ be $ A$ 's parent and $ \{B_c, c=1,2,3,4\}$ be $ B$ 's children from the previous level. Update $ \{\delta_t^{AB}\}$ from $ \{\delta_{t'}^{A_pB_c}\}$ by

$\displaystyle \delta_t^{AB}=e^{-2\pi i \Phi(\mathbf{x}_0(A),\mathbf{k}_t^B)}\su...
...2\pi i \Phi(\mathbf{x}_0(A),\mathbf{k}_{t'}^{B_c})}\delta_{t'}^{A_pB_c}\right).$ (24)

3. Switch. At middle level $ l=L/2$ , for each $ (A,B)$ compute the new set of coefficients $ \{\delta_t^{AB}\}$ from the old set $ \{\delta_s^{AB}\}$ by

$\displaystyle \delta^{AB}_t= \sum_s e^{2\pi i \Phi(\mathbf{x}_t^A,\mathbf{k}_s^B)}\delta_s^{AB}.$ (25)

4. Recursion. At $ l=L/2+1,...,L$ , for each pair $ (A,B)$ , update $ \{\delta_t^{AB}\}$ from $ \{\delta_{t'}^{A_pB_c}\}$ of the previous level by

$\displaystyle \delta_t^{AB}=\sum_c e^{2\pi i \Phi(\mathbf{x}_t^A,\mathbf{k}_0(B...
...pi i \Phi(\mathbf{x}_{t'}^{A_p},\mathbf{k}_0(B_c))}\delta_{t'}^{A_pB_c}\right).$ (26)

5. Termination. Finally at level $ l=L$ , $ B$ is the entire domain $ K$ . For every box $ A$ in $ X$ and every $ \mathbf{x}\in A$ , compute $ u(\mathbf {x})$ by

$\displaystyle u(\mathbf{x})=e^{2\pi i \Phi(\mathbf{x},\mathbf{k}_0(B))}\sum_t \...
...thbf{x}) e^{-2\pi i \Phi(\mathbf{x}_t^A,\mathbf{k}_0(B))} \delta_t^{AB}\right).$ (27)


next up previous [pdf]

Next: Numerical complexity and accuracy Up: Algorithm Previous: Butterfly structure

2013-07-26