preprint · arXiv (Cornell University) · 2022

pylspack: Parallel algorithms and data structures for sketching, column subset selection, regression and leverage scores

Aleksandros Sobczyk, Efstratios Gallopoulos

Cited by 0Open access

Abstract

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. We provide a detailed analysis of the ubiquitous CountSketch transform and its combination with Gaussian random projections, accounting for memory requirements, computational complexity and workload balancing. We also demonstrate how these results can be applied to column subset selection, least squares regression and leverage scores computation. These tools have been implemented in pylspack, a publicly available Python package (https://github.com/IBM/pylspack) whose core is written in C++ and parallelized with OpenMP, and which is compatible with standard matrix data structures of SciPy and NumPy. Extensive numerical experiments indicate that the proposed algorithms scale well and significantly outperform existing libraries for tall-and-skinny matrices.

Cite this paper

APA 7

Sobczyk, A., & Gallopoulos, E. (2022). pylspack: Parallel algorithms and data structures for sketching, column subset selection, regression and leverage scores. arXiv (Cornell University). https://doi.org/10.48550/arxiv.2203.02798

MLA 9

Sobczyk, Aleksandros, and Efstratios Gallopoulos. “pylspack: Parallel algorithms and data structures for sketching, column subset selection, regression and leverage scores.” arXiv (Cornell University), 2022, https://doi.org/10.48550/arxiv.2203.02798.

Chicago

Sobczyk, Aleksandros, and Efstratios Gallopoulos. 2022. “pylspack: Parallel algorithms and data structures for sketching, column subset selection, regression and leverage scores.” arXiv (Cornell University). https://doi.org/10.48550/arxiv.2203.02798.

Harvard

Sobczyk, A. and Gallopoulos, E. (2022) ‘pylspack: Parallel algorithms and data structures for sketching, column subset selection, regression and leverage scores’, arXiv (Cornell University). Available at: https://doi.org/10.48550/arxiv.2203.02798.

BibTeX

@misc{sobczyk2022pylspack,
  title = {{pylspack: Parallel algorithms and data structures for sketching, column subset selection, regression and leverage scores}},
  author = {Sobczyk, Aleksandros and Gallopoulos, Efstratios},
  journal = {arXiv (Cornell University)},
  year = {2022},
  doi = {10.48550/arxiv.2203.02798}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.