Aug 24, 2017 by Bennet Carstensen •

GCA Part 2 - Hybrid approximation

With the adaptive cross approximation we have a capable tool for creating low-rank approximation of arbitary matrices, thus saving memory storage and computation time [4, 5]. We are going to use this method to reduce the rank of the left factor of the

approximation of Green’s second identity $A_{t} \in \mathbb{R}^{\hat{t} \times 2K}$, $t \in \mathcal{T}_{\mathcal{I}}$ and K given like in the post mentioned before, and construct an approximation

$$A_{t} \approx L_{t}U_{t} = V_{t}P_{t}A_{t}, \qquad L_{t} \in \mathbb{R}^{\hat{t} \times k}, U_{t} \in \mathbb{R}^{k \times 2K}, P_{t} \in \mathbb{R}^{k \times \hat{t}} \text{ and } V_{t} := L_{t}(P_{t}L_{t})^{-1},$$

with $k \in \{ 1, \cdots, 2K \}$. Embedding this approximation in Green’s second identity leaves us with

$$G|_{\hat{t} \times \hat{s}} \approx A_{t} B_{ts}^{*} \approx L_{t}U_{t}B_{ts}^{*} = L_{t}(B_{ts}U_{t}^{*})^{*}.$$

In other words, we have reduced the rank of the approximation of Green’s second identity from $2K$ to $k$ [1].

Going a step further, we can avoid computing the matrx $B_{ts}$ entirely by again using algebraic interpolation [1]: for $\mathfrak{I}_{t} := V_{t}P_{t}$, the projection property yields

$$G|_{\hat{t} \times \hat{s}} \approx L_{t}(B_{ts}U_{t}^{*})^{*} = \mathfrak{I}_{t}L_{t}(B_{ts}U_{t}^{*})^{*} = \mathfrak{I}_{t} G|_{\hat{t} \times \hat{s}}$$

With this approach, we can provide the matrices $L_{t}, P_{t} \text{ and } P_{t}L_{t} \in \mathbb{R}^{l \times l}$ during a setup phase. Since those matrices rely exlusivly on $A_{t}$ which in turn solely relies on the cluster $t$, this phase needs a rather small amount of the global computation time.

After preparing the matrices, we approximate $G|_{\hat{t} \times \hat{s}}$ by computing the pivot rows $P_{t}G|_{\hat{t} \times \hat{s}}$ and estimating a $\tilde{B}_{ts}$ through solving the linear system

$$(P_{t}L_{t})\tilde{B}_{ts}^{*} = P_{t} G|_{\hat{t} \times \hat{s}}$$

or displayed as a matrix multiplaction with

$$\tilde{B}_{ts}^{*} = (P_{t}L_{t})^{-1}P_{t}G|_{\hat{t} \times \hat{s}},$$

resulting in a low-rank approximation

$$L_{t}\tilde{B}_{ts}^{*} = L_{t}(P_{t}L_{t})^{-1}P_{t} G|_{\hat{t} \times \hat{s}} = V_{t}P_{t}G|_{\hat{t} \times \hat{s}} = \mathfrak{I}_{t}G|_{\hat{t} \times \hat{s}}.$$

To summarize, we rely alone on the left factor of the adaptive cross approximation $L_{t}$ and the corresponding row pivot indices $P_{t}$ which in turn rely exlusivly on the left factor of Green’s second identity $A_{t}$ and of course the cluster $t$. We can discarde or approximate the other factors $U_{t}$ and $B_{ts}$ accordingly, thus saving computation time during the construction of the $\mathcal{H}^2$-matrix.