A sparse matrix is one that has “very few” non-zero elements. A sparse system is one in which its mathematical description gives rise to sparse matrices. Any large system that can be described by coupled nodes may give rise to a sparse matrix if the majority of nodes in the system have very few connections. Many systems in engineering and science result in sparse matrix descriptions. Large systems in which each node is connected to only a handful of other nodes include the mesh points in a ﬁnite-element-analysis, nodes in an electronic circuit, and the busbars in an electric power network. For example, power networks may contain thousands of nodes (busbars), but the average connectivity of electric power network nodes is three; each node is connected, on average, to three other nodes. This means that in a system comprised of a thousand nodes, the non-zero percentage of the descriptive system matrix is
4 non-zeros elements row × 1000 rows
1000× 1000 elements × 100% = 0.4% non-zero elements Thus, if only the non-zero elements were stored in memory, they would require only 0.4% of the memory requirements of the full 1000 × 1000 matrix. Full storage of an n×n system matrix grows as n2, whereas the sparse storage of the same system matrix increases only linearly as ∼ n. Thus signiﬁcant storage and computational savings can be realized by exploiting sparse storage and solution techniques. Another motivating factor in exploiting sparse matrix solution techniques is the computational eﬀort involved in solving matrices with large percentages of zero elements. Consider the solution of the linear problem
Ax = b
where A is sparse. The factorization of L and U from A requires a signiﬁcant number of multiplications where one or both of the factors may be zero. If it is known ahead of time where the zero elements reside in the matrix, these multiplications can be avoided (since their product will be zero) and signiﬁcant computational eﬀort can be saved. The salient point here is that these computations are skipped altogether. A person performing an LU factorization by hand can note which values are zero and skip those particular multiplications. A computer, however, does not have the ability to “see” the zero elements. Therefore the sparse solution technique must be formulated in such a way as to avoid zero computations altogether and operate only upon
FIGURE 4.1 Basic storage element for aij
In this chapter, both the storage and computational aspects of sparse matrix solutions will be explored. Several storage techniques will be discussed and ordering techniques to minimize computational eﬀort will be developed.