  Randomized numerical linear algebra - RandNLA, for short - concerns the use
of randomization as a resource to develop improved algorithms for large-scale
linear algebra computations.
  The origins of contemporary RandNLA lay in theoretical computer science,
where it blossomed from a simple idea: randomization provides an avenue for
computing approximate solutions to linear algebra problems more efficiently
than deterministic algorithms. This idea proved fruitful in the development of
scalable algorithms for machine learning and statistical data analysis
applications. However, RandNLA's true potential only came into focus upon
integration with the fields of numerical analysis and "classical" numerical
linear algebra. Through the efforts of many individuals, randomized algorithms
have been developed that provide full control over the accuracy of their
solutions and that can be every bit as reliable as algorithms that might be
found in libraries such as LAPACK. Recent years have even seen the
incorporation of certain RandNLA methods into MATLAB, the NAG Library, NVIDIA's
cuSOLVER, and SciKit-Learn.
  For all its success, we believe that RandNLA has yet to realize its full
potential. In particular, we believe the scientific community stands to benefit
significantly from suitably defined "RandBLAS" and "RandLAPACK" libraries, to
serve as standards conceptually analogous to BLAS and LAPACK. This 200-page
monograph represents a step toward defining such standards. In it, we cover
topics spanning basic sketching, least squares and optimization, low-rank
approximation, full matrix decompositions, leverage score sampling, and
sketching data with tensor product structures (among others). Much of the
provided pseudo-code has been tested via publicly available MATLAB and Python
implementations.
