Entropy Maximization in Sparse Matrix by Vector Multiplication ($\max_E SpMV$) Article Swipe
Paolo D’Alberto
,
Abhishek Jain
,
Ismail Bustany
,
Henri Fraisse
,
Mansimran Benipal
·
YOU?
·
· 2023
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2308.00106
YOU?
·
· 2023
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2308.00106
The peak performance of any SpMV depends primarily on the available memory bandwidth and its effective use. GPUs, ASICs, and new FPGAs have higher and higher bandwidth; however, for large scale and highly sparse matrices, SpMV is still a hard problem because of its random access pattern and workload imbalance. Here, we show how to turn randomness to our advantage. We propose a matrix permutation pre-processing step that aims to maximize the entropy of the distribution of the nonzero elements. We seek any permutation that uniformly distributes the non-zero elements' distribution, thereby generating a SpMV problem that is amenable to work load balancing or to speed up sort algorithms. We conjecture these permutations would be most effective for matrices with no dense rows or columns and, as in preconditioning, when the matrix is reused. We shall show that entropy maximization is an optimization that any architecture may take advantage although in different ways. Most importantly, any developer can consider and deploy. We shall present cases where we can improve performance by 15\% on AMD-based (GPU-CPU) systems.
Related Topics
Concepts
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2308.00106
- https://arxiv.org/pdf/2308.00106
- OA Status
- green
- Cited By
- 2
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4385507573
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4385507573Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2308.00106Digital Object Identifier
- Title
-
Entropy Maximization in Sparse Matrix by Vector Multiplication ($\max_E SpMV$)Work title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2023Year of publication
- Publication date
-
2023-07-24Full publication date if available
- Authors
-
Paolo D’Alberto, Abhishek Jain, Ismail Bustany, Henri Fraisse, Mansimran BenipalList of authors in order
- Landing page
-
https://arxiv.org/abs/2308.00106Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2308.00106Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://arxiv.org/pdf/2308.00106Direct OA link when available
- Concepts
-
Computer science, Parallel computing, Maximization, Sparse matrix, CUDA, Mathematics, Gaussian, Mathematical optimization, Quantum mechanics, PhysicsTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
2Total citation count in OpenAlex
- Citations by year (recent)
-
2025: 1, 2024: 1Per-year citation counts (last 5 years)
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4385507573 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2308.00106 |
| ids.doi | https://doi.org/10.48550/arxiv.2308.00106 |
| ids.openalex | https://openalex.org/W4385507573 |
| fwci | |
| type | preprint |
| title | Entropy Maximization in Sparse Matrix by Vector Multiplication ($\max_E SpMV$) |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T11321 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.9983000159263611 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1705 |
| topics[0].subfield.display_name | Computer Networks and Communications |
| topics[0].display_name | Error Correcting Code Techniques |
| topics[1].id | https://openalex.org/T10054 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.998199999332428 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1708 |
| topics[1].subfield.display_name | Hardware and Architecture |
| topics[1].display_name | Parallel Computing and Optimization Techniques |
| topics[2].id | https://openalex.org/T11612 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.9970999956130981 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1702 |
| topics[2].subfield.display_name | Artificial Intelligence |
| topics[2].display_name | Stochastic Gradient Optimization Techniques |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C41008148 |
| concepts[0].level | 0 |
| concepts[0].score | 0.7555773258209229 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[0].display_name | Computer science |
| concepts[1].id | https://openalex.org/C173608175 |
| concepts[1].level | 1 |
| concepts[1].score | 0.6842724680900574 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q232661 |
| concepts[1].display_name | Parallel computing |
| concepts[2].id | https://openalex.org/C2776330181 |
| concepts[2].level | 2 |
| concepts[2].score | 0.46703454852104187 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q18358244 |
| concepts[2].display_name | Maximization |
| concepts[3].id | https://openalex.org/C56372850 |
| concepts[3].level | 3 |
| concepts[3].score | 0.4660538136959076 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q1050404 |
| concepts[3].display_name | Sparse matrix |
| concepts[4].id | https://openalex.org/C2778119891 |
| concepts[4].level | 2 |
| concepts[4].score | 0.4271661341190338 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q477690 |
| concepts[4].display_name | CUDA |
| concepts[5].id | https://openalex.org/C33923547 |
| concepts[5].level | 0 |
| concepts[5].score | 0.18683794140815735 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[5].display_name | Mathematics |
| concepts[6].id | https://openalex.org/C163716315 |
| concepts[6].level | 2 |
| concepts[6].score | 0.17454379796981812 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q901177 |
| concepts[6].display_name | Gaussian |
| concepts[7].id | https://openalex.org/C126255220 |
| concepts[7].level | 1 |
| concepts[7].score | 0.12790197134017944 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q141495 |
| concepts[7].display_name | Mathematical optimization |
| concepts[8].id | https://openalex.org/C62520636 |
| concepts[8].level | 1 |
| concepts[8].score | 0.0 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q944 |
| concepts[8].display_name | Quantum mechanics |
| concepts[9].id | https://openalex.org/C121332964 |
| concepts[9].level | 0 |
| concepts[9].score | 0.0 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q413 |
| concepts[9].display_name | Physics |
| keywords[0].id | https://openalex.org/keywords/computer-science |
| keywords[0].score | 0.7555773258209229 |
| keywords[0].display_name | Computer science |
| keywords[1].id | https://openalex.org/keywords/parallel-computing |
| keywords[1].score | 0.6842724680900574 |
| keywords[1].display_name | Parallel computing |
| keywords[2].id | https://openalex.org/keywords/maximization |
| keywords[2].score | 0.46703454852104187 |
| keywords[2].display_name | Maximization |
| keywords[3].id | https://openalex.org/keywords/sparse-matrix |
| keywords[3].score | 0.4660538136959076 |
| keywords[3].display_name | Sparse matrix |
| keywords[4].id | https://openalex.org/keywords/cuda |
| keywords[4].score | 0.4271661341190338 |
| keywords[4].display_name | CUDA |
| keywords[5].id | https://openalex.org/keywords/mathematics |
| keywords[5].score | 0.18683794140815735 |
| keywords[5].display_name | Mathematics |
| keywords[6].id | https://openalex.org/keywords/gaussian |
| keywords[6].score | 0.17454379796981812 |
| keywords[6].display_name | Gaussian |
| keywords[7].id | https://openalex.org/keywords/mathematical-optimization |
| keywords[7].score | 0.12790197134017944 |
| keywords[7].display_name | Mathematical optimization |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:2308.00106 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306400194 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | arXiv (Cornell University) |
| locations[0].source.host_organization | https://openalex.org/I205783295 |
| locations[0].source.host_organization_name | Cornell University |
| locations[0].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[0].license | |
| locations[0].pdf_url | https://arxiv.org/pdf/2308.00106 |
| locations[0].version | submittedVersion |
| locations[0].raw_type | |
| locations[0].license_id | |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | http://arxiv.org/abs/2308.00106 |
| locations[1].id | doi:10.48550/arxiv.2308.00106 |
| locations[1].is_oa | True |
| locations[1].source.id | https://openalex.org/S4306400194 |
| locations[1].source.issn | |
| locations[1].source.type | repository |
| locations[1].source.is_oa | True |
| locations[1].source.issn_l | |
| locations[1].source.is_core | False |
| locations[1].source.is_in_doaj | False |
| locations[1].source.display_name | arXiv (Cornell University) |
| locations[1].source.host_organization | https://openalex.org/I205783295 |
| locations[1].source.host_organization_name | Cornell University |
| locations[1].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[1].license | public-domain |
| locations[1].pdf_url | |
| locations[1].version | |
| locations[1].raw_type | article |
| locations[1].license_id | https://openalex.org/licenses/public-domain |
| locations[1].is_accepted | False |
| locations[1].is_published | |
| locations[1].raw_source_name | |
| locations[1].landing_page_url | https://doi.org/10.48550/arxiv.2308.00106 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5052262436 |
| authorships[0].author.orcid | https://orcid.org/0000-0002-1584-1270 |
| authorships[0].author.display_name | Paolo D’Alberto |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | D'Alberto, Paolo |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5100661347 |
| authorships[1].author.orcid | https://orcid.org/0000-0002-3572-7643 |
| authorships[1].author.display_name | Abhishek Jain |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Jain, Abhishek |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | https://openalex.org/A5080828363 |
| authorships[2].author.orcid | https://orcid.org/0000-0002-7099-1546 |
| authorships[2].author.display_name | Ismail Bustany |
| authorships[2].author_position | middle |
| authorships[2].raw_author_name | Bustany, Ismail |
| authorships[2].is_corresponding | False |
| authorships[3].author.id | https://openalex.org/A5034948929 |
| authorships[3].author.orcid | |
| authorships[3].author.display_name | Henri Fraisse |
| authorships[3].author_position | middle |
| authorships[3].raw_author_name | Fraisse, Henri |
| authorships[3].is_corresponding | False |
| authorships[4].author.id | https://openalex.org/A5001386920 |
| authorships[4].author.orcid | |
| authorships[4].author.display_name | Mansimran Benipal |
| authorships[4].author_position | last |
| authorships[4].raw_author_name | Benipal, Mansimran |
| authorships[4].is_corresponding | False |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://arxiv.org/pdf/2308.00106 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | Entropy Maximization in Sparse Matrix by Vector Multiplication ($\max_E SpMV$) |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T11321 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.9983000159263611 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1705 |
| primary_topic.subfield.display_name | Computer Networks and Communications |
| primary_topic.display_name | Error Correcting Code Techniques |
| related_works | https://openalex.org/W3213381848, https://openalex.org/W2005148983, https://openalex.org/W2017587301, https://openalex.org/W2012954338, https://openalex.org/W2096672917, https://openalex.org/W2392023973, https://openalex.org/W2939411666, https://openalex.org/W2009169896, https://openalex.org/W2052993554, https://openalex.org/W2046125858 |
| cited_by_count | 2 |
| counts_by_year[0].year | 2025 |
| counts_by_year[0].cited_by_count | 1 |
| counts_by_year[1].year | 2024 |
| counts_by_year[1].cited_by_count | 1 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:arXiv.org:2308.00106 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306400194 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | True |
| best_oa_location.source.issn_l | |
| best_oa_location.source.is_core | False |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | arXiv (Cornell University) |
| best_oa_location.source.host_organization | https://openalex.org/I205783295 |
| best_oa_location.source.host_organization_name | Cornell University |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| best_oa_location.license | |
| best_oa_location.pdf_url | https://arxiv.org/pdf/2308.00106 |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | |
| best_oa_location.license_id | |
| best_oa_location.is_accepted | False |
| best_oa_location.is_published | False |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | http://arxiv.org/abs/2308.00106 |
| primary_location.id | pmh:oai:arXiv.org:2308.00106 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306400194 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | arXiv (Cornell University) |
| primary_location.source.host_organization | https://openalex.org/I205783295 |
| primary_location.source.host_organization_name | Cornell University |
| primary_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| primary_location.license | |
| primary_location.pdf_url | https://arxiv.org/pdf/2308.00106 |
| primary_location.version | submittedVersion |
| primary_location.raw_type | |
| primary_location.license_id | |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | http://arxiv.org/abs/2308.00106 |
| publication_date | 2023-07-24 |
| publication_year | 2023 |
| referenced_works_count | 0 |
| abstract_inverted_index.a | 38, 62, 93 |
| abstract_inverted_index.We | 60, 80, 109, 134, 161 |
| abstract_inverted_index.an | 141 |
| abstract_inverted_index.as | 126 |
| abstract_inverted_index.be | 114 |
| abstract_inverted_index.by | 170 |
| abstract_inverted_index.in | 127, 150 |
| abstract_inverted_index.is | 36, 97, 132, 140 |
| abstract_inverted_index.no | 120 |
| abstract_inverted_index.of | 3, 42, 73, 76 |
| abstract_inverted_index.on | 8, 172 |
| abstract_inverted_index.or | 103, 123 |
| abstract_inverted_index.to | 54, 57, 69, 99, 104 |
| abstract_inverted_index.up | 106 |
| abstract_inverted_index.we | 51, 166 |
| abstract_inverted_index.The | 0 |
| abstract_inverted_index.and | 13, 19, 24, 31, 47, 159 |
| abstract_inverted_index.any | 4, 82, 144, 155 |
| abstract_inverted_index.can | 157, 167 |
| abstract_inverted_index.for | 28, 117 |
| abstract_inverted_index.how | 53 |
| abstract_inverted_index.its | 14, 43 |
| abstract_inverted_index.may | 146 |
| abstract_inverted_index.new | 20 |
| abstract_inverted_index.our | 58 |
| abstract_inverted_index.the | 9, 71, 74, 77, 87, 130 |
| abstract_inverted_index.15\% | 171 |
| abstract_inverted_index.Most | 153 |
| abstract_inverted_index.SpMV | 5, 35, 94 |
| abstract_inverted_index.aims | 68 |
| abstract_inverted_index.and, | 125 |
| abstract_inverted_index.hard | 39 |
| abstract_inverted_index.have | 22 |
| abstract_inverted_index.load | 101 |
| abstract_inverted_index.most | 115 |
| abstract_inverted_index.peak | 1 |
| abstract_inverted_index.rows | 122 |
| abstract_inverted_index.seek | 81 |
| abstract_inverted_index.show | 52, 136 |
| abstract_inverted_index.sort | 107 |
| abstract_inverted_index.step | 66 |
| abstract_inverted_index.take | 147 |
| abstract_inverted_index.that | 67, 84, 96, 137, 143 |
| abstract_inverted_index.turn | 55 |
| abstract_inverted_index.use. | 16 |
| abstract_inverted_index.when | 129 |
| abstract_inverted_index.with | 119 |
| abstract_inverted_index.work | 100 |
| abstract_inverted_index.FPGAs | 21 |
| abstract_inverted_index.GPUs, | 17 |
| abstract_inverted_index.Here, | 50 |
| abstract_inverted_index.cases | 164 |
| abstract_inverted_index.dense | 121 |
| abstract_inverted_index.large | 29 |
| abstract_inverted_index.scale | 30 |
| abstract_inverted_index.shall | 135, 162 |
| abstract_inverted_index.speed | 105 |
| abstract_inverted_index.still | 37 |
| abstract_inverted_index.these | 111 |
| abstract_inverted_index.ways. | 152 |
| abstract_inverted_index.where | 165 |
| abstract_inverted_index.would | 113 |
| abstract_inverted_index.ASICs, | 18 |
| abstract_inverted_index.access | 45 |
| abstract_inverted_index.higher | 23, 25 |
| abstract_inverted_index.highly | 32 |
| abstract_inverted_index.matrix | 63, 131 |
| abstract_inverted_index.memory | 11 |
| abstract_inverted_index.random | 44 |
| abstract_inverted_index.sparse | 33 |
| abstract_inverted_index.because | 41 |
| abstract_inverted_index.columns | 124 |
| abstract_inverted_index.depends | 6 |
| abstract_inverted_index.deploy. | 160 |
| abstract_inverted_index.entropy | 72, 138 |
| abstract_inverted_index.improve | 168 |
| abstract_inverted_index.nonzero | 78 |
| abstract_inverted_index.pattern | 46 |
| abstract_inverted_index.present | 163 |
| abstract_inverted_index.problem | 40, 95 |
| abstract_inverted_index.propose | 61 |
| abstract_inverted_index.reused. | 133 |
| abstract_inverted_index.thereby | 91 |
| abstract_inverted_index.although | 149 |
| abstract_inverted_index.amenable | 98 |
| abstract_inverted_index.consider | 158 |
| abstract_inverted_index.however, | 27 |
| abstract_inverted_index.matrices | 118 |
| abstract_inverted_index.maximize | 70 |
| abstract_inverted_index.non-zero | 88 |
| abstract_inverted_index.systems. | 175 |
| abstract_inverted_index.workload | 48 |
| abstract_inverted_index.(GPU-CPU) | 174 |
| abstract_inverted_index.AMD-based | 173 |
| abstract_inverted_index.advantage | 148 |
| abstract_inverted_index.available | 10 |
| abstract_inverted_index.balancing | 102 |
| abstract_inverted_index.bandwidth | 12 |
| abstract_inverted_index.developer | 156 |
| abstract_inverted_index.different | 151 |
| abstract_inverted_index.effective | 15, 116 |
| abstract_inverted_index.elements' | 89 |
| abstract_inverted_index.elements. | 79 |
| abstract_inverted_index.matrices, | 34 |
| abstract_inverted_index.primarily | 7 |
| abstract_inverted_index.uniformly | 85 |
| abstract_inverted_index.advantage. | 59 |
| abstract_inverted_index.bandwidth; | 26 |
| abstract_inverted_index.conjecture | 110 |
| abstract_inverted_index.generating | 92 |
| abstract_inverted_index.imbalance. | 49 |
| abstract_inverted_index.randomness | 56 |
| abstract_inverted_index.algorithms. | 108 |
| abstract_inverted_index.distributes | 86 |
| abstract_inverted_index.performance | 2, 169 |
| abstract_inverted_index.permutation | 64, 83 |
| abstract_inverted_index.architecture | 145 |
| abstract_inverted_index.distribution | 75 |
| abstract_inverted_index.importantly, | 154 |
| abstract_inverted_index.maximization | 139 |
| abstract_inverted_index.optimization | 142 |
| abstract_inverted_index.permutations | 112 |
| abstract_inverted_index.distribution, | 90 |
| abstract_inverted_index.pre-processing | 65 |
| abstract_inverted_index.preconditioning, | 128 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 5 |
| citation_normalized_percentile |