--- abstract: 'Although some preconditioners are available for solving dense linear systems, there are still many matrices for which preconditioners are lacking, in particular in cases where the size of the matrix $N$ becomes very large. Examples of preconditioners include ILU preconditioners that sparsify the matrix based on some threshold, algebraic multigrid, and specialized preconditioners, e.g., Calderón and other analytical approximation methods when available. Despite these methods, there remains a great need to develop general purpose preconditioners whose cost scales well with the matrix size $N$. In this paper, we propose a preconditioner, with broad applicability and with cost ${\mathcal{O}}(N)$, for dense matrices, when the matrix is given by a smooth kernel. Extending the method using the same framework to general ${\mathcal{H}}^2$-matrices (i.e., algebraic instead of defined in terms of an analytical kernel) is relatively straightforward, but this won't be discussed here. These preconditioners have a controlled accuracy (e.g., machine accuracy can be achieved if needed) and scale linearly with $N$. They are based on an approximate direct solve of the system. The linear scaling of the algorithm is achieved by means of two key ideas. First, the ${\mathcal{H}}^2$-structure of the dense matrix is exploited to obtain an extended sparse system of equations. Second, fill-ins arising when performing the elimination of the latter are compressed as low-rank matrices if they correspond to well-separated interactions. This ensures that the sparsity pattern of the extended sparse matrix is preserved throughout the elimination, hence resulting in a very efficient algorithm with ${\mathcal{O}}(N \log(1/\varepsilon)^2 )$ computational cost and ${\mathcal{O}}(N \log 1/\varepsilon )$ memory requirement, for an error tolerance $0 < \varepsilon < 1$. The solver is inexact, although the error can be controlled and made as small as needed. These solvers are related to ILU in the sense that the fill-in is controlled. However, in ILU, most of the fill-in (i.e., below a certain tolerance) is simply discarded, whereas here it is approximated using low-rank blocks, with a prescribed tolerance. Numerical examples are discussed to demonstrate the linear scaling of the method and to illustrate its effectiveness as a preconditioner.' author: - Pieter Coulier - Hadi Pouransari - Eric Darve bibliography: - 'abbreviations.bib' - 'references.bib' title: 'The inverse fast multipole method: using a fast approximate direct solver as a preconditioner for dense linear systems' --- Fast direct solver, preconditioner, ${\mathcal{H}}^2$-matrices, extended sparsification, low-rank compression. 65F05, 65F08, 65Y20. Introduction ============ Large linear systems of equations $\mathbf{A}\mathbf{x} = \mathbf{b}$ involving dense matrices $\mathbf{A}$ arise in a variety of applications in science and engineering (e.g., in boundary element methods @bonn95a [@hsia06a], Kalman filtering @kalmij63a, radial basis function interpolation @buhm03a [@gume07a], etc.). Storing a dense matrix entrywise requires a quadratic amount of memory ${\mathcal{O}}(N^2)$ (where $N$ indicates the matrix size), while solving the corresponding system of equations with a direct solver involves ${\mathcal{O}}(N^3)$ flops. In order to alleviate these stringent requirements, fast methods have been developed in the past decades, including the fast multipole method (FMM) @darv00a [@gree87a; @nish02a; @rokh85a; @ying04a], the panel clustering technique @hack89a [@saut98a], and methods based on hierarchical matrices @bebe08a [@borm03a; @hack00a; @hack02a; @hack00b]. These methods rely on the observation that many dense matrices can be represented in a hierarchical format, i.e., the original matrix can be subdivided into a hierarchy of smaller block matrices and most of these blocks are replaceable by low-rank approximations. Several categories of hierarchical matrix representations can be distinguished. In the simplest case, all off-diagonal blocks are assumed to be low-rank, which is referred to as a weak admissibility criterion @hack04a. If the matrix entries can be interpreted as interactions between points in a physical domain, this criterion implies that all the interactions of a certain cluster of points with any other cluster (except itself) are low-rank. This assumption leads to hierarchically off-diagonal low-rank (HODLR) matrices @amin14a and hierarchically semi-separable (HSS) matrices @chan06a [@shen07b]. In the latter, a nested approach is used (i.e., the low-rank basis at a certain hierarchical level is constructed using the low-rank basis at the child level), while this is not the case in the former. If a more general strong admissibility criterion is adopted, ${\mathcal{H}}$- and ${\mathcal{H}}^2$-matrices are obtained for the non-nested and nested cases, respectively @bebe08a [@borm03a][^1]. In these matrices, only interactions between non-neighboring clusters of points are assumed to be low-rank. The FMM can be considered as a subcategory of ${\mathcal{H}}^2$-matrices @bebe08a. The reader is referred to @bebe08a [@borm03a] for a detailed overview of the various hierarchical structures. See also for additional discussion of this classification. The use of the aforementioned hierarchical matrix representations facilitates matrix-vector multiplications, hence paving the way for iterative solvers such as Krylov subspace methods for solving the linear system $\mathbf{A}\mathbf{x} = \mathbf{b}$ @saad81a. The precarious convergence behavior — and thus the number of iterations — is a major disadvantage of iterative solvers. This necessitates the incorporation of a preconditioning strategy to improve the latter, which is often a difficult and case-dependent problem. Typical preconditioners for dense matrices include the incomplete LU factorization (with thresholding) @lee03a, methods based on the sparse approximate inverse @carp04a, geometric and algebraic multigrid methods @lang05a [@trot00a], as well as analytical preconditioning techniques such as Calderón preconditioners @chri02a [@darb13a]. Although these techniques are usually well suited for the specific problem they have been designed for, their performance as robust and efficient black-box preconditioners for general problems remains rather limited. Another disadvantage of iterative solvers is that they do not lead to a factorization of $\mathbf{A}$ that can easily be re-used, implying that the algorithm needs to be restarted if the right hand side $\mathbf{b}$ of the system is modified. Direct solvers, on the other hand, are known to be more robust and are able to cope with multiple right hand sides, but at a high computational cost. Significant progress has been made in recent years regarding the development of fast direct solvers for hierarchical matrices, especially for the aforementioned category of HODLR and HSS matrices. For example, direct ${\mathcal{O}}(N)$ algorithms for HSS matrices have been presented by, among others, Martinsson and Rokhlin @mart05b, Chandrasekaran et al. @chan06a, Xia et al. @xia10a [@xia10b], and Gillman et al. @gill14a, while fast solvers for HODLR matrices can be found in @amin14a [@kong11a]. These methods can be applied as high accuracy direct solvers but are often more effective if employed as preconditioners in an iterative solver. The framework used for HODLR and HSS matrices is appropriate for one-dimensional (1D) applications. For higher dimensional problems (2D or 3D), the assumption that all off-diagonal blocks are low-rank does not hold in that case, that is the rank typically grows with $N$. For 2D problems (points distributed on a 2D manifold or 2D plane), the rank grows like ${\mathcal{O}}(\sqrt{N})$ @ambi13b, hence jeopardizing the computational efficiency of the algorithms. It is worth noting that the approach presented in @mart05b has recently been extended by Corona et al. @coro15a to obtain a direct solver for HSS matrices that scales even for 2D problems as ${\mathcal{O}}(N)$. This improvement in complexity is achieved by introducing an additional level of compression, which also results in an improved memory efficiency of the algorithm. Extensions of the method towards surfaces in 3D are currently underway @coro15a. Another recent development towards fast direct solvers is the hierarchical interpolative factorization recently introduced by Ho and Ying @ho15b [@ho15a], which combines ideas from @coro15a and @ho12a. In order to obtain a direct solver with a linear complexity ${\mathcal{O}}(N)$ for general 2D and 3D problems, the most general framework of ${\mathcal{H}}$- and ${\mathcal{H}}^2$-matrices seems to be very well suited as well. In this paper, the inverse fast multipole method (IFMM) is presented as a fast direct solver for dense ${\mathcal{H}}^2$-matrices, where "direct" refers to the use of an approximate LU factorization @ambi14a. We focus on matrices given by a smooth kernel. The solver is inexact, although the error can be controlled and made as small as needed. A low accuracy solver is hence applicable as a robust and efficient preconditioner for iterative schemes. The IFMM relies on two key ideas. First, the dense ${\mathcal{H}}^2$-matrix is converted to an extended sparse matrix through the introduction of auxiliary variables. Second, fill-ins[^2] arising during the elimination[^3] of the latter are compressed as low-rank matrices if they correspond to well-separated (i.e., non-neighboring) interactions. As a result, the sparsity of the extended sparse matrix is maintained throughout the elimination. Specifically, there is an upper bound in ${\mathcal{O}}(N)$ on the number of non-zero entries, at all steps during the elimination. This results in a very efficient algorithm with linear complexity. To the authors' knowledge, this is the first direct solver that achieves this complexity for the most general category of hierarchical matrices @ambi14a. This paper only considers dense matrices, but similar ideas can be employed to develop a fast hierarchical solver with linear complexity for sparse matrices. Such a solver is described in a companion paper @pour15b. The proposed strategy shows similarities to multigrid methods as it uses a hierarchical decomposition of the domain, as well as to the incomplete LU (ILU) factorization and its variants as the sparsity pattern is preserved. Contrary to ILU, the sparsity is maintained using low-rank compression instead of thresholding. The outline of this paper is as follows. introduces the IFMM and focuses on the key ideas required to achieve linear complexity; special attention is paid to a graph representation of the method. Numerical examples are subsequently discussed in to illustrate the computational efficiency of the methodology, both as a direct solver and as a preconditioner in an iterative scheme. The applicability of the method to a Stokes flow problem is finally demonstrated in , while summarizing conclusions are drawn in . In , we included a discussion of theoretical connections between the method discussed in this paper and the algorithms developed by Hackbusch et al. @bebe08a [@borm03a; @hack00a; @hack02a; @hack00b]. The inverse fast multipole method: key ideas and algorithm {#sec:IFMM} ========================================================== Extended sparsification {#subsec:extended_sparsification} ----------------------- It is the aim to obtain a fast solver for the dense linear system $\mathbf{A} \mathbf{x} = \mathbf{b}$, where $\mathbf{A}$ is an ${\mathcal{H}}^{2}$-matrix, i.e., a matrix constructed based on strong admissibility criteria (well-separated clusters are assumed to be low-rank only), and with a nested basis for the low-rank representations. The first step in obtaining such a solver is to exploit the ${\mathcal{H}}^{2}$-structure of the matrix in order to convert the original dense system into an extended sparse system, as solving the latter is more efficient from a computational point of view. The sparsification procedure is based on recursively decomposing a dense matrix into a sparse matrix (representing the "near field" interactions) and a low-rank approximation (representing the "far field" interactions), combined with the introduction of auxiliary variables. This is done in a multilevel fashion. Similar ideas have been considered for HSS matrices in @chan07a [@ho12a]. The sparsification concept is illustrated in the following paragraphs for a one-dimensional (1D) example, shown in . A 1D domain $\Omega$ is hierarchically subdivided into clusters $\Omega_{i}^{(l)}$ (with super- and subscripts $^{(l)}$ and $_{i}$ referring to the hierarchical level and the cluster index at that level, respectively) until the leaf level $l=L$ is reached (with $L=3$ in ). Blocks in the matrix $\mathbf{A}$ corresponding to interactions between well-separated clusters $\Omega_{i}^{(l)}$ and $\Omega_{j}^{(l)}$ are replaced by low-rank approximations of rank $r$, i.e., $\mathbf{A}^{(l)}_{ij} \simeq \mathbf{U}^{(l)}_{i} \mathbf{K}^{(l)}_{ij} \mathbf{V}^{(l)^{\mathrm{T}}}_{j}$ (see (b)). For the example of , the resulting matrix structure is shown in (a). Note that the nested structure of the ${\mathcal{H}}^{2}$-matrix is not shown in this figure. For readers familiar with the FMM, the matrices $\mathbf{U}^{(l)}_{i}$, $\mathbf{K}^{(l)}_{ij}$, and $\mathbf{V}^{(l)^{\mathrm{T}}}_{j}$ can be identified as `L2P`- (or `L2L`-), `M2L`-, and `P2M`- (or `M2M`-) operators, respectively. The dense matrix $\mathbf{A}$ can consequently be decomposed at the leaf level as follows: $$\begin{aligned} \mathbf{A} = \mathbf{S}^{(3)} + \mathbf{U}^{(3)} \mathbf{K}^{(3)}\mathbf{V}^{(3)^\mathrm{T}} \label{eq:A_decomp_l3} \end{aligned}$$ The matrix $\mathbf{S}^{(3)}$ in is a sparse matrix containing the interactions of leaf clusters with their neighbors (including the self-interactions). The full rank matrix blocks can be denoted as `P2P`-operators if the FMM terminology is employed. In 1D, $\mathbf{S}^{(3)}$ is a tri-diagonal matrix. However, for general point distributions, this matrix is a general sparse matrix, with no "particular" structure. The matrix $\mathbf{U}^{(3)} \mathbf{K}^{(3)}\mathbf{V}^{(3)^\mathrm{T}}$ represents the dense fill-ins arising from far field interactions. The decomposition presented in is pictorially depicted in for a 1D example and in for a 2D example. ![Quadtree decomposition of the matrix. This figure is showing the decomposition at level 3 for a 2D test case. This shows how the sketch in is generalized in dimensions higher than 1.<span data-label="fig:decomp_2D_l3"></span>](2D_quadtree_decomposition_level_3){width="\textwidth"} The matrix $\mathbf{K}^{(3)}$ in is representative for all far field interactions. It is still rather dense and is therefore further decomposed using a similar decomposition as for $\mathbf{A}$: $$\begin{aligned} \mathbf{A} = \mathbf{S}^{(3)} + \mathbf{U}^{(3)} \left( \mathbf{S}^{(2)} + \mathbf{U}^{(2)} \mathbf{K}^{(2)}\mathbf{V}^{(2)^\mathrm{T}} \right) \mathbf{V}^{(3)^\mathrm{T}} \label{eq:A_decomp_l2} \end{aligned}$$ This decomposition at level $l=2$ is illustrated in and \[fig:decomp\_2D\_l2\] for a 1D and 2D example, respectively. The sparse matrix $\mathbf{S}^{(2)}$ in represents near field interactions at level $l=2$ (that have not been accounted for through $\mathbf{S}^{(3)}$), while $\mathbf{K}^{(2)}$ represents the remaining far field interactions. As no well-separated clusters exist at level $l=1$, the matrix $\mathbf{K}^{(2)}$ can not be further decomposed. ![Quadtree decomposition at level 2 for a 2D test case. Compare with for a 1D distribution of points.<span data-label="fig:decomp_2D_l2"></span>](2D_quadtree_decomposition_level_2){width="\textwidth"} is still a dense system, but can now be converted into an extended sparse system by introducing auxiliary variables at each level that contains well-separated clusters (i.e., $l \geq 2$). More specifically, multipole coefficients $\mathbf{y}^{(l)}$ are defined as: $$\begin{aligned} \mathbf{y}^{(3)} &= \mathbf{V}^{(3)^\mathrm{T}}\mathbf{x} \label{eq:y3}\\ \mathbf{y}^{(2)} &= \mathbf{V}^{(2)^\mathrm{T}}\mathbf{y}^{(3)} \label{eq:y2} \end{aligned}$$ This allows rewriting the equation $\mathbf{A} \mathbf{x} = \mathbf{b}$ as: $$\begin{aligned} \mathbf{S}^{(3)}\mathbf{x} + \mathbf{U}^{(3)} \left( \mathbf{S}^{(2)}\mathbf{y}^{(3)} + \mathbf{U}^{(2)} \mathbf{K}^{(2)}\mathbf{y}^{(2)} \right) &= \mathbf{b} \label{eq:A_simplified} \end{aligned}$$ Furthermore, local coefficients $\mathbf{z}^{(l)}$ are identified at each level: $$\begin{aligned} \mathbf{z}^{(2)} &= \mathbf{K}^{(2)}\mathbf{y}^{(2)} \label{eq:z2}\\ \mathbf{z}^{(3)} &= \mathbf{S}^{(2)}\mathbf{y}^{(3)} + \mathbf{U}^{(2)}\mathbf{z}^{(2)} \label{eq:z3} \end{aligned}$$ The original equation $\mathbf{A} \mathbf{x} = \mathbf{b}$ thus becomes: $$\begin{aligned} \mathbf{S}^{(3)}\mathbf{x} + \mathbf{U}^{(3)} \mathbf{z}^{(3)} &= \mathbf{b} \label{eq:decomposition_compact} \end{aligned}$$ – provide an extended sparse system of equations: $$\begin{aligned} \begin{bmatrix} \mathbf{S}^{(3)} & \mathbf{U}^{(3)} & & & \\ \mathbf{V}^{(3)^\mathrm{T}} & & -\mathbf{I} & & \\ & -\mathbf{I} & \mathbf{S}^{(2)} & \mathbf{U}^{(2)} & \\ & & \mathbf{V}^{(2)^\mathrm{T}} & &-\mathbf{I} \\ & & & -\mathbf{I} & \mathbf{K}^{(2)} \end{bmatrix} \begin{Bmatrix} \mathbf{x} \\ \mathbf{z}^{(3)} \\ \mathbf{y}^{(3)} \\ \mathbf{z}^{(2)} \\ \mathbf{y}^{(2)} \end{Bmatrix} &= \begin{Bmatrix} \mathbf{b} \\ \mathbf{0} \\ \mathbf{0} \\ \mathbf{0} \\ \mathbf{0} \end{Bmatrix} \label{eq:Ax=b_extended} \end{aligned}$$ The extended sparse matrix in (indicated as $\mathbf{E}$ in the following) contains matrices from the decompositions introduced in and and exhibits a symmetric pattern in terms of fill-in, as is shown in and \[fig:extended\_matrix\_2D\]. In fact, for a symmetric matrix $\mathbf{A}$, the matrix $\mathbf{E}$ is symmetric as well. This is due to the specific ordering of the equations. The elimination and substitution processes are thus performed on this sparse system rather than on the original dense system. This sparsification procedure is a very general and powerful technique that is not restricted to 1D or 2D problems. In general, any dense ${\mathcal{H}}^{2}$-matrix can be recursively decomposed into sparse matrices and low-rank approximations to obtain an extended sparsified matrix. ![Extended sparse matrix for a 2D distribution of points. Compare with the sketch shown in for a 1D distribution of points.<span data-label="fig:extended_matrix_2D"></span>](2D_quadtree_decomposition_extended_matrix){width="50.00000%"} In order to further illustrate the sparsification procedure, it is instructive to consider graph representations of the linear systems under concern. This will be particularly helpful for the interpretation of the second key step of the algorithm, as will be elucidated in . Before discussing the graph of , the idea of representing a linear system as a graph is briefly recalled here by means of a small example. Consider the following generic $3 \times 3$ block system (this is not related to any of the systems discussed earlier): $$\begin{aligned} \begin{bmatrix} \mathbf{A}_{11} & \mathbf{A}_{12} & \mathbf{A}_{13} \\ \mathbf{A}_{21} & \mathbf{A}_{22} & \mathbf{A}_{23} \\ \mathbf{A}_{31} & \mathbf{A}_{32} & \mathbf{A}_{33} \end{bmatrix} \begin{Bmatrix} \mathbf{x}_{1} \\ \mathbf{x}_{2} \\ \mathbf{x}_{3} \end{Bmatrix} &= \begin{Bmatrix} \mathbf{b}_{1} \\ \mathbf{b}_{2} \\ \mathbf{b}_{3} \end{Bmatrix} \label{eq:Ax=b} \end{aligned}$$ A graph representation of , consisting of a set of vertices and edges, is depicted in (a). Each vertex in the graph is associated with a variable $\mathbf{x}_{i}$, while the set of incoming edges into that vertex defines an equation that corresponds to row $i$ of . The edges correspond to the matrix subblocks $\mathbf{A}_{ij}$ and represent the contribution of variable $\mathbf{x}_{j}$ to the equation of row $i$. The arrows indicate the direction of each edge. The effect of eliminating a variable from on the corresponding graph is illustrated in (b), highlighting how the edges are updated accordingly. It is worth noting that the columns of the matrix have a clear meaning (i.e., they correspond to the unknowns), while the meaning of the rows is less clear as they correspond to the equations (and these can easily be permuted). Correspondingly in the graph, the tail of an arrow has a clear interpretation as it is associated with an unknown, while the head is somewhat arbitrary as it corresponds to an equation (and thus a specific ordering of the equations). (a) \ (b) Coming back to the problem under concern, (a) and \[fig:initial\_graphs\](b) show the graphs of the original dense system and the extended sparse system corresponding to the 1D problem introduced in , respectively. Note that in- and outgoing edges have been combined into a single edge (with two arrows) in order to limit the number of edges in these figures. The layout of the graph is dictated by the specific ordering of equations that we have chosen in , leading to a symmetric extended sparse matrix. The same color convention as in is employed for the vertices and edges. The transformation from (a) to \[fig:initial\_graphs\](b) clearly demonstrates how one can take advantage of the ${\mathcal{H}}^{2}$-structure of the matrix to obtain a sparsified system. (b) also illustrates that the variables $\mathbf{y}^{(l)}$ at level $l$ can be considered as unknowns $\tilde{\mathbf{x}}^{(l-1)}$ at the parent level $l-1$, hence revealing the hierarchical structure of the ${\mathcal{H}}^2$-matrix (with $\tilde{\mathbf{x}}^{(L)}$ corresponding to $\mathbf{x}$). \ Compression and redirection of fill-ins {#subsec:compression} --------------------------------------- Transforming a dense ${\mathcal{H}}^{2}$-matrix into an extended sparse matrix is a crucial but insufficient step to obtain a fast solver. Indeed, feeding a matrix such as the ones depicted in and to a conventional sparse solver leads to the creation of dense fill-ins throughout the elimination phase (or, equivalently, additional edges in the graph of (b)), which is harmful for the scaling of the algorithm (see for example the thesis of Pals @pals04a). In order to preserve the initial sparsity pattern, a second key idea is therefore introduced: fill-ins corresponding to interactions between well-separated clusters are compressed into a low-rank representation and are subsequently redirected through other operators/edges. This procedure is discussed step by step in the next paragraphs, focusing on a graph representation of the methodology. To this end, the one-dimensional example introduced in is abandoned and a more general case is now considered. References to the original FMM-terminology (e.g., particles, multipoles, and locals) are omitted to stress the generality of the method. The following simplifying notations are introduced (see ): nodes in a graph corresponding to the variables $\tilde{\mathbf{x}}_{i}^{(l)}$, $\mathbf{z}_{i}^{(l)}$, and $\mathbf{y}_{i}^{(l)}$ of a cluster $\Omega_{i}^{(l)}$ are referred to as nodes $\underline{\texttt{i}}^{(l)}$, $\texttt{i}^{(l)}$, and $\overline{\texttt{i}}^{(l)}$, respectively (the position of the bar is a mnemonic corresponding to the location of the node in the tree, either below or above). The symbol $\texttt{i}^{\dagger^{(l)}}$ represents the variable $\mathbf{z}_{\mathrm{p}}^{(l-1)}$ of its parent cluster $\Omega_{\mathrm{p}}^{(l-1)}$. The latter can also be denoted as $\texttt{p}^{(l-1)}$. If no confusion is possible, the superscripts referring to the hierarchical level of a cluster will be omitted in the following for sake of readability. With this notation in place, operators such as the inter- and anterpolation[^4] matrices $\mathbf{U}_{i}$ and $\mathbf{V}^{\mathrm{T}}_{i}$ of a cluster $\Omega_{i}$ are written as $ \mathbf{U} ( \underline{\texttt{i}}, \texttt{i} )$ and $\mathbf{V}^{\mathrm{T}}(\texttt{i}, \underline{\texttt{i}} )$, respectively. \(a) shows part of a graph of an extended sparse matrix at a certain stage of the elimination phase of level $l$, i.e., after elimination of levels $L$, $L-1$, …, $l+1$. This graph shows a "generic" description of the process of removing fill-in. The nodes shown are generic nodes in the graph of the matrix. The variables $\tilde{\mathbf{x}}^{(l)}$ and $\mathbf{z}^{(l)}$ of some clusters at level $l$ have already been eliminated at this point, e.g., $\tilde{\mathbf{x}}_{h}^{(l)}$ and $\mathbf{z}_{h}^{(l)}$ of cluster $\Omega_{h}^{(l)}$ (or, equivalently, the nodes $\underline{\texttt{h}}$ and $\texttt{h}$). This has created edges in the graph between neighboring clusters, e.g., connections $\left( \overline{\texttt{h}},\underline{\texttt{i}} \right)$ and $\left( \underline{\texttt{i}},\overline{\texttt{h}} \right)$ between $\mathbf{y}_{h}^{(l)}$ and $\tilde{\mathbf{x}}_{i}^{(l)}$ (and vice versa). Additional edges such as $\left( \overline{\texttt{h}}, \overline{\texttt{h}} \right)$ (i.e., between $\mathbf{y}_{h}^{(l)}$ and itself) have been established as well. The variables $\tilde{\mathbf{x}}_{i}^{(l)}$ and $\mathbf{z}_{i}^{(l)}$ of cluster $\Omega_{i}^{(l)}$ that are to be eliminated next are highlighted in (a). Performing this elimination results in new interactions between all neighbors of $\Omega_{i}^{(l)}$ (including itself), as is illustrated in (b)[^5]. Some of these fill-ins establish direct connections between clusters that did not exist prior to this elimination step, however. For example, fill-ins $\mathbf{E}^{\prime}(\underline{\texttt{k}}, \underline{\texttt{j}})$ and $\mathbf{E}^{\prime}( \underline{\texttt{j}}, \underline{\texttt{k}} )$ between $\Omega_{j}^{(l)}$ and $\Omega_{k}^{(l)}$ arise (where $\mathbf{E}^{\prime}$ denotes a fill-in in the extended sparse matrix). As the aforementioned clusters are well-separated (i.e., their existing interactions are accounted for through the edges between $\overline{\texttt{k}}$ and $\overline{\texttt{j}}$ rather than between $\underline{\texttt{k}}$ and $\underline{\texttt{j}}$), these fill-ins are expected to be low-rank and can be approximated as follows: $$\begin{aligned} \mathbf{E}^{\prime}(\underline{\texttt{k}}, \underline{\texttt{j}}) & \simeq \mathbf{U}^{\prime}( \underline{\texttt{k}}, \texttt{k} ) \, \mathbf{K}^{\prime}( \overline{\texttt{k}}, \overline{\texttt{j}} ) \, \mathbf{V}^{\prime^{\mathrm{T}}} ( \texttt{j}, \underline{\texttt{j}} ) \label{eq:P2P_kj}\\ \mathbf{E}^{\prime}(\underline{\texttt{j}}, \underline{\texttt{k}}) & \simeq \mathbf{U}^{\prime} ( \underline{\texttt{j}}, \texttt{j} ) \, \mathbf{K}^{\prime}( \overline{\texttt{j}}, \overline{\texttt{k}} ) \, \mathbf{V}^{\prime^{\mathrm{T}}}( \texttt{k}, \underline{\texttt{k}} ) \label{eq:P2P_jk}\end{aligned}$$ It is assumed in the following that and represent partial singular value decompositions (SVD), implying that the matrices $\mathbf{U}^{\prime}$ and $\mathbf{V}^{\prime}$ are orthonormal and that $\mathbf{K}^{\prime}$ is a diagonal matrix containing the singular values. The matrices $\mathbf{K}^{\prime}( \overline{\texttt{k}}, \overline{\texttt{j}} )$ and $\mathbf{K}^{\prime}( \overline{\texttt{j}}, \overline{\texttt{k}} )$ are therefore also denoted as $\mathbf{\Sigma}^{\prime}( \overline{\texttt{k}}, \overline{\texttt{j}} )$ and $\mathbf{\Sigma}^{\prime}( \overline{\texttt{j}}, \overline{\texttt{k}} )$, respectively. The implications for the algorithm if this is not the case will be discussed in . It is also assumed that a criterion is available for determining an appropriate rank for approximations and (see for more details). These low-rank approximations for the fill-in enable the calculation of new inter- and anterpolation operators for $\Omega_{j}^{(l)}$ and $\Omega_{k}^{(l)}$, respectively. For example, a new interpolation operator $\widehat{\mathbf{U}}(\underline{\texttt{j}}, \texttt{j})$ for $\Omega_{j}^{(l)}$ is obtained by concatenating the existing scaled interpolation operator $\mathbf{U}(\underline{\texttt{j}}, \texttt{j}) \, \mathbf{\Sigma}_\mathbf{U}$ (where $\mathbf{\Sigma}_\mathbf{U}$ contains the weights associated with each column of $\mathbf{U}(\underline{\texttt{j}}, \texttt{j})$)[^6] and the scaled fill-in operator $\mathbf{U}^{\prime} ( \underline{\texttt{j}}, \texttt{j} ) \, \mathbf{\Sigma}^{\prime}( \overline{\texttt{j}}, \overline{\texttt{k}} )$ and subsequently applying a low-rank recompression (thin SVD): $$\begin{aligned} \left[\mathbf{U}(\underline{\texttt{j}}, \texttt{j}) \, \mathbf{\Sigma}_\mathbf{U} \, | \, \mathbf{U}^{\prime} ( \underline{\texttt{j}}, \texttt{j} ) \, \mathbf{\Sigma}^{\prime}( \overline{\texttt{j}}, \overline{\texttt{k}} ) \right] & \simeq \widehat{\mathbf{U}}(\underline{\texttt{j}}, \texttt{j}) \, \widehat{\mathbf{\Sigma}}_\mathbf{U} \, \mathbf{\Phi}_{j} \label{eq:U_j_recomp}\end{aligned}$$ $\mathbf{\Phi}_{j} = \left[ {\boldsymbol{\phi}}_{j} \, | \, \boldsymbol{\phi}^{\prime}_{j} \right]$ represents a fat, row orthogonal, matrix. It is important to note that the recompression in is applied to the scaled interpolation operators rather than to $\left[\mathbf{U}(\underline{\texttt{j}}, \texttt{j}) \, | \, \mathbf{U}^{\prime} ( \underline{\texttt{j}}, \texttt{j} ) \right]$, as this allows to account for the correct "weight" of each vector when obtaining a new basis.[^7] allows expressing the existing and fill-in operators $\mathbf{U}(\underline{\texttt{j}}, \texttt{j})$ and $\mathbf{U}^{\prime}(\underline{\texttt{j}}, \texttt{j})$ in terms of the new basis $\widehat{\mathbf{U}}(\underline{\texttt{j}}, \texttt{j})$: $$\begin{aligned} \mathbf{U}(\underline{\texttt{j}}, \texttt{j}) & \simeq \widehat{\mathbf{U}}(\underline{\texttt{j}}, \texttt{j}) \, \widehat{\mathbf{\Sigma}}_\mathbf{U} \, {\boldsymbol{\phi}}_{j} \, \mathbf{\Sigma}^{-1}_\mathbf{U} = \widehat{\mathbf{U}}(\underline{\texttt{j}}, \texttt{j}) \, \mathbf{r}_{j}\\ \mathbf{U}^{\prime}(\underline{\texttt{j}}, \texttt{j}) & \simeq \widehat{\mathbf{U}}(\underline{\texttt{j}}, \texttt{j}) \, \widehat{\mathbf{\Sigma}}_\mathbf{U} \, {\boldsymbol{\phi}}^{\prime}_{j} \, \mathbf{\Sigma}^{\prime}( \overline{\texttt{j}}, \overline{\texttt{k}} )^{-1} = \widehat{\mathbf{U}}(\underline{\texttt{j}}, \texttt{j}) \, \mathbf{r}^{\prime}_{j}\end{aligned}$$ The weights $\widehat{\Sigma}_\mathbf{U}$ of the new interpolation basis $\widehat{\mathbf{U}}(\underline{\texttt{j}}, \texttt{j})$ are stored, as they are needed in potential future recompressions. A new anterpolation operator $\widehat{\mathbf{V}}(\texttt{j},\underline{\texttt{j}})$ for $\Omega_{j}^{(l)}$ is obtained in a similar way: $$\begin{aligned} \left[ \mathbf{V}(\texttt{j}, \underline{\texttt{j}}) \, \mathbf{\Sigma}_\mathbf{V} \, | \, \mathbf{V}^{\prime}(\texttt{j}, \underline{\texttt{j}}) \, \mathbf{\Sigma}^{\prime}( \overline{\texttt{k}}, \overline{\texttt{j}} ) \right] & \simeq \widehat{\mathbf{V}}(\texttt{j},\underline{\texttt{j}}) \, \widehat{\mathbf{\Sigma}}_\mathbf{V} \, \mathbf{\Psi}_{j} \label{eq:V_j_recomp}\end{aligned}$$ with $\mathbf{\Psi}_{j} = \left[ \boldsymbol{\psi}_{j} \, | \, \boldsymbol{\psi}^{\prime}_{j} \right]$, such that $\mathbf{V}(\texttt{j}, \underline{\texttt{j}})$ and $\mathbf{V}^{\prime}(\texttt{j}, \underline{\texttt{j}})$ can be written as: $$\begin{aligned} \mathbf{V}(\underline{\texttt{j}}, \texttt{j}) & \simeq \widehat{\mathbf{V}}(\underline{\texttt{j}}, \texttt{j}) \, \widehat{\mathbf{\Sigma}}_\mathbf{V} \, {\boldsymbol{\psi}}_{j} \, \mathbf{\Sigma}^{-1}_\mathbf{V} = \widehat{\mathbf{V}}(\underline{\texttt{j}}, \texttt{j}) \, \mathbf{t}_{j}\\ \mathbf{V}^{\prime}(\underline{\texttt{j}}, \texttt{j}) & \simeq \widehat{\mathbf{V}}(\underline{\texttt{j}}, \texttt{j}) \, \widehat{\mathbf{\Sigma}}_\mathbf{V} \, {\boldsymbol{\psi}}^{\prime}_{j} \, \mathbf{\Sigma}^{\prime}( \overline{\texttt{k}}, \overline{\texttt{j}} )^{-1} = \widehat{\mathbf{V}}(\underline{\texttt{j}}, \texttt{j}) \, \mathbf{t}^{\prime}_{j}\label{eq:V_prime}\end{aligned}$$ The same strategy as outlined in to is applicable for obtaining new operators $\widehat{\mathbf{U}} ( \underline{\texttt{k}}, \texttt{k} )$ and $\widehat{\mathbf{V}}(\texttt{k},\underline{\texttt{k}})$ for $\Omega_{k}^{(l)}$. The crucial benefit of compressing the dense fill-ins and updating the inter- and anterpolation operators of the corresponding clusters is that the former can now be accounted for through the operators $\mathbf{K}(\overline{\texttt{k}}, \overline{\texttt{j}})$ and $\mathbf{K}(\overline{\texttt{j}}, \overline{\texttt{k}})$ between $\Omega_{j}^{(l)}$ and $\Omega_{k}^{(l)}$. For example, the fill-in $\mathbf{E}^{\prime} ( \underline{\texttt{k}}, \underline{\texttt{j}} )$ is redirected through the $\mathbf{K}(\overline{\texttt{k}}, \overline{\texttt{j}})$-operator, which becomes: $$\begin{aligned} \mathbf{K}(\overline{\texttt{k}}, \overline{\texttt{j}}) &\leftarrow \mathbf{r}_{k} \, \mathbf{K}(\overline{\texttt{k}}, \overline{\texttt{j}}) \, \mathbf{t}^{\mathrm{T}}_{j} + \mathbf{r}^{\prime}_{k} \, \mathbf{K}^{\prime}(\overline{\texttt{k}},\overline{\texttt{j}}) \, \mathbf{t}^{\prime^{\mathrm{T}}}_{j} \label{eq:K_kj_update}\end{aligned}$$ Updating the inter- and anterpolation operators also implies that all the other edges in the graph associated with $\Omega_{j}^{(l)}$ need to be adjusted. More specifically, the remaining operators $\mathbf{K}(\overline{\texttt{q}}, \overline{\texttt{j}})$ and $\mathbf{K}( \overline{\texttt{j}}, \overline{\texttt{q}})$ (with $\Omega_{q}^{(l)} \in \mathcal{N}_{j}^{(l)} \cup \mathcal{I}_{j}^{(l)} \backslash \Omega_{k}^{(l)} $) are replaced by: $$\begin{aligned} \mathbf{K}(\overline{\texttt{q}}, \overline{\texttt{j}}) &\leftarrow \mathbf{K}(\overline{\texttt{q}}, \overline{\texttt{j}}) \, \mathbf{t}^{\mathrm{T}}_{j} \label{eq:K_qj_update}\\ \mathbf{K}(\overline{\texttt{j}}, \overline{\texttt{q}}) &\leftarrow \mathbf{r}_{j} \, \mathbf{K}(\overline{\texttt{j}}, \overline{\texttt{q}}) \label{eq:K_jq_update}\end{aligned}$$ where $\mathcal{N}_{j}^{(l)}$ and $\mathcal{I}_{j}^{(l)}$ represent the neighbor list (including itself) and interaction list (i.e., well-separated clusters that are children of its parent's neighbors) of $\Omega_{j}^{(l)}$, respectively. Furthermore, the inter- and anterpolation operators of the parent cluster of $\Omega_{j}^{(l)}$ are updated as follows: $$\begin{aligned} \mathbf{U}( \overline{\texttt{j}},\texttt{j}^{\dagger} ) &\leftarrow \mathbf{r}_{j} \, \mathbf{U}( \overline{\texttt{j}},\texttt{j}^{\dagger} ) \label{eq:U_parent_j_update}\\ \mathbf{V}( \texttt{j}^{\dagger}, \overline{\texttt{j}} ) &\leftarrow \mathbf{t}_{j} \mathbf{V}( \texttt{j}^{\dagger}, \overline{\texttt{j}} ) \label{eq:V_parent_j_update}\end{aligned}$$ Similar updates as in – are required for all edges associated with the cluster $\Omega_{k}^{(l)}$. Edges that need to be updated are highlighted in yellow in (c). The technique outlined above leads to a significant reduction of the amount of fill-in and ensures that the sparsity pattern of the extended sparse matrix is preserved throughout the elimination phase. This leads to an algorithm with linear complexity ${\mathcal{O}}(N)$. This assumes that the rank remains bounded independent of the matrix size. This is expected to be the case, as only interactions between well-separated clusters are replaced by low-rank approximations. This strategy of compressing and redirecting dense fill-ins is very similar to the initial sparsification approach introduced in , as low-rank interactions are represented at the parent level. Apart from fill-ins between the $\tilde{\mathbf{x}}$-variables (e.g., between $\tilde{\mathbf{x}}_{j}^{(l)}$ and $\tilde{\mathbf{x}}_{k}^{(l)}$), fill-ins between the variables $\tilde{\mathbf{x}}^{(l)}$ and $\mathbf{y}^{(l)}$ are created as well throughout the elimination phase. If these occur between well-separated clusters (for example $\mathbf{E}^{\prime}(\overline{\texttt{h}},\underline{\texttt{j}})$, $\mathbf{E}^{\prime}(\underline{\texttt{j}}, \overline{\texttt{h}})$ and $\mathbf{E}^{\prime}( \overline{\texttt{h}},\underline{\texttt{k}})$, $\mathbf{E}^{\prime}(\underline{\texttt{k}}, \overline{\texttt{h}})$ in (b)), the fill-ins are compressed and redirected through other operators at the parent level. (a) \ (b) \ (c) Once all unknowns $\tilde{\mathbf{x}}^{(l)}$ and variables $\mathbf{z}^{(l)}$ at level $l$ have been eliminated, the next level is considered. From a conceptual point of view, variables $\mathbf{y}^{(l)}$ can be interpreted as unknowns $\tilde{\mathbf{x}}^{(l-1)}$ of the parent level $l-1$. More specifically, a set of variables $\mathbf{y}_{i}^{(l)}$ is combined to form $\tilde{\mathbf{x}}_{\mathrm{p}}^{(l-1)}$, where the clusters $\Omega_{i}^{(l)}$ are children of the parent cluster $\Omega_{\mathrm{p}}^{(l-1)}$: $$\begin{aligned} \tilde{\mathbf{x}}_{\mathrm{p}}^{(l-1)} &= \begin{Bmatrix} \cdots \, \mathbf{y}_{i}^{(l)} \, \cdots \end{Bmatrix}^{\mathrm{T}} \qquad \forall \, \Omega_{i}^{(l)} \in \mathcal{C}_{\mathrm{p}}^{(l-1)} \label{eq:y_merge}\end{aligned}$$ or, equivalently, the nodes $\overline{\texttt{i}}^{(l)}$ are joined to form $\underline{\texttt{p}}^{(l-1)}$: $$\begin{aligned} \underline{\texttt{p}}^{(l-1)} &= \bigcup_{\Omega_{i}^{(l)} \in \mathcal{C}_{\mathrm{p}}^{(l-1)}} \overline{\texttt{i}}^{(l)} \label{eq:y_merge_2}\end{aligned}$$ $\mathcal{C}_{\mathrm{p}}^{(l-1)}$ in and denotes the children list of $\Omega_{\mathrm{p}}^{(l-1)}$. This merging procedure is illustrated in . Furthermore, the corresponding operators are combined accordingly to form the inter- and anterpolation operators $\mathbf{U} ( \underline{\texttt{p}}^{(l-1)}, \texttt{p}^{(l-1)} )$ and $\mathbf{V} ( \texttt{p}^{(l-1)}, \underline{\texttt{p}}^{(l-1)} )$ of $\Omega_{\mathrm{p}}^{(l-1)}$: $$\begin{aligned} \mathbf{U} ( \underline{\texttt{p}}^{(l-1)}, \texttt{p}^{(l-1)} ) &= \begin{bmatrix} \vdots \\ \mathbf{U}(\overline{\texttt{i}}^{(l)}, {\texttt{i}^{\dagger}}^{(l)}) \\ \vdots \end{bmatrix} \qquad \forall \, \Omega_{i}^{(l)} \in \mathcal{C}_{\mathrm{p}}^{(l-1)} \label{eq:U_merge}\\ \mathbf{V} ( \texttt{p}^{(l-1)}, \underline{\texttt{p}}^{(l-1)} ) &= \begin{bmatrix} \vdots \\ \mathbf{V}({\texttt{i}^{\dagger}}^{(l)}), \overline{\texttt{i}}^{(l)}) \\ \vdots \end{bmatrix} \qquad \forall \, \Omega_{i}^{(l)} \in \mathcal{C}_{\mathrm{p}}^{(l-1)} \label{eq:V_merge}\end{aligned}$$ A similar operation is performed to merge the interactions between variables $\mathbf{y}^{(l)}$ into interactions between unknowns $\tilde{\mathbf{x}}^{(l-1)}$. For example, the interaction between $\tilde{\mathbf{x}}_{\mathrm{p}}^{(l-1)}$ and $\tilde{\mathbf{x}}_{\mathrm{q}}^{(l-1)}$ of clusters $\Omega_{\mathrm{p}}^{(l-1)}$ and $\Omega_{\mathrm{q}}^{(l-1)}$ is assembled as follows: $$\begin{aligned} \mathbf{K}( \underline{\texttt{p}}^{(l-1)}, \underline{\texttt{q}}^{(l-1)}) &= \begin{bmatrix} & \vdots & \\ \cdots & \mathbf{K}( \overline{\texttt{i}}^{(l)}, \overline{\texttt{j}}^{(l)} ) & \cdots \\ & \vdots & \end{bmatrix} \qquad \forall \, \Omega_{i}^{(l)} \in \mathcal{C}_{\mathrm{p}}^{(l-1)}, \, \forall \, \Omega_{j}^{(l)} \in \mathcal{C}_{\mathrm{q}}^{(l-1)} \label{eq:K_merge}\end{aligned}$$ The resulting graph has exactly the same structure as the initial one, except for the fact that it consists of one level less. The elimination and merging procedure are repeated consecutively for each level $l \geq 2$ until only a small dense system for $\mathbf{y}^{(2)}$ (or, equivalently, $\tilde{\mathbf{x}}^{(1)}$) remains to be solved. Once this is done, the elimination phase is terminated and all the other variables can be retrieved through substitution, marching down the graph in the reverse order. In the end, the solution $\mathbf{x}$ is obtained. (a) \ (b) The algorithm {#subsec:algorithm} ------------- Based on the key ideas introduced in and \[subsec:compression\], the general IFMM algorithm can now be presented in a formal way. In the following, it is assumed that the ${\mathcal{H}}^2$-structure of the matrix $\mathbf{A}$ is based on a three-dimensional octree decomposition, implying that every cluster $\Omega_{i}^{(l)}$ can have up to $3^3 = 27$ clusters in its neighbor list $\mathcal{N}_{i}^{(l)}$ (including itself) and up to $6^3-3^3 = 189$ clusters in its interaction list $\mathcal{I}_{i}^{(l)}$. presents the general outline of the IFMM. It consists of initializing the IFMM-operators, performing an upward pass to eliminate each level $l$ (and forming the appropriate operators of the parent level $l-1$), solving for $\mathbf{y}^{(2)} (= \tilde{\mathbf{x}}^{(1)})$ at the top level, and substituting through a downward pass to finally retrieve the solution $\mathbf{x}$. The elimination procedure at each level $l$ is detailed in . Eliminating a cluster $\Omega_{i}^{(l)}$ leads to new interactions between its neighbors $\Omega_{j}^{(l)}$ and $\Omega_{k}^{(l)}$ (with $\Omega_{j}^{(l)},\Omega_{k}^{(l)} \in \mathcal{N}_{i}^{(l)}$): $\mathbf{E}^{\prime}(\overline{\texttt{k}}, \overline{\texttt{j}} )$ and $\mathbf{E}^{\prime} (\overline{\texttt{j}}, \overline{\texttt{k}})$ if both $\Omega_{j}^{(l)}$ and $\Omega_{k}^{(l)}$ have already been eliminated, $\mathbf{E}^{\prime}( \underline{\texttt{k}}, \overline{\texttt{j}} )$ and $\mathbf{E}^{\prime}(\overline{\texttt{j}}, \underline{\texttt{k}})$ if $\Omega_{j}^{(l)}$ has been eliminated but $\Omega_{k}^{(l)}$ has not (and vice versa), and $\mathbf{E}^{\prime}(\underline{\texttt{k}}, \underline{\texttt{j}})$ and $\mathbf{E}^{\prime} (\underline{\texttt{j}}, \underline{\texttt{k}})$ if neither $\Omega_{j}^{(l)}$ nor $\Omega_{k}^{(l)}$ has been eliminated yet. If $\Omega_{j}^{(l)}$ and $\Omega_{k}^{(l)}$ are well-separated, these fill-ins are compressed into a low-rank approximation and subsequently redirected through other operators, as discussed in . This redirection procedure is described in . If this is not the case, the additional interactions are added to the existing ones. The substitution phase proceeds level per level in the reverse elimination order and allows determining $\mathbf{z}^{(l)}$ and $\tilde{\mathbf{x}}^{(l)}$ based on $\mathbf{y}^{(l)}$. If $l$ is not the leaf level, the variables $\tilde{\mathbf{x}}^{(l)}$ are nothing else than the variables $\mathbf{y}^{(l+1)}$ of the child level, cf., . At the leaf level, $\tilde{\mathbf{x}}^{(L)}$ corresponds to the desired solution $\mathbf{x}$. As the elimination phase is decoupled from the substitution phase (as in a standard direct solve), the algorithm is well suited to handle multiple right hand sides $\mathbf{b}$. The algorithm, as described in this Subsection, is for a general matrix $\mathbf{A}$; it is not specialized for the symmetric and positive definite case. It is possible to take advantage of the symmetry and positive-definiteness of a matrix to reduce the computational cost with almost a factor of two (similar to the Cholesky factorization that is almost twice as efficient as the LU factorization). This does not alter the fundamental ideas of the proposed algorithm. \[1\] Construct an octree decomposition of the domain $\Omega$ Initialize the IFMM operators at level $l$ Eliminate level $l$ *()* and update the right hand side Form the appropriate operators of the parent level $l-1$ Solve for $\mathbf{y}^{(2)} (= \tilde{\mathbf{x}}^{(1)})$ Substitute at level $l$ for $\mathbf{z}^{(l)}$ and $\tilde{\mathbf{x}}^{(l)}$ Form $\mathbf{y}^{(l+1)}$ based on $\tilde{\mathbf{x}}^{(l)}$ *()* Set $\mathbf{x} = \tilde{\mathbf{x}}^{(L)}$ \[1\] Eliminate $\underline{\texttt{i}}$ and $\texttt{i}$ of $\Omega_{i}^{(l)}$ Compute the fill-ins $\mathbf{E}^{\prime}(\overline{\texttt{k}}, \overline{\texttt{j}})$ and $\mathbf{E}^{\prime}(\overline{\texttt{j}}, \overline{\texttt{k}})$ Add the fill-ins: $\mathbf{E}(\overline{\texttt{k}}, \overline{\texttt{j}}) \leftarrow \mathbf{E}(\overline{\texttt{k}}, \overline{\texttt{j}}) + \mathbf{E}^{\prime}(\overline{\texttt{k}}, \overline{\texttt{j}})$ and $\mathbf{E}(\overline{\texttt{j}}, \overline{\texttt{k}}) \leftarrow \mathbf{E}(\overline{\texttt{j}}, \overline{\texttt{k}}) + \mathbf{E}^{\prime}(\overline{\texttt{j}}, \overline{\texttt{k}})$ Compute the fill-ins $\mathbf{E}^{\prime} ( \underline{\texttt{k}}, \overline{\texttt{j}})$ and $\mathbf{E}^{\prime} (\overline{\texttt{j}}, \underline{\texttt{k}})$ Compress $\mathbf{E}^{\prime} (\underline{\texttt{k}}, \overline{\texttt{j}}) \simeq \mathbf{U}^{\prime}(\underline{\texttt{k}}, \texttt{k}) \, \mathbf{K}^{\prime} (\overline{\texttt{k}}, \overline{\texttt{j}})$ and $\mathbf{E}^{\prime}(\overline{\texttt{j}}, \underline{\texttt{k}}) \simeq \mathbf{K}^{\prime} (\overline{\texttt{j}}, \overline{\texttt{k}}) \, \mathbf{V}^{\prime^{\mathrm{T}}}( \texttt{k}, \underline{\texttt{k}}) $ Update the edges associated with $\Omega_{k}^{(l)}$ *()* Add the fill-ins: $\mathbf{E} ( \underline{\texttt{k}}, \overline{\texttt{j}}) \leftarrow \mathbf{E} ( \underline{\texttt{k}}, \overline{\texttt{j}})+ \mathbf{E}^{\prime} ( \underline{\texttt{k}}, \overline{\texttt{j}})$ and $\mathbf{E}(\overline{\texttt{j}}, \underline{\texttt{k}}) \leftarrow \mathbf{E}(\overline{\texttt{j}}, \underline{\texttt{k}}) + \mathbf{E}^{\prime} (\overline{\texttt{j}}, \underline{\texttt{k}})$ Compute the fill-ins: $\mathbf{E}^{\prime}(\overline{\texttt{k}}, \underline{\texttt{j}})$ and $\mathbf{E}^{\prime}(\underline{\texttt{j}}, \overline{\texttt{k}})$ Compress $\mathbf{E}^{\prime}(\overline{\texttt{k}}, \underline{\texttt{j}} ) \simeq \mathbf{K}^{\prime}( \overline{\texttt{k}}, \overline{\texttt{j}}) \, \mathbf{V}^{\prime^{\mathrm{T}}}(\texttt{j},\underline{\texttt{j}}) $ and $\mathbf{E}^{\prime}(\underline{\texttt{j}}, \overline{\texttt{k}}) \simeq \mathbf{U}^{\prime}(\underline{\texttt{j}}, \texttt{j}) \, \mathbf{K}^{\prime} (\overline{\texttt{j}}, \overline{\texttt{k}})$ Update the edges associated with $\Omega_{j}^{(l)}$ *()* Add the fill-ins: $\mathbf{E}( \overline{\texttt{k}}, \underline{\texttt{j}}) \leftarrow \mathbf{E} ( \overline{\texttt{k}}, \underline{\texttt{j}})+ \mathbf{E}^{\prime} ( \overline{\texttt{k}}, \underline{\texttt{j}})$ and $\mathbf{E}(\underline{\texttt{j}}, \overline{\texttt{k}}) \leftarrow \mathbf{E}(\underline{\texttt{j}}, \overline{\texttt{k}}) + \mathbf{E}^{\prime} (\underline{\texttt{j}}, \overline{\texttt{k}})$ Compute the fill-ins $\mathbf{E}^{\prime}( \underline{\texttt{k}}, \underline{\texttt{j}})$ and $\mathbf{E}^{\prime}(\underline{\texttt{j}}, \underline{\texttt{k}})$ Compress $\mathbf{E}^{\prime}(\underline{\texttt{k}}, \underline{\texttt{j}}) \simeq \mathbf{U}^{\prime}( \underline{\texttt{k}}, \texttt{k}) \, \mathbf{K}^{\prime}( \overline{\texttt{k}}, \overline{\texttt{j}} ) \, \mathbf{V}^{\prime^{\mathrm{T}}} ( \texttt{j}, \underline{\texttt{j}} )$ and $\mathbf{E}^{\prime}(\underline{\texttt{j}}, \underline{\texttt{k}}) \simeq \mathbf{U}^{\prime} ( \underline{\texttt{j}}, \texttt{j} ) \, \mathbf{K}^{\prime}( \overline{\texttt{j}}, \overline{\texttt{k}} ) \, \mathbf{V}^{\prime^{\mathrm{T}}}( \texttt{k}, \underline{\texttt{k}})$ Update the edges associated with $\Omega_{j}^{(l)}$ *()* Update the edges associated with $\Omega_{k}^{(l)}$ *()* Add the fill-ins: $\mathbf{E}( \underline{\texttt{k}}, \underline{\texttt{j}}) \leftarrow \mathbf{E}( \underline{\texttt{k}}, \underline{\texttt{j}}) + \mathbf{E}^{\prime}( \underline{\texttt{k}}, \underline{\texttt{j}})$ and $\mathbf{E}( \underline{\texttt{j}}, \underline{\texttt{k}}) \leftarrow \mathbf{E}( \underline{\texttt{j}}, \underline{\texttt{k}}) + \mathbf{E}^{\prime}( \underline{\texttt{j}}, \underline{\texttt{k}})$ \[1\] $\mathbf{U}(\underline{\texttt{j}}, \texttt{j}) \leftarrow \widehat{\mathbf{U}}(\underline{\texttt{j}}, \texttt{j})$, $\mathbf{\Sigma}_\mathbf{U} \leftarrow \widehat{\mathbf{\Sigma}}_\mathbf{U}$ $\mathbf{V}(\texttt{j},\underline{\texttt{j}}) \leftarrow \widehat{\mathbf{V}}(\texttt{j}, \underline{\texttt{j}})$, $\mathbf{\Sigma}_\mathbf{V} \leftarrow \widehat{\mathbf{\Sigma}}_\mathbf{V}$ $\mathbf{U}( \overline{\texttt{j}},\texttt{j}^{\dagger} ) \leftarrow \mathbf{r}_{j} \, \mathbf{U}( \overline{\texttt{j}},\texttt{j}^{\dagger} )$ $\mathbf{V}( \texttt{j}^{\dagger}, \overline{\texttt{j}} ) \leftarrow \mathbf{t}_{j} \mathbf{V}( \texttt{j}^{\dagger}, \overline{\texttt{j}} )$ $\mathbf{K}(\overline{\texttt{q}}, \overline{\texttt{j}}) \leftarrow \mathbf{K}(\overline{\texttt{q}}, \overline{\texttt{j}}) \, \mathbf{t}^{\mathrm{T}}_{j}$ $\mathbf{K}(\overline{\texttt{j}}, \overline{\texttt{q}}) \leftarrow \mathbf{r}_{j} \, \mathbf{K}(\overline{\texttt{j}}, \overline{\texttt{q}})$ $\mathbf{K}(\overline{\texttt{k}}, \overline{\texttt{j}}) \leftarrow \mathbf{K}(\overline{\texttt{k}}, \overline{\texttt{j}}) \, \mathbf{t}^{\mathrm{T}}_{j} + \mathbf{K}^{\prime}(\overline{\texttt{k}},\overline{\texttt{j}}) \, \mathbf{t}^{\prime^{\mathrm{T}}}_{j}$ $\mathbf{K}(\overline{\texttt{j}}, \overline{\texttt{k}}) \leftarrow \mathbf{r}_{j} \, \mathbf{K}(\overline{\texttt{j}}, \overline{\texttt{k}}) + \mathbf{r}^{\prime}_{j} \, \mathbf{K}^{\prime}(\overline{\texttt{j}},\overline{\texttt{k}})$ $\mathbf{K}(\overline{\texttt{k}}, \overline{\texttt{j}}) \leftarrow \mathbf{r}_{k} \, \mathbf{K}(\overline{\texttt{k}}, \overline{\texttt{j}}) \, \mathbf{t}^{\mathrm{T}}_{j} + \mathbf{r}^{\prime}_{k} \, \mathbf{K}^{\prime}(\overline{\texttt{k}},\overline{\texttt{j}}) \, \mathbf{t}^{\prime^{\mathrm{T}}}_{j} $ Some important remarks {#subsec:remarks} ---------------------- Several techniques can be employed for obtaining a suitable low-rank approximation for the dense fill-ins $\mathbf{E}^{\prime}$ arising throughout the elimination phase (cf., and ). The best possible approximation of rank $k$ of a matrix (minimizing the error norm) is given by its $k^{\mathrm{th}}$ partial singular value decomposition (SVD) @golu96a. Unfortunately, the calculation of a complete SVD requires ${\mathcal{O}}\left(\min \left(m n^2, m^2 n \right)\right)$ arithmetical operations for a $(m \times n)$ matrix, making it rather unattractive from a computational point of view. The randomized SVD (rSVD) algorithm @halk11a provides a very efficient alternative for computing (approximations of) the first few singular values and vectors. This method exploits the power of randomization to identify a subspace that captures most of the action of a matrix @halk11a. It involves generating random matrices, performing matrix-matrix products, applying orthonormalizations, and computing the SVD of a much smaller matrix. Although it uses random matrices, the rSVD algorithm gives very accurate results with a high probability, provided that the singular values of the matrix decay sufficiently fast. Rather than specifying a fixed rank for the low-rank approximation of a dense fill-in, the rank can also be determined by prescribing a relative accuracy $\varepsilon$. The relative importance of a fill-in is hence evaluated by weighting its singular values (obtained, for example, with the rSVD algorithm) with respect to some reference value. In this paper, it is proposed to employ the largest singular value $\sigma_{0}(\mathbf{E})$ of the extended sparse matrix $\mathbf{E}$ for this purpose. The retained rank of a fill-in $\mathbf{E}^{\prime}$ is thus given by[^8]: $$k(\varepsilon) = \min \left\{ k \in \mathbb{N} : \sigma_{k+1}(\mathbf{E}^{\prime}) \leq \varepsilon \sigma_{0}(\mathbf{E}) \right\} \label{eq:methods_SVD_rank_spectralnorm}$$ $\sigma_{0}(\mathbf{E})$ can easily be estimated by application of the rSVD algorithm to the extended sparse matrix $\mathbf{E}$. A low-rank recompression is also required for calculating new inter- and anterpolation operators of a cluster after compression of the fill-ins (cf., and ). Once again, computing the SVD will provide the optimal recompression, but at a relatively high computational cost. Applying the rSVD algorithm will not be very efficient either in this case, as the rank of the new operators $\widehat{\mathbf{U}}(\underline{\texttt{j}}, \texttt{j})$ and $\widehat{\mathbf{V}}(\texttt{j},\underline{\texttt{j}})$ is at least as large as the rank of the original operators $\mathbf{U}(\underline{\texttt{j}}, \texttt{j})$ and $\mathbf{V}(\texttt{j},\underline{\texttt{j}})$ (as the latter consist of orthogonal columns). This recompression hence differs from the compression of the fill-ins, where only the first few singular values are (expected to be) of importance. The fully pivoted adaptive cross approximation (ACA) algorithm @bebe03a [@rjas07a][^9], followed by an SVD recompression (i.e., two skinny QR decompositions and an SVD performed on the product of the resulting triangular matrices), provides a more efficient way for performing the recompression and is therefore favored. A final remark is related to the weighting of the basis vectors when computing new inter- and anterpolation operators, as presented in and . The advantage of using rSVD and ACA+SVD is that the obtained singular values straightforwardly provide the weights for each vector in the basis. If the low-rank approximations in , , and do not correspond to singular value decompositions (e.g., when using a rank-revealing LU decomposition), the weighting needs to be chosen in a different manner. The pivots of the LU factorization could, for example, be employed for this purpose. Although this approach is less accurate than using the singular values, it can still provide a reasonable measure of the scale of each basis vector when performing the recompression. Computational cost ------------------ We will derive the computational cost in the case of a uniform tree decomposition of the matrix (as opposed to adaptive), although the proof extends to general adaptive trees. Let's assume that we have a matrix $\mathbf{A}$ in ${\mathcal{H}}^2$-format. Given a tolerance $\varepsilon$, we assume that there is an upper bound $r$ on the rank of all compressed blocks such that $r \in {\mathcal{O}}(\log 1/\varepsilon)$. One can prove that for the original matrix $\mathbf{A}$, in the case of smooth kernels (e.g., Green's functions), the rank $r$ of the compressed blocks does satisfy this property @fong09a. However, in our case, as we proceed through the LU factorization, recompression is required. We have not proved that the rank does not increase in an unbounded fashion (for a fixed $\varepsilon$, as $N$ varies) as a result of this process. However, we did observe experimentally that the rank is in fact bounded. See in particular . Under these assumptions, the cost of operating on a node at a given level is ${\mathcal{O}}(r^3)$. The cost of a leaf node elimination is ${\mathcal{O}}( N_0^3 )$, where $N_0$ is an upper bound on the size of all leaf clusters. Choose $N_0 \in \Omega(r)$. This requirement sets the number of levels in the tree, and the number of leaf nodes. In that case, the cost of the elimination of all leaf nodes is ${\mathcal{O}}( N r^2 )$. The cost of compression of the far-away fill-in blocks, and computation of the updated parent-level matrix blocks is also ${\mathcal{O}}( N r^2 )$. Since at the next level, the number of clusters is divided at least by a fixed factor (e.g., 2 for a binary tree or 8 for an octree), the total computational cost of the method is ${\mathcal{O}}( N r^2 )$ or ${\mathcal{O}}( N \log(1/\varepsilon)^2 )$. Numerical examples {#sec:NumericalExamples} ================== The IFMM algorithm has been implemented in `C++`, using the `Eigen`-library @eigen-3 for performing dense linear algebra operations. In the following subsections, numerical examples are considered to validate the implementation and to demonstrate the efficiency of the methodology. All computations have been performed on Intel^^ Xeon^^ E5-2650 v2 (2.60 GHz) CPUs. In each of these examples, the initial low-rank approximations in the ${\mathcal{H}}^2$-matrix are created using interpolation based on Chebyshev polynomials @fong09a, followed by an additional SVD to reduce the rank. A uniform octree decomposition of the domain is employed; the number of levels is adjusted to ensure that the leaf clusters contain approximately $100$ points. This value was found to provide a reasonable trade-off between the time spent at the leaf level and the time spent at higher levels in the tree.[^10] A relative accuracy $\varepsilon = 10^{-3}$ is used, both for compressing the fill-ins (with rSVD) and for updating the inter- and anterpolation operators (with ACA). The IFMM as a direct solver {#subsec:ifmm_direct} --------------------------- Consider the linear system of equations $\mathbf{A} \mathbf{x} = \mathbf{b}$ with matrix entries $a_{ij} = K(\|\mathbf{r}_i - \mathbf{r}_j \|)$ depending on the kernel $K(r)$: $$K(r)= \begin{cases} 1 & \text{if} \quad r =0, \\ \frac{r}{d} & \text{if} \quad 0<r<d, \\ \frac{d}{r} & \text{if} \quad r \geq d. \end{cases} \label{eq:K_ij}$$ with $\mathbf{r}_i$ and $\mathbf{r}_j$ indicating 3D position vectors and $r = \|\mathbf{r}_i - \mathbf{r}_j \|$. shows the kernel function $K(r)$ for three values of the parameter $d$ in . This parameter strongly affects the condition number $\kappa(\mathbf{A})$ of the matrix $\mathbf{A}$: the larger $d$, the larger the condition number (for a fixed matrix size $N$). The condition number also increases with $N$ for a fixed value of $d$, as illustrated in . Note that the matrix entries are directly defined by the kernel, rather than by a boundary integral formulation that involves integration of the kernel. Instead of using a kernel $K(r) = 1/r$, the kernel is modified near $r=0$ according to in order to ensure that bounded matrix entries are obtained on/near the diagonal of $\mathbf{A}$. ![Kernel function $K(r)$ for three values of the parameter $d$.<span data-label="fig:kernel_benchmark_ii_semilogy_paper"></span>](kernel_benchmark_ii_semilogy_paper.eps){width="0.475\linewidth"} (a) ![Condition number $\kappa(\mathbf{A})$ as a function of the matrix size $N$, for points randomly distributed (a) on the unit sphere and (b) in the cube $\left[-1,1\right]^3$.<span data-label="fig:benchmark_ii_conditionnumber"></span>](3D_sphere_benchmark_ii_a_1e-3_conditionnumber.eps "fig:"){width="0.475\linewidth"} (b) ![Condition number $\kappa(\mathbf{A})$ as a function of the matrix size $N$, for points randomly distributed (a) on the unit sphere and (b) in the cube $\left[-1,1\right]^3$.<span data-label="fig:benchmark_ii_conditionnumber"></span>](3D_randompoints_benchmark_ii_a_1e-3_conditionnumber.eps){width="0.475\linewidth"} In the following, a known vector $\mathbf{x}$ is chosen and the matrix-vector product $\mathbf{A} \mathbf{x}$ is evaluated for obtaining $\mathbf{b}$. The IFMM is subsequently used as a direct solver, with the aforementioned vector $\mathbf{b}$ as right hand side. The retrieved solution is denoted as $\widehat{\mathbf{x}}$. In a first example, $N$ points $\mathbf{r}$ are randomly distributed on the unit sphere. The parameter $d$ is scaled according to $d =10^{-3} \, (N/1000)^{-1/2}$ in order to ensure that the condition number of $\mathbf{A}$ remains nearly constant for all $N$ (see (a)). (a) shows the total time taken by the IFMM solver as a function of the number of points $N$, with the number of Chebyshev nodes $n$ (in each dimension) varying from $1$ to $4$ (the total number of Chebyshev interpolation nodes employed for constructing the initial low-rank approximations hence equals $n^3$). These curves demonstrate that, as expected, a linear complexity ${\mathcal{O}}(N)$ is achieved. The computation time increases for larger values of $n$. The relative error $\|\mathbf{x} - \widehat{\mathbf{x}} \|_{2}/ \| \mathbf{x} \|_{2}$ for each of these cases is depicted in (b). The figure clearly shows a decrease of the error as $n$ is increased. The errors are reasonably small for all problem sizes $N$. (a) ![(a) Total CPU time and (b) the relative error $\|\mathbf{x} - \widehat{\mathbf{x}} \|_{2}/ \| \mathbf{x} \|_{2}$ as a function of the matrix size $N$, for points randomly distributed on the unit sphere.<span data-label="fig:benchmark_ii_3D_sphere"></span>](benchmark_ii_3D_sphere_paper_time_vs_N.eps "fig:"){width="0.475\linewidth"} (b) ![(a) Total CPU time and (b) the relative error $\|\mathbf{x} - \widehat{\mathbf{x}} \|_{2}/ \| \mathbf{x} \|_{2}$ as a function of the matrix size $N$, for points randomly distributed on the unit sphere.<span data-label="fig:benchmark_ii_3D_sphere"></span>](benchmark_ii_3D_sphere_scaled_paper_error_vs_N.eps){width="0.475\linewidth"} A crucial feature for achieving the linear complexity demonstrated in (a) is the fact that the rank of the matrix blocks corresponding to far field interactions remains (almost) constant if the matrix size $N$ is increased (due to the strong admissibility criterion employed for ${\mathcal{H}}^2$-matrices). This is in contrast with HODLR and HSS matrices, where the rank grows like ${\mathcal{O}}(\sqrt{N})$ for 2D problems @ambi13b. shows the maximum and average rank of the aforementioned matrix blocks as a function of $N$ for the case of $n=4$, confirming the previous statement (especially for $N > 10^{4}$). The kinks in the curve of the average rank are caused by varying the number of levels in the octree. ![Maximum (black line) and average (grey line) rank of the matrix blocks corresponding to far field interactions as a function of the matrix size $N$, for points randomly distributed on the unit sphere (with $n=4$).<span data-label="fig:benchmark_ii_3D_sphere_paper_rank_vs_N_n_4"></span>](benchmark_ii_3D_sphere_paper_rank_vs_N_n_4.eps){width="0.475\linewidth"} Next, a more general example of $N$ points $\mathbf{r}$ randomly distributed in the cube $\left[-1,1\right]^3$ is investigated. The parameter $d$ varies in this case as $d =10^{-3} \, (N/1000)^{-1/3}$ to keep the condition number of $\mathbf{A}$ nearly constant for all $N$ (see (b)). (a) confirms that a linear scaling of the computation time is also obtained in this case (although only from $N \sim 10^{4}$ upwards), while (b) demonstrates the convergence of the relative error as the number of Chebyshev nodes is increased. The computation times are slightly higher than in the case of points distributed on a sphere ((a)). This is due to the fact that a uniform octree decomposition of a sphere leads to many empty clusters, implying that most of the clusters will have less than 27 neighbors, while it is likely that almost all clusters will possess the maximum number of neighbors in case the points are randomly distributed in a cube. The reader is referred to for a detailed breakdown of the computational cost for this example. (a) ![(a) Total CPU time and (b) the relative error $\|\mathbf{x} - \widehat{\mathbf{x}} \|_{2}/ \| \mathbf{x} \|_{2}$ as a function of the matrix size $N$, for points randomly distributed in the cube $\left[-1,1\right]^3$.<span data-label="fig:benchmark_ii_3D_random"></span>](benchmark_ii_3D_random_paper_time_vs_N.eps "fig:"){width="0.475\linewidth"} (b) ![(a) Total CPU time and (b) the relative error $\|\mathbf{x} - \widehat{\mathbf{x}} \|_{2}/ \| \mathbf{x} \|_{2}$ as a function of the matrix size $N$, for points randomly distributed in the cube $\left[-1,1\right]^3$.<span data-label="fig:benchmark_ii_3D_random"></span>](benchmark_ii_3D_random_scaled_paper_error_vs_N.eps){width="0.475\linewidth"} Depending on the application of interest, the errors shown in (b) and \[fig:benchmark\_ii\_3D\_random\](b) might already be sufficiently small. The convergence of the IFMM is investigated in more detail in , which shows the relative error $\|\mathbf{x} - \widehat{\mathbf{x}} \|_{2}/ \| \mathbf{x} \|_{2}$ as a function of the number of Chebyshev nodes for a fixed matrix size $N=8 \times 10^{3}$. An increase of $n$ leads to more accurate low-rank approximations of the far field interactions and consequently a smaller overall error in $\widehat{\mathbf{x}}$. This figure demonstrates that the method is capable of serving as a highly accurate direct solver. The number of Chebyshev nodes needs to be increased significantly if 10 or more digits of accuracy are desired, however, which leads to a strong increase of the computational cost (even if the linear complexity is preserved). In most cases (depending on the number of right-hand sides), it is more efficient to apply a low accuracy IFMM solver as a preconditioner in an iterative method rather than using a highly accurate direct IFMM solver, as will be illustrated in the next subsection. ![The relative error $\|\mathbf{x} - \widehat{\mathbf{x}} \|_{2}/ \| \mathbf{x} \|_{2}$ as a function of the number of Chebyshev nodes $n$, for $N=8000$ points randomly distributed in the cube $\left[-1,1\right]^3$.<span data-label="fig:Sherlock_iFMM_paper_3D_randompoints_a_1e-3_scaled_N_8000_convergence"></span>](Sherlock_iFMM_paper_3D_randompoints_a_1e-3_scaled_N_8000_convergence.eps){width="0.475\linewidth"} The IFMM as a preconditioner in an iterative scheme {#subsec:ifmm_precon} --------------------------------------------------- In this subsection, the linear system $ \mathbf{A} \mathbf{x} = \mathbf{b}$ is solved iteratively using a non-restarted GMRES-algorithm @saad93a [@saad86a] with a tolerance $\varepsilon = 10^{-10}$ for the relative residual $\| \mathbf{b} - \mathbf{A} \widehat{\mathbf{x}} \|_{2}/ \| \mathbf{b} \|_{2}$ and a maximum of $500$ iterations. The same kernel $K(r)$ as in is used. The black-box FMM @fong09a is employed for evaluating the matrix-vector products within GMRES, while a low accuracy IFMM solver is applied as right preconditioner in each iterative step. A comparison of right and left preconditioning is provided in . The first example involves $N =10^5$ points randomly distributed in the cube $\left[-1,1\right]^3$, with $d=10^{-3}$ (in ). (a) shows the relative residual as a function of the number of GMRES-iterations for several preconditioning approaches. Without preconditioning, convergence is rather slow and a total of $78$ iterations are required to achieve convergence. The application of the IFMM as preconditioner results in a much faster convergence. Even with a rank-1 approximation of the far field interactions (i.e., $n=1$), a significant reduction of the number of iterations is obtained. An increase of the number of Chebyshev nodes leads to a more accurate preconditioner and hence a further reduction of the number of iterations; this comes at the price of a higher cost to construct the preconditioner, however. The computation times for the considered preconditioning strategies are presented in (b), where a decomposition is made into the time required to construct the preconditioner (i.e., the elimination phase in the IFMM) and the actual iteration time (i.e., the substitution phase in the IFMM, together with all GMRES-related computations). For the example under concern, the use of three Chebyshev nodes per dimension leads to the smallest overall computation time. The results are summarized in . (a) ![(a) Relative residual $\| \mathbf{b} - \mathbf{A} \widehat{\mathbf{x}} \|_{2}/ \| \mathbf{b} \|_{2}$ as a function of the iteration step and (b) total CPU time for $d=10^{-3}$.<span data-label="fig:GMRES_3D_randompoints_benchmark_ii_a_1e-3_plot"></span>](3D_randompoints_benchmark_ii_a_1e-3_newtol_N_100000_l_3_residual_vs_iteration.eps "fig:"){width="0.475\linewidth"} (b) ![(a) Relative residual $\| \mathbf{b} - \mathbf{A} \widehat{\mathbf{x}} \|_{2}/ \| \mathbf{b} \|_{2}$ as a function of the iteration step and (b) total CPU time for $d=10^{-3}$.<span data-label="fig:GMRES_3D_randompoints_benchmark_ii_a_1e-3_plot"></span>](3D_randompoints_benchmark_ii_a_1e-3_newtol_N_100000_l_3_computation_time.eps){width="0.475\linewidth"} \# iterations Total CPU time \[s\] $\| \mathbf{b} - \mathbf{A} \widehat{\mathbf{x}} \|_{2}/ \| \mathbf{b} \|_{2}$ $\|\mathbf{x} - \widehat{\mathbf{x}} \|_{2}/ \| \mathbf{x} \|_{2}$ -------------- --------------- ---------------------- --------------------------------------------------------------------------------- --------------------------------------------------------------------- No precon 78 509 $9.1 \times 10^{-11}$ $4.6 \times 10^{-10}$ IFMM ($n=1$) 19 213 $6.1 \times 10^{-11}$ $4.0 \times 10^{-11}$ IFMM ($n=2$) 6 119 $1.5 \times 10^{-11}$ $9.6 \times 10^{-12}$ IFMM ($n=3$) 3 118 $5.2 \times 10^{-11}$ $2.9 \times 10^{-11}$ IFMM ($n=4$) 2 265 $2.7 \times 10^{-11}$ $2.1 \times 10^{-11}$ : Overview of the results for various preconditioning strategies for $d=10^{-3}$.<span data-label="tbl:GMRES_3D_randompoints_benchmark_ii_a_1e-3_tbl"></span> In the second example, the parameter $d$ in is increased
{'source': 'arXiv_out/1508'}