Publication: An Inexact Combinatorial Model for Maximizing the Number of Discovered Nonzero Entries
Introduction
Applications
Tools
Research Groups
Workshops
Publications
   List Publications
   Advanced Search
   Info
   Add Publications
My Account
About

An Inexact Combinatorial Model for Maximizing the Number of Discovered Nonzero Entries

- Part of a collection -
 

Author(s)
M. A. Rostami , H. M. Bücker

Published in
2020 Proceedings of the Ninth SIAM Workshop on Combinatorial Scientific Computing, Seattle, Washington, USA, February 11--13, 2020

Editor(s)
H. M. Bücker, X. S. Li, S. Rajamanickam

Year
2020

Publisher
SIAM

Abstract
Given a large sparse Jacobian matrix with a known sparsity pattern and a positive integer p, we formulate the new combinatorial problem of maximizing the number of nonzero elements that can be discovered by forming p groups of linear combinations of columns of the matrix. This combinatorial problem is addressed by introducing a novel graph model that does not represent the underlying aspects exactly, but aims at capturing the main aspects of the situation. In an attempt to encode information on the number of discovered nonzeros, an edge-weighted column intersection graph is transformed into an edge-weighted and vertex-weighted column gain graph. This combinatorial model gives rise to heuristic algorithms which are compared by computational experiments using a set of matrices arising from different scientific disciplines.

AD Theory and Techniques
Sparsity

BibTeX
@INPROCEEDINGS{
         Rostami2020AIC,
       author = "M. A. Rostami and H. M. B{\"u}cker",
       title = "An Inexact Combinatorial Model for Maximizing the Number of Discovered Nonzero
         Entries",
       booktitle = "2020 Proceedings of the Ninth SIAM Workshop on Combinatorial Scientific Computing,
         Seattle, Washington, USA, February~11--13, 2020",
       editor = "H. M. B{\"u}cker and X. S. Li and S. Rajamanickam",
       pages = "32--44",
       address = "Philadelphia, PA, USA",
       publisher = "SIAM",
       url = "https://doi.org/10.1137/1.9781611976229.4",
       doi = "10.1137/1.9781611976229.4",
       abstract = "Given a large sparse Jacobian matrix with a known sparsity pattern and a positive
         integer $p$, we formulate the new combinatorial problem of maximizing the number of nonzero elements
         that can be discovered by forming $p$ groups of linear combinations of columns of the matrix. This
         combinatorial problem is addressed by introducing a novel graph model that does not represent the
         underlying aspects exactly, but aims at capturing the main aspects of the situation. In an attempt
         to encode information on the number of discovered nonzeros, an edge-weighted column intersection
         graph is transformed into an edge-weighted and vertex-weighted column gain graph. This combinatorial
         model gives rise to heuristic algorithms which are compared by computational experiments using a set
         of matrices arising from different scientific disciplines.",
       year = "2020",
       ad_theotech = "Sparsity"
}


back
  

Contact:
autodiff.org
Username:
Password:
(lost password)