Hierarchical low rank matrices and error propagation

Let $I$ be a nonempty finite totally ordered set, let $d\ge 1$, and assign a point ${\xi }_i\in {\mathbb{R}}^d$ to each $i\in I$. A cluster is a nonempty subset of $I$. For a cluster $\tau$, write $X_{\tau }=\{{\xi }_i:i\in \tau \}$, $\mathrm{diam}(\tau )={\max }_{i,j\in \tau }\mathrm{\parallel }{\xi }_i-{\xi }_j{\mathrm{\parallel }}_2$, and $\mathrm{dist}(\tau ,\sigma )={\min }_{i\in \tau ,j\in \sigma }\mathrm{\parallel }{\xi }_i-{\xi }_j{\mathrm{\parallel }}_2$. These extrema exist because the index sets are finite and nonempty; repeated geometric points are allowed.

A balanced cluster tree with leaf threshold $b$, where $1\le b\le \mathrm{\mid }I\mathrm{\mid }$, is the rooted binary tree whose root is $I$, whose children of an internal cluster $\tau$ are its first $\lfloor \mathrm{\mid }\tau \mathrm{\mid }\mathrm{/}2\rfloor$ and last $\lceil \mathrm{\mid }\tau \mathrm{\mid }\mathrm{/}2\rceil$ indices in the fixed order, and which stops splitting at clusters of size at most $b$. Its two children are disjoint and their union is $\tau$.

For the column side, let $J$ be a nonempty finite totally ordered set, assign points ${\zeta }_j\in {\mathbb{R}}^d$ for $j\in J$, and build its balanced cluster tree by the same rule with its own threshold $1\le b_J\le \mathrm{\mid }J\mathrm{\mid }$. Column clusters are nonempty subsets $\sigma \subseteq J$, with $X_{\sigma }=\{{\zeta }_j:j\in \sigma \}$ and $\mathrm{diam}(\sigma )={\max }_{j,j^{\mathrm{\prime }}\in \sigma }\mathrm{\parallel }{\zeta }_j-{\zeta }_{j^{\mathrm{\prime }}}{\mathrm{\parallel }}_2$. For a row cluster $\tau \subseteq I$ and a column cluster $\sigma \subseteq J$, set $\mathrm{dist}(\tau ,\sigma )={\min }_{i\in \tau ,j\in \sigma }\mathrm{\parallel }{\xi }_i-{\zeta }_j{\mathrm{\parallel }}_2$. Row and column roles distinguish the assignments even when the index sets overlap. In the square case with a common point assignment, take $J=I$ and ${\zeta }_i={\xi }_i$.

Fix an admissibility parameter $\eta >0$. A pair of clusters $(\tau ,\sigma )$ is admissible when $\mathrm{dist}(\tau ,\sigma )>0$ and $\mathrm{dist}(\tau ,\sigma )\ge \eta \max (\mathrm{diam}(\tau ),\mathrm{diam}(\sigma ))$. The strict positive-distance condition keeps coincident or intersecting clusters in the near field, including diagonal singleton blocks.

The block-cluster tree starts at $(I,J)$. It stops at a pair if that pair is admissible or if both clusters are leaves. Otherwise, if only one cluster is nonleaf, it splits that cluster. If both are nonleaf, it splits the cluster of larger cardinality; ties are resolved by splitting the row cluster. The children of a split are the corresponding child-cluster pairs. Its terminal pairs are called block-cluster leaves. Admissible leaves are far blocks; nonadmissible leaves, which have two leaf clusters, are near blocks.

Let $I$ be a finite ordered set of size $n\ge 1$, and let $b$ be an integer with $1\le b\le n$. In the balanced cluster tree of Finite cluster trees and geometric admissibility, every cluster at depth $h$ has size at most $\lceil n\mathrm{/}{2}^h\rceil$. The tree has depth at most $\lceil {\log }_2(n\mathrm{/}b)\rceil$, at most $2n\mathrm{/}b$ leaves, and at most $4n\mathrm{/}b-1$ nodes.

