The choice of norm matrix $G$

Accurate evaluation of $F$ is a rapid procedure because it only involves integration over the boundary $\Gamma$. It requires $O(NM)$ basis function evaluations, where the number of discretization points on the boundary is $M \sim k^{d-1}{\mathsf{A}}$ (see Appendix G). However the evaluation of the norm matrix $G$ at first sight seems like a tremendous bottleneck. Eq.(5.13) for $G$ involves computing $N^2$ overlaps $\left\langle \phi_i \left\vert\phi_j\right.\right\rangle _{\mathcal{D}}$ each of which is a $d$ dimensional integral over the domain. Since the $\phi{({\mathbf r})}$ are oscillatory at scale $1/k$, each integral would require $O(k^{d})$ basis function evaluations, and the construction of $G$ would scale as $k^{d+2}$. If this were performed literally, then much of the advantage of a surface method would be lost. In fact, in any implementation of the PWDM as originally described, almost all the time is spent performing normalizations over the domain, which is wasteful.

The aim of this section is to describe more rapid evaluations of $G$, both approximate and exact, which scale like the boundary. (In Section 5.5 we will see that the accuracy of $G$ needed is actually quite low).

Figure 5.5: Tension minima using single-interior-point method for calculation of $G$ (many dotted lines, each for different interior point choice), versus exact $G$ (solid line). Note that the single-interior-point minima are often indistinct, and one is missed ($k=200.390$).