Adaptive multiplication of $$\mathcal {H}^2$$-matrices with block-relative error control

Abstract The discretization of non-local operators, e.g., solution operators of partial differential equations or integral operators, leads to large densely populated matrices. $$\mathcal {H}^2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>H</mml:mi> </mml:mrow> <mml:mn>2</mml:mn> </mml:msup> </mml:math> -matrices take advantage of local low-rank structures in these matrices to provide an efficient data-sparse approximation that allows us to handle large matrices efficiently, e.g., to reduce the storage requirements to $$\mathcal {O}(n k)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mi>k</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> for n -dimensional matrices with local rank k , and to reduce the complexity of the matrix-vector multiplication to $$\mathcal {O}(n k)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mi>k</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> operations. In order to perform more advanced operations, e.g., to construct efficient preconditioners or evaluate matrix functions, we require algorithms that take $$\mathcal {H}^2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>H</mml:mi> </mml:mrow> <mml:mn>2</mml:mn> </mml:msup> </mml:math> -matrices as input and approximate the result again by $$\mathcal {H}^2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>H</mml:mi> </mml:mrow> <mml:mn>2</mml:mn> </mml:msup> </mml:math> -matrices, ideally with controllable accuracy. In this manuscript, we introduce an algorithm that approximates the product of two $$\mathcal {H}^2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mi>H</mml:mi> </mml:mrow> <mml:mn>2</mml:mn> </mml:msup> </mml:math> -matrices in $$\mathcal {O}(n k^2 \log n)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:msup> <mml:mi>k</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> operations and guarantees block-relative error estimates for the submatrices of the result. It uses specialized tree structures to represent the exact product in an intermediate step, thereby allowing us to apply mathematically rigorous error control strategies.