The bounds include $b=1$ and $b=n$. For $b=n$ the root alone is a leaf; for $b=1$ every leaf is a singleton.

Let $I,J$ be nonempty finite index sets with finite cluster trees, and construct the block-cluster tree as in Finite cluster trees and geometric admissibility. Its terminal rectangles $\tau \times \sigma$ are pairwise disjoint and their union is $I\times J$.

Input: A field $\mathbb{F}\in \{\mathbb{R},\mathbb{C}\}$, positive integers $m,n$, a finite factor list $U_s\in {\mathbb{F}}^{m\times r_s}$ and $V_s\in {\mathbb{F}}^{n\times r_s}$ representing $M={\sum }_s{U}_s{V}_s^{\ast }$, a rank cap $0\le k\le \min (m,n)$, and a Frobenius tolerance $\delta \ge 0$. The conjugate transpose $M^{\ast }$ and Frobenius norm are those of Finite tensor arrays and the Frobenius inner product.

Procedure: Concatenate the factors as $U=[U_1\cdots U_p]$ and $V=[V_1\cdots V_p]$, so $M=U{V}^{\ast }$. Take compact singular value decompositions $U=Q_U{R}_U$ and $V=Q_V{R}_V$, where the columns of $Q_U,Q_V$ are orthonormal and span the respective column spaces. Form the core $C=R_U{R}_V^{\ast }$ and compute an SVD $C=P\mathrm{\Sigma }{Q}^{\ast }$. Let its positive singular values be $s_1\ge \cdots \ge s_t>0$. Find the smallest $q\in \{0,\dots ,\min (k,t)\}$ for which $e_q:=({\sum }_{j>q}{s}_j^2{)}^{1\mathrm{/}2}\le \delta$. If no such $q$ exists, return tolerance-not-met. Otherwise return success with factors $\widehat{U}=Q_U{P}_{[:,1:q]}{\mathrm{\Sigma }}_q$ and $\widehat{V}=Q_V{Q}_{[:,1:q]}$, where ${\mathrm{\Sigma }}_q=\mathrm{diag}(s_1,\dots ,s_q)$, and the exact discarded-tail certificate $e_q$; when $q=0$, use empty $m\times 0$ and $n\times 0$ factors.

The compact decompositions retain only positive singular directions. If the factor list is empty or its represented matrix is zero, then $t=0$ and the procedure returns the rank-zero representation because $\delta \ge 0$. Any SVD choices in repeated singular subspaces are permitted. No result is returned when the requested cap cannot certify the tolerance.

Let $\mathbb{F}\in \{\mathbb{R},\mathbb{C}\}$, let $I,J$ be nonempty finite index sets with point assignments as in Finite cluster trees and geometric admissibility, and let $\mathcal{P}$ be the block-cluster leaves of Block-cluster leaves partition the index-pair set. Fix an integer rank cap $k\ge 1$. An H-matrix representation with cap $k$ assigns to each far block $b=(\tau ,\sigma )\in \mathcal{P}$ factors $U_b\in {\mathbb{F}}^{\tau \times r_b}$ and $V_b\in {\mathbb{F}}^{\sigma \times r_b}$ with $0\le r_b\le k$, representing that block by $U_b{V}_b^{\ast }$. Each near block is stored as its full dense matrix $D_b\in {\mathbb{F}}^{\tau \times \sigma }$. Since $\mathcal{P}$ partitions $I\times J$, these blocks determine a unique represented matrix $\tilde{A}\in {\mathbb{F}}^{I\times J}$.

The rank cap on far blocks is an assumption about the representation or the target's approximability; geometric admissibility alone does not imply that a given matrix block has low rank. Near blocks remain dense and receive no low-rank guarantee.

