ABSTRACT
A sparse matrix is one that has “very few” nonzero 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 finite-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 composed of a thousand nodes, the nonzero percentage of the descriptive system matrix is
4 nonzero elements row × 1000 rows
1000× 1000 elements × 100% = 0.4% nonzero elements Thus, if only the nonzero 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 significant 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 effort 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 significant 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 significant computational effort 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
Electric
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 effort will be developed.
