Rank of Off-diagonal blocks of Laplacian Kernel in 3D
We consider a cube domain in 3D, then a hierarchical subdivision performed using a oct tree of level L. Then, for any level \(l\) where \(0<l\leq L\), we have four different types of interactions, viz.,
- Well-separated interactions
- Vertex-sharing interactions
- Edge-sharing interactions
- Face-sharing interactions
Theorem
Let \(\{q_j\}_{j=1}^N\) be \(N\) uniformly located charges at \(\{z_j\}_{j=1}^N\) inside a box \(B_1\) of side length \(l\). Let \(Q = \sum_{i=1}^N |q_i|\). The potential due to these \(N\) charges at \(M\) locations \(\{w_i\}_{i=1}^M\), with \(M \geq N\), inside another box \(B_2\) is given by \(\phi_i = \sum_{j=1}^N \frac{q_j}{|w_j-z_j|}\). In matrix-vector parlance, we have $$\vec{\phi}=A\vec{q}$$ where \(\vec{q} \in \mathbb{R}^{N \times 1}\), \(\vec{\phi} \in \mathbb{R}^{M \times 1}\) and \(A \in \mathbb{R}^{M \times N}\) with \(A_{ij} = \frac{1}{|w_j-z_j|}\). Then we claim that for a hierarchical subdivision using an oct tree, given \(\epsilon > 0\), there exists a matrix \(\tilde{A} \in \mathbb{R}^{M \times N}\) with rank of \(\tilde{A}\) at most \(\tau\), where \(\tau \in \mathcal{O} (R(N)\log^2_8(\frac{S(N)Q}{l\epsilon}))\) that approximates \(\phi_i\) such that \(|\phi_i-\{\tilde{A}q\}_i| < \epsilon\), where
- \(R(N) = 1,S(N)=1\) if the boxes \(B_1\) and \(B_2\) are at least one box away, i.e., \(\text{dist}(B_1,B_2) \geq l\).
- \(R(N) = \log(N),S(N)=\sqrt[3]{N}\) if the boxes \(B_1\) and \(B_2\) are vertex sharing neighbors.
- \(R(N) = \sqrt[3]{N}, S(N)=\sqrt[3]{N^2}\) if the boxes \(B_1\) and \(B_2\) are edge sharing neighbors.
- \(R(N) = \sqrt[3]{N^2}, S(N)=N\) if the boxes \(B_1\) and \(B_2\) are face sharing neighbors.
In this page, we would like to show in an interactive way of how the cube considered is subdivided. Following that the construction of a sphere that ensures for \(\epsilon\) we have a rank \(\tau\) approximation. For detailed proof and steps, please refer the article.