Let $M={\sum }_s{U}_s{V}_s^{\ast }$ be the finite matrix input to Core-SVD recompression with rank and error tolerances, and let $k$ and $\delta \ge 0$ be its rank cap and Frobenius tolerance. If the algorithm returns success with rank $q$, its returned matrix $\widehat{M}$ has rank $q$ and satisfies $\mathrm{\parallel }M-\widehat{M}{\mathrm{\parallel }}_F=({\sum }_{j>q}{s}_j(M{)}^2{)}^{1\mathrm{/}2}\le \delta$. No lower-rank matrix meets the same tolerance. If the algorithm returns tolerance-not-met, no matrix of rank at most $k$ meets the tolerance.

In the H-matrix setting of H-matrix block representation, an H² representation assigns a row basis $U_{\tau }\in {\mathbb{F}}^{\tau \times r_{\tau }}$ to every row cluster $\tau$ and a column basis $V_{\sigma }\in {\mathbb{F}}^{\sigma \times s_{\sigma }}$ to every column cluster $\sigma$, with $0\le r_{\tau },s_{\sigma }\le k$. For every internal row cluster $\tau$ with children ${\tau }_1,{\tau }_2$, it stores transfer matrices $E_{{\tau }_i}^U\in {\mathbb{F}}^{r_{{\tau }_i}\times r_{\tau }}$ satisfying

$U_{\tau }{\mathrm{\mid }}_{{\tau }_i}=U_{{\tau }_i}{E}_{{\tau }_i}^U(i=1,2)\mathrm{.}$

For every internal column cluster $\sigma$ with children ${\sigma }_1,{\sigma }_2$, it stores transfer matrices $E_{{\sigma }_j}^V\in {\mathbb{F}}^{s_{{\sigma }_j}\times s_{\sigma }}$ satisfying $V_{\sigma }{\mathrm{\mid }}_{{\sigma }_j}=V_{{\sigma }_j}{E}_{{\sigma }_j}^V$. These identities are the nested-basis conditions. An admissible block leaf $(\tau ,\sigma )$ is represented by $U_{\tau }{S}_{\tau \sigma }{V}_{\sigma }^{\ast }$ with coupling matrix $S_{\tau \sigma }\in {\mathbb{F}}^{r_{\tau }\times s_{\sigma }}$; near block leaves remain dense.

Let ${\mathcal{P}}_{\mathrm{f}\mathrm{a}\mathrm{r}}$ denote the admissible leaves of the block-cluster partition. The row interaction list of $\tau$ is ${\mathcal{L}}_U(\tau )=\{\sigma :(\tau ,\sigma )\in {\mathcal{P}}_{\mathrm{f}\mathrm{a}\mathrm{r}}\}$, and the column interaction list of $\sigma$ is ${\mathcal{L}}_V(\sigma )=\{\tau :(\tau ,\sigma )\in {\mathcal{P}}_{\mathrm{f}\mathrm{a}\mathrm{r}}\}$. An H² representation may impose a bound on these list lengths or on their total count; any complexity theorem must state which bound it uses.

Storage convention: Store the basis arrays explicitly only at leaf clusters. Store each internal cluster's child-to-parent transfer matrices; the basis of an internal cluster is reconstructed recursively from its children and these transfers.

Input: An H-matrix representation $\tilde{A}$ on a finite block-cluster partition $\mathcal{P}$ as in H-matrix block representation, and a vector $x\in {\mathbb{F}}^J$.

Procedure: Initialize $y\in {\mathbb{F}}^I$ to zero. For every far block $b=(\tau ,\sigma )$ with factors $U_b,V_b$, compute $z_b=V_b^{\ast }x{\mathrm{\mid }}_{\sigma }$ and add $U_b{z}_b$ to $y{\mathrm{\mid }}_{\tau }$. For every near block with dense entries $D_b$, compute $D_{b}x{\mathrm{\mid }}_{\sigma }$ and add it to $y{\mathrm{\mid }}_{\tau }$. Return $y$. All arithmetic is exact; contributions to a row cluster are summed over its block leaves.

