Optimal sparse matrix dense vector multiplication in the I/O-model

DOI10.1007/S00224-010-9285-4MaRDI QIDQ613122zbMATH OpenOpenAlexFDO

Authors Michael A. Bender, Gerth Stølting Brodal, Rolf Fagerberg, Riko Jacob, E. Vicari

Publication date 17 December 2010

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/20.500.11850/66998

zbMATH Keywords

lower boundexternal memory algorithmsI/O-modelsparse matrix dense vector multiplication

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Analysis of algorithms (68W40) Mathematical problems of computer architecture (68M07) Numerical algorithms for specific classes of architectures (65Y10)

Recommendations

• The I/O Complexity of Sparse Matrix Dense Matrix Multiplication
• The input/output complexity of sparse matrix multiplication
• Evaluating non-square sparse bilinear forms on multiple vector pairs in the I/O-model
• Cache oblivious sparse matrix multiplication
• Fast Output-Sensitive Matrix Multiplication

Cites work

• scientific article; zbMATH DE number 1424311 (Why is no real title available?)
• scientific article; zbMATH DE number 1424315 (Why is no real title available?)
• scientific article; zbMATH DE number 1424322 (Why is no real title available?)
• Asymptotically Tight Bounds for Performing BMMC Permutations on Parallel Disk Systems
• Automata, Languages and Programming
• Cache-oblivious algorithms
• Gaussian elimination is not optimal
• Multi-linear formulas for permanent and determinant are of super-polynomial size
• On the limits of cache-obliviousness
• PSBLAS

Cited in

(10)

• Efficient boundary condition-enforced immersed boundary method for incompressible flows with moving boundaries
• The Usefulness of Sparsifiable Inputs: How to Avoid Subexponential iO
• Evaluating non-square sparse bilinear forms on multiple vector pairs in the I/O-model
• A Cache-Oblivious Sparse Matrix–Vector Multiplication Scheme Based on the Hilbert Curve
• Reducing the I/O Volume in Sparse Out-of-core Multifrontal Methods
• Optimal cache-oblivious mesh layouts
• The I/O Complexity of Sparse Matrix Dense Matrix Multiplication
• Communication lower bounds and optimal algorithms for numerical linear algebra
• Storing matrices on disk for efficient row and column retrieval
• The input/output complexity of sparse matrix multiplication

Describes a project that uses

Uses Software

• SPARSKIT
• OSKI
• ITSOL
• PSBLAS

This page was built for publication: Optimal sparse matrix dense vector multiplication in the I/O-model

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