  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.
