The Mailman algorithm: a note on matrix-vector multiplication

DOI10.1016/J.IPL.2008.09.028zbMATH Open1191.68832OpenAlexW1973089001MaRDI QIDQ976066FDOQ976066

Authors: Edo Liberty, Steven W. Zucker 

Publication date: 16 June 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2008.09.028

Recommendations

• Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication
• Compressed matrix multiplication
• Compressed matrix multiplication
• Matrix-vector multiplication in sub-quadratic time (some preprocessing required)
• Fast, deterministic and sparse dimensionality reduction

zbMATH Keywords

algorithmsrandom projectionsmatrix-vector multiplicationMailman algorithm

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Cites Work

• Extensions of Lipschitz mappings into a Hilbert space
• Gaussian elimination is not optimal
• An extended set of FORTRAN basic linear algebra subprograms
• Basic Linear Algebra Subprograms for Fortran Usage
• Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
• Title not available (Why is that?)
• On the number of multiplications necessary to compute certain functions
• Matrix-vector multiplication in sub-quadratic time (some preprocessing required)
• Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform
• On the Number of Multiplications Required for Matrix Multiplication
• Title not available (Why is that?)
• An Algorithm for the Computation of Linear Forms
• An improved algorithm for Boolean matrix multiplication
• Extending the four Russians' bound to general matrix multiplication

Cited In (10)

• Detecting low-rank clusters via random sampling
• Efficient methods for grouping vectors into low-rank clusters
• Matrix-vector multiplication in sub-quadratic time (some preprocessing required)
• Faster algorithms for weighted recursive state machines
• Sketching with Kerdock's crayons: fast sparsifying transforms for arbitrary linear maps
• Feasibility checking in Horn constraint systems through a reduction based approach
• On geometric prototype and applications
• Learning the truth vector in high dimensions
• Real-valued embeddings and sketches for fast distance and similarity estimation
• Dense fast random projections and Lean Walsh transforms

Uses Software

• BLAS

This page was built for publication: The Mailman algorithm: a note on matrix-vector multiplication

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q976066)