BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Peter James Ahrens (MIT) DTSTART:20210507T160000Z DTEND:20210507T170000Z DTSTAMP:20260423T005824Z UID:CRIBB/7 DESCRIPTION:Title: On Optimal Partitioning for Variable Block Row Format\nby Peter James Ah rens (MIT) as part of Computational Research in Boston and Beyond Seminar (CRIBB)\n\nLecture held in Virtual.\n\nAbstract\nThe Variable Block Row (V BR) format is an influential blocked sparse matrix format designed for mat rices with shared sparsity structure between adjacent rows and columns. VB R groups adjacent rows and columns\, storing the resulting blocks that con tain nonzeros in a dense format. This reduces the memory footprint and en ables optimizations such as register blocking and instruction-level parall elism. Existing approaches use heuristics to determine which rows and col umns should be grouped together. We show that finding the optimal groupin g of rows and columns for VBR is NP-hard under several reasonable cost mod els. In light of this finding\, we propose a 1-dimensional variant of VBR\ , called 1D-VBR\, which achieves better performance than VBR by only group ing rows. We describe detailed cost models for runtime and memory consump tion. Then\, we describe a linear time dynamic programming solution for o ptimally grouping the rows for 1D-VBR format. We extend our algorithm to p roduce a heuristic VBR partitioner which alternates between optimally part itioning rows and columns\, assuming the columns or rows to be fixed\, res pectively. Our alternating heuristic produces VBR matrices with the smalle st memory footprint of any partitioner we tested.\n\n ZOOM MEETING info:\n\n https:/ /mit.zoom.us/j/96155042770\n\n Meeting ID : 961 5504 2770\n LOCATION:https://researchseminars.org/talk/CRIBB/7/ END:VEVENT END:VCALENDAR