ABSTRACT
A sparse matrix is one that has “very few” non-zero elements. A sparse sys tem 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 elec tronic 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 x 1QQQ rQWS ----------------- x 100% = 0.4% non-zero elements
1000 x 1000 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 x 1000 matrix. Full storage of an n x 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 signifi 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 significant computational effort can be saved. The salient point here is that these computations are skipped altogether. A person performing an LU fac torization 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
FIGURE 4.1 Basic storage element for a^
such a way as to avoid zero computations altogether and operate only upon non-zero elements.
