52 Chapter 2.Solution of Linear Algebraic Equations In that case,the solution of the linear system by LU decomposition can be accomplished much faster,and in much less storage,than for the general N x N case. The precise definition of a band diagonal matrix with elements is that aij=0 when j>i+m2 or i>j+m (2.4.3) Band diagonal matrices are stored and manipulated in a so-called compact form,which results if the matrix is tilted 45 clockwise,so that its nonzero elements lie in a long,narrow matrix with m+1 +m2 columns and N rows.This is best illustrated by an example: The band diagonal matrix 3 100000 ￥ 15000 0 9 6 令 0 0 0 0 9 0 0 (2.4.4) granted for 18881892 0 0 9 2 0 g 0 0 0 2 38 4 1-800 0 0 0 0 2 4 from NUMERICAL RECIPES I which has N =7,m=2,and m2 =1,is stored compactly as the 7 x 4 matrix, 3 S 4 (North 1 5 9 2 6 5 3 8 9 (2.4.5) computer Ameri Press. 9 2 ART 3 8 4 6 2 4 4 9 Program Here x denotes elements that are wasted space in the compact format;these will not be referenced by any manipulations and can have arbitrary values.Notice that the diagonal of the original matrix appears in column m+1,with subdiagonal elements to its left, superdiagonal elements to its right. to dir The simplest manipulation of a band diagonal matrix,stored compactly,is to multiply it by a vector to its right.Although this is algorithmically trivial,you might want to study the following routine carefully,as an example of how to pull nonzero elements aj out of the OF SCIENTIFIC COMPUTING(ISBN compact storage format in an orderly fashion. 198918920 #include "nrutil.h" void banmul(float **a,unsigned long n,int m1,int m2,float x[],float b[]) Numerical Recipes 10-621 43108 Matrix multiply b =A.x,where A is band diagonal with m1 rows below the diagonal and m2 rows above.The input vector x and output vector b are stored as x[1..n]and b[1..n], respectively. The array a[1..n][1..m1+m2+1]stores A as follows:The diagonal elements (outside are in a[1..n][m1+1].Subdiagonal elements are in a[j..n][1..m1](with>1 ap- 膜 propriate to the number of elements on each subdiagonal).Superdiagonal elements are in a[1..j][m1+2..m1+m2+1]with j<n appropriate to the number of elements on each su- North Software. perdiagonal. Ame unsigned long i,j,k,tmploop; for(i=1;1<=n;1+){ k=1-m1-1; tmploop=LMIN(m1+m2+1,n-k); b[i]=0.0; for (j=LMAX(1,1-k);j<=tmploop;j++)b[i]+a[i][j]*x[j+k];52 Chapter 2. Solution of Linear Algebraic Equations 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). In that case, the solution of the linear system by LU decomposition can be accomplished much faster, and in much less storage, than for the general N × N case. The precise definition of a band diagonal matrix with elements aij is that aij = 0 when j>i + m2 or i>j + m1 (2.4.3) Band diagonal matrices are stored and manipulated in a so-called compact form, which results if the matrix is tilted 45◦ clockwise, so that its nonzero elements lie in a long, narrow matrix with m1 +1+ m2 columns and N rows. This is best illustrated by an example: The band diagonal matrix   3100000 4150000 9265000 0358900 0079320 0003846 0000244   (2.4.4) which has N = 7, m1 = 2, and m2 = 1, is stored compactly as the 7 × 4 matrix,   x x 3 1 x 415 9265 3589 7932 3846 244 x   (2.4.5) Here x denotes elements that are wasted space in the compact format; these will not be referenced by any manipulations and can have arbitrary values. Notice that the diagonal of the original matrix appears in column m1 + 1, with subdiagonal elements to its left, superdiagonal elements to its right. The simplest manipulation of a band diagonal matrix, stored compactly, is to multiply it by a vector to its right. Although this is algorithmically trivial, you might want to study the following routine carefully, as an example of how to pull nonzero elements aij out of the compact storage format in an orderly fashion. #include "nrutil.h" void banmul(float **a, unsigned long n, int m1, int m2, float x[], float b[]) Matrix multiply b = A · x, w here A is band diagonal with m1 rows below the diagonal and m2 rows above. The input vector x and output vector b are stored as x[1..n] and b[1..n], respectively. The array a[1..n][1..m1+m2+1] stores A as follows: The diagonal elements are in a[1..n][m1+1]. Subdiagonal elements are in a[j..n][1..m1] (with j > 1 ap￾propriate to the number of elements on each subdiagonal). Superdiagonal elements are in a[1..j][m1+2..m1+m2+1] with j < n appropriate to the number of elements on each su￾perdiagonal. { unsigned long i,j,k,tmploop; for (i=1;i<=n;i++) { k=i-m1-1; tmploop=LMIN(m1+m2+1,n-k); b[i]=0.0; for (j=LMAX(1,1-k);j<=tmploop;j++) b[i] += a[i][j]*x[j+k]; } }