Fetching the paper…
Reading the bibliography…
We present parallel algorithms and data structures for three fundamental operations in Numerical Linear Algebra: (i) Gaussian and CountSketch random projections and their combination, (ii) computation of the Gram matrix and (iii) computation of the squared row norms of the product of two matrices, with a special focus on "tall-and-skinny" matrices, which arise in many applications.
Two fast algorithms for sparse matrices: Multiplication and permuted transposition
Fred G Gustavson · 1978
Earlier work this paper cites.
Extensions of Lipschitz mappings into a Hilbert space
William B Johnson and Joram Lindenstrauss · 1984
Earlier work this paper cites.
Sparskit: A basic tool kit for sparse matrix computations
Youcef Saad · 1990
Earlier work this paper cites.
Openmp: an industry standard api for shared-memory programming
Leonardo Dagum and Ramesh Menon · 1998
Earlier work this paper cites.
Approximate nearest neighbors: Towards removing the curse of dimensionality
Piotr Indyk and Rajeev Motwani · 1998
Earlier work this paper cites.
The Ziggurat method for generating random variables
George Marsaglia, Wai Wan Tsang, et al · 2000
Earlier work this paper cites.
Database-friendly random projections
Dimitris Achlioptas · 2001
Earlier work this paper cites.
Finding frequent items in data streams
Moses Charikar, Kevin Chen, and Martin Farach-Colton · 2002
Earlier work this paper cites.
An overview of the sparse basic linear algebra subprograms: The new standard from the blas technical forum
Iain S Duff, Michael A Heroux, and Roldan Pozo · 2002
Earlier work this paper cites.
Matrix rank certification
B Saunders, Arne Storjohann, and Gilles Villard · 2004
Earlier work this paper cites.
Fast sparse matrix multiplication
Raphael Yuster and Uri Zwick · 2005
Earlier work this paper cites.
Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform
Nir Ailon and Bernard Chazelle · 2006
Earlier work this paper cites.
Direct Methods for Sparse Linear Systems
Timothy A. Davis · 2006
Earlier work this paper cites.
Very sparse random projections
Ping Li, Trevor J Hastie, and Kenneth W Church · 2006
Earlier work this paper cites.
Improved approximation algorithms for large matrices via random projections
Tamás Sarlós · 2006
Earlier work this paper cites.
Distributed sparse random projections for refinable approximation
Wei Wang, Minos Garofalakis, and Kannan Ramchandran · 2007
Earlier work this paper cites.
On the representation and multiplication of hypersparse matrices
Aydin Buluc and John R Gilbert · 2008
Earlier work this paper cites.
Optimizing sparse matrix-vector multiplication using index and value compression
Kornilios Kourtis, Georgios Goumas, and Nectarios Koziris · 2008
Earlier work this paper cites.
A fast randomized algorithm for overdetermined linear least-squares regression
V. Rokhlin and M. Tygert · 2008
Earlier work this paper cites.
Graph sparsification by effective resistances
Daniel A Spielman and Nikhil Srivastava · 2008
Earlier work this paper cites.
80 million tiny images: A large data set for nonparametric object and scene recognition
Antonio Torralba, Rob Fergus, and William T Freeman · 2008
Earlier work this paper cites.
Fast dimension reduction using Rademacher series on dual BCH codes
Nir Ailon and Edo Liberty · 2009
Earlier work this paper cites.
An improved approximation algorithm for the column subset selection problem
Christos Boutsidis, Michael W Mahoney, and Petros Drineas · 2009
Earlier work this paper cites.
Blendenpik: Supercharging LAPACK’s least-squares solver
H. Avron, P. Maymounkov, and S. Toledo · 2010
Earlier work this paper cites.
Counting triangles in large graphs using randomized matrix trace estimation
Haim Avron · 2010
Earlier work this paper cites.
Faster least squares approximation
P. Drineas, M.W. Mahoney, S. Muthukrishnan, and T. Sarlós · 2010
Earlier work this paper cites.
Eigen v3
Gaël Guennebaud, Benoît Jacob, et al · 2010
Earlier work this paper cites.
The combinatorial blas: Design, implementation, and applications
Aydın Buluç and John R Gilbert · 2011
Earlier work this paper cites.
Graph algorithms in the language of linear algebra
Jeremy Kepner and John Gilbert · 2011
Earlier work this paper cites.
Csx: an extended compression format for spmv on shared memory systems
Kornilios Kourtis, Vasileios Karakasis, Georgios Goumas, and Nectarios Koziris · 2011
Cited alongside, same era.
Scikit-learn: Machine learning in Python
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay · 2011
Cited alongside, same era.
Parallel random numbers: as easy as 1, 2, 3
John K Salmon, Mark A Moraes, Ron O Dror, and David E Shaw · 2011
Cited alongside, same era.
Improved analysis of the subsampled randomized Hadamard transform
Joel A Tropp · 2011
Cited alongside, same era.
Fast approximation of matrix coherence and statistical leverage
Petros Drineas, Malik Magdon-Ismail, Michael W Mahoney, and David P Woodruff · 2012
Cited alongside, same era.
Faster subset selection for matrices and applications
Low-rank approximation and regression in input sparsity time
Kenneth L. Clarkson and David P. Woodruff · 2017
Later among the works it cites.
Input sparsity time low-rank approximation via ridge leverage score sampling
Michael B. Cohen, Cameron Musco, and Christopher Musco · 2017
Later among the works it cites.
Newton sketch: A near linear-time optimization algorithm with linear-quadratic convergence
Mert Pilanci and Martin J Wainwright · 2017
Later among the works it cites.
An empirical evaluation of sketching for numerical linear algebra
Yogesh Dahiya, Dimitris Konomis, and David P Woodruff · 2018
Later among the works it cites.
Improved rectangular matrix multiplication using powers of the coppersmith-winograd tensor
François Le Gall and Florent Urrutia · 2018
Later among the works it cites.
Spectrum approximation beyond fast matrix multiplication: algorithms and hardness
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Haim Avron and Christos Boutsidis · 2013
Cited alongside, same era.
Fast matrix rank algorithms and applications
Ho Yee Cheung, Tsz Chiu Kwok, and Lap Chi Lau · 2013
Cited alongside, same era.
Revisiting the Nyström method for improved large-scale machine learning
Alex Gittens and Michael W Mahoney · 2013
Cited alongside, same era.
Iterative row sampling
Mu Li, Gary L Miller, and Richard Peng · 2013
Cited alongside, same era.
Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression
Xiangrui Meng and Michael W Mahoney · 2013
Cited alongside, same era.
OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings
Jelani Nelson and Huy L Nguyên · 2013
Cited alongside, same era.
Sparsity lower bounds for dimensionality reducing maps
Jelani Nelson and Huy L Nguyên · 2013
Cited alongside, same era.
Cameron Musco, Praneeth Netrapalli, Aaron Sidford, Shashanka Ubaru, and David P Woodruff · 2018
Later among the works it cites.
High-dimensional probability: An introduction with applications in data science
Roman Vershynin · 2018
Later among the works it cites.
Red-blue pebbling revisited: near optimal parallel matrix-matrix multiplication
Grzegorz Kwasniewski, Marko Kabić, Maciej Besta, Joost VandeVondele, Raffaele Solcà, and Torsten Hoefler · 2019
Later among the works it cites.
Ginkgo: A high performance numerical linear algebra library
Hartwig Anzt, Terry Cojean, Yen-Chen Chen, Goran Flegar, Fritz Göbel, Thomas Grützmacher, Pratik Nayak, Tobias Ribizel, and Yu-Hsiang Tsai · 2020
Later among the works it cites.
Mathematics of Data Science
Afonso S Bandeira, Amit Singer, and Thomas Strohmer · 2020
Later among the works it cites.
On fast multiplication of a matrix by its transpose
Jean-Guillaume Dumas, Clement Pernet, and Alexandre Sedoglavic · 2020
Later among the works it cites.
Randomized linear algebra approaches to estimate the von Neumann entropy of density matrices
Eugenia-Maria Kontopoulou, Gregory-Paul Dexter, Wojciech Szpankowski, Ananth Grama, and Petros Drineas · 2020
Later among the works it cites.
Packing lps are hard to solve accurately, assuming linear equations are hard
Rasmus Kyng, Di Wang, and Peng Zhang · 2020
Later among the works it cites.
Randomized numerical linear algebra: Foundations and algorithms
Per-Gunnar Martinsson and Joel A Tropp · 2020
Later among the works it cites.
Scipy 1.0: Fundamental algorithms for scientific computing in python
Pauli Virtanen, Ralf Gommers, Travis E Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, et al · 2020
Later among the works it cites.
A refined laser method and faster matrix multiplication
Josh Alman and Virginia Vassilevska Williams · 2021
Later among the works it cites.
Efficiently parallelizable strassen-based multiplication of a matrix by its transpose
Viviana Arrigoni, Filippo Maggioli, Annalisa Massini, and Emanuele Rodolà · 2021
Later among the works it cites.
Optimal fine-grained hardness of approximation of linear equations
Mitali Bafna and Nikhil Vyas · 2021
Later among the works it cites.
Hashing embeddings of optimal dimension, with applications to linear least squares
Coralia Cartis, Jan Fiala, and Zhen Shao · 2021
Later among the works it cites.
Newton-less: Sparsification without trade-offs for the sketched newton update
Michal Derezinski, Jonathan Lacotte, Mert Pilanci, and Michael W Mahoney · 2021
Later among the works it cites.
Sparse sketches with small inversion bias
Michal Derezinski, Zhenyu Liao, Edgar Dobriban, and Michael Mahoney · 2021
Later among the works it cites.
On the parallel i/o optimality of linear algebra kernels: Near-optimal lu factorization
Grzegorz Kwasniewski, Tal Ben-Nun, Alexandros Nikolaos Ziogas, Timo Schneider, Maciej Besta, and Torsten Hoefler · 2021
Later among the works it cites.
Fast randomized numerical rank estimation
Maike Meier and Yuji Nakatsukasa · 2021
Later among the works it cites.
Hutch++: Optimal stochastic trace estimation
Raphael A Meyer, Cameron Musco, Christopher Musco, and David P Woodruff · 2021
Later among the works it cites.
Column subset selection is NP-complete
Yaroslav Shitov · 2021
Later among the works it cites.
Estimating leverage scores via rank revealing methods and randomization
Aleksandros Sobczyk and Efstratios Gallopoulos · 2021
Later among the works it cites.
A quantum-inspired algorithm for approximating statistical leverage scores
Qian Zuo and Hua Xiang · 2021
Later among the works it cites.
Near-optimal algorithms for linear algebra in the current matrix multiplication time
Nadiia Chepurko, Kenneth L Clarkson, Praneeth Kacham, and David P Woodruff · 2022
Closest in time.