Let $b=(\tau ,\sigma )$ be an admissible leaf of the finite block-cluster partition in H-matrix block representation. A factor-sum tree for $b$ is a finite rooted binary tree whose leaves carry factor pairs $U_v\in {\mathbb{F}}^{\tau \times r_v}$, $V_v\in {\mathbb{F}}^{\sigma \times r_v}$ for exact contributions $M_v=U_v{V}_v^{\ast }$; each internal node denotes the sum of the exact matrices denoted by its two children. Here $\mathbb{F}\in \{\mathbb{R},\mathbb{C}\}$, $\ast$ is conjugate transpose, and all factors have the displayed finite dimensions.

Input: Such a tree, a rank cap $k\ge 1$, node tolerances ${\theta }_v\ge 0$ whose sum over all nodes is at most a requested block tolerance ${\delta }_b\ge 0$, and the procedures/results Core-SVD recompression with rank and error tolerances and Core-SVD recompression is best at the declared Frobenius tolerance.

Procedure: Traverse the tree in postorder. At a leaf, pass its exact factor pair to core-SVD recompression. At an internal node, concatenate the returned child factor pairs, which represents the sum of the two child approximations, and pass that pair to core-SVD recompression. At every node use effective core cap $k_b=\min (k,\mathrm{\mid }\tau \mathrm{\mid },\mathrm{\mid }\sigma \mathrm{\mid })$ and tolerance ${\theta }_v$. If any call returns tolerance-not-met, return that status and node. On success, retain its factors and exact discarded-tail norm ${\rho }_v$. Define the node's reported error bound by $e_v={\rho }_v$ at a leaf and $e_v=e_{v_1}+e_{v_2}+{\rho }_v$ at an internal node. If all calls succeed, return the root factors and $e_{\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{t}}$. Then the root matrix has rank at most $k$ and its Frobenius error from the sum of all leaf contributions is at most $e_{\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{t}}\le {\sum }_v{\theta }_v\le {\delta }_b$. A failed call means only that this chosen tree and its assigned local budgets did not produce a certificate; it does not assert that no rank-$k$ approximation of the full sum meets ${\delta }_b$.

Near blocks are not passed to this routine: they are assembled and stored densely and exactly. For a leaf carrying a dense contribution $D\in {\mathbb{F}}^{m\times n}$, use the exact factor pair $(D,I_n)$, where $I_n$ is the identity matrix; the routine may then compress it under its assigned tolerance.

The rank and error guarantees are proved in Bottom-up factor-sum recompression has the reported rank and Frobenius error bound ↗.

Let $0\le a<b$, $c\ge 0$, and choose $m,n\ge 1$ points $x_i\in [0,a]$ and $y_j\in [b,b+c]$. Put $q=a\mathrm{/}b<1$ and define the Cauchy block $K_{ij}=1\mathrm{/}(y_j-x_i)$. For any integer $r\ge 1$, the matrix $\tilde{K}$ with entries ${\tilde{K}}_{ij}={\sum }_{\mathrm{\ell }=0}^{r-1}{x}_i^{\mathrm{\ell }}{y}_j^{-(\mathrm{\ell }+1)}$ has rank at most $r$ and satisfies $\mathrm{\mid }{K}_{ij}-{\tilde{K}}_{ij}\mathrm{\mid }\le q^r\mathrm{/}(b-a)$ and $\mathrm{\parallel }K-\tilde{K}{\mathrm{\parallel }}_F\le \sqrt{mn}{q}^r\mathrm{/}(b-a)$. If $b-a\ge \eta \max (a,c)$ and the H-matrix rank cap satisfies $k\ge r$, the sampled clusters are admissible and $\tilde{K}$ is a permitted rank-at-most-$k$ far-block representation.

Input: An exact factorization $A=LU$ of a square matrix $A\in {\mathbb{F}}^{n\times n}$, where $\mathbb{F}\in \{\mathbb{R},\mathbb{C}\}$ and $n\ge 1$, with $L$ block lower triangular and $U$ block upper triangular on a common ordered cluster partition; an integer rank cap $k\ge 1$; and a nonnegative local Frobenius tolerance for each admissible off-diagonal block of $L$ and $U$. The factorization $A=LU$ is supplied as a hypothesis, not computed by this procedure.

