10. Common Issues
Jack J. Dongarra, P. Koev, Xian‐Jin Li, J. Demmel, Henk A. van der Vorst · Society for Industrial and Applied Mathematics eBooks · 2000
10.1 Sparse Matrix Storage Formats The efficiency of most of the iterative methods considered in this book is determined primarily by the performance of the matrix-vector product and therefore on the storage scheme used for the matrix. 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 have been used in numerical software packages such as ITPACK [263], NSPCG [345], and SPARSPAK [191], some of which have more recently been adopted as part of a new software standard by the BLAS Technical Forum (see ETHOME for further information). In §10.2.2, we demonstrate how the matrix-vector product is formulated using two of the sparse matrix formats. If the coefficient matrix A is sparse, large scale eigenvalue problems can be most efficiently solved if the zero elements of A are neither manipulated nor stored. Sparse storage schemes allocate contiguous storage in memory for the nonzero elements of the matrix, and perhaps a limited number of zeros. This, of course, requires a scheme for knowing where the elements fit into the full matrix. There are many methods for storing the data (see, for instance, Saad [386] and Eijkhout [156]). Here we will discuss compressed row and column storage, block compressed row storage, diagonal storage, jagged diagonal storage, and skyline storage. 10.1.1 Compressed Row Storage The compressed row and column (in the next section) storage formats are the most general: they make absolutely no assumptions about the sparsity structure of the matrix, and they don't store any unnecessary elements. On the other hand, they are not very efficient, needing an indirect addressing step for every single scalar operation in a matrix-vector product or preconditioner solve. The compressed row storage (CRS) format puts the subsequent nonzeros of the matrix rows in contiguous memory locations.