Efficient and Scalable Kernel Matrix Approximations Using Hierarchical Decomposition

Publikation: Beitrag in Buch/Bericht/KonferenzbandKonferenzbeitragBegutachtung

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.

OriginalspracheEnglisch
TitelIntelligent Computers, Algorithms, and Applications - Third BenchCouncil International Symposium, IC 2023, Revised Selected Papers
Redakteure/-innenChristophe Cruz, Yanchun Zhang, Wanling Gao
Herausgeber (Verlag)Springer Science and Business Media Deutschland GmbH
Seiten3-16
Seitenumfang14
ISBN (Print)9789819700646
PublikationsstatusVeröffentlicht - 2024
Veranstaltung3rd BenchCouncil International Symposium on Intelligent Computers, Algorithms, and Applications, IC 2023 - Sanya, China
Dauer: 3 Dez. 20236 Dez. 2023

Publikationsreihe

NameCommunications in Computer and Information Science
Band2036 CCIS
ISSN (Print)1865-0929
ISSN (elektronisch)1865-0937

Konferenz

Konferenz3rd BenchCouncil International Symposium on Intelligent Computers, Algorithms, and Applications, IC 2023
Land/GebietChina
OrtSanya
Zeitraum3/12/236/12/23

Fingerprint

Untersuchen Sie die Forschungsthemen von „Efficient and Scalable Kernel Matrix Approximations Using Hierarchical Decomposition“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren