TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck pass

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Balanced H and H² storage and matvec complexity

Statement

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

at each level of the block-cluster tree, the far leaves satisfy $\sum_{(τ, σ)} (∣ τ ∣ + ∣ σ ∣) \leq 2 s n$ ;
the total number of near leaves is at most $s ⌈ n / k ⌉$ ;
the total number of admissible H² coupling blocks is at most $s ⌈ n / k ⌉$ .

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 (s k n \log_{2} (2 n / k))$ . An H²-matrix with nested bases of ranks at most $k$ has storage and matvec work $O (s k n)$ . The bounds depend on the stated block-count assumptions; geometric admissibility alone does not imply them.

Facts & Assumptions

Given: The balanced cluster trees, block-cluster partition, H/H² representations, rank cap $k$ , and the three stated counting hypotheses.

[F1]

Finite cluster trees and geometric admissibility: each internal cluster splits into two children whose sizes differ by at most one, and the block-cluster recursion splits one cluster at a time until admissibility or two leaf clusters.

[F2]

Size and depth of a balanced cluster tree: a threshold- $k$ cluster tree has depth at most $⌈ \log_{2} (n / k) ⌉$ , at most $2 n / k$ leaves, and at most $4 n / k - 1$ nodes.

[F3]

H-matrix block representation: each admissible H block stores at most $k$ columns in each factor, and each near block is stored densely.

[F4]

Nested H² cluster bases and interaction lists: H² stores at most $k$ columns for each leaf basis, at most $k \times k$ entries for each transfer and coupling matrix, and dense near blocks.

[F5]

H-matrix block matrix-vector multiplication and Nested-basis H² matrix-vector multiplication: H matvec applies each far factor through two rank-sized products and each near block densely; H² matvec uses leaf basis products, transfer products, coupling products, and dense near products.

Proof

1.1F1F2algebra

Let $h = ⌈ \log_{2} (n / k) ⌉$ . By [F1], each split descends one level in either the row tree or the column tree, whose depths are each at most $h$ by [F2]. Hence the block tree has depth at most $2 h$ . At each level, the first counting hypothesis bounds the total participating far-block side sizes by $2 s n$ .

2.1F1F3step 1.1algebra

Each far H block stores at most $k (∣ τ ∣ + ∣ σ ∣)$ scalar factor entries. Summing over at most $2 h + 1$ levels gives $O (s k n (h + 1))$ far storage. Every near block has both cluster sizes at most $k$ by [F1], so it stores at most $k^{2}$ entries; the second counting hypothesis bounds total near storage by $s ⌈ n / k ⌉ k^{2} = O (s k n)$ because $k \leq n$ . This proves the H storage bound.

3.1F1F3F5step 1.1step 2.1algebra

In [F5], a far-block product first multiplies an $r_{b} \times ∣ σ ∣$ factor by $x ∣_{σ}$ and then a $∣ τ ∣ \times r_{b}$ factor by the result, so it costs $O (k (∣ τ ∣ + ∣ σ ∣))$ . A near-block product costs $O (∣ τ ∣ ∣ σ ∣) \leq O (k^{2})$ . The same level and near-block counts used in step 2.1 therefore give H matvec work $O (s k n (h + 1)) = O (s k n \log_{2} (2 n / k))$ .

3.2F2F3F4step 2.1algebra

By the storage convention in [F4], the leaf row and column bases require at most $2 k n$ entries because the leaves partition $I$ and each basis rank is at most $k$ . By [F2], each tree has $O (n / k)$ nodes, so all $k \times k$ transfer matrices require $O (k n)$ entries. The third counting hypothesis gives $O (k n)$ entries for all coupling matrices, and step 2.1 bounds dense near blocks by $O (s k n)$ . Thus H² storage is $O (s k n)$ .

4.1F2F4F5step 2.1algebra∎

The leaf basis products in [F5] cost $O (k n)$ because their index sets partition $I$ and $J$ . Each transfer product costs at most $O (k^{2})$ and there are $O (n / k)$ internal clusters by [F2]; each coupling product costs at most $O (k^{2})$ and the third hypothesis bounds their number by $s ⌈ n / k ⌉$ . Dense near products cost $O (s k n)$ by step 2.1. Summing gives H² matvec work $O (s k n)$ .

Remarks

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

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · one level

7 results within one dependency step of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Steffen Börm, Lars Grasedyck, and Wolfgang Hackbusch, Hierarchical Matrices, MiS Lecture Note 21 (2003; revised June 2006), §§1.6, 7.1, 9.2 (standard reference, not scraped)
Ralf Hiptmair, AdvNumCSE Lecture Document, Chapter 2, “Local Low-Rank Compression of Non-Local Operators” (ETH Zürich, AT’23), §§2.3.5, 2.4 (standard reference, not scraped)