@inproceedings{92d0b4cc395f420c92e73c6b496c3742,
title = "Efficient and Scalable Kernel Matrix Approximations Using Hierarchical Decomposition",
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.",
keywords = "Diffusion maps, Hierarchical matrix, Manifold learning, Numerical algorithms, Strong Scaling",
author = "Keerthi Gaddameedi and Severin Reiz and Tobias Neckel and Bungartz, {Hans Joachim}",
note = "Publisher Copyright: {\textcopyright} 2024, The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.; 3rd BenchCouncil International Symposium on Intelligent Computers, Algorithms, and Applications, IC 2023 ; Conference date: 03-12-2023 Through 06-12-2023",
year = "2024",
language = "English",
isbn = "9789819700646",
series = "Communications in Computer and Information Science",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "3--16",
editor = "Christophe Cruz and Yanchun Zhang and Wanling Gao",
booktitle = "Intelligent Computers, Algorithms, and Applications - Third BenchCouncil International Symposium, IC 2023, Revised Selected Papers",
}