Procedure: Copy every dense nearfield block and every diagonal block exactly. For each strictly lower admissible block $D_b\in {\mathbb{F}}^{m_b\times n_b}$ of $L$ and each strictly upper admissible block $D_b$ of $U$, form the one-pair factor list $(D_b,I_{n_b})$, representing $D_b=D_b{I}_{n_b}^{\ast }$, and pass it to Core-SVD recompression with rank and error tolerances with effective cap $\min (k,m_b,n_b)$ and its given local tolerance. Keep structural zero blocks zero. If any compression reports tolerance-not-met, return that status and the factor/block identity. Otherwise return $\widehat{L},\widehat{U}$ and the local discarded-tail bounds ${ϵ}_b^L,{ϵ}_c^U$ reported by the recompressions. The exact diagonal blocks preserve block triangularity; no claim is made that the compressed factors are exact factors of $A$.

Use Bottom-up low-rank recompression of block contributions on a finite factor-sum tree for one admissible block over $\mathbb{F}\in \{\mathbb{R},\mathbb{C}\}$, with exact arithmetic, rank cap $k\ge 1$, node tolerances ${\theta }_v\ge 0$, and ${\sum }_v{\theta }_v\le {\delta }_b$. Let $T_v$ be the subtree rooted at $v$, and let $M_v$ be the sum of its exact leaf contributions. Whenever all calls in $T_v$ succeed, the returned factors represent a matrix ${\widehat{M}}_v$ of rank at most $k$, and the reported bound satisfies $\mathrm{\parallel }{M}_v-{\widehat{M}}_v{\mathrm{\parallel }}_F\le e_v={\sum }_{w\in T_v}{\rho }_w\le {\sum }_{w\in T_v}{\theta }_w\mathrm{.}$ In particular, if the routine succeeds at the root, $\mathrm{rank}({\widehat{M}}_{\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{t}})\le k,\mathrm{\parallel }{M}_{\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{t}}-{\widehat{M}}_{\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{t}}{\mathrm{\parallel }}_F\le e_{\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{t}}={\sum }_w{\rho }_w\le {\sum }_w{\theta }_w\le {\delta }_b\mathrm{.}$ Here ${\rho }_w$ is the exact discarded-tail norm returned at node $w$. A tolerance-not-met status at a node only means this chosen tree and these assigned local budgets did not produce the requested certificate; it does not assert that no rank-$k$ approximation of the exact full sum meets ${\delta }_b$.

Input: Two H-matrix representations $A,B$ on the same block-cluster partition $\mathcal{P}$, a rank cap $k\ge 1$, and for each far block $b\in \mathcal{P}$ a factor-sum tree with node tolerances whose total is at most ${\delta }_b\ge 0$. The tree leaves are the exact factors of $A_b$ and $B_b$.

Procedure: For each near block, store the exact dense sum $A_b+B_b$ and report local error $e_b=0$. For each far block, run Bottom-up low-rank recompression of block contributions on its factor-sum tree with cap $k$. If any block returns tolerance-not-met, return that status and the block identity; otherwise store the root factors, report the certified error bound $e_b$ returned by that routine, and retain the block partition. The input's node budgets sum to at most ${\delta }_b$, so $e_b\le {\delta }_b$ by the bottom-up error guarantee.

Input: H-matrix representations $A\in {\mathbb{F}}^{I\times K}$ and $B\in {\mathbb{F}}^{K\times J}$, a recursively generated output block-cluster partition as in Finite cluster trees and geometric admissibility, a rank cap $k\ge 1$, local tolerances ${\delta }_b\ge 0$ for far output blocks, and for each output block $b=(\tau ,\sigma )$ a finite intermediate-cluster family ${\mathcal{K}}_b$ partitioning $K$ such that the restrictions $A_{\tau \kappa }$ and $B_{\kappa \sigma }$ are available in dense or factorized form for each $\kappa \in {\mathcal{K}}_b$. For a far output block, its factor-sum tree has one exact product term for each $\kappa \in {\mathcal{K}}_b$ and node tolerances totaling at most ${\delta }_b$. This compatibility condition is part of the input.

