Previous: Stopping Criteria
Up: Related Issues
Next: Parallelism
Previous Page: Accounting for floating point errors
Next Page: Survey of Sparse Matrix Storage Formats

Data Structures

The efficiency of any of the iterative methods considered in previous sections is determined primarily by the performance of the matrix-vector product and the preconditioner solve, and therefore on the storage scheme used for the matrix and the preconditioner. Since iterative methods are typically used on sparse matrices, we will review here a number of sparse storage formats. Often, the storage scheme used arises naturally from the specific application problem.

In this section we will review some of the more popular sparse matrix formats that are used in numerical software packages such as ITPACK [138] and NSPCG [161]. After surveying the various formats, we demonstrate how the matrix-vector product and an incomplete factorization solve are formulated using two of the sparse matrix formats.

• Survey of Sparse Matrix Storage Formats
  • Compressed Row Storage (CRS)
  • Compressed Column Storage (CCS)
  • Block Compressed Row Storage (BCRS)
  • Compressed Diagonal Storage (CDS)
  • Jagged Diagonal Storage (JDS)
  • Skyline Storage (SKS)
• Matrix vector products
  • CRS Matrix-Vector Product
  • CDS Matrix-Vector Product
• Sparse Incomplete Factorizations
  • Generating a CRS-based Incomplete Factorization
  • CRS-based Factorization Solve
  • CRS-based Factorization Transpose Solve