{"corpus_id":14535142,"paper_sha":"2f91a872ee65ce2b2358ced38e5729fa4cdfef7e","doi":"10.1137/S1064827502401953","arxiv_id":null,"pmid":null,"pmcid":null,"mag_id":1996309908,"dblp_id":"journals/siamsc/AykanatPC04","acl_id":null,"title":"Permuting Sparse Rectangular Matrices into Block-Diagonal Form","year":2004,"publication_date":"2004-01-01","venue":"SIAM Journal on Scientific Computing","journal":{"name":"SIAM J. Sci. Comput.","pages":"1860-1879","volume":"25"},"journal_issn":null,"journal_title":null,"publication_types":["JournalArticle"],"pubmed_pub_types":null,"s2_fields_of_study":["Mathematics","Computer Science"],"reference_count":67,"citation_count":160,"influential_citation_count":13,"is_open_access":true,"arxiv_categories":null,"arxiv_license":null,"arxiv_journal_ref":null,"mesh_headings":null,"chemicals":null,"comments_corrections":null,"source_flags":1,"s2_open_access_pdf_url":"https://digital.library.unt.edu/ark:/67531/metadc786866/m2/1/high_res_d/826102.pdf","s2_open_access_landing_url":"https://www.semanticscholar.org/paper/2f91a872ee65ce2b2358ced38e5729fa4cdfef7e","s2_open_access_license":"other-oa","s2_open_access_status":"GREEN","pmc_open_access_pdf_url":null,"pmc_open_access_landing_url":null,"pmc_open_access_license":null,"pmc_open_access_status":null,"unpaywall_open_access_pdf_url":null,"unpaywall_open_access_landing_url":null,"unpaywall_open_access_license":null,"unpaywall_open_access_status":null,"abstract":"We investigate the problem of permuting a sparse rectangular matrix into block-diagonal form. Block-diagonal form of a matrix grants an inherent parallelism for solving the deriving problem, as recently investigated in the context of mathematical programming, LU factorization, and QR factorization. To represent the nonzero structure of a matrix, we propose bipartite graph and hypergraph models that reduce the permutation problem to those of graph partitioning by vertex separator and hypergraph partitioning, respectively. Our experiments on a wide range of matrices, using the state-of-the-art graph and hypergraph partitioning tools MeTiS and PaToH\\@, revealed that the proposed methods yield very effective solutions both in terms of solution quality and runtime.","claims":[{"public_id":"cl_f4ecca53800bb6db00d487ae07c4368b","status":"active","text":"Bipartite graph and hypergraph models reduce the sparse rectangular matrix permutation problem to graph partitioning by vertex separator and hypergraph partitioning, respectively.","confidence":0.95,"contributors":[{"id":171,"public_id":"b9tnx83g25","public_label":"eunsjani (b9tnx83g25)","roles":["extraction"],"url":"https://sah.borca.ai/u/b9tnx83g25"},{"id":2,"public_id":"4715169a40","public_label":"AK (4715169a40)","roles":["review"],"url":"https://sah.borca.ai/u/4715169a40"},{"id":17,"public_id":"322360f1c1","public_label":"Killer Whale (322360f1c1)","roles":["review"],"url":"https://sah.borca.ai/u/322360f1c1"}],"url":"https://sah.borca.ai/claims/cl_f4ecca53800bb6db00d487ae07c4368b"},{"public_id":"cl_b65c233f13b6d44d9436ecbc60727daa","status":"active","text":"Experiments using MeTiS and PaToH on a wide range of matrices show the proposed permutation methods yield very effective solutions in both solution quality and runtime.","confidence":0.92,"contributors":[{"id":171,"public_id":"b9tnx83g25","public_label":"eunsjani (b9tnx83g25)","roles":["extraction"],"url":"https://sah.borca.ai/u/b9tnx83g25"},{"id":2,"public_id":"4715169a40","public_label":"AK (4715169a40)","roles":["review"],"url":"https://sah.borca.ai/u/4715169a40"},{"id":17,"public_id":"322360f1c1","public_label":"Killer Whale (322360f1c1)","roles":["review"],"url":"https://sah.borca.ai/u/322360f1c1"}],"url":"https://sah.borca.ai/claims/cl_b65c233f13b6d44d9436ecbc60727daa"}],"concepts":[{"public_id":"co_048bfddefb33d1deaeb2476769209653","status":"active","name":"block-diagonal form","description":"A matrix structure in which nonzero entries are confined to diagonal blocks, enabling inherent parallelism for derived problems.","types":["matrix structure"],"aliases":[],"contributors":[{"id":171,"public_id":"b9tnx83g25","public_label":"eunsjani (b9tnx83g25)","roles":["extraction"],"url":"https://sah.borca.ai/u/b9tnx83g25"},{"id":2,"public_id":"4715169a40","public_label":"AK (4715169a40)","roles":["review"],"url":"https://sah.borca.ai/u/4715169a40"},{"id":17,"public_id":"322360f1c1","public_label":"Killer Whale (322360f1c1)","roles":["review"],"url":"https://sah.borca.ai/u/322360f1c1"}],"url":"https://sah.borca.ai/concepts/co_048bfddefb33d1deaeb2476769209653"},{"public_id":"co_0e2885bfd4416adf87be45520f1ce003","status":"active","name":"MeTiS","description":"A state-of-the-art graph partitioning tool used in experiments to evaluate the bipartite graph model approach.","types":["software tool"],"aliases":[],"contributors":[{"id":171,"public_id":"b9tnx83g25","public_label":"eunsjani (b9tnx83g25)","roles":["extraction"],"url":"https://sah.borca.ai/u/b9tnx83g25"},{"id":2,"public_id":"4715169a40","public_label":"AK (4715169a40)","roles":["review"],"url":"https://sah.borca.ai/u/4715169a40"},{"id":17,"public_id":"322360f1c1","public_label":"Killer Whale (322360f1c1)","roles":["review"],"url":"https://sah.borca.ai/u/322360f1c1"}],"url":"https://sah.borca.ai/concepts/co_0e2885bfd4416adf87be45520f1ce003"},{"public_id":"co_23ed31777f04a8b6bcfc52f1e7a919cf","status":"active","name":"sparse rectangular matrix permutation","description":"The problem of reordering the rows and columns of a sparse rectangular matrix to achieve block-diagonal structure.","types":["problem"],"aliases":[],"contributors":[{"id":171,"public_id":"b9tnx83g25","public_label":"eunsjani (b9tnx83g25)","roles":["extraction"],"url":"https://sah.borca.ai/u/b9tnx83g25"},{"id":2,"public_id":"4715169a40","public_label":"AK (4715169a40)","roles":["review"],"url":"https://sah.borca.ai/u/4715169a40"},{"id":17,"public_id":"322360f1c1","public_label":"Killer Whale (322360f1c1)","roles":["review"],"url":"https://sah.borca.ai/u/322360f1c1"}],"url":"https://sah.borca.ai/concepts/co_23ed31777f04a8b6bcfc52f1e7a919cf"},{"public_id":"co_2755e11f59e2f6eedda74904dded6aaa","status":"active","name":"bipartite graph model","description":"A graph model proposed in this paper to represent the nonzero structure of a matrix for reducing the permutation problem to graph partitioning by vertex separator.","types":["method","model"],"aliases":[],"contributors":[{"id":171,"public_id":"b9tnx83g25","public_label":"eunsjani (b9tnx83g25)","roles":["extraction"],"url":"https://sah.borca.ai/u/b9tnx83g25"},{"id":2,"public_id":"4715169a40","public_label":"AK (4715169a40)","roles":["review"],"url":"https://sah.borca.ai/u/4715169a40"},{"id":17,"public_id":"322360f1c1","public_label":"Killer Whale (322360f1c1)","roles":["review"],"url":"https://sah.borca.ai/u/322360f1c1"}],"url":"https://sah.borca.ai/concepts/co_2755e11f59e2f6eedda74904dded6aaa"},{"public_id":"co_5488be5e2c18b6c499588167ef70b4ed","status":"active","name":"graph partitioning by vertex separator","description":"A graph partitioning technique to which the bipartite graph model reduces the sparse matrix permutation problem.","types":["method"],"aliases":[],"contributors":[{"id":171,"public_id":"b9tnx83g25","public_label":"eunsjani (b9tnx83g25)","roles":["extraction"],"url":"https://sah.borca.ai/u/b9tnx83g25"},{"id":2,"public_id":"4715169a40","public_label":"AK (4715169a40)","roles":["review"],"url":"https://sah.borca.ai/u/4715169a40"},{"id":17,"public_id":"322360f1c1","public_label":"Killer Whale (322360f1c1)","roles":["review"],"url":"https://sah.borca.ai/u/322360f1c1"}],"url":"https://sah.borca.ai/concepts/co_5488be5e2c18b6c499588167ef70b4ed"},{"public_id":"co_5adc0ac34df7270e0deae29643bd1bf9","status":"active","name":"hypergraph partitioning","description":"A partitioning method for hypergraphs to which the hypergraph model reduces the sparse matrix permutation problem.","types":["method"],"aliases":[],"contributors":[{"id":171,"public_id":"b9tnx83g25","public_label":"eunsjani (b9tnx83g25)","roles":["extraction"],"url":"https://sah.borca.ai/u/b9tnx83g25"},{"id":2,"public_id":"4715169a40","public_label":"AK (4715169a40)","roles":["review"],"url":"https://sah.borca.ai/u/4715169a40"},{"id":17,"public_id":"322360f1c1","public_label":"Killer Whale (322360f1c1)","roles":["review"],"url":"https://sah.borca.ai/u/322360f1c1"}],"url":"https://sah.borca.ai/concepts/co_5adc0ac34df7270e0deae29643bd1bf9"},{"public_id":"co_7148d5da2129494aaa3d95eba56982c0","status":"active","name":"mathematical programming","description":"An application domain in which block-diagonal permutation of matrices grants inherent parallelism.","types":["application domain"],"aliases":[],"contributors":[{"id":171,"public_id":"b9tnx83g25","public_label":"eunsjani (b9tnx83g25)","roles":["extraction"],"url":"https://sah.borca.ai/u/b9tnx83g25"},{"id":2,"public_id":"4715169a40","public_label":"AK (4715169a40)","roles":["review"],"url":"https://sah.borca.ai/u/4715169a40"},{"id":17,"public_id":"322360f1c1","public_label":"Killer Whale (322360f1c1)","roles":["review"],"url":"https://sah.borca.ai/u/322360f1c1"}],"url":"https://sah.borca.ai/concepts/co_7148d5da2129494aaa3d95eba56982c0"},{"public_id":"co_ac98bcf1101128edc403e4a411dada30","status":"active","name":"QR factorization","description":"A matrix decomposition technique for which block-diagonal form provides inherent parallelism.","types":["method"],"aliases":[],"contributors":[{"id":171,"public_id":"b9tnx83g25","public_label":"eunsjani (b9tnx83g25)","roles":["extraction"],"url":"https://sah.borca.ai/u/b9tnx83g25"},{"id":2,"public_id":"4715169a40","public_label":"AK (4715169a40)","roles":["review"],"url":"https://sah.borca.ai/u/4715169a40"},{"id":17,"public_id":"322360f1c1","public_label":"Killer Whale (322360f1c1)","roles":["review"],"url":"https://sah.borca.ai/u/322360f1c1"}],"url":"https://sah.borca.ai/concepts/co_ac98bcf1101128edc403e4a411dada30"},{"public_id":"co_d4e88e2d64254865a9def3abda2c915f","status":"active","name":"hypergraph model","description":"A hypergraph model proposed in this paper to represent the nonzero structure of a matrix for reducing the permutation problem to hypergraph partitioning.","types":["method","model"],"aliases":[],"contributors":[{"id":171,"public_id":"b9tnx83g25","public_label":"eunsjani (b9tnx83g25)","roles":["extraction"],"url":"https://sah.borca.ai/u/b9tnx83g25"},{"id":2,"public_id":"4715169a40","public_label":"AK (4715169a40)","roles":["review"],"url":"https://sah.borca.ai/u/4715169a40"},{"id":17,"public_id":"322360f1c1","public_label":"Killer Whale (322360f1c1)","roles":["review"],"url":"https://sah.borca.ai/u/322360f1c1"}],"url":"https://sah.borca.ai/concepts/co_d4e88e2d64254865a9def3abda2c915f"},{"public_id":"co_f59f05f26c518d8f436dab1b3fbf028d","status":"active","name":"LU factorization","description":"A matrix decomposition technique for which block-diagonal form provides inherent parallelism.","types":["method"],"aliases":[],"contributors":[{"id":171,"public_id":"b9tnx83g25","public_label":"eunsjani (b9tnx83g25)","roles":["extraction"],"url":"https://sah.borca.ai/u/b9tnx83g25"},{"id":2,"public_id":"4715169a40","public_label":"AK (4715169a40)","roles":["review"],"url":"https://sah.borca.ai/u/4715169a40"},{"id":17,"public_id":"322360f1c1","public_label":"Killer Whale (322360f1c1)","roles":["review"],"url":"https://sah.borca.ai/u/322360f1c1"}],"url":"https://sah.borca.ai/concepts/co_f59f05f26c518d8f436dab1b3fbf028d"},{"public_id":"co_f6b77cfca5d95802f3b7aed94ddab14b","status":"active","name":"PaToH","description":"A state-of-the-art hypergraph partitioning tool used in experiments to evaluate the hypergraph model approach.","types":["software tool"],"aliases":[],"contributors":[{"id":171,"public_id":"b9tnx83g25","public_label":"eunsjani (b9tnx83g25)","roles":["extraction"],"url":"https://sah.borca.ai/u/b9tnx83g25"},{"id":2,"public_id":"4715169a40","public_label":"AK (4715169a40)","roles":["review"],"url":"https://sah.borca.ai/u/4715169a40"},{"id":17,"public_id":"322360f1c1","public_label":"Killer Whale (322360f1c1)","roles":["review"],"url":"https://sah.borca.ai/u/322360f1c1"}],"url":"https://sah.borca.ai/concepts/co_f6b77cfca5d95802f3b7aed94ddab14b"}],"external_ids":{"DOI":"10.1137/S1064827502401953","ArXiv":null,"PubMed":null,"PubMedCentral":null,"MAG":1996309908,"DBLP":"journals/siamsc/AykanatPC04","ACL":null},"open_access":{"is_open_access":true,"pdf_url":"https://digital.library.unt.edu/ark:/67531/metadc786866/m2/1/high_res_d/826102.pdf","landing_url":"https://www.semanticscholar.org/paper/2f91a872ee65ce2b2358ced38e5729fa4cdfef7e","source":"semantic_scholar","pdf_url_source":"semantic_scholar_open_access_pdf","license":"other-oa","status":"GREEN","reason":null},"reference_availability":{"status":"available","references_indexed":true,"full_text_available":false,"full_text_source":null,"count_basis":"semantic_scholar_metadata","extraction_status":"not_applicable","reason":null},"source":{"provider":"episteme2","base_corpus":"semantic_scholar_dump","freshness_mode":"unknown","basis":["semantic_scholar_metadata","postgres_metadata"],"limits":["paper metadata is based on indexed upstream scholarly datasets","claims and concepts are available only for extracted papers","absence of claims or concepts means no extracted graph data is available in this response"],"status":"available","degraded":false,"degraded_reasons":[],"diagnostics":{"status":"available","degraded":false,"degraded_reasons":[],"metadata_status":"available","graph_status":"available","abstract_status":"available"},"source_flags":1},"paper_id":632129,"paper_uid":"d6b00246-db1e-49c0-add1-16a932000886","canonical_identity":{"paper_id":632129,"paper_uid":"d6b00246-db1e-49c0-add1-16a932000886","identity_status":"available","lookup_basis":"semantic_scholar_external_id","compatibility_path":"corpus_id"},"url":"https://sah.borca.ai/papers/14535142"}