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

DOI10.1007/s00224-010-9285-4zbMath1213.68069OpenAlexW2677289244MaRDI QIDQ613122

Rolf Fagerberg, Riko Jacob, Gerth Stølting Brodal, Michael A. Bender, Elias 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)

Related Items (4)

Efficient boundary condition-enforced immersed boundary method for incompressible flows with moving boundaries ⋮ A Cache-Oblivious Sparse Matrix–Vector Multiplication Scheme Based on the Hilbert Curve ⋮ Optimal cache-oblivious mesh layouts ⋮ Communication lower bounds and optimal algorithms for numerical linear algebra

Uses Software

• PSBLAS
• ITSOL
• OSKI
• SPARSKIT

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Gaussian elimination is not optimal
• Cache-Oblivious Algorithms
• On the limits of cache-obliviousness
• Asymptotically Tight Bounds for Performing BMMC Permutations on Parallel Disk Systems
• PSBLAS
• Automata, Languages and Programming
• Multi-linear formulas for permanent and determinant are of super-polynomial size

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