Efficient and Scalable Kernel Matrix Approximations Using Hierarchical Decomposition

Keerthi Gaddameedi, Severin Reiz, Tobias Neckel, Hans Joachim Bungartz

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

With the emergence of Artificial Intelligence, numerical algorithms are moving towards more approximate approaches. For methods such as PCA or diffusion maps, it is necessary to compute eigenvalues of a large matrix, which may also be dense depending on the kernel. A global method, i.e. a method that requires all data points simultaneously, scales with the data dimension N and not with the intrinsic dimension d ; the complexity for an exact dense eigendecomposition leads to O(N3). We have combined the two frameworks, datafold and GOFMM. The first framework computes diffusion maps, where the computational bottleneck is the eigendecomposition while with the second framework we compute the eigendecomposition approximately within the iterative Lanczos method. A hierarchical approximation approach scales roughly with a runtime complexity of O(Nlog(N) ) vs. O(N3) for a classic approach. We evaluate the approach on two benchmark datasets – scurve and MNIST – with strong and weak scaling using OpenMP and MPI on dense matrices with maximum size of 100 k× 100 k.

Original languageEnglish
Title of host publicationIntelligent Computers, Algorithms, and Applications - Third BenchCouncil International Symposium, IC 2023, Revised Selected Papers
EditorsChristophe Cruz, Yanchun Zhang, Wanling Gao
PublisherSpringer Science and Business Media Deutschland GmbH
Pages3-16
Number of pages14
ISBN (Print)9789819700646
DOIs
StatePublished - 2024
Event3rd BenchCouncil International Symposium on Intelligent Computers, Algorithms, and Applications, IC 2023 - Sanya, China
Duration: 3 Dec 20236 Dec 2023

Publication series

NameCommunications in Computer and Information Science
Volume2036 CCIS
ISSN (Print)1865-0929
ISSN (Electronic)1865-0937

Conference

Conference3rd BenchCouncil International Symposium on Intelligent Computers, Algorithms, and Applications, IC 2023
Country/TerritoryChina
CitySanya
Period3/12/236/12/23

Keywords

  • Diffusion maps
  • Hierarchical matrix
  • Manifold learning
  • Numerical algorithms
  • Strong Scaling

Fingerprint

Dive into the research topics of 'Efficient and Scalable Kernel Matrix Approximations Using Hierarchical Decomposition'. Together they form a unique fingerprint.

Cite this