Procedure: For each output block, use the exact identity $C_b={\sum }_{\kappa \in {\mathcal{K}}_b}{A}_{\tau \kappa }{B}_{\kappa \sigma }$. If the output block is near, form and store this dense sum exactly and report $e_b=0$. For a far output block, convert each product term to factor form: $U{V}^{\ast }\cdot P{Q}^{\ast }=U(V^{\ast }P)Q^{\ast }$ when both factors are low rank; $U{V}^{\ast }\cdot D=U(D^{\ast }V{)}^{\ast }$ and $D\cdot P{Q}^{\ast }=(DP)Q^{\ast }$ when one factor is dense; and $D_1{D}_2=D_1(D_2^{\ast }{)}^{\ast }$ when both are dense. These formulas produce factors with matching inner dimensions. Run Bottom-up low-rank recompression of block contributions on the resulting finite factor-sum tree with cap $k$. If any block returns tolerance-not-met, return that status and block identity; otherwise store the root factors and its certified bound $e_b\le {\delta }_b$.

For every H-matrix representation $\tilde{A}\in {\mathbb{F}}^{I\times J}$ on the block-cluster partition of Block-cluster leaves partition the index-pair set and every vector $x\in {\mathbb{F}}^J$, H-matrix block matrix-vector multiplication returns $\tilde{A}x$ exactly.

Input: An H² representation $\tilde{A}$ with row bases $U_{\tau }$, column bases $V_{\sigma }$, transfer matrices from Nested H² cluster bases and interaction lists, and a vector $x\in {\mathbb{F}}^J$.

Procedure:

1. Initialize an upward coefficient vector $z_{\sigma }$ for each column cluster. At each leaf $\sigma$, set $z_{\sigma }=V_{\sigma }^{\ast }x{\mathrm{\mid }}_{\sigma }$. At each internal cluster $\sigma$ with children ${\sigma }_1,{\sigma }_2$, set $z_{\sigma }={\sum }_{j=1}^2(E_{{\sigma }_j}^V{)}^{\ast }{z}_{{\sigma }_j}$.
2. Initialize a downward coefficient vector $w_{\tau }=0$ for each row cluster and an output vector $y=0$. For each admissible leaf $(\tau ,\sigma )$, add $S_{\tau \sigma }{z}_{\sigma }$ to $w_{\tau }$. For each near leaf $(\tau ,\sigma )$, add $D_{\tau \sigma }x{\mathrm{\mid }}_{\sigma }$ to $y{\mathrm{\mid }}_{\tau }$.
3. Traverse the row tree from root to leaves. For each parent $\tau$ and child ${\tau }_i$, add $E_{{\tau }_i}^U{w}_{\tau }$ to $w_{{\tau }_i}$. At each row leaf $\tau$, add $U_{\tau }{w}_{\tau }$ to $y{\mathrm{\mid }}_{\tau }$. Return $y$.

The upward and downward traversals follow the finite cluster trees; block and cluster contributions are accumulated in exact arithmetic.

For any finite matrix partition into disjoint blocks, if each local residual satisfies $\mathrm{\parallel }{E}_b{\mathrm{\parallel }}_F\le {\delta }_b$, then the assembled residual satisfies $\mathrm{\parallel }E{\mathrm{\parallel }}_F\le ({\sum }_b{\delta }_b^2{)}^{1\mathrm{/}2}$. In particular, let $A,B$ be conformable finite real or complex matrices, and let $\tilde{A},\tilde{B}$ be approximations with $\mathrm{\parallel }A-\tilde{A}{\mathrm{\parallel }}_F\le {ϵ}_A$ and $\mathrm{\parallel }B-\tilde{B}{\mathrm{\parallel }}_F\le {ϵ}_B$. If a successful block addition or block product from Tolerance-controlled H-matrix block addition or Tolerance-controlled H-matrix block product returns $\widehat{S}$ or $\widehat{C}$, with disjoint output blocks $b$ and local Frobenius errors $e_b\le {\delta }_b$, put $\delta =({\sum }_b{\delta }_b^2{)}^{1\mathrm{/}2}$. Then

