2.7 Sparse Linear Systems 71 2.7 Sparse Linear Systems A system of linear equations is called sparse if only a relatively small number of its matrix elements aij are nonzero.It is wasteful to use general methods of linear algebra on such problems,because most of the O(N3)arithmetic operations devoted to solving the set of equations or inverting the matrix involve zero operands. Furthermore,you might wish to work problems so large as to tax your available memory space,and it is wasteful to reserve storage for unfruitful zero elements. Note that there are two distinct (and not always compatible)goals for any sparse matrix method:saving time and/or saving space. We have already considered one archetypal sparse form in $2.4,the band diagonal matrix.In the tridiagonal case,e.g.,we saw that it was possible to save both time (order N instead of N3)and space (order N instead of N2).The method of solution was not different in principle from the general method of LU decomposition;it was just applied cleverly,and with due attention to the bookkeeping of zero elements.Many practical schemes for dealing with sparse problems have this same character.They are fundamentally decomposition schemes,or else elimination schemes akin to Gauss-Jordan,but carefully optimized so as to minimize the number of so-called fill-ins,initially zero elements which must become nonzero during the solution process,and for which storage must be reserved. Direct methods for solving sparse equations,then,depend crucially on the precise pattern of sparsity of the matrix.Patterns that occur frequently,or that are useful as way-stations in the reduction of more general forms,already have special names and special methods of solution.We do not have space here for any detailed review of these.References listed at the end of this section will furnish you with an "in"to the specialized literature,and the following list of buzz words(and Figure 2.7.1)will at least let you hold your own at cocktail parties: ●tridiagonal band diagonal (or banded)with bandwidth M ·band triangular ·block diagonal 。block tridiagonal ●block triangular v@cambridge.org ·cyclic banded 客 OF SCIENTIFIC COMPUTING (ISBN 1988-1992 by Numerical Recipes 12-:621-43106-50 singly (or doubly)bordered block diagonal singly (or doubly)bordered block triangular singly (or doubly)bordered band diagonal (outside North Software. singly (or doubly)bordered band triangular ·other() You should also be aware of some of the special sparse forms that occur in the ,visit website machine solution of partial differential equations in two or more dimensions.See Chapter 19. If your particular pattern of sparsity is not a simple one,then you may wish to try an analyze/factorize/operate package,which automates the procedure of figuring out how fill-ins are to be minimized.The analyze stage is done once only for each pattern of sparsity.The factorize stage is done once for each particular matrix that fits the pattern.The operate stage is performed once for each right-hand side to2.7 Sparse Linear Systems 71 Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) g of machine￾readable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (outside North America). 2.7 Sparse Linear Systems A system of linear equations is called sparse if only a relatively small number of its matrix elements aij are nonzero. It is wasteful to use general methods of linear algebra on such problems, because most of the O(N 3) arithmetic operations devoted to solving the set of equations or inverting the matrix involve zero operands. Furthermore, you might wish to work problems so large as to tax your available memory space, and it is wasteful to reserve storage for unfruitful zero elements. Note that there are two distinct (and not always compatible) goals for any sparse matrix method: saving time and/or saving space. We have already considered one archetypal sparse form in §2.4, the band diagonal matrix. In the tridiagonal case, e.g., we saw that it was possible to save both time (order N instead of N 3) and space (order N instead of N 2). The method of solution was not different in principle from the general method of LU decomposition; it was just applied cleverly, and with due attention to the bookkeeping of zero elements. Many practical schemes for dealing with sparse problems have this same character. They are fundamentally decomposition schemes, or else elimination schemes akin to Gauss-Jordan, but carefully optimized so as to minimize the number of so-called fill-ins, initially zero elements which must become nonzero during the solution process, and for which storage must be reserved. Direct methods for solving sparse equations, then, depend crucially on the precise pattern of sparsity of the matrix. Patterns that occur frequently, or that are useful as way-stations in the reduction of more general forms, already have special names and special methods of solution. We do not have space here for any detailed review of these. References listed at the end of this section will furnish you with an “in” to the specialized literature, and the following list of buzz words (and Figure 2.7.1) will at least let you hold your own at cocktail parties: • tridiagonal • band diagonal (or banded) with bandwidth M • band triangular • block diagonal • block tridiagonal • block triangular • cyclic banded • singly (or doubly) bordered block diagonal • singly (or doubly) bordered block triangular • singly (or doubly) bordered band diagonal • singly (or doubly) bordered band triangular • other (!) You should also be aware of some of the special sparse forms that occur in the solution of partial differential equations in two or more dimensions. See Chapter 19. If your particular pattern of sparsity is not a simple one, then you may wish to try an analyze/factorize/operate package, which automates the procedure of figuring out how fill-ins are to be minimized. The analyze stage is done once only for each pattern of sparsity. The factorize stage is done once for each particular matrix that fits the pattern. The operate stage is performed once for each right-hand side to