Low-Rank Kernel Matrix Approximation Using Skeletonized Interpolation With Endo- or Exo-Vertices
arXiv:1807.04787
Abstract
The efficient compression of kernel matrices, for instance the off-diagonal blocks of discretized integral equations, is a crucial step in many algorithms. In this paper, we study the application of Skeletonized Interpolation to construct such factorizations. In particular, we study four different strategies for selecting the initial candidate pivots of the algorithm: Chebyshev grids, points on a sphere, maximally-dispersed and random vertices. Among them, the first two introduce new interpolation points (exo-vertices) while the last two are subsets of the given clusters (endo- vertices). We perform experiments using three real-world problems coming from the multiphysics code LS-DYNA. The pivot selection strategies are compared in term of quality (final rank) and efficiency (size of the initial grid). These benchmarks demonstrate that overall, maximally-dispersed vertices provide an accurate and efficient sets of pivots for most applications. It allows to reach near-optimal ranks while starting with relatively small sets of vertices, compared to other strategies.
References in corpus (7)
- Measurement of areas on a sphere using Fibonacci and latitude-longitude lattices
- Yet another fast multipole method without multipoles --- Pseudo-particle multipole method
- Quasioptimality of maximum-volume cross interpolation of tensors
- Rectangular maximum-volume submatrices and their applications
- Low-rank approximations for large stationary covariance matrices, as used in the Bayesian and generalized-least-squares analysis of pulsar-timing data
- Fast Low-Rank Kernel Matrix Factorization through Skeletonized Interpolation
- Rank Revealing Gaussian Elimination by the Maximum Volume Concept