Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Adaptive compression of large vectors

Author: Steffen Börm
Journal: Math. Comp. 87 (2018), 209-235
MSC (2010): Primary 15A03; Secondary 41A50, 65F10, 65D05
Published electronically: May 31, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Numerical algorithms for elliptic partial differential equations frequently employ error estimators and adaptive mesh refinement strategies in order to reduce the computational cost.

We can extend these techniques to general vectors by splitting the vectors into a hierarchically organized partition of subsets and using appropriate bases to represent the corresponding parts of the vectors. This leads to the concept of hierarchical vectors.

A hierarchical vector with $ m$ subsets and bases of rank $ k$ requires $ mk$ units of storage, and typical operations like the evaluation of norms and inner products or linear updates can be carried out in $ \mathcal {O}(mk^2)$ operations.

Using an auxiliary basis, the product of a hierarchical vector and an $ \mathcal {H}^2$-matrix can also be computed in $ \mathcal {O}(mk^2)$ operations, and if the result admits an approximation with $ \widetilde m$ subsets in the original basis, this approximation can be obtained in $ \mathcal {O}((m+\widetilde m)k^2)$ operations. Since it is possible to compute the corresponding approximation error exactly, sophisticated error control strategies can be used to ensure the optimal compression.

Possible applications of hierarchical vectors include the approximation of eigenvectors, optimal control problems, and time-dependent partial differential equations with moving local irregularities.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 15A03, 41A50, 65F10, 65D05

Retrieve articles in all journals with MSC (2010): 15A03, 41A50, 65F10, 65D05

Additional Information

Steffen Börm
Affiliation: Department of Computer Science, University of Kiel, 24118 Kiel, Germany

Keywords: Data-sparse representation, $\mathcal{H}^2$-matrices, adaptive approximation
Received by editor(s): May 31, 2015
Received by editor(s) in revised form: July 12, 2016, and August 8, 2016
Published electronically: May 31, 2017
Article copyright: © Copyright 2017 American Mathematical Society

American Mathematical Society