Finding Nonoverlapping Substructures of a Sparse Matrix Metadata

Metadata describes a digital item, providing (if known) such information as creator, publisher, contents, size, relationship to other resources, and more. Metadata may also contain "preservation" components that help us to maintain the integrity of digital files over time.

Available Formats

Dublin Core: XML Dublin Core: JSON Dublin Core: Text Dublin Core: RDF/XML UNTL: XML Access METS: XML

Title

  • Main Title Finding Nonoverlapping Substructures of a Sparse Matrix

Creator

  • Author: Pinar, Ali
    Creator Type: Personal
  • Author: Vassilevska, Virginia
    Creator Type: Personal

Contributor

  • Sponsor: USDOE Director. Office of Science. Office of AdvancedScientific Computing Research. Mathematical Information and ComputationalSciences
    Contributor Type: Organization

Publisher

  • Name: Lawrence Berkeley National Laboratory
    Place of Publication: Berkeley, California
    Additional Info: Ernest Orlando Lawrence Berkeley National Laboratory, Berkeley, CA (United States)

Date

  • Creation: 2005-08-11

Language

  • English

Description

  • Content Description: Many applications of scientific computing rely on computations on sparse matrices. The design of efficient implementations of sparse matrix kernels is crucial for the overall efficiency of these applications. Due to the high compute-to-memory ratio and irregular memory access patterns, the performance of sparse matrix kernels is often far away from the peak performance on a modern processor. Alternative data structures have been proposed, which split the original matrix A into A{sub d} and A{sub s}, so that A{sub d} contains all dense blocks of a specified size in the matrix, and A{sub s} contains the remaining entries. This enables the use of dense matrix kernels on the entries of A{sub d} producing better memory performance. In this work, we study the problem of finding a maximum number of nonoverlapping dense blocks in a sparse matrix, which is previously not studied in the sparse matrix community. We show that the maximum nonoverlapping dense blocks problem is NP-complete by using a reduction from the maximum independent set problem on cubic planar graphs. We also propose a 2/3-approximation algorithm that runs in linear time in the number of nonzeros in the matrix. This extended abstract focuses on our results for 2x2 dense blocks. However we show that our results can be generalized to arbitrary sized dense blocks, and many other oriented substructures, which can be exploited to improve the memory performance of sparse matrix operations.

Subject

  • Keyword: Performance Memory Performance Memory-Efficient Data Structureshigh-Performance Computing Sparse Matrices Independent Setsnp-Completeness Approximation Algorithms.
  • STI Subject Categories: 99 General And Miscellaneous//Mathematics, Computing, And Information Science
  • Keyword: Kernels
  • Keyword: Efficiency
  • Keyword: Memory Performance Memory-Efficient Data Structureshigh-Performance Computing Sparse Matrices Independent Setsnp-Completeness Approximation Algorithms.
  • Keyword: Algorithms
  • Keyword: Matrices
  • Keyword: Design

Source

  • Journal Name: Electric Transactions Numerical Analysis; Journal Volume: 21; Related Information: Journal Publication Date: 2005

Collection

  • Name: Office of Scientific & Technical Information Technical Reports
    Code: OSTI

Institution

  • Name: UNT Libraries Government Documents Department
    Code: UNTGD

Resource Type

  • Article

Format

  • Text

Identifier

  • Report No.: LBNL--54498
  • Grant Number: DE-AC02-05CH11231
  • Office of Scientific & Technical Information Report Number: 886815
  • Archival Resource Key: ark:/67531/metadc876767
Back to Top of Screen