ASKIT swMATH ID: 17470 Software Authors: March, William B.; Xiao, Bo; Yu, Chenhan D.; Biros, George Description: ASKIT: an efficient, parallel library for high-dimensional kernel summations. Kernel-based methods are a powerful tool in a variety of machine learning and computational statistics methods. A key bottleneck in these methods is computations involving the kernel matrix, which scales quadratically with the problem size. Previously, we introduced ASKIT (Approximate Skeletonization Kernel Independent Treecode), an efficient, scalable, kernel-independent method for approximately evaluating kernel matrix-vector products. ASKIT is based on a novel, randomized method for efficiently factoring off-diagonal blocks of the kernel matrix using approximate nearest neighbor information. In this context, ASKIT can be viewed as an algebraic fast multipole method for arbitrary dimensions. In this paper, we introduce our open-source implementation of ASKIT. Features of our ASKIT library include linear dependence on the input dimension of the data, the ability to approximate kernel functions with no prior information on the kernel, and scalability to tens of thousands of compute cores and data with billions of points or hundreds of dimensions. We also introduce some new extensions and improvements of ASKIT, included in our library. We introduce a new method for adaptively selecting approximation ranks and correctly partition the nearest neighbor information, both of which improve the performance of ASKIT over our previous implementation. We describe the ASKIT algorithm in detail, and collect and summarize our previous theoretical complexity and error bounds in one place. We present a brief selection of experimental results illustrating the accuracy and scalability of ASKIT. We then provide some details and guidance for users of ASKIT. Homepage: http://users.ices.utexas.edu/~march/wp-content/uploads/2015/07/sisc15askit.pdf Keywords: N-body methods; treecodes; machine learning; kernel machines; linear algebra; randomized matrix approximation Related Software: UCI-ml; GitHub; STRUMPACK; ScalFMM; H2Lib; Thrust; hlib; tabipb; TABI; PetRBF; NFFT; NFFT3; UTV; JDQR; JDQZ; Algorithm 971; LSRN; Blendenpik; HODLRlib; Hm-toolbox Cited in: 14 Documents Standard Articles 1 Publication describing the Software, including 1 Publication in zbMATH Year ASKIT: an efficient, parallel library for high-dimensional kernel summations. Zbl 1416.65578March, William B.; Xiao, Bo; Yu, Chenhan D.; Biros, George 2016 all top 5 Cited by 30 Authors 5 Biros, George 3 March, William B. 3 Xiao, Bo 2 Yu, Chenhan D. 1 Avron, Haim 1 Boukaram, Wajih-Halim 1 Bungartz, Hans-Joachim 1 Cai, Wei 1 Chen, Chao 1 Chen, Duan 1 Chen, Jie 1 Chow, Edmond 1 Grooms, Ian G. 1 Keyes, David Elliot 1 Knio, Omar M. 1 Krasny, Robert 1 Martinsson, Per-Gunnar 1 Nestler, Franziska 1 Reiz, Severin 1 Robinson, Gregor 1 Sindhwani, Vikas 1 Stoll, Martin 1 Tlupova, Svetlana 1 Tropp, Joel A. 1 Turkiyyah, George M. 1 Wagner, Theresa 1 Wang, Lei 1 Xing, Xin 1 Zampini, Stefano 1 Zaspel, Peter all top 5 Cited in 10 Serials 4 SIAM Journal on Scientific Computing 2 SIAM Journal on Matrix Analysis and Applications 1 Journal of Computational Physics 1 Journal of Scientific Computing 1 Applied and Computational Harmonic Analysis 1 Advances in Computational Mathematics 1 Journal of Machine Learning Research (JMLR) 1 Acta Numerica 1 Communications in Computational Physics 1 Foundations of Data Science all top 5 Cited in 7 Fields 12 Numerical analysis (65-XX) 7 Computer science (68-XX) 4 Statistics (62-XX) 2 Fluid mechanics (76-XX) 1 Probability theory and stochastic processes (60-XX) 1 Systems theory; control (93-XX) 1 Information and communication theory, circuits (94-XX) Citations by Year