{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:33:07Z","timestamp":1787337187290,"version":"3.56.0"},"reference-count":43,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2009,1]]},"abstract":"<jats:p>In this article, we introduce a cache-oblivious method for sparse matrix\u2013vector multiplication. Our method attempts to permute the rows and columns of the input matrix using a recursive hypergraph-based sparse matrix partitioning scheme so that the resulting matrix induces cache-friendly behavior during sparse matrix\u2013vector multiplication. Matrices are assumed to be stored in row-major format, by means of the compressed row storage (CRS) or its variants incremental CRS and zig-zag CRS. The zig-zag CRS data structure is shown to fit well with the hypergraph metric used in partitioning sparse matrices for the purpose of parallel computation. The separated block-diagonal (SBD) form is shown to be the appropriate matrix structure for cache enhancement. We have implemented a run-time cache simulation library enabling us to analyze cache behavior for arbitrary matrices and arbitrary cache properties during matrix\u2013vector multiplication within a k-way set-associative idealized cache model. The results of these simulations are then verified by actual experiments run on various cache architectures. In all these experiments, we use the Mondriaan sparse matrix partitioner in one-dimensional mode. The savings in computation time achieved by our matrix reorderings reach up to 50 percent, in the case of a large link matrix.<\/jats:p>","DOI":"10.1137\/080733243","type":"journal-article","created":{"date-parts":[[2009,7,31]],"date-time":"2009-07-31T18:29:16Z","timestamp":1249064956000},"page":"3128-3154","source":"Crossref","is-referenced-by-count":58,"title":["Cache-Oblivious Sparse Matrix\u2013Vector Multiplication by Using Sparse Matrix Partitioning Methods"],"prefix":"10.1137","volume":"31","author":[{"given":"A. N.","family":"Yzelman","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rob H.","family":"Bisseling","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2009,7,31]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827502401953"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"Z. Bai, J. Demmel, J. Dongarra, A. Ruhe, and H. van der Vorst, eds.\n                      Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide\n                      , SIAM, Philadelphia, 2000.","DOI":"10.1137\/1.9780898719581"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"M. A. Bender, G. S. Brodal, R. Fagerberg, R. Jacob, and E. Vicari,\n                      Optimal sparse matrix dense vector multiplication in the I\/O-model\n                      , in Proceedings of the 19th Annual ACM Symposium on Parallel Algorithms and Architectures, ACM Press, New York, 2007, pp. 61\u201370.","DOI":"10.1145\/1248377.1248391"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-7552(98)00110-X"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1109\/71.780863"},{"key":"R6","unstructured":"\u00dc. V. \u00c7ataly\u00fcrek and C. Aykanat,\n                      A fine-grain hypergraph model for 2D decomposition of sparse matrices\n                      , in Proceedings of the 8th International Workshop on Solving Irregularly Structured Problems in Parallel, IEEE Press, Los Alamitos, CA, 2001, p. 118."},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.2514\/3.12012"},{"key":"R8","unstructured":"T. A. Davis,\n                      University of Florida sparse matrix collection\n                      , http:\/\/www.cise.ufl.edu\/research\/sparse\/matrices, Department of Computer and Information Science and Engineering, University of Florida, Gainesville, FL, 1994-2008."},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1137\/060661533"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"K. D. Devine, E. G. Boman, R. Heaphy, R. H. Bisseling, and U. V. Catalyurek,\n                      Parallel hypergraph partitioning for scientific computing\n                      , in Proceedings of the IEEE International Parallel and Distributed Processing Symposium 2006, IEEE Press, New York, 2006.","DOI":"10.1109\/IPDPS.2006.1639359"},{"key":"R11","unstructured":"I. S. Duff, A. M. Erisman, and J. K. Reid,\n                      Direct Methods for Sparse Matrices\n                      , Monographs on Numerical Analysis, Oxford University Press, Oxford, UK, 1986."},{"key":"R12","doi-asserted-by":"crossref","unstructured":"M. Frigo and S. G. Johnson,\n                      FFTW: An adaptive software architecture for the FFT\n                      , in Proceedings IEEE International Conference on Acoustics, Speech, and Signal Processing, Vol. 3, IEEE Press, Los Alamitos, CA, 1998, pp. 1381\u20131384.","DOI":"10.1109\/ICASSP.1998.681704"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2004.840301"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"M. Frigo, C. E. Leiserson, H. Prokop, and S. Ramachandran,\n                      Cache-oblivious algorithms\n                      , in Proceedings of the 40th Annual Symposium on Foundations of Computer Science, IEEE Press, Los Alamitos, CA, 1999, p. 285.","DOI":"10.1109\/SFFCS.1999.814600"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1137\/0710032"},{"key":"R16","unstructured":"K. Goto and R. van de Geijn,\n                      On reducing TLB misses in matrix multiplication\n                      , Technical report TR-2002-55, Department of Computer Sciences, University of Texas at Austin, Austin, TX, 2002, FLAME Working Note #9."},{"key":"R17","unstructured":"L. Grigori, E. Boman, S. Donfack, and T. A. Davis,\n                      Hypergraph-based unsymmetric nested dissection ordering for sparse LU factorization\n                      , Technical report 6520, INRIA Saclay, Orsay, France, April 2008."},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1080\/17445760601122084"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827596300656"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1016\/S0098-1354(99)00314-2"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"E.J. Im and K. A. Yelick,\n                      Optimizing sparse matrix\u2013vector multiplication for register reuse in SPARSITY\n                      , in Proceedings of the International Conference on Computational Science, Part I, Lecture Notes in Computer Science 2073, 2001, pp. 127\u2013136.","DOI":"10.1007\/3-540-45545-0_22"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"G. Karypis and V. Kumar,\n                      Multilevel k-way hypergraph partitioning\n                      , in Proceedings of the 36th ACM\/IEEE Conference on Design Automation, ACM Press, New York, 1999, pp. 343\u2013348.","DOI":"10.1145\/309847.309954"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2005.09.005"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1145\/324133.324140"},{"key":"R26","unstructured":"J. Koster,\n                      Parallel templates for numerical linear algebra, a high-performance computation library\n                      , Master's Thesis, Department of Mathematics, Utrecht University, 2002."},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1007\/s006070070032"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"A. N. Langville and C. D. Meyer,\n                      Google's PageRank and Beyond: The Science of Search Engine Rankings\n                      , Princeton University Press, Princeton, NJ, 2006.","DOI":"10.1515\/9781400830329"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"T. Lengauer,\n                      Combinatorial Algorithms for Integrated Circuit Layout\n                      , John Wiley and Sons, Chichester, UK, 1990.","DOI":"10.1007\/978-3-322-92106-2"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1007\/s00200-007-0038-9"},{"key":"R31","doi-asserted-by":"crossref","unstructured":"A. Pinar and M. T. Heath,\n                      Improving performance of sparse matrix-vector multiplication\n                      , in Proceedings Supercomputing 1999, ACM Press, New York, 1999, p. 30.","DOI":"10.1145\/331532.331562"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1177\/1094342004041294"},{"key":"R33","doi-asserted-by":"crossref","unstructured":"M. M. Strout and P. D. Hovland,\n                      Metrics and models for reordering transformations\n                      , in Proceedings of the 2004 Workshop on Memory System Performance, ACM Press, New York, 2004, pp. 23\u201334.","DOI":"10.1145\/1065895.1065899"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1147\/rd.416.0711"},{"key":"R35","doi-asserted-by":"crossref","unstructured":"A. Trifunovic and W. J. Knottenbelt,\n                      \n                        A parallel algorithm for multilevel\n                        k\n                        -way hypergraph partitioning\n                      \n                      , in Proceedings of the 3rd International Symposium on Parallel and Distributed Computing, IEEE Press, Los Alamitos, CA, 2004, pp. 114\u2013121.","DOI":"10.1109\/ISPDC.2004.6"},{"key":"R36","unstructured":"R. van der Pas,\n                      Memory hierarchy in cache-based systems\n                      , Tech. Report 817-0742-10, Sun Microsystems, Inc., Santa Clara, CA, 2002."},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1006\/jcph.2002.7095"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144502409019"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1088\/1742-6596\/16\/1\/071"},{"key":"R40","doi-asserted-by":"crossref","unstructured":"R. W. Vuduc and H.J. Moon,\n                      Fast sparse matrix-vector multiplication by exploiting variable block structure\n                      , in High Performance Computing and Communications 2005, Lecture Notes in Computer Science 3726, 2005, pp. 807\u2013816.","DOI":"10.1007\/11557654_91"},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1002\/spe.626"},{"key":"R42","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(00)00087-9"},{"key":"R43","doi-asserted-by":"crossref","unstructured":"J. B. White, III and P. Sadayappan,\n                      On improving the performance of sparse matrix-vector multiplication\n                      , in Proceedings of the 4th International Conference on High-Performance Computing, IEEE Press, Los Alamitos, CA, 1997, pp. 66\u201371.","DOI":"10.1109\/HIPC.1997.634472"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/080733243","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:48:25Z","timestamp":1787334505000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/080733243"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1]]},"references-count":43,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2009,1]]}},"alternative-id":["10.1137\/080733243"],"URL":"https:\/\/doi.org\/10.1137\/080733243","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,1]]}}}