{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/45518"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/45518","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Sparse matrix-vector multiplication by specialization","abstract":"Program specialization is the process of generating optimized programs based on available inputs. It is particularly applicable when some input data are used repeatedly while other input data vary. Specialization can be employed at compile-time as well as at run-time, depending on when the inputs become available. This technique has the potential of generating highly efficient codes, at the expense of the overheads of the run-time code generation. In this thesis, the potential for using specialization to obtain speed-ups in the very common numerical procedure of sparse matrix-vector multiplication, in the case where a single matrix is to be multiplied by many vectors, is explored. The main objective is the evaluation of the speed-ups that can be obtained with program specialization without considering the overheads of the code generation. Tests were prepared to probe several sparse matrix-vector multiplication methods using fifty-three sparse matrices obtained from the Matrix Market and the University of Florida Sparse Matrix Collection and run on four target platforms. In this investigation, only sequential execution was tested. The research found that two of the methods were more frequently faster that all the other methods combined and that the speed-up of these methods was significant when compared to a variant of the standard compressed sparse rows (CSR) method.","abstract_html":"Program specialization is the process of generating optimized programs based on available inputs. It is particularly applicable when some input data are used repeatedly while other input data vary. Specialization can be employed at compile-time as well as at run-time, depending on when the inputs become available. This technique has the potential of generating highly efficient codes, at the expense of the overheads of the run-time code generation. In this thesis, the potential for using specialization to obtain speed-ups in the very common numerical procedure of sparse matrix-vector multiplication, in the case where a single matrix is to be multiplied by many vectors, is explored. The main objective is the evaluation of the speed-ups that can be obtained with program specialization without considering the overheads of the code generation. Tests were prepared to probe several sparse matrix-vector multiplication methods using fifty-three sparse matrices obtained from the Matrix Market and the University of Florida Sparse Matrix Collection and run on four target platforms. In this investigation, only sequential execution was tested. The research found that two of the methods were more frequently faster that all the other methods combined and that the speed-up of these methods was significant when compared to a variant of the standard compressed sparse rows (CSR) method.","abstract_has_math":false,"creators":["Black Silva, Edgar"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Kamin, Samuel N."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2013,"date_issued":"2013-08-22T16:42:56Z","date_published":"2013-08-22T16:42:56Z","updated_at":"2026-07-22T22:25:36Z","subjects":["sparse matrix-vector multiplication","program specialization","run-time code generation."],"languages":["en"],"rights":["Copyright 2013 Edgar Black Silva"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/45518","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Kamin, Samuel N."]},{"key":"dc:creator","label":"Author","values":["Black Silva, Edgar"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2013-08-22T16:42:56Z","2013-08"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["sparse matrix-vector multiplication","program specialization","run-time code generation."]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2013 Edgar Black Silva"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/45518"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Program specialization is the process of generating optimized programs based on available inputs. It is particularly applicable when some input data are used repeatedly while other input data vary. Specialization can be employed at compile-time as well as at run-time, depending on when the inputs become available. This technique has the potential of generating highly efficient codes, at the expense of the overheads of the run-time code generation. In this thesis, the potential for using specialization to obtain speed-ups in the very common numerical procedure of sparse matrix-vector multiplication, in the case where a single matrix is to be multiplied by many vectors, is explored. The main objective is the evaluation of the speed-ups that can be obtained with program specialization without considering the overheads of the code generation. Tests were prepared to probe several sparse matrix-vector multiplication methods using fifty-three sparse matrices obtained from the Matrix Market and the University of Florida Sparse Matrix Collection and run on four target platforms. In this investigation, only sequential execution was tested. The research found that two of the methods were more frequently faster that all the other methods combined and that the speed-up of these methods was significant when compared to a variant of the standard compressed sparse rows (CSR) method.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2013-07-12T18:38:16Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Black_Edgar.pdf: 1752894 bytes, checksum: 6e57ed3de4dae640f2b2c89adae0de36 (MD5)","Made available in DSpace on 2013-08-22T16:42:56Z (GMT). No. of bitstreams: 2 Edgar_Black Silva.pdf: 1752894 bytes, checksum: 6e57ed3de4dae640f2b2c89adae0de36 (MD5) license.txt: 4067 bytes, checksum: 7e07a4a4efd2ef112dee8666aad21504 (MD5)"]},{"key":"dc:title","label":"Title","values":["Sparse matrix-vector multiplication by specialization"]}]}],"canonical_facts":{"dc:contributor":["Kamin, Samuel N."],"dc:creator":["Black Silva, Edgar"],"dc:date":["2013-08-22T16:42:56Z","2013-08"],"dc:description":["Program specialization is the process of generating optimized programs based on available inputs. It is particularly applicable when some input data are used repeatedly while other input data vary. Specialization can be employed at compile-time as well as at run-time, depending on when the inputs become available. This technique has the potential of generating highly efficient codes, at the expense of the overheads of the run-time code generation. In this thesis, the potential for using specialization to obtain speed-ups in the very common numerical procedure of sparse matrix-vector multiplication, in the case where a single matrix is to be multiplied by many vectors, is explored. The main objective is the evaluation of the speed-ups that can be obtained with program specialization without considering the overheads of the code generation. Tests were prepared to probe several sparse matrix-vector multiplication methods using fifty-three sparse matrices obtained from the Matrix Market and the University of Florida Sparse Matrix Collection and run on four target platforms. In this investigation, only sequential execution was tested. The research found that two of the methods were more frequently faster that all the other methods combined and that the speed-up of these methods was significant when compared to a variant of the standard compressed sparse rows (CSR) method.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2013-07-12T18:38:16Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Black_Edgar.pdf: 1752894 bytes, checksum: 6e57ed3de4dae640f2b2c89adae0de36 (MD5)","Made available in DSpace on 2013-08-22T16:42:56Z (GMT). No. of bitstreams: 2 Edgar_Black Silva.pdf: 1752894 bytes, checksum: 6e57ed3de4dae640f2b2c89adae0de36 (MD5) license.txt: 4067 bytes, checksum: 7e07a4a4efd2ef112dee8666aad21504 (MD5)"],"dc:identifier":["http://hdl.handle.net/2142/45518"],"dc:language":["en"],"dc:rights":["Copyright 2013 Edgar Black Silva"],"dc:subject":["sparse matrix-vector multiplication","program specialization","run-time code generation."],"dc:title":["Sparse matrix-vector multiplication by specialization"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:36Z"}