Technical Papers Archive

Communication Avoiding Parallel Sketching via Sparse Subspace Embeddings


Authors: Hussam Al Daas (Rutherford Appleton Laboratory), Grey Ballard (Wake Forest University), Laura Grigori (École Polytechnique Fédérale de Lausanne), Md Taufique Hussain (Wake Forest University), Suraj Kumar (French Institute for Research in Computer Science and Automation (INRIA)), Johannes Laute (Paul Scherrer Institute), and Kathryn Rouse (Inmar Intelligence)

Abstract: This paper considers sketching via sparse subspace embeddings that are commonly employed in randomized algorithms due to their efficiency when applied to large-scale matrices. We introduce lower bounds on communication and design optimal algorithms for sketching large-scale matrices using sparse random embeddings. We consider different matrix dimensions and aspect ratios that are relevant for scientific computing and machine learning applications. We demonstrate the strong and weak scalability of these algorithms on both CPU and GPU architectures.


Presentation: file

Back to Technical Papers Archive Listing