$\mathrm{\parallel }A+B-\widehat{S}{\mathrm{\parallel }}_F\le {ϵ}_A+{ϵ}_B+\delta ,$

and

$\mathrm{\parallel }AB-\widehat{C}{\mathrm{\parallel }}_F\le {ϵ}_A\mathrm{\parallel }B{\mathrm{\parallel }}_F+\mathrm{\parallel }A{\mathrm{\parallel }}_F{ϵ}_B+{ϵ}_A{ϵ}_B+\delta \mathrm{.}$

Let $I=J$ have size $n$, let $1\le k\le n$, and use balanced cluster trees with leaf threshold $b=k$. Let $s\ge 1$ be independent of $n,k$. Assume:

1. at each level of the block-cluster tree, the far leaves satisfy ${\sum }_{(\tau ,\sigma )}(\mathrm{\mid }\tau \mathrm{\mid }+\mathrm{\mid }\sigma \mathrm{\mid })\le 2sn$;
2. the total number of near leaves is at most $s\lceil n\mathrm{/}k\rceil$;
3. the total number of admissible H² coupling blocks is at most $s\lceil n\mathrm{/}k\rceil$.

Count scalar storage entries and exact scalar arithmetic operations, with constants allowed to depend on $s$ but not on $n,k$. Then an H-matrix with far-block ranks at most $k$ has storage and matvec work $O(skn{\log }_2(2n\mathrm{/}k))$. An H²-matrix with nested bases of ranks at most $k$ has storage and matvec work $O(skn)$. The bounds depend on the stated block-count assumptions; geometric admissibility alone does not imply them.

This theorem gives storage and matrix-vector costs. It does not assert that formatted H-matrix addition or multiplication is uniformly $O(kn\log n)$ in the variable rank $k$; their recompression work has additional rank-dependent factors.

For every nested-basis H² representation $\tilde{A}\in {\mathbb{F}}^{I\times J}$ and every vector $x\in {\mathbb{F}}^J$, Nested-basis H² matrix-vector multiplication returns $\tilde{A}x$ exactly.

Let $A\in {\mathbb{F}}^{n\times n}$ be invertible over $\mathbb{F}\in \{\mathbb{R},\mathbb{C}\}$, $n\ge 1$, and let $A=LU$ be an exact block lower-upper factorization. Suppose Compress exact block LU factors with local tolerances returns $\widehat{L},\widehat{U}$ and exact local discarded-tail errors $e_b^L,e_c^U$. All operations and norms in this theorem are exact. Put ${ϵ}_L=({\sum }_b(e_b^L{)}^2{)}^{1\mathrm{/}2}$, ${ϵ}_U=({\sum }_c(e_c^U{)}^2{)}^{1\mathrm{/}2}$, $\widehat{A}=\widehat{L}\widehat{U}$, and $\eta ={ϵ}_L\mathrm{\parallel }U{\mathrm{\parallel }}_F+\mathrm{\parallel }\widehat{L}{\mathrm{\parallel }}_F{ϵ}_U$. Then

$\mathrm{\parallel }A-\widehat{A}{\mathrm{\parallel }}_F\le \eta \text{and}\mathrm{\parallel }A-\widehat{A}{\mathrm{\parallel }}_2\le \eta \mathrm{.}$

If $q=\mathrm{\parallel }{A}^{-1}{\mathrm{\parallel }}_2\eta <1$, then $\widehat{A}$ is invertible and

$\mathrm{\parallel }{\widehat{A}}^{-1}-A^{-1}{\mathrm{\parallel }}_2\le \frac{\mathrm{\parallel }{A}^{-1}{\mathrm{\parallel }}_2^2\eta }{1-q}\mathrm{.}$