19.0 Introduction 833 So-called rapid methods [5]apply for only a rather special class of equations: those with constant coefficients,or,more generally,those that are separable in the chosen coordinates.In addition.the boundaries must coincide with coordinate lines. This special class of equations is met quite often in practice.We defer detailed discussion to $19.4.Note,however,that the multigrid relaxation methods discussed insl9.6 can be faster than“rapid”methods. Matrix methods attempt to solve the equation A·x=b (19.0.15) 三 81 directly.The degree to which this is practical depends very strongly on the exact structure of the matrix A for the problem at hand,so our discussion can go no farther than a few remarks and references at this point. Sparseness of the matrix must be the guiding force.Otherwise the matrix problem is prohibitively large.For example,the simplest problem on a 100 x 100 spatial grid would involve 10000 unknown ui's,implying a 10000 x 10000 matrix A,containing 108 elements! As we discussed at the end of $2.7,if A is symmetric and positive definite 9 (as it usually is in elliptic problems),the conjugate-gradient algorithm can be used.In practice,rounding error often spoils the effectiveness of the conjugate gradient algorithm for solving finite-difference equations.However,it is useful when incorporated in methods that first rewrite the equations so that A is transformed to a matrix A'that is close to the identity matrix.The quadratic surface defined by the equations then has almost spherical contours,and the conjugate gradient algorithm 心蓬邑O works very well.In $2.7,in the routine linbcg,an analogous preconditioner OF SCIENTIFIC was exploited for non-positive definite problems with the more general biconjugate gradient method.For the positive definite case that arises in PDEs,an example of 6 a successful implementation is the incomplete Cholesky conjugate gradient method (ICCG)(see [6-81). Another method that relies on a transformation approach is the strongly implicit procedure of Stone [91.A program called SIPSOL that implements this routine has been published [10]. 是是 A third class of matrix methods is the Analyze-Factorize-Operate approach as Recipes Numerica 10621 described in $2.7. 43106 Generally speaking,when you have the storage available to implement these methods-not nearly as much as the 10s above,but usually much more than is Recipes required by relaxation methods-then you should consider doing so.Only multigrid 腿 relaxation methods(819.6)are competitive with the best matrix methods.For grids North larger than,say,300 x 300,however,it is generally found that only relaxation methods,or"rapid"methods when they are applicable,are possible. There Is More to Life than Finite Differencing Besides finite differencing,there are other methods for solving PDEs.Most important are finite element,Monte Carlo,spectral,and variational methods.Unfor- tunately.we shall barely be able to do justice to finite differencing in this chapter. and so shall not be able to discuss these other methods in this book.Finite element methods [11-12]are often preferred by practitioners in solid mechanics and structural19.0 Introduction 833 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). So-called rapid methods [5] apply for only a rather special class of equations: those with constant coefficients, or, more generally, those that are separable in the chosen coordinates. In addition, the boundaries must coincide with coordinate lines. This special class of equations is met quite often in practice. We defer detailed discussion to §19.4. Note, however, that the multigrid relaxation methods discussed in §19.6 can be faster than “rapid” methods. Matrix methods attempt to solve the equation A · x = b (19.0.15) directly. The degree to which this is practical depends very strongly on the exact structure of the matrix A for the problem at hand, so our discussion can go no farther than a few remarks and references at this point. Sparseness of the matrix must be the guiding force. Otherwise the matrix problem is prohibitively large. For example, the simplest problem on a 100 × 100 spatial grid would involve 10000 unknown uj,l’s, implying a 10000 × 10000 matrix A, containing 108 elements! As we discussed at the end of §2.7, if A is symmetric and positive definite (as it usually is in elliptic problems), the conjugate-gradient algorithm can be used. In practice, rounding error often spoils the effectiveness of the conjugate gradient algorithm for solving finite-difference equations. However, it is useful when incorporated in methods that first rewrite the equations so that A is transformed to a matrix A that is close to the identity matrix. The quadratic surface defined by the equations then has almost spherical contours, and the conjugate gradient algorithm works very well. In §2.7, in the routine linbcg, an analogous preconditioner was exploited for non-positive definite problems with the more general biconjugate gradient method. For the positive definite case that arises in PDEs, an example of a successful implementation is the incomplete Cholesky conjugate gradient method (ICCG) (see [6-8]). Another method that relies on a transformation approach is the strongly implicit procedure of Stone [9]. A program called SIPSOL that implements this routine has been published [10]. A third class of matrix methods is the Analyze-Factorize-Operate approach as described in §2.7. Generally speaking, when you have the storage available to implement these methods — not nearly as much as the 108 above, but usually much more than is required by relaxation methods — then you should consider doing so. Only multigrid relaxation methods (§19.6) are competitive with the best matrix methods. For grids larger than, say, 300 × 300, however, it is generally found that only relaxation methods, or “rapid” methods when they are applicable, are possible. There Is More to Life than Finite Differencing Besides finite differencing, there are other methods for solving PDEs. Most important are finite element, Monte Carlo, spectral, and variational methods. Unfor￾tunately, we shall barely be able to do justice to finite differencing in this chapter, and so shall not be able to discuss these other methods in this book. Finite element methods [11-12] are often preferred by practitioners in solid mechanics and structural