Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.arcetri.astro.it/irlab/doc/library/nr/f21-2.pdf
Дата изменения: Thu Oct 7 13:11:40 1999
Дата индексирования: Sat Dec 22 09:34:23 2007
Кодировка: ISO8859-5
Поисковые слова: п п п п п п п п п п п п п р п р п р п р п р п р п р п р п р п р п р п р п р п р п р п р п р п р п р п р п р п р п р п р п р п

General Index to Volumes 1 and 2
In this index, page numbers 1 through 934 refer to Volume 1, Numerical Recipes in Fortran 77, while page numbers 935 through 1446 refer to Volume 2, Numerical Recipes in Fortran 90. Front matter in Volume 1 is indicated by page numbers in the range 1/i through 1/xxxi, while front matter in Volume 2 is indicated 2/i through 2/xx.

A

bstract data types 2/xiii, 1030 Accelerated convergence of series 160ff., 1070 Accuracy 19f. achievable in minimization 392, 397, 404 achievable in root finding 346f. contrasted with fidelity 832, 840 CPU different from memory 181 vs. stability 704, 729, 830, 844 Accuracy parameters 1362f. Acknowledgments 1/xvi, 2/ix Ada 2/x Adams-Bashford-Moulton method 741 Adams' stopping criterion 366 Adaptive integration 123, 135, 703, 708ff., 720, 726, 731f., 737, 742ff., 788, 1298ff., 1303, 1308f. Monte Carlo 306ff., 1161ff. Addition, multiple precision 907, 1353 Addition theorem, elliptic integrals 255 ADI (alternating direction implicit) method 847, 861f., 906 Adjoint operator 867 Adobe Illustrator 1/xvi, 2/xx Advective equation 826 AGM (arithmetic geometric mean) 906 Airy function 204, 234, 243f. routine for 244f., 1121 Aitken's delta squared process 160 Aitken's interpolation algorithm 102 Algol 2/x, 2/xiv Algorithms, non-numerical 881ff., 1343ff. Aliasing 495, 569 see also Fourier transform all() intrinsic function 945, 948 All-poles model 566 see also Maximum entropy method (MEM) All-zeros model 566 see also Periodogram Allocatable array 938, 941, 952ff., 1197, 1212, 1266, 1293, 1306, 1336 allocate statement 938f., 941, 953f., 1197, 1266, 1293, 1306, 1336 allocated() intrinsic function 938, 952ff., 1197, 1266, 1293 Allocation status 938, 952ff., 961, 1197, 1266, 1293

Alpha AXP 2/xix Alternating-direction implicit method (ADI) 847, 861f., 906 Alternating series 160f., 1070 Alternative extended Simpson's rule 128 American National Standards Institute (ANSI) 2/x, 2/xiii Amoeba 403 see also Simplex, method of Nelder and Mead Amplification factor 828, 830, 832, 840, 845f. Amplitude error 831 Analog-to-digital converter 812, 886 Analyticity 195 Analyze/factorize/operate package 64, 824 Anderson-Darling statistic 621 Andrew's sine 697 Annealing, method of simulated 387f., 436ff., 1219ff. assessment 447 for continuous variables 437, 443ff., 1222 schedule 438 thermodynamic analogy 437 traveling salesman problem 438ff., 1219ff. ANSI (American National Standards Institute) 2/x, 2/xiii Antonov-Saleev variant of Sobol' sequence 300, 1160 any() intrinsic function 945, 948 APL (computer language) 2/xi Apple 1/xxiii Macintosh 2/xix, 4, 886 Approximate inverse of matrix 49 Approximation of functions 99, 1043 by Chebyshev polynomials 185f., 513, 1076ff. Pade approximant 194ff., 1080f. Д by rational functions 197ff., 1081f. by wavelets 594f., 782 see also Fitting Argument keyword 2/xiv, 947f., 1341 optional 2/xiv, 947f., 1092, 1228, 1230, 1256, 1272, 1275, 1340 Argument checking 994f., 1086, 1090, 1092, 1370f.

934

Index to Volumes 1 and 2

935

Arithmetic arbitrary precision 881, 906ff., 1352ff. floating point 881, 1343 IEEE standard 276, 882, 1343 rounding 882, 1343 Arithmetic coding 881, 902ff., 1349ff. Arithmetic-geometric mean (AGM) method 906 Arithmetic-if statement 2/xi Arithmetic progression 971f., 996, 1072, 1127, 1365, 1371f. Array 953ff. allocatable 938, 941, 952ff., 1197, 1212, 1266, 1293, 1306, 1336 allocated with pointer 941 allocation 953 array manipulation functions 950 array sections 939, 941, 943ff. of arrays 2/xii, 956, 1336 associated pointer 953f. assumed-shape 942 automatic 938, 954, 1197, 1212, 1336 centered subarray of 113 conformable to a scalar 942f., 965, 1094 constructor 2/xii, 968, 971, 1022, 1052, 1055, 1127 copying 991, 1034, 1327f., 1365f. cumulative product 997f., 1072, 1086, 1375 cumulative sum 997, 1280f., 1365, 1375 deallocation 938, 953f., 1197, 1266, 1293 disassociated pointer 953 extents 938, 949 in Fortran 90 941 increasing storage for 955, 1070, 1302 index loss 967f. index table 1173ff. indices 942 inquiry functions 948ff. intrinsic procedures 2/xiii, 948ff. of length 0 944 of length 1 949 location of first "true" 993, 1041, 1369 location of maximum value 993, 1015, 1017, 1365, 1369 location of minimum value 993, 1369f. manipulation functions 950, 1247 masked swapping of elements in two arrays 1368 operations on 942, 949, 964ff., 969, 1026, 1040, 1050, 1200, 1326 outer product 949, 1076 parallel features 941ff., 964ff., 985 passing variable number of arguments to function 1022 of pointers forbidden 956, 1337 rank 938, 949 reallocation 955, 992, 1070f., 1365, 1368f. reduction functions 948ff. shape 938, 944, 949 size 938 skew sections 945, 985 stride 944 subscript bounds 942 subscript triplet 944

swapping elements of two arrays 991, 1015, 1365ff. target 938 three-dimensional, in Fortran 90 1248 transformational functions 948ff. unary and binary functions 949 undefined status 952ff., 961, 1266, 1293 zero-length 944 Array section 2/xiii, 943ff., 960 matches by shape 944 pointer alias 939, 944f., 1286, 1333 skew 2/xii, 945, 960, 985, 1284 vs. eoshift 1078 array copy() utility function 988, 991, 1034, 1153, 1278, 1328 arth() utility function 972, 974, 988, 996, 1072, 1086, 1127 replaces do-list 968 Artificial viscosity 831, 837 Ascending transformation, elliptic integrals 256 ASCII character set 6, 888, 896, 902 Assembly language 269 assert() utility function 988, 994, 1086, 1090, 1249 assert eq() utility function 988, 995, 1022 associated() intrinsic function 952f. Associated Legendre polynomials 246ff., 764, 1122f., 1319 recurrence relation for 247 relation to Legendre polynomials 246 Association, measures of 604, 622ff., 1275 Assumed-shape array 942 Asymptotic series 161 exponential integral 218 Attenuation factors 583, 1261 Autocorrelation 492 in linear prediction 558 use of FFT 538f., 1254 Wiener-Khinchin theorem 492, 566f. AUTODIN-II polynomial 890 Automatic array 938, 954, 1197, 1212, 1336 specifying size of 938, 954 Automatic deallocation 2/xv, 961 Autonomous differential equations 729f. Autoregressive model (AR) see Maximum entropy method (MEM) Average deviation of distribution 605, 1269 Averaging kernel, in Backus-Gilbert method 807

B

acksubstitution 33ff., 39, 42, 92, 1017 in band diagonal matrix 46, 1021 in Cholesky decomposition 90, 1039 complex equations 41 direct for computing A-1 З B 40 with QR decomposition 93, 1040 relaxation solution of boundary value problems 755, 1316 in singular value decomposition 56, 1022f. Backtracking 419 in quasi-Newton methods 376f., 1195 Backus-Gilbert method 806ff. Backus, John 2/x Backward deflation 363

936
Ba Ba Ba Ba

Index to Volumes 1 and 2

der-Deuflhard method 730, 735, 1310f. irstow's method 364, 370, 1193 lancing 476f., 1230f. nd diagonal matrix 42ff., 1019 backsubstitution 46, 1021 LU decomposition 45, 1020 multiply by vector 44, 1019 storage 44, 1019 Band-pass filter 551, 554f. wavelets 584, 592f. Bandwidth limited function 495 Bank accounts, checksum for 894 Bar codes, checksum for 894 Bartlett window 547, 1254ff. Base case, of recursive procedure 958 Base of representation 19, 882, 1343 BASIC, Numerical Recipes in 1, 2/x, 2/xviii Basis functions in general linear least squares 665 Bayes' Theorem 810 Bayesian approach to inverse problems 799, 810f., 816f. contrasted with frequentist 810 vs. historic maximum entropy method 816f. views on straight line fitting 664 Bays' shuffle 270 Bernoulli number 132 Bessel functions 223ff., 234ff., 936, 1101ff. asymptotic form 223f., 229f. complex 204 continued fraction 234, 239 double precision 223 fractional order 223, 234ff., 1115ff. Miller's algorithm 175, 228, 1106 modified 229ff. modified, fractional order 239ff. modified, normalization formula 232, 240 modified, routines for 230ff., 1109ff. normalization formula 175 parallel computation of 1107ff. recurrence relation 172, 224, 232, 234 reflection formulas 236 reflection formulas, modified functions 241 routines for 225ff., 236ff., 1101ff. routines for modified functions 241ff., 1118 series for 160, 223 series for K 241 series for Y 235 spherical 234, 245, 1121f. turning point 234 Wronskian 234, 239 Best-fit parameters 650, 656, 660, 698, 1285ff. see also Fitting Beta function 206ff., 1089 incomplete see Incomplete beta function BFGS algorithm see Broyden-Fletcher-GoldfarbShanno algorithm Bias, of exponent 19 Bias, removal in linear prediction 563 Biconjugacy 77

Biconjugate gradient method elliptic partial differential equations 824 preconditioning 78f., 824, 1037 for sparse system 77, 599, 1034ff. Bicubic interpolation 118f., 1049f. Bicubic spline 120f., 1050f. Big-endian 293 Bilinear interpolation 117 Binary constant, initialization 959 Binomial coefficients 206ff., 1087f. recurrences for 209 Binomial probability function 208 cumulative 222f. deviates from 281, 285f., 1155 Binormal distribution 631, 690 Biorthogonality 77 Bisection 111, 359, 1045f. compared to minimum bracketing 390ff. minimum finding with derivatives 399 root finding 343, 346f., 352f., 390, 469, 1184f. BISYNCH 890 Bit 18 manipulation functions see Bitwise logical functions reversal in fast Fourier transform (FFT) 499f., 525 bit size() intrinsic function 951 Bitwise logical functions 2/xiii, 17, 287, 890f., 951 Block-by-block method 788 Block of statements 7 Bode's rule 126 Boltzmann probability distribution 437 Boltzmann's constant 437 Bootstrap method 686f. Bordering method for Toeplitz matrix 85f. Borwein and Borwein method for 906, 1357 Boundary 155f., 425f., 745 Boundary conditions for differential equations 701f. initial value problems 702 in multigrid method 868f. partial differential equations 508, 819ff., 848ff. for spheroidal harmonics 764 two-point boundary value problems 702, 745ff., 1314ff. Boundary value problems see Differential equations; Elliptic partial differential equations; Two-point boundary value problems Box-Muller algorithm for normal deviate 279f., 1152 Bracketing of function minimum 343, 390ff., 402, 1201f. of roots 341, 343ff., 353f., 362, 364, 369, 390, 1183f. Branch cut, for hypergeometric function 203 Branching 9 Break iteration 14 Brenner, N.M. 500, 517

Index to Volumes 1 and 2

937

Brent's method minimization 389, 395ff., 660f., 1204ff., 1286 minimization, using derivative 389, 399, 1205 root finding 341, 349, 660f., 1188f., 1286 Broadcast (parallel capability) 965ff. Broyden-Fletcher-Goldfarb-Shanno algorithm 390, 418ff., 1215 Broyden's method 373, 382f., 386, 1199f. singular Jacobian 386 btest() intrinsic function 951 Bubble sort 321, 1168 Bugs 4 in compilers 1/xvii how to report 1/iv, 2/iv Bulirsch-Stoer algorithm for rational function interpolation 105f., 1043 method (differential equations) 202, 263, 702f., 706, 716, 718ff., 726, 740, 1138, 1303ff. method (differential equations), stepsize control 719, 726 for second order equations 726, 1307 Burg's LP algorithm 561, 1256 Byte 18 (programming language) 13, 2/viii and case construct 1010 Numerical Recipes in 1, 2/x, 2/xvii C++ 1/xiv, 2/viii, 2/xvi, 7f. class templates 1083, 1106 Calendar algorithms 1f., 13ff., 1010ff. Calibration 653 Capital letters in programs 3, 937 Cards, sorting a hand of 321 Carlson's elliptic integrals 255f., 1128ff. case construct 2/xiv, 1010 trapping errors 1036 Cash-Karp parameters 710, 1299f. Cauchy probability distribution see Lorentzian probability distribution Cauchy problem for partial differential equations 818f. Cayley's representation of exp(-iH t) 844 CCITT (Comite Consultatif International TeleД ДД graphique et Telephonique) 889f., 901 ДД CCITT polynomial 889f. ceiling() intrinsic function 947 Center of mass 295ff. Central limit theorem 652f. Central tendency, measures of 604ff., 1269 Change of variable in integration 137ff., 788, 1056ff. in Monte Carlo integration 298 in probability distribution 279 Character functions 952 Character variables, in Fortran 90 1183 Characteristic polynomial digital filter 554 eigensystems 449, 469 linear prediction 559 matrix with a specified 368, 1193 of recurrence relation 175

C

Characteristics of partial differential equations 818 Chebyshev acceleration in successive overrelaxation (SOR) 859f., 1332 Chebyshev approximation 84, 124, 183, 184ff., 1076ff. Clenshaw-Curtis quadrature 190 Clenshaw's recurrence formula 187, 1076 coefficients for 185f., 1076 contrasted with Pade approximation 195 Д derivative of approximated function 183, 189, 1077f. economization of series 192f., 195, 1080 for error function 214, 1095 even function 188 and fast cosine transform 513 gamma functions 236, 1118 integral of approximated function 189, 1078 odd function 188 polynomial fits derived from 191, 1078 rational function 197ff., 1081f. Remes exchange algorithm for filter 553 Chebyshev polynomials 184ff., 1076ff. continuous orthonormality 184 discrete orthonormality 185 explicit formulas for 184 formula for xk in terms of 193, 1080 Check digit 894, 1345f. Checksum 881, 888 cyclic redundancy (CRC) 888ff., 1344f. Cherry, sundae without a 809 Chi-by-eye 651 Chi-square fitting see Fitting; Least squares fitting Chi-square probability function 209ff., 215, 615, 654, 798, 1272 as boundary of confidence region 688f. related to incomplete gamma function 215 Chi-square test 614f. for binned data 614f., 1272 chi-by-eye 651 and confidence limit estimation 688f. for contingency table 623ff., 1275 degrees of freedom 615f. for inverse problems 797 least squares fitting 653ff., 1285 nonlinear models 675ff., 1292 rule of thumb 655 for straight line fitting 655ff., 1285 for straight line fitting, errors in both coordinates 660, 1286ff. for two binned data sets 616, 1272 unequal size samples 617 Chip rate 290 Chirp signal 556 Cholesky decomposition 89f., 423, 455, 1038 backsubstitution 90, 1039 operation count 90 pivoting 90 solution of normal equations 668 Circulant 585 Class, data type 7 Clenshaw-Curtis quadrature 124, 190, 512f.

938

Index to Volumes 1 and 2

Clenshaw's recurrence formula 176f., 191, 1078 for Chebyshev polynomials 187, 1076 stability 176f. Clocking errors 891 CM computers (Thinking Machines Inc.) 964 CM Fortran 2/xv cn function 261, 1137f. Coarse-grid correction 864f. Coarse-to-fine operator 864, 1337 Coding arithmetic 902ff., 1349ff. checksums 888, 1344 decoding a Huffman-encoded message 900, 1349 Huffman 896f., 1346ff. run-length 901 variable length code 896, 1346ff. Ziv-Lempel 896 see also Arithmetic coding; Huffman coding Coefficients binomial 208, 1087f. for Gaussian quadrature 140ff., 1059ff. for Gaussian quadrature, nonclassical weight function 151ff., 788f., 1064 for quadrature formulas 125ff., 789, 1328 Cohen, Malcolm 2/xiv Column degeneracy 22 Column operations on matrix 29, 31f. Column totals 624 Combinatorial minimization see Annealing Comite Consultatif International Telegraphique Д ДД et Telephonique (CCITT) 889f., 901 ДД Common block obsolescent 2/xif. superseded by internal subprogram 957, 1067 superseded by module 940, 953, 1298, 1320, 1322, 1324, 1330 Communication costs, in parallel processing 969, 981, 1250 Communication theory, use in adaptive integration 721 Communications protocol 888 Comparison function for rejection method 281 Compilers 964, 1364 CM Fortran 968 DEC (Digital Equipment Corp.) 2/viii IBM (International Business Machines) 2/viii Microsoft Fortran PowerStation 2/viii NAG (Numerical Algorithms Group) 2/viii, 2/xiv for parallel supercomputers 2/viii Complementary error function 1094f. see Error function Complete elliptic integral see Elliptic integrals Complex arithmetic 171f. avoidance of in path integration 203 cubic equations 179f. for linear equations 41 quadratic equations 178 Complex error function 252

Complex plane fractal structure for Newton's rule 360f. path integration for function evaluation 201ff., 263, 1138 poles in 105, 160, 202f., 206, 554, 566, 718f. Complex systems of linear equations 41f. Compression of data 596f. Concordant pair for Kendall's tau 637, 1281 Condition number 53, 78 Confidence level 687, 691ff. Confidence limits bootstrap method 687f. and chi-square 688f. confidence region, confidence interval 687 on estimated model parameters 684ff. by Monte Carlo simulation 684ff. from singular value decomposition (SVD) 693f. Confluent hypergeometric function 204, 239 Conformable arrays 942f., 1094 Conjugate directions 408f., 414ff., 1210 Conjugate gradient method biconjugate 77, 1034 compared to variable metric method 418 elliptic partial differential equations 824 for minimization 390, 413ff., 804, 815, 1210, 1214 minimum residual method 78 preconditioner 78f., 1037 for sparse system 77ff., 599, 1034 and wavelets 599 Conservative differential equations 726, 1307 Constrained linear inversion method 799ff. Constrained linear optimization see Linear programming Constrained optimization 387 Constraints, deterministic 804ff. Constraints, linear 423 CONTAINS statement 954, 957, 1067, 1134, 1202 Contingency coefficient C 625, 1275 Contingency table 622ff., 638, 1275f. statistics based on chi-square 623ff., 1275 statistics based on entropy 626ff., 1275f. Continued fraction 163ff. Bessel functions 234 convergence criterion 165 equivalence transformation 166 evaluation 163ff. evaluation along with normalization condition 240 even and odd parts 166, 211, 216 even part 249, 251 exponential integral 216 Fresnel integral 248f. incomplete beta function 219f., 1099f. incomplete gamma function 211, 1092f. Lentz's method 165, 212 modified Lentz's method 165 Pincherle's theorem 175 ratio of Bessel functions 239 rational function approximation 164, 211, 219f. recurrence for evaluating 164f.

Index to Volumes 1 and 2

939

and recurrence relation 175 sine and cosine integrals 250f. Steed's method 164f. tangent function 164 typography for 163 Continuous variable (statistics) 623 Control structures 7ff., 2/xiv bad 15 named 959, 1219, 1305 Convergence accelerated, for series 160ff., 1070 of algorithm for pi 906 criteria for 347, 392, 404, 483, 488, 679, 759 eigenvalues accelerated by shifting 470f. golden ratio 349, 399 of golden section search 392f. of Levenberg-Marquardt method 679 linear 346, 393 of QL method 470f. quadratic 49, 351, 356, 409f., 419, 906 rate 346f., 353, 356 recurrence relation 175 of Ridders' method 351 series vs. continued fraction 163f. and spectral radius 856ff., 862 Conversion intrinsic functions 946f. Convex sets, use in inverse problems 804 Convolution denoted by asterisk 492 finite impulse response (FIR) 531 of functions 492, 503f. of large data sets 536f. for multiple precision arithmetic 909, 1354 multiplication as 909, 1354 necessity for optimal filtering 535 overlap-add method 537 overlap-save method 536f. and polynomial interpolation 113 relation to wavelet transform 585 theorem 492, 531ff., 546 theorem, discrete 531ff. treatment of end effects 533 use of FFT 523, 531ff., 1253 wraparound problem 533 Cooley-Tukey FFT algorithm 503, 1250 parallel version 1239f. Co-processor, floating point 886 Copyright rules 1/xx, 2/xix Cornwell-Evans algorithm 816 Corporate promotion ladder 328 Corrected two-pass algorithm 607, 1269 Correction, in multigrid method 863 Correlation coefficient (linear) 630ff., 1276 Correlation function 492 autocorrelation 492, 539, 558 and Fourier transforms 492 theorem 492, 538 treatment of end effects 538f. using FFT 538f., 1254 Wiener-Khinchin theorem 492, 566f. Correlation, statistical 603f., 622 Kendall's tau 634, 637ff., 1279

linear correlation coefficient 630ff., 658, 1276 linear related to least square fitting 630, 658 nonparametric or rank statistical 633ff., 1277 among parameters in a fit 657, 667, 670 in random number generators 268 Spearman rank-order coefficient 634f., 1277 sum squared difference of ranks 634, 1277 Cosine function, recurrence 172 Cosine integral 248, 250ff., 1125f. continued fraction 250 routine for 251f., 1125 series 250 Cosine transform see Fast Fourier transform (FFT); Fourier transform Coulomb wave function 204, 234 count() intrinsic function 948 Courant condition 829, 832ff., 836 multidimensional 846 Courant-Friedrichs-Lewy stability criterion see Courant condition Covariance a priori 700 in general linear least squares 667, 671, 1288ff. matrix, by Cholesky decomposition 91, 667 matrix, of errors 796, 808 matrix, is inverse of Hessian matrix 679 matrix, when it is meaningful 690ff. in nonlinear models 679, 681, 1292 relation to chi-square 690ff. from singular value decomposition (SVD) 693f. in straight line fitting 657 cpu time() intrinsic function (Fortran 95) 961 CR method see Cyclic reduction (CR) Cramer's V 625, 1275 Crank-Nicholson method 840, 844, 846 Cray computers 964 CRC (cyclic redundancy check) 888ff., 1344f. CRC-12 890 CRC-16 polynomial 890 CRC-CCITT 890 Creativity, essay on 9 Critical (Nyquist) sampling 494, 543 Cross (denotes matrix outer product) 66 Crosstabulation analysis 623 see also Contingency table Crout's algorithm 36ff., 45, 1017 cshift() intrinsic function 950 communication bottleneck 969 Cubic equations 178ff., 360 Cubic spline interpolation 107ff., 1044f. see also Spline cumprod() utility function 974, 988, 997, 1072, 1086 cumsum() utility function 974, 989, 997, 1280, 1305 Cumulant, of a polynomial 977, 999, 1071f., 1192

940

Index to Volumes 1 and 2

Cumulative binomial distribution 222f. Cumulative Poisson function 214 related to incomplete gamma function 214 Curvature matrix see Hessian matrix cycle statement 959, 1219 Cycle, in multigrid method 865 Cyclic Jacobi method 459, 1225 Cyclic reduction (CR) 848f., 852ff. linear recurrences 974 tridiagonal systems 976, 1018 Cyclic redundancy check (CRC) 888ff., 1344f. Cyclic tridiagonal systems 67, 1030

D

.C. (direct current) 492 Danielson-Lanczos lemma 498f., 525, 1235ff. DAP Fortran 2/xi Data assigning keys to 889 continuous vs. binned 614 entropy 626ff., 896, 1275 essay on 603 fitting 650ff., 1285ff. fraudulent 655 glitches in 653 iid (independent and identically distributed) 686 modeling 650ff., 1285ff. serial port 892 smoothing 604, 644ff., 1283f. statistical tests 603ff., 1269ff. unevenly or irregularly sampled 569, 574, 648f., 1258ff. use of CRCs in manipulating 889 windowing 545ff., 1254 see also Statistical tests Data compression 596f., 881 arithmetic coding 902ff., 1349ff. cosine transform 513 Huffman coding 896f., 902, 1346ff. linear predictive coding (LPC) 563ff. lossless 896 Data Encryption Standard (DES) 290ff., 1144, 1147f., 1156ff. Data hiding 956ff., 1209, 1293, 1296 Data parallelism 941, 964ff., 985 DATA statement 959 for binary, octal, hexadecimal constants 959 repeat count feature 959 superseded by initialization expression 943, 959, 1127 Data type 18, 936 accuracy parameters 1362f. character 1183 derived 2/xiii, 937, 1030, 1336, 1346 derived, for array of arrays 956, 1336 derived, initialization 2/xv derived, for Numerical Recipes 1361 derived, storage allocation 955 DP (double precision) 1361f. DPC (double precision complex) 1361 I1B (1 byte integer) 1361 I2B (2 byte integer) 1361 I4B (4 byte integer) 1361

intrinsic 937 LGT (default logical type) 1361 nrtype.f90 1361f. passing complex as real 1140 SP (single precision) 1361f. SPC (single precision complex) 1361 user-defined 1346 DAUB4 584ff., 588, 590f., 594, 1264f. DAUB6 586 DAUB12 598 DAUB20 590f., 1265 Daubechies wavelet coefficients 584ff., 588, 590f., 594, 598, 1264ff. Davidon-Fletcher-Powell algorithm 390, 418ff., 1215 Dawson's integral 252ff., 600, 1127f. approximation for 252f. routine for 253f., 1127 dble() intrinsic function (deprecated) 947 deallocate statement 938f., 953f., 1197, 1266, 1293 Deallocation, of allocatable array 938, 953f., 1197, 1266, 1293 Debugging 8 DEC (Digital Equipment Corp.) 1/xxiii, 2/xix, 886 Alpha AXP 2/viii Fortran 90 compiler 2/viii quadruple precision option 1362 VAX 4 Decomposition see Cholesky decomposition; LU decomposition; QR decomposition; Singular value decomposition (SVD) Deconvolution 535, 540, 1253 see also Convolution; Fast Fourier transform (FFT); Fourier transform Defect, in multigrid method 863 Deferred approach to the limit see Richardson's deferred approach to the limit Deflation of matrix 471 of polynomials 362ff., 370f., 977 Degeneracy of linear algebraic equations 22, 53, 57, 670 Degenerate kernel 785 Degenerate minimization principle 795 Degrees of freedom 615f., 654, 691 Dekker, T.J. 353 Demonstration programs 3, 936 Deprecated features common block 2/xif., 940, 953, 957, 1067, 1298, 1320, 1322, 1324, 1330 dble() intrinsic function 947 EQUIVALENCE statement 2/xif., 1161, 1286 statement function 1057, 1256 Derivatives computation via Chebyshev approximation 183, 189, 1077f. computation via Savitzky-Golay filters 183, 645 matrix of first partial see Jacobian determinant matrix of second partial see Hessian matrix

Index to Volumes 1 and 2

941

numerical computation 180ff., 379, 645, 732, 750, 771, 1075, 1197, 1309 of polynomial 167, 978, 1071f. use in optimization 388f., 399, 1205ff. Derived data type see Data type, derived DES see Data Encryption Standard Descending transformation, elliptic integrals 256 Descent direction 376, 382, 419 Descriptive statistics 603ff., 1269ff. see also Statistical tests Design matrix 645, 665, 795, 801, 1082 Determinant 25, 41 Deviates, random see Random deviates DFP algorithm see Davidon-Fletcher-Powell algorithm diagadd() utility function 985, 989, 1004 diagmult() utility function 985, 989, 1004, 1294 Diagonal dominance 43, 679, 780, 856 Difference equations, finite see Finite difference equations (FDEs) Difference operator 161 Differential equations 701ff., 1297ff. accuracy vs. stability 704, 729 Adams-Bashforth-Moulton schemes 741 adaptive stepsize control 703, 708ff., 719, 726, 731, 737, 742f., 1298ff., 1303ff., 1308f., 1311ff. algebraically difficult sets 763 backward Euler's method 729 Bader-Deuflhard method for stiff 730, 735, 1310f. boundary conditions 701f., 745ff., 749, 751f., 771, 1314ff. Bulirsch-Stoer method 202, 263, 702, 706, 716, 718ff., 740, 1138, 1303 Bulirsch-Stoer method for conservative equations 726, 1307 comparison of methods 702f., 739f., 743 conservative 726, 1307 danger of too small stepsize 714 eigenvalue problem 748, 764ff., 770ff., 1319ff. embedded Runge-Kutta method 709f., 731, 1298, 1308 equivalence of multistep and multivalue methods 743 Euler's method 702, 704, 728f. forward Euler's method 728 free boundary problem 748, 776 high-order implicit methods 730ff., 1308ff. implicit differencing 729, 740, 1308 initial value problems 702 internal boundary conditions 775ff. internal singular points 775ff. interpolation on right-hand sides 111 Kaps-Rentrop method for stiff 730, 1308 local extrapolation 709 modified midpoint method 716f., 719, 1302f. multistep methods 740ff. multivalue methods 740 order of method 704f., 719

path integration for function evaluation 201ff., 263, 1138 predictor-corrector methods 702, 730, 740ff. reduction to first-order sets 701, 745 relaxation method 746f., 753ff., 1316ff. relaxation method, example of 764ff., 1319ff. r.h.s. independent of x 729f. Rosenbrock methods for stiff 730, 1308f. Runge-Kutta method 702, 704ff., 708ff., 731, 740, 1297f., 1308 Runge-Kutta method, high-order 705, 1297 Runge-Kutta-Fehlberg method 709ff., 1298 scaling stepsize to required accuracy 709 second order 726, 1307 semi-implicit differencing 730 semi-implicit Euler method 730, 735f. semi-implicit extrapolation method 730, 735f., 1311ff. semi-implicit midpoint rule 735f., 1310f. shooting method 746, 749ff., 1314ff. shooting method, example 770ff., 1321ff. similarity to Volterra integral equations 786 singular points 718f., 751, 775ff., 1315f., 1323ff. step doubling 708f. stepsize control 703, 708ff., 719, 726, 731, 737, 742f., 1298, 1303ff., 1308f. stiff 703, 727ff., 1308ff. stiff methods compared 739 Stoermer's rule 726, 1307 see also Partial differential equations; Twopoint boundary value problems Diffusion equation 818, 838ff., 855 Crank-Nicholson method 840, 844, 846 Forward Time Centered Space (FTCS) 839ff., 855 implicit differencing 840 multidimensional 846 Digamma function 216 Digital filtering see Filter Dihedral group D5 894 dim optional argument 948 Dimensional expansion 965ff. Dimensions (units) 678 Diminishing increment sort 322, 1168 Dirac delta function 284, 780 Direct method see Periodogram Direct methods for linear algebraic equations 26, 1014 Direct product see Outer product of matrices Direction of largest decrease 410f. Direction numbers, Sobol's sequence 300 Direction-set methods for minimization 389, 406f., 1210ff. Dirichlet boundary conditions 820, 840, 850, 856, 858 Disclaimer of warranty 1/xx, 2/xvii Discordant pair for Kendall's tau 637, 1281 Discrete convolution theorem 531ff.

942

Index to Volumes 1 and 2

Discrete Fourier transform (DFT) 495ff., 1235ff. as approximate continuous transform 497 see also Fast Fourier transform (FFT) Discrete optimization 436ff., 1219ff. Discriminant 178, 457 Diskettes are ANSI standard 3 how to order 1/xxi, 2/xvii Dispersion 831 DISPO see Savitzky-Golay filters Dissipation, numerical 830 Divergent series 161 Divide and conquer algorithm 1226, 1229 Division complex 171 multiple precision 910f., 1356 of polynomials 169, 362, 370, 1072 dn function 261, 1137f. Do-list, implied 968, 971, 1127 Do-loop 2/xiv Do-until iteration 14 Do-while iteration 13 Dogleg step methods 386 Domain of integration 155f. Dominant solution of recurrence relation 174 Dot (denotes matrix multiplication) 23 dot product() intrinsic function 945, 949, 969, 1216 Double exponential error distribution 696 Double precision converting to 1362 as refuge of scoundrels 882 use in iterative improvement 47, 1022 Double root 341 Downhill simplex method see Simplex, method of Nelder and Mead DP, defined 937 Driver programs 3 Dual viewpoint, in multigrid method 875 Duplication theorem, elliptic integrals 256 DWT (discrete wavelet transform) see Wavelet transform Dynamical allocation of storage 2/xiii, 869, 938, 941f., 953ff., 1327, 1336 garbage collection 956 increasing 955, 1070, 1302

E

ardley, D.M. 338 EBCDIC 890 Economization of power series 192f., 195, 1080 Eigensystems 449ff., 1225ff. balancing matrix 476f., 1230f. bounds on eigenvalues 50 calculation of few eigenvalues 454, 488 canned routines 454f. characteristic polynomial 449, 469 completeness 450 defective 450, 476, 489 deflation 471 degenerate eigenvalues 449ff. elimination method 453, 478, 1231 factorization method 453

fast Givens reduction 463 generalized eigenproblem 455 Givens reduction 462f. Hermitian matrix 475 Hessenberg matrix 453, 470, 476ff., 488, 1232 Householder transformation 453, 462ff., 469, 473, 475, 478, 1227f., 1231 ill-conditioned eigenvalues 477 implicit shifts 472ff., 1228f. and integral equations 779, 785 invariance under similarity transform 452 inverse iteration 455, 469, 476, 487ff., 1230 Jacobi transformation 453, 456ff., 462, 475, 489, 1225f. left eigenvalues 451 list of tasks 454f. multiple eigenvalues 489 nonlinear 455 nonsymmetric matrix 476ff., 1230ff. operation count of balancing 476 operation count of Givens reduction 463 operation count of Householder reduction 467 operation count of inverse iteration 488 operation count of Jacobi method 460 operation count of QL method 470, 473 operation count of QR method for Hessenberg matrices 484 operation count of reduction to Hessenberg form 479 orthogonality 450 parallel algorithms 1226, 1229 polynomial roots and 368, 1193 QL method 469ff., 475, 488f. QL method with implicit shifts 472ff., 1228f. QR method 52, 453, 456, 469ff., 1228 QR method for Hessenberg matrices 480ff., 1232ff. real, symmetric matrix 150, 467, 785, 1225, 1228 reduction to Hessenberg form 478f., 1231 right eigenvalues 451 shifting eigenvalues 449, 470f., 480 special matrices 454 termination criterion 484, 488 tridiagonal matrix 453, 469ff., 488, 1228 Eigenvalue and eigenvector, defined 449 Eigenvalue problem for differential equations 748, 764ff., 770ff., 1319ff. Eigenvalues and polynomial root finding 368, 1193 EISPACK 454, 475 Electromagnetic potential 519 ELEMENTAL attribute (Fortran 95) 961, 1084 Elemental functions 2/xiii, 2/xv, 940, 942, 946f., 961, 986, 1015, 1083, 1097f. Elimination see Gaussian elimination Ellipse in confidence limit estimation 688 Elliptic integrals 254ff., 906 addition theorem 255

Index to Volumes 1 and 2

943

Carlson's forms and algorithms 255f., 1128ff. Cauchy principal value 256f. duplication theorem 256 Legendre 254ff., 260f., 1135ff. routines for 257ff., 1128ff. symmetric form 255 Weierstrass 255 Elliptic partial differential equations 818, 1332ff. alternating-direction implicit method (ADI) 861f., 906 analyze/factorize/operate package 824 biconjugate gradient method 824 boundary conditions 820 comparison of rapid methods 854 conjugate gradient method 824 cyclic reduction 848f., 852ff. Fourier analysis and cyclic reduction (FACR) 848ff., 854 Gauss-Seidel method 855, 864ff., 876, 1338, 1341 incomplete Cholesky conjugate gradient method (ICCG) 824 Jacobi's method 855f., 864 matrix methods 824 multigrid method 824, 862ff., 1009, 1334ff. rapid (Fourier) method 824, 848ff. relaxation method 823, 854ff., 1332 strongly implicit procedure 824 successive over-relaxation (SOR) 857ff., 862, 866, 1332 elsewhere construct 943 Emacs, GNU 1/xvi Embedded Runge-Kutta method 709f., 731, 1298, 1308 Encapsulation, in programs 7 Encryption 290, 1156 enddo statement 12, 17 Entropy 896 of data 626ff., 811, 1275 EOM (end of message) 902 eoshift() intrinsic function 950 communication bottleneck 969 vector shift argument 1019f. vs. array section 1078 epsilon() intrinsic function 951, 1189 Equality constraints 423 Equations cubic 178ff., 360 normal (fitting) 645, 666ff., 800, 1288 quadratic 20, 178 see also Differential equations; Partial differential equations; Root finding Equivalence classes 337f., 1180 EQUIVALENCE statement 2/xif., 1161, 1286 Equivalence transformation 166 Error checksums for preventing 891 clocking 891 double exponential distribution 696 local truncation 875 Lorentzian distribution 696f. in multigrid method 863 nonnormal 653, 690, 694ff.

relative truncation 875 roundoff 180f., 881, 1362 series, advantage of an even 132f., 717, 1362 systematic vs. statistical 653, 1362 truncation 20f., 180, 399, 709, 881, 1362 varieties found by check digits 895 varieties of, in PDEs 831ff. see also Roundoff error Error function 213f., 601, 1094f. approximation via sampling theorem 601 Chebyshev approximation 214, 1095 complex 252 for Fisher's z-transformation 632, 1276 relation to Dawson's integral 252, 1127 relation to Fresnel integrals 248 relation to incomplete gamma function 213 routine for 214, 1094 for significance of correlation 631, 1276 for sum squared difference of ranks 635, 1277 Error handling in programs 2/xii, 2/xvi, 3, 994f., 1036, 1370f. Estimation of parameters see Fitting; Maximum likelihood estimate Estimation of power spectrum 542ff., 565ff., 1254ff., 1258 Euler equation (fluid flow) 831 Euler-Maclaurin summation formula 132, 135 Euler's constant 216ff., 250 Euler's method for differential equations 702, 704, 728f. Euler's transformation 160f., 1070 generalized form 162f. Evaluation of functions see Function Even and odd parts, of continued fraction 166, 211, 216 Even parity 888 Exception handling in programs see Error handling in programs exit statement 959, 1219 Explicit differencing 827 Exponent in floating point format 19, 882, 1343 exponent intrinsic function 1107 Exponential deviate 278, 1151f. Exponential integral 215ff., 1096f. asymptotic expansion 218 continued fraction 216 recurrence relation 172 related to incomplete gamma function 215 relation to cosine integral 250 routine for Ei(x) 218, 1097 routine for En (x) 217, 1096 series 216 Exponential probability distribution 570 Extended midpoint rule 124f., 129f., 135, 1054f. Extended Simpson's rule 128, 788, 790 Extended Simpson's three-eighths rule 789 Extended trapezoidal rule 125, 127, 130ff., 135, 786, 1052ff., 1326 roundoff error 132 Extirpolation (so-called) 574, 1261

944

Index to Volumes 1 and 2

Extrapolation 99ff. in Bulirsch-Stoer method 718ff., 726, 1305ff. differential equations 702 by linear prediction 557ff., 1256f. local 709 maximum entropy method as type of 567 polynomial 724, 726, 740, 1305f. rational function 718ff., 726, 1306f. relation to interpolation 101 for Romberg integration 134 see also Interpolation Extremization see Minimization

F

-distribution probability function 222 F-test for differences of variances 611, 613, 1271 FACR see Fourier analysis and cyclic reduction (FACR) Facsimile standard 901 Factorial double (denoted "!!") 247 evaluation of 159, 1072, 1086 relation to gamma function 206 routine for 207f., 1086ff. False position 347ff., 1185f. Family tree 338 FAS (full approximation storage algorithm) 874, 1339ff. Fast Fourier transform (FFT) 498ff., 881, 981, 1235f. alternative algorithms 503f. as approximation to continuous transform 497 Bartlett window 547, 1254 bit reversal 499f., 525 and Clenshaw-Curtis quadrature 190 column-parallel algorithm 981, 1237ff. communication bottleneck 969, 981, 1250 convolution 503f., 523, 531ff., 909, 1253, 1354 convolution of large data sets 536f. Cooley-Tukey algorithm 503, 1250 Cooley-Tukey algorithm, parallel 1239f. correlation 538f., 1254 cosine transform 190, 511ff., 851, 1245f. cosine transform, second form 513, 852, 1246 Danielson-Lanczos lemma 498f., 525 data sets not a power of 2 503 data smoothing 645 data windowing 545ff., 1254 decimation-in-frequency algorithm 503 decimation-in-time algorithm 503 discrete autocorrelation 539, 1254 discrete convolution theorem 531ff. discrete correlation theorem 538 at double frequency 575 effect of caching 982 endpoint corrections 578f., 1261ff. external storage 525 figures of merit for data windows 548 filtering 551ff. FIR filter 553 four-step framework 983, 1239

Fourier integrals 577ff., 1261 Fourier integrals, infinite range 583 Hamming window 547 Hann window 547 history 498 IIR filter 553ff. image processing 803, 805 integrals using 124 inverse of cosine transform 512ff. inverse of sine transform 511 large data sets 525 leakage 544 memory-local algorithm 528 multidimensional 515ff., 1236f., 1241, 1246, 1251 for multiple precision arithmetic 906 for multiple precision multiplication 909, 1354 number-theoretic transforms 503f. operation count 498 optimal (Wiener) filtering 539ff., 558 order of storage in 501 parallel algorithms 981ff., 1235ff. partial differential equations 824, 848ff. Parzen window 547 periodicity of 497 periodogram 543ff., 566 power spectrum estimation 542ff., 1254ff. for quadrature 124 of real data in 2D and 3D 519ff., 1248f. of real functions 504ff., 519ff., 1242f., 1248f. related algorithms 503f. row-parallel algorithm 981, 1235f. Sande-Tukey algorithm 503 sine transform 508ff., 850, 1245 Singleton's algorithm 525 six-step framework 983, 1240 square window 546, 1254 timing 982 treatment of end effects in convolution 533 treatment of end effects in correlation 538f. Tukey's trick for frequency doubling 575 use in smoothing data 645 used for Lomb periodogram 574, 1259 variance of power spectrum estimate 544f., 549 virtual memory machine 528 Welch window 547, 1254 Winograd algorithms 503 see also Discrete Fourier transform (DFT); Fourier transform; Spectral density Faure sequence 300 Fax (facsimile) Group 3 standard 901 Feasible vector 424 FFT see Fast Fourier transform (FFT) Field, in data record 329 Figure-of-merit function 650 Filon's method 583 Filter 551ff. acausal 552 bilinear transformation method 554 causal 552, 644

Index to Volumes 1 and 2

945

characteristic polynomial 554 data smoothing 644f., 1283f. digital 551ff. DISPO 644 by fast Fourier transform (FFT) 523, 551ff. finite impulse response (FIR) 531, 552 homogeneous modes of 554 infinite impulse response (IIR) 552ff., 566 Kalman 700 linear 552ff. low-pass for smoothing 644ff., 1283f. nonrecursive 552 optimal (Wiener) 535, 539ff., 558, 644 quadrature mirror 585, 593 realizable 552, 554f. recursive 552ff., 566 Remes exchange algorithm 553 Savitzky-Golay 183, 644ff., 1283f. stability of 554f. in the time domain 551ff. Fine-to-coarse operator 864, 1337 Finite difference equations (FDEs) 753, 763, 774 alternating-direction implicit method (ADI) 847, 861f. art not science 829 Cayley's form for unitary operator 844 Courant condition 829, 832ff., 836 Courant condition (multidimensional) 846 Crank-Nicholson method 840, 844, 846 eigenmodes of 827f. explicit vs. implicit schemes 827 forward Euler 826f. Forward Time Centered Space (FTCS) 827ff., 839ff., 843, 855 implicit scheme 840 Lax method 828ff., 836 Lax method (multidimensional) 845f. mesh drifting instability 834f. numerical derivatives 181 partial differential equations 821ff. in relaxation methods 753ff. staggered leapfrog method 833f. two-step Lax-Wendroff method 835ff. upwind differencing 832f., 837 see also Partial differential equations Finite element methods, partial differential equations 824 Finite impulse response (FIR) 531 Finkelstein, S. 1/xvi, 2/ix FIR (finite impulse response) filter 552 Fisher's z-transformation 631f., 1276 Fitting 650ff., 1285ff. basis functions 665 by Chebyshev approximation 185f., 1076 chi-square 653ff., 1285ff. confidence levels related to chi-square values 691ff. confidence levels from singular value decomposition (SVD) 693f. confidence limits on fitted parameters 684ff. covariance matrix not always meaningful 651, 690 degeneracy of parameters 674

an exponential 674 freezing parameters in 668, 700 Gaussians, a sum of 682, 1294 general linear least squares 665ff., 1288, 1290f. Kalman filter 700 K-S test, caution regarding 621f. least squares 651ff., 1285 Legendre polynomials 674, 1291f. Levenberg-Marquardt method 678ff., 816, 1292f. linear regression 655ff., 1285ff. maximum likelihood estimation 652f., 694ff. Monte Carlo simulation 622, 654, 684ff. multidimensional 675 nonlinear models 675ff., 1292f. nonlinear models, advanced methods 683 nonlinear problems that are linear 674 nonnormal errors 656, 690, 694ff. polynomial 83, 114, 191, 645, 665, 674, 1078, 1291 by rational Chebyshev approximation 197ff., 1081f. robust methods 694ff., 1294 of sharp spectral features 566 standard (probable) errors on fitted parameters 657f., 661, 667, 671, 684ff., 1285f., 1288, 1290 straight line 655ff., 667f., 698, 1285ff., 1294ff. straight line, errors in both coordinates 660ff., 1286ff. see also Error; Least squares fitting; Maximum likelihood estimate; Robust estimation Five-point difference star 867 Fixed point format 18 Fletcher-Powell algorithm see Davidon-FletcherPowell algorithm Fletcher-Reeves algorithm 390, 414ff., 1214 Floating point co-processor 886 Floating point format 18ff., 882, 1343 care in numerical derivatives 181 IEEE 276, 882, 1343 floor() intrinsic function 948 Flux-conservative initial value problems 825ff. FMG (full multigrid method) 863, 868, 1334ff. FOR iteration 9f., 12 forall statement 2/xii, 2/xv, 960, 964, 986 access to associated index 968 skew array sections 985, 1007 Formats of numbers 18ff., 882, 1343 Fortran 9 arithmetic-if statement 2/xi COMMON block 2/xif., 953, 957 deprecated features 2/xif., 947, 1057, 1161, 1256, 1286 dynamical allocation of storage 869, 1336 EQUIVALENCE statement 2/xif., 1161, 1286 evolution of 2/xivff. exception handling 2/xii, 2/xvi filenames 935 Fortran 2000 (planned) 2/xvi

946

Index to Volumes 1 and 2

Fo Fo

Fo Fo

Fortran 95 2/xv, 945, 947, 1084, 1100, 1364 HPF (High-Performance Fortran) 2/xvf. Numerical Recipes in 2/x, 2/xvii, 1 obsolescent features 2/xif. side effects 960 see also Fortran 90 rtran D 2/xv rtran 77 1/xix bit manipulation functions 17 hexadecimal constants 17 rtran 8x 2/xi, 2/xiii rtran 90 3 abstract data types 2/xiii, 1030 all() intrinsic function 945, 948 allocatable array 938, 941, 953ff., 1197, 1212, 1266, 1293, 1306, 1336 allocate statement 938f., 941, 953f., 1197, 1266, 1293, 1306, 1336 allocated() intrinsic function 938, 952ff., 1197, 1266, 1293 any() intrinsic function 945, 948 array allocation and deallocation 953 array of arrays 2/xii, 956, 1336 array constructor 2/xii, 968, 971, 1022, 1052, 1055, 1127 array constructor with implied do-list 968, 971 array extents 938, 949 array features 941ff., 953ff. array intrinsic procedures 2/xiii, 948ff. array of length 0 944 array of length 1 949 array manipulation functions 950 array parallel operations 964f. array rank 938, 949 array reallocation 955 array section 2/xiif., 2/xiii, 939, 941ff., 960, 1078, 1284, 1286, 1333 array shape 938, 949 array size 938, 942 array transpose 981f. array unary and binary functions 949 associated() intrinsic function 952f. associated pointer 953f. assumed-shape array 942 automatic array 938, 954, 1197, 1212, 1336 backwards-compatibility 935, 946 bit manipulation functions 2/xiii, 951 bit size() intrinsic function 951 broadcasts 965f. btest() intrinsic function 951 case construct 1010, 1036 case insensitive 937 ceiling() intrinsic function 947 character functions 952 character variables 1183 cmplx function 1125 communication bottlenecks 969, 981, 1250 compatibility with Fortran 77 935, 946 compilers 2/viii, 2/xiv, 1364 compiling 936 conformable arrays 942f., 1094

CONTAINS statement 954, 957, 985, 1067, 1134, 1202 control structure 2/xiv, 959, 1219, 1305 conversion elemental functions 946 count() intrinsic function 948 cshift() intrinsic function 950, 969 cycle statement 959, 1219 data hiding 956ff., 1209 data parallelism 964 DATA statement 959 data types 937, 1336, 1346, 1361 deallocate statement 938f., 953f., 1197, 1266, 1293 deallocating array 938, 953f., 1197, 1266, 1293 defined types 956 deprecated features 947, 1057, 1161, 1256, 1286 derived types 937, 955 dimensional expansion 965ff. do-loop 2/xiv dot product() intrinsic function 945, 949, 969, 1216 dynamical allocation of storage 2/xiii, 938, 941f., 953ff., 1327, 1336 elemental functions 940, 942, 946f., 951, 1015, 1083, 1364 elsewhere construct 943 eoshift() intrinsic function 950, 969, 1019f., 1078 epsilon() intrinsic function 951, 1189 evolution 2/xivff., 959, 987f. example 936 exit statement 959, 1219 exponent() intrinsic function 1107 floor() intrinsic function 948 Fortran tip icon 1009 garbage collection 956 gather-scatter operations 2/xiif., 969, 981, 984, 1002, 1032, 1034, 1250 generic interface 2/xiii, 1083 generic procedures 939, 1015, 1083, 1094, 1096, 1364 global variables 955, 957, 1210 history 2/xff. huge() intrinsic function 951 iand() intrinsic function 951 ibclr() intrinsic function 951 ibits() intrinsic function 951 ibset() intrinsic function 951 ieor() intrinsic function 951 IMPLICIT NONE statement 2/xiv, 936 implied do-list 968, 971, 1127 index loss 967f. initialization expression 943, 959, 1012, 1127 inquiry functions 948 integer model 1144, 1149, 1156 INTENT attribute 1072, 1092 interface 939, 942, 1067, 1084, 1384 internal subprogram 2/xii, 2/xiv, 957, 1057, 1067, 1202f., 1256, 1302 interprocessor communication 969, 981, 1250 intrinsic data types 937

Index to Volumes 1 and 2

947

intrinsic procedures 939, 945ff., 987, 1016 ior() intrinsic function 951 ishft() intrinsic function 951 ishftc() intrinsic function 951 ISO (International Standards Organization) 2/xf., 2/xiiif. keyword argument 2/xiv, 947f., 1341 kind() intrinsic function 951 KIND parameter 937, 946, 1125, 1144, 1192, 1254, 1261, 1284, 1361 language features 935ff. lbound() intrinsic function 949 lexical comparison 952 linear algebra 969f., 1000ff., 1018f., 1026, 1040, 1200, 1326 linear recurrence 971, 988 linking 936 literal constant 937, 1361 logo for tips 2/viii, 1009 mask 948, 967f., 1006f., 1038, 1102, 1200, 1226, 1305, 1333f., 1368, 1378, 1382 matmul() intrinsic function 945, 949, 969, 1026, 1040, 1050, 1076, 1200, 1216, 1290, 1326 maxexponent() intrinsic function 1107 maxloc() intrinsic function 949, 961, 992f., 1015 maxval() intrinsic function 945, 948, 961, 1016, 1273 memory leaks 953, 956, 1327 memory management 938, 953ff. merge() intrinsic function 945, 950, 1010, 1094f., 1099f. Metcalf and Reid (M&R) 935 minloc() intrinsic function 949, 961, 992f. minval() intrinsic function 948, 961 missing language features 983ff., 987ff. modularization 956f. MODULE facility 2/xiii, 936f., 939f., 953f., 957, 1067, 1298, 1320, 1322, 1324, 1330, 1346 MODULE subprograms 940 modulo() intrinsic function 946, 1156 named constant 940, 1012, 1361 named control structure 959, 1219, 1305 nearest() intrinsic function 952, 1146 nested where construct forbidden 943 not() intrinsic function 951 nullify statement 953f., 1070, 1302 numerical representation functions 951 ONLY option 941, 957, 1067 operator overloading 2/xiif. operator, user-defined 2/xii optional argument 2/xiv, 947f., 1092, 1228, 1230, 1256, 1272, 1275, 1340 outer product 969f. overloading 940, 1083, 1102 pack() intrinsic function 945, 950, 964, 969, 991, 1170, 1176, 1178 pack, for selective evaluation 1087 parallel extensions 2/xv, 959ff., 964, 981, 984, 987, 1002, 1032 parallel programming 963ff. PARAMETER attribute 1012

pointer 2/xiiif., 938f., 941, 944f., 952ff., 1067, 1070, 1197, 1210, 1212, 1266, 1302, 1327, 1336 pointer to function (missing) 1067 portability 963 present() intrinsic function 952 PRIVATE attribute 957, 1067 product() intrinsic function 948 programming conventions 937 PUBLIC attribute 957, 1067 quick start 936 radix() intrinsic function 1231 random number() intrinsic function 1141, 1143 random seed() intrinsic function 1141 real() intrinsic function 947, 1125 RECURSIVE keyword 958, 1065, 1067 recursive procedure 2/xiv, 958, 1065, 1067, 1166 reduction functions 948 reshape() intrinsic function 950, 969, 1247 RESULT keyword 958, 1073 SAVE attribute 953f., 958f., 1052, 1070, 1266, 1293 scale() intrinsic function 1107 scatter-with-combine (missing function) 984 scope 956ff. scoping units 939 select case statement 2/xiv, 1010, 1036 shape() intrinsic function 938, 949 size() intrinsic function 938, 942, 945, 948 skew sections 985 sparse matrix representation 1030 specification statement 2/xiv spread() intrinsic function 945, 950, 966ff., 969, 1000, 1094, 1290f. statement functions deprecated 1057 stride (of an array) 944 structure constructor 2/xii subscript triplet 944 sum() intrinsic function 945, 948, 966 tiny() intrinsic function 952 transformational functions 948 transpose() intrinsic function 950, 960, 969, 981, 1247 tricks 1009, 1072, 1146, 1274, 1278, 1280 truncation elemental functions 946 type checking 1140 ubound() intrinsic function 949 undefined pointer 953 unpack() intrinsic function 950, 964, 969 USE statement 936, 939f., 954, 957, 1067, 1384 utility functions 987ff. vector subscripts 2/xiif., 969, 981, 984, 1002, 1032, 1034, 1250 visibility 956ff., 1209, 1293, 1296 WG5 technical committee 2/xi, 2/xiii, 2/xvf. where construct 943, 985, 1060, 1291 X3J3 Committee 2/viii, 2/xff., 2/xv, 947, 959, 964, 968, 990 zero-length array 944

948

Index to Volumes 1 and 2

see also Intrinsic procedures see also Fortran Fortran 95 947, 959ff. allocatable variables 961 blocks 960 cpu time() intrinsic function 961 elemental functions 2/xiii, 2/xv, 940, 961, 986, 1015, 1083f., 1097f. forall statement 2/xii, 2/xv, 960, 964, 968, 986, 1007 initialization of derived data type 2/xv initialization of pointer 2/xv, 961 minor changes from Fortran 90 961 modified intrinsic functions 961 nested where construct 2/xv, 960, 1100 pointer association status 961 pointers 961 PURE attribute 2/xv, 960f., 964, 986 SAVE attribute 961 side effects 960 and skew array section 945, 985 see also Fortran Fortran 2000 2/xvi Forward deflation 363 Forward difference operator 161 Forward Euler differencing 826f. Forward Time Centered Space see FTCS Four-step framework, for FFT 983, 1239 Fourier analysis and cyclic reduction (FACR) 848f., 854 Fourier integrals attenuation factors 583, 1261 endpoint corrections 578f., 1261 tail integration by parts 583 use of fast Fourier transform (FFT) 577ff., 1261ff. Fourier transform 99, 490ff., 1235ff. aliasing 495, 569 approximation of Dawson's integral 253 autocorrelation 492 basis functions compared 508f. contrasted with wavelet transform 584, 594 convolution 492, 503f., 531ff., 909, 1253, 1354 correlation 492, 538f., 1254 cosine transform 190, 511ff., 851, 1245f. cosine transform, second form 513, 852, 1246 critical sampling 494, 543, 545 definition 490 discrete Fourier transform (DFT) 184, 495ff. Gaussian function 600 image processing 803, 805 infinite range 583 inverse of discrete Fourier transform 497 method for partial differential equations 848ff. missing data 569 missing data, fast algorithm 574f., 1259 Nyquist frequency 494ff., 520, 543, 545, 569, 571 optimal (Wiener) filtering 539ff., 558 Parseval's theorem 492, 498, 544

power spectral density (PSD) 492f. power spectrum estimation by FFT 542ff., 1254ff. power spectrum estimation by maximum entropy method 565ff., 1258 properties of 491f. sampling theorem 495, 543, 545, 600 scalings of 491 significance of a peak in 570 sine transform 508ff., 850, 1245 symmetries of 491 uneven sampling, fast algorithm 574f., 1259 unevenly sampled data 569ff., 574, 1258 and wavelets 592f. Wiener-Khinchin theorem 492, 558, 566f. see also Fast Fourier transform (FFT); Spectral density Fractal region 360f. Fractional step methods 847f. Fredholm alternative 780 Fredholm equations 779f. eigenvalue problems 780, 785 error estimate in solution 784 first kind 779 Fredholm alternative 780 homogeneous, second kind 785, 1325 homogeneous vs. inhomogeneous 779f. ill-conditioned 780 infinite range 789 inverse problems 780, 795ff. kernel 779f. nonlinear 781 Nystrom method 782ff., 789, 1325 product Nystrom method 789, 1328ff. second kind 779f., 782ff., 1325, 1331 with singularities 788, 1328ff. with singularities, worked example 792, 1328ff. subtraction of singularity 789 symmetric kernel 785 see also Inverse problems Frequency domain 490 Frequency spectrum see Fast Fourier transform (FFT) Frequentist, contrasted with Bayesian 810 Fresnel integrals 248ff. asymptotic form 249 continued fraction 248f. routine for 249f., 1123 series 248 Friday the Thirteenth 14f., 1011f. FTCS (forward time centered space) 827ff., 839ff., 843 stability of 827ff., 839ff., 855 Full approximation storage (FAS) algorithm 874, 1339ff. Full moon 14f., 936, 1011f. Full multigrid method (FMG) 863, 868, 1334ff. Full Newton methods, nonlinear least squares 683 Full pivoting 29, 1014 Full weighting 867 Function Airy 204, 243f., 1121

Index to Volumes 1 and 2

949

approximation 99ff., 184ff., 1043, 1076ff. associated Legendre polynomial 246ff., 764, 1122f., 1319 autocorrelation of 492 bandwidth limited 495 Bessel 172, 204, 223ff., 234, 1101ff., 1115ff. beta 209, 1089 binomial coefficients 208f., 1087f. branch cuts of 202f. chi-square probability 215, 798 complex 202 confluent hypergeometric 204, 239 convolution of 492 correlation of 492 cosine integral 250f., 1123f. Coulomb wave 204, 234 cumulative binomial probability 222f. cumulative Poisson 209ff. Dawson's integral 252ff., 600, 1127f. digamma 216 elliptic integrals 254ff., 906, 1128ff. error 213f., 248, 252, 601, 631, 635, 1094f., 1127, 1276f. evaluation 159ff., 1070ff. evaluation by path integration 201ff., 263, 1138 exponential integral 172, 215ff., 250, 1096f. F-distribution probability 222 Fresnel integral 248ff., 1123 gamma 206, 1085 hypergeometric 202f., 263ff., 1138ff. incomplete beta 219ff., 610, 1098ff., 1269 incomplete gamma 209ff., 615, 654, 657f., 1089ff., 1272, 1285 inverse hyperbolic 178, 255 inverse trigonometric 255 Jacobian elliptic 261, 1137f. Kolmogorov-Smirnov probability 618f., 640, 1274, 1281 Legendre polynomial 172, 246, 674, 1122, 1291 logarithm 255 modified Bessel 229ff., 1109ff. modified Bessel, fractional order 239ff., 1118ff. overloading 1083 parallel evaluation 986, 1009, 1084, 1087, 1090, 1102, 1128, 1134 path integration to evaluate 201ff. pathological 99f., 343 Poisson cumulant 214 representations of 490 routine for plotting a 342, 1182 sine and cosine integrals 248, 250ff., 1125f. sn, dn, cn 261, 1137f. spherical harmonics 246ff., 1122 spheroidal harmonic 764ff., 770ff., 1319ff., 1323ff. Student's probability 221f. variable number of arguments 1022 Weber 204

Functional iteration, for implicit equations 740f. FWHM (full width at half maximum) 548f.

G amma deviate 282f., 1153f. Gamma function 206ff., 1085 incomplete see Incomplete gamma function Garbage collection 956 Gather-scatter operations 2/xiif., 984, 1002, 1032, 1034 communication bottleneck 969, 981, 1250 many-to-one 984, 1002, 1032, 1034 Gauss-Chebyshev integration 141, 144, 512f. Gauss-Hermite integration 144, 789 abscissas and weights 147, 1062 normalization 147 Gauss-Jacobi integration 144 abscissas and weights 148, 1063 Gauss-Jordan elimination 27ff., 33, 64, 1014f. operation count 34, 39 solution of normal equations 667, 1288 storage requirements 30 Gauss-Kronrod quadrature 154 Gauss-Laguerre integration 144, 789, 1060 Gauss-Legendre integration 145f., 1059 see also Gaussian integration Gauss-Lobatto quadrature 154, 190, 512 Gauss-Radau quadrature 154 Gauss-Seidel method (relaxation) 855, 857, 864ff., 1338 nonlinear 876, 1341 Gauss transformation 256 Gaussian (normal) distribution 267, 652, 798 central limit theorem 652f. deviates from 279f., 571, 1152 kurtosis of 606 multivariate 690 semi-invariants of 608 tails compared to Poisson 653 two-dimensional (binormal) 631 variance of skewness of 606 Gaussian elimination 33f., 51, 55, 1014f. fill-in 45, 64 integral equations 786, 1326 operation count 34 outer product variant 1017 in reduction to Hessenberg form 478, 1231 relaxation solution of boundary value problems 753ff., 777, 1316 Gaussian function Hardy's theorem on Fourier transforms 600 see also Gaussian (normal) distribution Gaussian integration 127, 140ff., 789, 1059ff. calculation of abscissas and weights 142ff., 1009, 1059ff. error estimate in solution 784 extensions of 153f. Golub-Welsch algorithm for weights and abscissas 150, 1064 for integral equations 781, 783, 1325 from known recurrence relation 150, 1064

950

Index to Volumes 1 and 2

nonclassical weight function 151ff., 788f., 1064f., 1328f. and orthogonal polynomials 142, 1009, 1061 parallel calculation of formulas 1009, 1061 preassigned nodes 153f. weight function log x 153 weight functions 140ff., 788f., 1059ff., 1328f. Gear's method (stiff ODEs) 730 Geiger counter 266 Generalized eigenvalue problems 455 Generalized minimum residual method (GMRES) 78 Generic interface see Interface, generic Generic procedures 939, 1083, 1094, 1096, 1364 elemental 940, 942, 946f., 1015, 1083 Geometric progression 972, 996f., 1365, 1372ff. geop() utility function 972, 974, 989, 996, 1127 Geophysics, use of Backus-Gilbert method 809 Gerchberg-Saxton algorithm 805 get diag() utility function 985, 989, 1005, 1226 Gilbert and Sullivan 714 Givens reduction 462f., 473 fast 463 operation count 463 Glassman, A.J. 180 Global optimization 387f., 436ff., 650, 1219ff. continuous variables 443f., 1222 Global variables 940, 953f., 1210 allocatable array method 954, 1197, 1212, 1266, 1287, 1298 communicated via internal subprogram 954, 957f., 1067, 1226 danger of 957, 1209, 1293, 1296 pointer method 954, 1197, 1212, 1266, 1287, 1302 Globally convergent minimization 418ff., 1215 root finding 373, 376ff., 382, 749f., 752, 1196, 1314f. GMRES (generalized minimum residual method) 78 GNU Emacs 1/xvi Godunov's method 837 Golden mean (golden ratio) 21, 349, 392f., 399 Golden section search 341, 389ff., 395, 1202ff. Golub-Welsch algorithm, for Gaussian quadrature 150, 1064 Goodness-of-fit 650, 654, 657f., 662, 690, 1285 GOTO statements, danger of 9, 959 Gram-Schmidt biorthogonalization 415f. orthogonalization 94, 450f., 1039 SVD as alternative to 58 Graphics, function plotting 342, 1182f. Gravitational potential 519

G G G G G G

ray code 300, 881, 886ff., 1344 reenbaum, A. 79 regorian calendar 13, 16, 1011, 1013 rid square 116f. roup, dihedral 894, 1345 uard digits 882, 1343

alf weighting 867, 1337 lton's quasi-random sequence 300 mming window 547 mming's motto 341 nn window 547 rmonic analysis see Fourier transform shing 293, 1144, 1148, 1156 for random number seeds 1147f. HDLC checksum 890 Heap (data structure) 327f., 336, 897, 1179 Heapsort 320, 327f., 336, 1171f., 1179 Helmholtz equation 852 Hermite polynomials 144, 147 approximation of roots 1062 Hermitian matrix 450ff., 475 Hertz (unit of frequency) 490 Hessenberg matrix 94, 453, 470, 476ff., 488, 1231 see also Matrix Hessian matrix 382, 408, 415f., 419f., 676ff., 803, 815 is inverse of covariance matrix 667, 679 second derivatives in 676 Hexadecimal constants 17f., 276, 293 initialization 959 Hierarchically band diagonal matrix 598 Hierarchy of program structure 6ff. High-order not same as high-accuracy 100f., 124, 389, 399, 705, 709, 741 High-pass filter 551 High-Performance Fortran (HPF) 2/xvf., 964, 981, 984 scatter-with-add 1032 Hilbert matrix 83 Home page, Numerical Recipes 1/xx, 2/xvii Homogeneous linear equations 53 Hook step methods 386 Hotelling's method for matrix inverse 49, 598 Householder transformation 52, 453, 462ff., 469, 473, 475, 478, 481ff., 1227f. operation count 467 in QR decomposition 92, 1039 HPF see High-Performance Fortran Huffman coding 564, 881, 896f., 902, 1346ff. huge() intrinsic function 951 Hyperbolic functions, explicit formulas for inverse 178 Hyperbolic partial differential equations 818 advective equation 826 flux-conservative initial value problems 825ff. Hypergeometric function 202f., 263ff. routine for 264f., 1138 Hypothesis, null 603 H H H H H H a a a a a a

H

I

2B, defined 937

Index to Volumes 1 and 2

951

I4B, defined 937 iand() intrinsic function 951 ibclr() intrinsic function 951 ibits() intrinsic function 951 IBM 1/xxiii, 2/xix bad random number generator 268 Fortran 90 compiler 2/viii PC 4, 276, 293, 886 PC-RT 4 radix base for floating point arithmetic 476 RS6000 2/viii, 4 IBM checksum 894 ibset() intrinsic function 951 ICCG (incomplete Cholesky conjugate gradient method) 824 ICF (intrinsic correlation function) model 817 Identity (unit) matrix 25 IEEE floating point format 276, 882f., 1343 ieor() intrinsic function 951 if statement, arithmetic 2/xi if structure 12f. ifirstloc() utility function 989, 993, 1041, 1346 IIR (infinite impulse response) filter 552ff., 566 Ill-conditioned integral equations 780 Image processing 519, 803 cosine transform 513 fast Fourier transform (FFT) 519, 523, 803 as an inverse problem 803 maximum entropy method (MEM) 809ff. from modulus of Fourier transform 805 wavelet transform 596f., 1267f. imaxloc() utility function 989, 993, 1017 iminloc() utility function 989, 993, 1046, 1076 Implicit function theorem 340 pivoting 30, 1014 shifts in QL method 472ff. Implicit differencing 827 for diffusion equation 840 for stiff equations 729, 740, 1308 IMPLICIT NONE statement 2/xiv, 936 Implied do-list 968, 971, 1127 Importance sampling, in Monte Carlo 306f. Improper integrals 135ff., 1055 Impulse response function 531, 540, 552 IMSL 1/xxiii, 2/xx, 26, 64, 205, 364, 369, 454 In-place selection 335, 1178f. Included file, superseded by module 940 Incomplete beta function 219ff., 1098ff. for F-test 613, 1271 routine for 220f., 1097 for Student's t 610, 613, 1269 Incomplete Cholesky conjugate gradient method (ICCG) 824 Incomplete gamma function 209ff., 1089ff. for chi-square 615, 654, 657f., 1272, 1285 deviates from 282f., 1153 in mode estimation 610 routine for 211f., 1089

Increment of linear congruential generator 268 Indentation of blocks 9 Index 934ff., 1446ff. this entry 1464 Index loss 967f., 1038 Index table 320, 329f., 1173ff., 1176 Inequality constraints 423 Inheritance 8 Initial value problems 702, 818f. see also Differential equations; Partial differential equations Initialization of derived data type 2/xv Initialization expression 943, 959, 1012, 1127 Injection operator 864, 1337 Instability see Stability Integer model, in Fortran 90 1144, 1149, 1156 Integer programming 436 Integral equations 779ff. adaptive stepsize control 788 block-by-block method 788 correspondence with linear algebraic equations 779ff. degenerate kernel 785 eigenvalue problems 780, 785 error estimate in solution 784 Fredholm 779f., 782ff., 1325, 1331 Fredholm alternative 780 homogeneous, second kind 785, 1325 ill-conditioned 780 infinite range 789 inverse problems 780, 795ff. kernel 779 nonlinear 781, 787 Nystrom method 782ff., 789, 1325 product Nystrom method 789, 1328ff. with singularities 788ff., 1328ff. with singularities, worked example 792, 1328ff. subtraction of singularity 789 symmetric kernel 785 unstable quadrature 787f. Volterra 780f., 786ff., 1326f. wavelets 782 see also Inverse problems Integral operator, wavelet approximation of 597, 782 Integration of functions 123ff., 1052ff. cosine integrals 250, 1125 Fourier integrals 577ff., 1261 Fourier integrals, infinite range 583 Fresnel integrals 248, 1123 Gauss-Hermite 147f., 1062 Gauss-Jacobi 148, 1063 Gauss-Laguerre 146, 1060 Gauss-Legendre 145, 1059 integrals that are elliptic integrals 254 path integration 201ff. sine integrals 250, 1125 see also Quadrature Integro-differential equations 782 INTENT attribute 1072, 1092 Interface (Fortran 90) 939, 942, 1067

952

Index to Volumes 1 and 2

In In In In

In In In

In In In In In

for communication between program parts 957, 1209, 1293, 1296 explicit 939, 942, 1067, 1384 generic 2/xiii, 940, 1015, 1083, 1094, 1096 implicit 939 for Numerical Recipes 1384ff. terface block 939, 1084, 1384 terface, in programs 2, 8 termediate value theorem 343 ternal subprogram (Fortran 90) 2/xiv, 954, 957, 1067, 1202f., 1226 nesting of 2/xii resembles C macro 1302 supersedes statement function 1057, 1256 ternational Standards Organization (ISO) 2/xf., 2/xiii ternet, availability of code over 1/xx, 2/xvii terpolation 99ff. Aitken's algorithm 102 avoid 2-stage method 100 avoid in Fourier analysis 569 bicubic 118f., 1049f. bilinear 117 caution on high-order 100 coefficients of polynomial 100, 113ff., 191, 575, 1047f., 1078 for computing Fourier integrals 578 error estimates for 100 of functions with poles 104ff., 1043f. inverse quadratic 353, 395ff., 1204 multidimensional 101f., 116ff., 1049ff. in multigrid method 866, 1337 Neville's algorithm 102f., 182, 1043 Nystrom 783, 1326 offset arrays 104, 113 operation count for 100 operator 864, 1337 order of 100 and ordinary differential equations 101 oscillations of polynomial 100, 116, 389, 399 parabolic, for minimum finding 395, 1204 polynomial 99, 102ff., 182, 1043 rational Chebyshev approximation 197ff., 1081 rational function 99, 104ff., 194ff., 225, 718ff., 726, 1043f., 1080, 1306 reverse (extirpolation) 574, 1261 spline 100, 107ff., 120f., 1044f., 1050f. trigonometric 99 see also Fitting terprocessor communication 969, 981 terval variable (statistics) 623 trinsic correlation function (ICF) model 817 trinsic data types 937 trinsic procedures array inquiry 938, 942, 948ff. array manipulation 950 array reduction 948 array unary and binary functions 949 backwards-compatibility 946 bit manipulation 2/xiii, 951 character 952 cmplx 1254

conversion elemental 946 elemental 940, 942, 946f., 951, 1083, 1364 generic 939, 1083f., 1364 lexical comparison 952 numeric inquiry 2/xiv, 1107, 1231, 1343 numerical 946, 951f. numerical representation 951 pack used for sorting 1171 random number 1143 real 1254 top 10 945 truncation 946f. see also Fortran 90 Inverse hyperbolic function 178, 255 Inverse iteration see Eigensystems Inverse problems 779, 795ff. Backus-Gilbert method 806ff. Bayesian approach 799, 810f., 816f. central idea 799 constrained linear inversion method 799ff. data inversion 807 deterministic constraints 804ff. in geophysics 809 Gerchberg-Saxton algorithm 805 incomplete Fourier coefficients 813 and integral equations 780 linear regularization 799ff. maximum entropy method (MEM) 810, 815f. MEM demystified 814 Phillips-Twomey method 799ff. principal solution 797 regularization 796ff. regularizing operator 798 stabilizing functional 798 Tikhonov-Miller regularization 799ff. trade-off curve 795 trade-off curve, Backus-Gilbert method 809 two-dimensional regularization 803 use of conjugate gradient minimization 804, 815 use of convex sets 804 use of Fourier transform 803, 805 Van Cittert's method 804 Inverse quadratic interpolation 353, 395ff., 1204 Inverse response kernel, in Backus-Gilbert method 807 Inverse trigonometric function 255 ior() intrinsic function 951 ISBN (International Standard Book Number) checksum 894 ishft() intrinsic function 951 ishftc() intrinsic function 951 ISO (International Standards Organization) 2/xf., 2/xiii Iterated integrals 155 Iteration 9f. functional 740f. to improve solution of linear algebraic equations 47ff., 195, 1022 for linear algebraic equations 26

Index to Volumes 1 and 2

953

required for two-point boundary value problems 745 in root finding 340f. Iteration matrix 856 ITPACK 71 Iverson, John 2/xi

J
J J J J J J J J J

acobi matrix, for Gaussian quadrature 150, 1064 acobi polynomials, approximation of roots 1064 acobi transformation (or rotation) 94, 453, 456ff., 462, 475, 489, 1041, 1225 acobian determinant 279, 774 acobian elliptic functions 261, 1137f. acobian matrix 374, 376, 379, 382, 731, 1197f., 1309 singular in Newton's rule 386 acobi's method (relaxation) 855ff., 864 enkins-Traub method 369 ulian Day 1, 13, 16, 936, 1010ff. ump transposition errors 895

-S test see Kolmogorov-Smirnov test lman filter 700 nji 2/xii ps-Rentrop method 730, 1308 ndall's tau 634, 637ff., 1279 nnedy, Ken 2/xv pler's equation 1061 rmit checksum 889 rnel 779 averaging, in Backus-Gilbert method 807 degenerate 785 finite rank 785 inverse response 807 separable 785 singular 788f., 1328 symmetric 785 Keys used in sorting 329, 889 Keyword argument 2/xiv, 947f., 1341 kind() intrinsic function 951 KIND parameter 946, 1261, 1284 and cmplx() intrinsic function 1125, 1192, 1254 default 937 for Numerical Recipes 1361 for random numbers 1144 and real() intrinsic function 1125 Kolmogorov-Smirnov test 614, 617ff., 694, 1273f. two-dimensional 640, 1281ff. variants 620ff., 640, 1281 Kuiper's statistic 621 Kurtosis 606, 608, 1269 K K K K K K K K a a a e e e e e

K

L-e
La La La La La

stimate 694 bels, statement 9 g 492, 538, 553 gged Fibonacci generator 1142, 1148ff. grange multiplier 795 grange's formula for polynomial interpolation 84, 102f., 575, 578

Laguerre polynomials, approximation of roots 1061 Laguerre's method 341, 365f., 1191f. Lanczos lemma 498f. Lanczos method for gamma function 206, 1085 Landen transformation 256 LAPACK 26, 1230 Laplace's equation 246, 818 see also Poisson equation Las Vegas 625 Latin square or hypercube 305f. Laurent series 566 Lax method 828ff., 836, 845f. multidimensional 845f. Lax-Wendroff method 835ff. lbound() intrinsic function 949 Leakage in power spectrum estimation 544, 548 Leakage width 548f. Leapfrog method 833f. Least squares filters see Savitzky-Golay filters Least squares fitting 645, 651ff., 655ff., 660ff., 665ff., 1285f., 1288f. contrasted to general minimization problems 684ff. degeneracies in 671f., 674 Fourier components 570 as M-estimate for normal errors 696 as maximum likelihood estimator 652 as method for smoothing data 645, 1283 Fourier components 1258 freezing parameters in 668, 700 general linear case 665ff., 1288, 1290f. Levenberg-Marquardt method 678ff., 816, 1292f. Lomb periodogram 570, 1258 multidimensional 675 nonlinear 386, 675ff., 816, 1292 nonlinear, advanced methods 683 normal equations 645, 666f., 800, 1288 normal equations often singular 670, 674 optimal (Wiener) filtering 540f. QR method in 94, 668 for rational Chebyshev approximation 199f., 1081f. relation to linear correlation 630, 658 Savitzky-Golay filter as 645, 1283 singular value decomposition (SVD) 25f., 51ff., 199f., 670ff., 1081, 1290 skewed by outliers 653 for spectral analysis 570, 1258 standard (probable) errors on fitted parameters 667, 671 weighted 652 see also Fitting L'Ecuyer's long period random generator 271, 273 Least squares fitting standard (probable) errors on fitted parameters 1288, 1290 weighted 1285 Left eigenvalues or eigenvectors 451 Legal matters 1/xx, 2/xvii Legendre elliptic integral see Elliptic integrals

954

Index to Volumes 1 and 2

Legendre polynomials 246, 1122 fitting data to 674, 1291f. recurrence relation 172 shifted monic 151 see also Associated Legendre polynomials; Spherical harmonics Lehmer-Schur algorithm 369 Lemarie's wavelet 593 Lentz's method for continued fraction 165, 212 Lepage, P. 309 Leptokurtic distribution 606 Levenberg-Marquardt algorithm 386, 678ff., 816, 1292 advanced implementation 683 Levinson's method 86, 1038 Lewis, H.W. 275 Lexical comparison functions 952 LGT, defined 937 License information 1/xx, 2/xviiff. Limbo 356 Limit cycle, in Laguerre's method 365 Line minimization see Minimization, along a ray Line search see Minimization, along a ray Linear algebra, intrinsic functions for parallelization 969f., 1026, 1040, 1200, 1326 Linear algebraic equations 22ff., 1014 band diagonal 43ff., 1019 biconjugate gradient method 77, 1034ff. Cholesky decomposition 89f., 423, 455, 668, 1038f. complex 41 computing A-1 З B 40 conjugate gradient method 77ff., 599, 1034 cyclic tridiagonal 67, 1030 direct methods 26, 64, 1014, 1030 Fortran 90 vs. library routines 1016 Gauss-Jordan elimination 27ff., 1014 Gaussian elimination 33f., 1014f. Hilbert matrix 83 Hotelling's method 49, 598 and integral equations 779ff., 783, 1325 iterative improvement 47ff., 195, 1022 iterative methods 26, 77ff., 1034 large sets of 23 least squares solution 53ff., 57f., 199f., 671, 1081, 1290 LU decomposition 34ff., 195, 386, 732, 783, 786, 801, 1016, 1022, 1325f. nonsingular 23 overdetermined 25f., 199, 670, 797 partitioned 70 QR decomposition 91f., 382, 386, 668, 1039f., 1199 row vs. column elimination 31f. Schultz's method 49, 598 Sherman-Morrison formula 65ff., 83 singular 22, 53, 58, 199, 670 singular value decomposition (SVD) 51ff., 199f., 670ff., 797, 1022, 1081, 1290 sparse 23, 43, 63ff., 732, 804, 1020f., 1030

summary of tasks 25f. Toeplitz 82, 85ff., 195, 1038 tridiagonal 26, 42f., 64, 109, 150, 453f., 462ff., 469ff., 488, 839f., 853, 861f., 1018f., 1227ff. Vandermonde 82ff., 114, 1037, 1047 wavelet solution 597ff., 782 Woodbury formula 68ff., 83 see also Eigensystems Linear congruential random number generator 267ff., 1142 choice of constants for 274ff. Linear constraints 423 Linear convergence 346, 393 Linear correlation (statistics) 630ff., 1276 Linear dependency constructing orthonormal basis 58, 94 of directions in N -dimensional space 409 in linear algebraic equations 22f. Linear equations see Differential equations; Integral equations; Linear algebraic equations Linear inversion method, constrained 799ff. Linear prediction 557ff. characteristic polynomial 559 coefficients 557ff., 1256 compared to maximum entropy method 558 compared with regularization 801 contrasted to polynomial extrapolation 560 related to optimal filtering 558 removal of bias in 563 stability 559f., 1257 Linear predictive coding (LPC) 563ff. Linear programming 387, 423ff., 1216ff. artificial variables 429 auxiliary objective function 430 basic variables 426 composite simplex algorithm 435 constraints 423 convergence criteria 432 degenerate feasible vector 429 dual problem 435 equality constraints 423 feasible basis vector 426 feasible vector 424 fundamental theorem 426 inequality constraints 423 left-hand variables 426 nonbasic variables 426 normal form 426 objective function 424 optimal feasible vector 424 pivot element 428f. primal-dual algorithm 435 primal problem 435 reduction to normal form 429ff. restricted normal form 426ff. revised simplex method 435 right-hand variables 426 simplex method 402, 423ff., 431ff., 1216ff. slack variables 429 tableau 427 vertex of simplex 426

Index to Volumes 1 and 2

955

Linear recurrence see Recurrence relation Linear regression 655ff., 660ff., 1285ff. see also Fitting Linear regularization 799ff. LINPACK 26 Literal constant 937, 1361 Little-endian 293 Local extrapolation 709 Local extremum 387f., 437 Localization of roots see Bracketing Logarithmic function 255 Lomb periodogram method of spectral analysis 569f., 1258f. fast algorithm 574f., 1259 Loops 9f. Lorentzian probability distribution 282, 696f. Low-pass filter 551, 644f., 1283f. Lower subscript 944 lower triangle() utility function 989, 1007, 1200 LP coefficients see Linear prediction LPC (linear predictive coding) 563ff. LU decomposition 34ff., 47f., 51, 55, 64, 97, 374, 667, 732, 1016, 1022 for A-1 З B 40 backsubstitution 39, 1017 band diagonal matrix 43ff., 1020 complex equations 41f. Crout's algorithm 36ff., 45, 1017 for integral equations 783, 786, 1325f. for inverse iteration of eigenvectors 488 for inverse problems 801 for matrix determinant 41 for matrix inverse 40, 1016 for nonlinear sets of equations 374, 386, 1196 operation count 36, 39 outer product Gaussian elimination 1017 for Pade approximant 195, 1080 Д pivoting 37f., 1017 repeated backsubstitution 40, 46 solution of linear algebraic equations 40, 1017 solution of normal equations 667 for Toeplitz matrix 87 Lucifer 290

M

&R (Metcalf and Reid) 935 M-estimates 694ff. how to compute 697f. local 695ff. see also Maximum likelihood estimate Machine accuracy 19f., 881f., 1189, 1343 Macintosh, see Apple Macintosh Maehly's procedure 364, 371 Magic in MEM image restoration 814 in Pade approximation 195 Д Mantissa in floating point format 19, 882, 909, 1343 Marginals 624 Marquardt method (least squares fitting) 678ff., 816, 1292f. Marsaglia shift register 1142, 1148ff. Marsaglia, G. 1142, 1149

mask 1006f., 1102, 1200, 1226, 1305, 1333f., 1368, 1378, 1382 optional argument 948 optional argument, facilitates parallelism 967f., 1038 Mass, center of 295ff. MasterCard checksum 894 Mathematical Center (Amsterdam) 353 Mathematical intrinsic functions 946, 951f. matmul() intrinsic function 945, 949, 969, 1026, 1040, 1050, 1076, 1200, 1216, 1290, 1326 Matrix 23ff. add vector to diagonal 1004, 1234, 1366, 1381 approximation of 58f., 598f. band diagonal 42ff., 64, 1019 band triangular 64 banded 26, 454 bidiagonal 52 block diagonal 64, 754 block triangular 64 block tridiagonal 64 bordered 64 characteristic polynomial 449, 469 Cholesky decomposition 89f., 423, 455, 668, 1038f. column augmented 28, 1014 complex 41 condition number 53, 78 create unit matrix 1006, 1382 curvature 677 cyclic banded 64 cyclic tridiagonal 67, 1030 defective 450, 476, 489 of derivatives see Hessian matrix; Jacobian determinant design (fitting) 645, 665, 801, 1082 determinant of 25, 41 diagonal of sparse matrix 1033ff. diagonalization 452ff., 1225ff. elementary row and column operations 28f. finite differencing of partial differential equations 821ff. get diagonal 985, 1005, 1226f., 1366, 1381f. Hermitian 450, 454, 475 Hermitian conjugate 450 Hessenberg 94, 453, 470, 476ff., 488, 1231ff. Hessian see Hessian matrix hierarchically band diagonal 598 Hilbert 83 identity 25 ill-conditioned 53, 56, 114 indexed storage of 71f., 1030 and integral equations 779, 783, 1325 inverse 25, 27, 34, 40, 65ff., 70, 95ff., 1014, 1016f. inverse, approximate 49 inverse by Hotelling's method 49, 598 inverse by Schultz's method 49, 598 inverse multiplied by a matrix 40 iteration for inverse 49, 598

956

Index to Volumes 1 and 2

Jacobi transformation 453, 456ff., 462, 1225f. Jacobian 731, 1309 logical dimension 24 lower triangular 34f., 89, 781, 1016 lower triangular mask 1007, 1200, 1382 multiplication denoted by dot 23 multiplication, intrinsic function 949, 969, 1026, 1040, 1050, 1200, 1326 norm 50 normal 450ff. nullity 53 nullspace 25, 53f., 449, 795 orthogonal 91, 450, 463ff., 587 orthogonal transformation 452, 463ff., 469, 1227 orthonormal basis 58, 94 outer product denoted by cross 66, 420 partitioning for determinant 70 partitioning for inverse 70 pattern multiply of sparse 74 physical dimension 24 positive definite 26, 89f., 668, 1038 QR decomposition 91f., 382, 386, 668, 1039, 1199 range 53 rank 53 residual 49 row and column indices 23 row vs. column operations 31f. self-adjoint 450 set diagonal elements 1005, 1200, 1366, 1382 similarity transform 452ff., 456, 476, 478, 482 singular 53f., 58, 449 singular value decomposition 26, 51ff., 797 sparse 23, 63ff., 71, 598, 732, 754, 804, 1030ff. special forms 26 splitting in relaxation method 856f. spread 808 square root of 423, 455 symmetric 26, 89, 450, 454, 462ff., 668, 785, 1038, 1225, 1227 threshold multiply of sparse 74, 1031 Toeplitz 82, 85ff., 195, 1038 transpose() intrinsic function 950 transpose of sparse 73f., 1033 triangular 453 tridiagonal 26, 42f., 64, 109, 150, 453f., 462ff., 469ff., 488, 839f., 853, 861f., 1018f., 1227ff. tridiagonal with fringes 822 unitary 450 updating 94, 382, 386, 1041, 1199 upper triangular 34f., 91, 1016 upper triangular mask 1006, 1226, 1305, 1382 Vandermonde 82ff., 114, 1037, 1047 see also Eigensystems Matrix equations see Linear algebraic equations Matterhorn 606

maxexponent() intrinsic function 1107 Maximization see Minimization Maximum entropy method (MEM) 565ff., 1258 algorithms for image restoration 815f. Bayesian 816f. Cornwell-Evans algorithm 816 demystified 814 historic vs. Bayesian 816f. image restoration 809ff. intrinsic correlation function (ICF) model 817 for inverse problems 809ff. operation count 567 see also Linear prediction Maximum likelihood estimate (M-estimates) 690, 694ff. and Bayes' Theorem 811 chi-square test 690 defined 652 how to compute 697f. mean absolute deviation 696, 698, 1294 relation to least squares 652 maxloc() intrinsic function 949, 992f., 1015 modified in Fortran 95 961 maxval() intrinsic function 945, 948, 961, 1016, 1273 Maxwell's equations 825f. Mean(s) of distribution 604f., 608f., 1269 statistical differences between two 609ff., 1269f. Mean absolute deviation of distribution 605, 696, 1294 related to median 698 Measurement errors 650 Median 320 calculating 333 of distribution 605, 608f. as L-estimate 694 role in robust straight line fitting 698 by selection 698, 1294 Median-of-three, in Quicksort 324 MEM see Maximum entropy method (MEM) Memory leak 953, 956, 1071, 1327 Memory management 938, 941f., 953ff., 1327, 1336 merge construct 945, 950, 1099f. for conditional scalar expression 1010, 1094f. contrasted with where 1023 parallelization 1011 Merge-with-dummy-values idiom 1090 Merit function 650 in general linear least squares 665 for inverse problems 797 nonlinear models 675 for straight line fitting 656, 698 for straight line fitting, errors in both coordinates 660, 1286 Mesh-drift instability 834f. Mesokurtic distribution 606 Metcalf, Michael 2/viii see also M&R Method of regularization 799ff.

Index to Volumes 1 and 2

957

Metropolis algorithm 437f., 1219 Microsoft 1/xxii, 2/xix Microsoft Fortran PowerStation 2/viii Midpoint method see Modified midpoint method; Semi-implicit midpoint rule Mikado, or Town of Titipu 714 Miller's algorithm 175, 228, 1106 MIMD machines (Multiple Instruction Multiple Data) 964, 985, 1071, 1084 Minimal solution of recurrence relation 174 Minimax polynomial 186, 198, 1076 Minimax rational function 198 Minimization 387ff. along a ray 77, 376f., 389, 406ff., 412f., 415f., 418, 1195f., 1211, 1213 annealing, method of simulated 387f., 436ff., 1219ff. bracketing of minimum 390ff., 402, 1201f. Brent's method 389, 395ff., 399, 660f., 1204ff., 1286 Broyden-Fletcher-Goldfarb-Shanno algorithm 390, 418ff., 1215 chi-square 653ff., 675ff., 1285, 1292 choice of methods 388f. combinatorial 436f., 1219 conjugate gradient method 390, 413ff., 804, 815, 1210, 1214 convergence rate 393, 409 Davidon-Fletcher-Powell algorithm 390, 418ff., 1215 degenerate 795 direction-set methods 389, 406ff., 1210ff. downhill simplex method 389, 402ff., 444, 697f., 1208, 1222ff. finding best-fit parameters 650 Fletcher-Reeves algorithm 390, 414ff., 1214 functional 795 global 387f., 443f., 650, 1219, 1222 globally convergent multidimensional 418, 1215 golden section search 390ff., 395, 1202ff. multidimensional 388f., 402ff., 1208ff., 1214 in nonlinear model fitting 675f., 1292 Polak-Ribiere algorithm 389, 414ff., 1214 Powell's method 389, 402, 406ff., 1210ff. quasi-Newton methods 376, 390, 418ff., 1215 and root finding 375 scaling of variables 420 by searching smaller subspaces 815 steepest descent method 414, 804 termination criterion 392, 404 use in finding double roots 341 use for sparse linear systems 77ff. using derivatives 389f., 399ff., 1205ff. variable metric methods 390, 418ff., 1215 see also Linear programming Minimum residual method, for sparse system 78 minloc() intrinsic function 949, 992f. modified in Fortran 95 961 MINPACK 683 minval() intrinsic function 948, 961

MIPS 886 Missing data problem 569 Mississippi River 438f., 447 MMP (massively multiprocessor) machines 965ff., 974, 981, 984, 1016ff., 1021, 1045, 1226ff., 1250 Mode of distribution 605, 609 Modeling of data see Fitting Model-trust region 386, 683 Modes, homogeneous, of recursive filters 554 Modified Bessel functions see Bessel functions Modified Lentz's method, for continued fractions 165 Modified midpoint method 716ff., 720, 1302f. Modified moments 152 Modula-2 7 Modular arithmetic, without overflow 269, 271, 275 Modular programming 2/xiii, 7f., 956ff., 1209, 1293, 1296, 1346 MODULE facility 2/xiii, 936f., 939f., 957, 1067, 1298, 1320, 1322, 1324, 1330, 1346 initializing random number generator 1144ff. in nr.f90 936, 941f., 1362, 1384ff. in nrtype.f90 936f., 1361f. in nrutil.f90 936, 1070, 1362, 1364ff. sparse matrix 1031 undefined variables on exit 953, 1266 Module subprogram 940 modulo() intrinsic function 946, 1156 Modulus of linear congruential generator 268 Moments of distribution 604ff., 1269 filter that preserves 645 modified problem of 151f. problem of 83 and quadrature formulas 791, 1328 semi-invariants 608 Monic polynomial 142f. Monotonicity constraint, in upwind differencing 837 Monte Carlo 155ff., 267 adaptive 306ff., 1161ff. bootstrap method 686f. comparison of sampling methods 309 exploration of binary tree 290 importance sampling 306f. integration 124, 155ff., 295ff., 306ff., 1161 integration, recursive 314ff., 1164ff. integration, using Sobol' sequence 304 integration, VEGAS algorithm 309ff., 1161 and Kolmogorov-Smirnov statistic 622, 640 partial differential equations 824 quasi-random sequences in 299ff. quick and dirty 686f. recursive 306ff., 314ff., 1161, 1164ff. significance of Lomb periodogram 570 simulation of data 654, 684ff., 690 stratified sampling 308f., 314, 1164

958

Index to Volumes 1 and 2

Moon, calculate phases of 1f., 14f., 936, 1010f. Mother functions 584 Mother Nature 684, 686 Moving average (MA) model 566 Moving window averaging 644 Mozart 9 MS 1/xxii, 2/xix Muller's method 364, 372 Multidimensional confidence levels of fitting 688f. data, use of binning 623 Fourier transform 515ff., 1241, 1246, 1251 Fourier transform, real data 519ff., 1248f. initial value problems 844ff. integrals 124, 155ff., 295ff., 306ff., 1065ff., 1161ff. interpolation 116ff., 1049ff. Kolmogorov-Smirnov test 640, 1281 least squares fitting 675 minimization 402ff., 406ff., 413ff., 1208ff., 1214f., 1222ff. Monte Carlo integration 295ff., 306ff., 1161ff. normal (Gaussian) distribution 690 optimization 388f. partial differential equations 844ff. root finding 340ff., 358, 370, 372ff., 746, 749f., 752, 754, 1194ff., 1314ff. search using quasi-random sequence 300 secant method 373, 382f., 1199f. wavelet transform 595, 1267f. Multigrid method 824, 862ff., 1334ff. avoid SOR 866 boundary conditions 868f. choice of operators 868 coarse-to-fine operator 864, 1337 coarse-grid correction 864f. cycle 865 dual viewpoint 875 fine-to-coarse operator 864, 1337 full approximation storage (FAS) algorithm 874, 1339ff. full multigrid method (FMG) 863, 868, 1334ff. full weighting 867 Gauss-Seidel relaxation 865f., 1338 half weighting 867, 1337 importance of adjoint operator 867 injection operator 864, 1337 interpolation operator 864, 1337 line relaxation 866 local truncation error 875 Newton's rule 874, 876, 1339, 1341 nonlinear equations 874ff., 1339ff. nonlinear Gauss-Seidel relaxation 876, 1341 odd-even ordering 866, 869, 1338 operation count 862 prolongation operator 864, 1337 recursive nature 865, 1009, 1336 relative truncation error 875 relaxation as smoothing operator 865 restriction operator 864, 1337

speeding up FMG algorithm 873 stopping criterion 875f. straight injection 867 symbol of operator 866f. use of Richardson extrapolation 869 V-cycle 865, 1336 W-cycle 865, 1336 zebra relaxation 866 Multiple precision arithmetic 906ff., 1352ff. Multiple roots 341, 362 Multiplication, complex 171 Multiplication, multiple precision 907, 909, 1353f. Multiplier of linear congruential generator 268 Multistep and multivalue methods (ODEs) 740ff. see also Differential Equations; Predictorcorrector methods Multivariate normal distribution 690 Murphy's Law 407 Musical scores 5f. AG 1/xxiii, 2/xx, 26, 64, 205, 454 Fortran 90 compiler 2/viii, 2/xiv Named constant 940 initialization 1012 for Numerical Recipes 1361 Named control structure 959, 1219, 1305 National Science Foundation (U.S.) 1/xvii, 1/xix, 2/ix Natural cubic spline 109, 1044f. Navier-Stokes equation 830f. nearest() intrinsic function 952, 1146 Needle, eye of (minimization) 403 Negation, multiple precision 907, 1353f. Negentropy 811, 896 Nelder-Mead minimization method 389, 402, 1208 Nested iteration 868 Neumann boundary conditions 820, 840, 851, 858 Neutrino 640 Neville's algorithm 102f., 105, 134, 182, 1043 Newton-Cotes formulas 125ff., 140 Newton-Raphson method see Newton's rule Newton's rule 143f., 180, 341, 355ff., 362, 364, 469, 1059, 1189 with backtracking 376, 1196 caution on use of numerical derivatives 356ff. fractal domain of convergence 360f. globally convergent multidimensional 373, 376ff., 382, 749f., 752, 1196, 1199, 1314f. for matrix inverse 49, 598 in multidimensions 370, 372ff., 749f., 752, 754, 1194ff., 1314ff. in nonlinear multigrid 874, 876, 1339, 1341 nonlinear Volterra equations 787 for reciprocal of number 911, 1355 safe 359, 1190 scaling of variables 381

N

Index to Volumes 1 and 2

959

singular Jacobian 386 solving stiff ODEs 740 for square root of number 912, 1356 Niederreiter sequence 300 NL2SOL 683 Noise bursty 889 effect on maximum entropy method 567 equivalent bandwidth 548 fitting data which contains 647f., 650 model, for optimal filtering 541 Nominal variable (statistics) 623 Nonexpansive projection operator 805 Non-interfering directions see Conjugate directions Nonlinear eigenvalue problems 455 Nonlinear elliptic equations, multigrid method 874ff., 1339ff. Nonlinear equations, in MEM inverse problems 813 Nonlinear equations, roots of 340ff. Nonlinear instability 831 Nonlinear integral equations 781, 787 Nonlinear programming 436 Nonnegativity constraints 423 Nonparametric statistics 633ff., 1277ff. Nonpolynomial complete (NP-complete) 438 Norm, of matrix 50 Normal (Gaussian) distribution 267, 652, 682, 798, 1294 central limit theorem 652f. deviates from 279f., 571, 1152 kurtosis of 607 multivariate 690 semi-invariants of 608 tails compared to Poisson 653 two-dimensional (binormal) 631 variance of skewness of 606 Normal equations (fitting) 26, 645, 666ff., 795, 800, 1288 often are singular 670 Normalization of Bessel functions 175 of floating-point representation 19, 882, 1343 of functions 142, 765 of modified Bessel functions 232 not() intrinsic function 951 Notch filter 551, 555f. NP-complete problem 438 nr.f90 (module file) 936, 1362, 1384ff. nrerror() utility function 989, 995 nrtype.f90 (module file) 936f. named constants 1361 nrutil.f90 (module file) 936, 1070, 1362, 1364ff. table of contents 1364 Null hypothesis 603 nullify statement 953f., 1070, 1302 Nullity 53 Nullspace 25, 53f., 449, 795 Number-theoretic transforms 503f. Numeric inquiry functions 2/xiv, 1107, 1231, 1343 Numerical derivatives 180ff., 645, 1075

Numerical integration see Quadrature Numerical intrinsic functions 946, 951f. Numerical Recipes compatibility with First Edition 4 Example Book 3 Fortran 90 types 936f., 1361 how to get programs 1/xx, 2/xvii how to report bugs 1/iv, 2/iv interface blocks (Fortran 90) 937, 941f., 1084, 1384ff. no warranty on 1/xx, 2/xvii plan of two-volume edition 1/xiii table of dependencies 921ff., 1434ff. as trademark 1/xxiii, 2/xx utility functions (Fortran 90) 936f., 945, 968, 970, 972ff., 977, 984, 987ff., 1015, 1071f., 1361ff. Numerical Recipes Software 1/xv, 1/xxiiff., 2/xviiff. address and fax number 1/iv, 1/xxii, 2/iv, 2/xix Web home page 1/xx, 2/xvii Nyquist frequency 494ff., 520, 543, 545, 569ff. Nystrom method 782f., 789, 1325 product version 789, 1331

bject extensibility 8 jective function 424 ject-oriented programming 2/xvi, 2, 8 lateness parameter 764 solete features see Fortran, Obsolescent features Octal constant, initialization 959 Odd-even ordering allows parallelization 1333 in Gauss-Seidel relaxation 866, 869, 1338 in successive over-relaxation (SOR) 859, 1332 Odd parity 888 OEM information 1/xxii One-sided power spectral density 492 ONLY option, for USE statement 941, 957, 1067 Operation count balancing 476 Bessel function evaluation 228 bisection method 346 Cholesky decomposition 90 coefficients of interpolating polynomial 114f. complex multiplication 97 cubic spline interpolation 109 evaluating polynomial 168 fast Fourier transform (FFT) 498 Gauss-Jordan elimination 34, 39 Gaussian elimination 34 Givens reduction 463 Householder reduction 467 interpolation 100 inverse iteration 488 iterative improvement 48 Jacobi transformation 460 Kendall's tau 637 O O O O b b b b

O

960

Index to Volumes 1 and 2

linear congruential generator 268 LU decomposition 36, 39 matrix inversion 97 matrix multiplication 96 maximum entropy method 567 multidimensional minimization 413f. multigrid method 862 multiplication 909 polynomial evaluation 97f., 168 QL method 470, 473 QR decomposition 92 QR method for Hessenberg matrices 484 reduction to Hessenberg form 479 selection by partitioning 333 sorting 320ff. Spearman rank-order coefficient 638 Toeplitz matrix 83 Vandermonde matrix 83 Operator overloading 2/xiif., 7 Operator splitting 823, 847f., 861 Operator, user-defined 2/xii Optimal feasible vector 424 Optimal (Wiener) filtering 535, 539ff., 558, 644 compared with regularization 801 Optimization see Minimization Optimization of code 2/xiii Optional argument 2/xiv, 947f., 1092, 1228, 1230, 1256, 1272, 1275, 1340 dim 948 mask 948, 968, 1038 testing for 952 Ordering Numerical Recipes 1/xxf., 2/xviif. Ordinal variable (statistics) 623 Ordinary differential equations see Differential equations Orthogonal see Orthonormal functions; Orthonormal polynomials Orthogonal transformation 452, 463ff., 469, 584, 1227 Orthonormal basis, constructing 58, 94, 1039 Orthonormal functions 142, 246 Orthonormal polynomials Chebyshev 144, 184ff., 1076ff. construct for arbitrary weight 151ff., 1064 in Gauss-Hermite integration 147, 1062 and Gaussian quadrature 142, 1009, 1061 Gaussian weights from recurrence 150, 1064 Hermite 144, 1062 Jacobi 144, 1063 Laguerre 144, 1060 Legendre 144, 1059 weight function log x 153 Orthonormality 51, 142, 463 Outer product Gaussian elimination 1017 Outer product of matrices (denoted by cross) 66, 420, 949, 969f., 989, 1000ff., 1017, 1026, 1040, 1076, 1200, 1216, 1275 outerand() utility function 989, 1002, 1015 outerdiff() utility function 989, 1001 outerdiv() utility function 989, 1001 outerprod() utility function 970, 989, 1000, 1017, 1026, 1040, 1076, 1200, 1216, 1275

outersum() utility function 989, 1001 Outgoing wave boundary conditions 820 Outlier 605, 653, 656, 694, 697 see also Robust estimation Overcorrection 857 Overflow 882, 1343 how to avoid in modulo multiplication 269 in complex arithmetic 171 Overlap-add and overlap-save methods 536f. Overloading operator 2/xiif. procedures 940, 1015, 1083, 1094, 1096 Overrelaxation parameter 857, 1332 choice of 858

ack() intrinsic function 945, 950, 964, 991, 1031 communication bottleneck 969 for index table 1176 for partition-exchange 1170 for selection 1178 for selective evaluation 1087 Pack-unpack idiom 1087, 1134, 1153 Pade approximant 194ff., 1080f. Д Pade approximation 105 Д Parabolic interpolation 395, 1204 Parabolic partial differential equations 818, 838ff. Parallel axis theorem 308 Parallel programming 2/xv, 941, 958ff., 962ff., 965f., 968f., 987 array operations 964f. array ranking 1278f. band diagonal linear equations 1021 Bessel functions 1107ff. broadcasts 965ff. C and C++ 2/viii communication costs 969, 981, 1250 counting do-loops 1015 cyclic reduction 974 deflation 977ff. design matrix 1082 dimensional expansion 965ff. eigensystems 1226, 1229f. fast Fourier transform (FFT) 981, 1235ff., 1250 in Fortran 90 963ff. Fortran 90 tricks 1009, 1274, 1278, 1280 function evaluation 986, 1009, 1084f., 1087, 1090, 1102, 1128, 1134 Gaussian quadrature 1009, 1061 geometric progressions 972 index loss 967f., 1038 index table 1176f. interprocessor communication 981 Kendall's tau 1280 linear algebra 969f., 1000ff., 1018f., 1026, 1040, 1200, 1326 linear recurrence 973f., 1073ff. logo 2/viii, 1009 masks 967f., 1006f., 1038, 1102, 1200, 1226, 1305, 1333f., 1368, 1378, 1382 merge statement 1010

P

Index to Volumes 1 and 2

961

MIMD (multiple instruction, multiple data) 964, 985f., 1084 MMP (massively multiprocessor) machines 965ff., 974, 984, 1016ff., 1226ff., 1250 nrutil.f90 (module file) 1364ff. odd-even ordering 1333 one-dimensional FFT 982f. parallel note icon 1009 partial differential equations 1333 in-place selection 1178f. polynomial coefficients from roots 980 polynomial evaluation 972f., 977, 998 random numbers 1009, 1141ff. recursive doubling 973f., 976f., 979, 988, 999, 1071ff. scatter-with-combine 984, 1002f., 1032f. second order recurrence 974f., 1074 SIMD (Single Instruction Multiple Data) 964, 985f., 1009, 1084f. singular value decomposition (SVD) 1026 sorting 1167ff., 1171, 1176f. special functions 1009 SSP (small-scale parallel) machines 965ff., 984, 1010ff., 1016ff., 1059f., 1226ff., 1250 subvector scaling 972, 974, 996, 1000 successive over-relaxation (SOR) 1333 supercomputers 2/viii, 962 SVD algorithm 1026 synthetic division 977ff., 999, 1048, 1071f., 1079, 1192 tridiagonal systems 975f., 1018, 1229f. utilities 1364ff. vector reduction 972f., 977, 998 vs. serial programming 965, 987 PARAMETER attribute 1012 Parameters in fitting function 651, 684ff. Parity bit 888 Park and Miller minimal standard random generator 269, 1142 Parkinson's Law 328 Parseval's Theorem 492, 544 discrete form 498 Partial differential equations 818ff., 1332ff. advective equation 826 alternating-direction implicit method (ADI) 847, 861f. amplification factor 828, 834 analyze/factorize/operate package 824 artificial viscosity 831, 837 biconjugate gradient method 824 boundary conditions 819ff. boundary value problems 819, 848 Cauchy problem 818f. caution on high-order methods 844f. Cayley's form 844 characteristics 818 Chebyshev acceleration 859f., 1332 classification of 818f. comparison of rapid methods 854 conjugate gradient method 824 Courant condition 829, 832ff., 836 Courant condition (multidimensional) 846 Crank-Nicholson method 840, 842, 844, 846

cyclic reduction (CR) method 848f., 852ff. diffusion equation 818, 838ff., 846, 855 Dirichlet boundary conditions 508, 820, 840, 850, 856, 858 elliptic, defined 818 error, varieties of 831ff. explicit vs. implicit differencing 827 FACR method 854 finite difference method 821ff. finite element methods 824 flux-conservative initial value problems 825ff. forward Euler differencing 826f. Forward Time Centered Space (FTCS) 827ff., 839ff., 843, 855 Fourier analysis and cyclic reduction (FACR) 848ff., 854 Gauss-Seidel method (relaxation) 855, 864ff., 876, 1338, 1341 Godunov's method 837 Helmholtz equation 852 hyperbolic 818, 825f. implicit differencing 840 incomplete Cholesky conjugate gradient method (ICCG) 824 inhomogeneous boundary conditions 850f. initial value problems 818f. initial value problems, recommendations on 838ff. Jacobi's method (relaxation) 855ff., 864 Laplace's equation 818 Lax method 828ff., 836, 845f. Lax method (multidimensional) 845f. matrix methods 824 mesh-drift instability 834f. Monte Carlo methods 824 multidimensional initial value problems 844ff. multigrid method 824, 862ff., 1009, 1334ff. Neumann boundary conditions 508, 820, 840, 851, 858 nonlinear diffusion equation 842 nonlinear instability 831 numerical dissipation or viscosity 830 operator splitting 823, 847f., 861 outgoing wave boundary conditions 820 parabolic 818, 838ff. parallel computing 1333 periodic boundary conditions 850, 858 piecewise parabolic method (PPM) 837 Poisson equation 818, 852 rapid (Fourier) methods 508ff., 824, 848ff. relaxation methods 823, 854ff., 1332f. Schrodinger equation 842ff. ? second-order accuracy 833ff., 840 shock 831, 837 sparse matrices from 64 spectral methods 825 spectral radius 856ff., 862 stability vs. accuracy 830 stability vs. efficiency 821 staggered grids 513, 852 staggered leapfrog method 833f. strongly implicit procedure 824

962

Index to Volumes 1 and 2

successive over-relaxation (SOR) 857ff., 862, 866, 1332f. time splitting 847f., 861 two-step Lax-Wendroff method 835ff. upwind differencing 832f., 837 variational methods 824 varieties of error 831ff. von Neumann stability analysis 827f., 830, 833f., 840 wave equation 818, 825f. see also Elliptic partial differential equations; Finite difference equations (FDEs) Partial pivoting 29 Partition-exchange 323, 333 and pack() intrinsic function 1170 Partitioned matrix, inverse of 70 Party tricks 95ff., 168 Parzen window 547 Pascal, Numerical Recipes in 2/x, 2/xvii, 1 Pass-the-buck idiom 1102, 1128 Path integration, for function evaluation 201ff., 263, 1138 Pattern multiply of sparse matrices 74 PBCG (preconditioned biconjugate gradient method) 78f., 824 PC methods see Predictor-corrector methods PCGPACK 71 PDEs see Partial differential equations Pearson's r 630ff., 1276 PECE method 741 Pentagon, symmetries of 895 Percentile 320 Period of linear congruential generator 268 Periodic boundary conditions 850, 858 Periodogram 543ff., 566, 1258ff. Lomb's normalized 569f., 574f., 1258ff. variance of 544f. Perl (programming language) 1/xvi Perron's theorems, for convergence of recurrence relations 174f. Perturbation methods for matrix inversion 65ff. Phase error 831 Phase-locked loop 700 Phi statistic 625 Phillips-Twomey method 799ff. Pi, computation of 906ff., 1352ff., 1357f. Piecewise parabolic method (PPM) 837 Pincherle's theorem 175 Pivot element 29, 33, 757 in linear programming 428f. Pivoting 27, 29ff., 46, 66, 90, 1014 full 29, 1014 implicit 30, 38, 1014, 1017 in LU decomposition 37f., 1017 partial 29, 33, 37f., 1017 and QR decomposition 92 in reduction to Hessenberg form 478 in relaxation method 757 as row and column operations 32 for tridiagonal systems 43 Pixel 519, 596, 803, 811 PL/1 2/x Planck's constant 842

Plane rotation see Givens reduction; Jacobi transformation (or rotation) Platykurtic distribution 606 Plotting of functions 342, 1182f. POCS (projection onto convex sets) 805 Poetry 5f. Pointer (Fortran 90) 2/xiiif., 938f., 944f., 953ff., 1197, 1212, 1266 as alias 939, 944f., 1286, 1333 allocating an array 941 allocating storage for derived type 955 for array of arrays 956, 1336 array of, forbidden 956, 1337 associated with target 938f., 944f., 952f., 1197 in Fortran 95 961 to function, forbidden 1067, 1210 initialization to null 2/xv, 961 returning array of unknown size 955f., 1184, 1259, 1261, 1327 undefined status 952f., 961, 1070, 1266, 1302 Poisson equation 519, 818, 852 Poisson probability function cumulative 214 deviates from 281, 283ff., 571, 1154 semi-invariants of 608 tails compared to Gaussian 653 Poisson process 278, 282ff., 1153 Polak-Ribiere algorithm 390, 414ff., 1214 Poles see Complex plane, poles in Polishing of roots 356, 363ff., 370f., 1193 poly() utility function 973, 977, 989, 998, 1072, 1096, 1192, 1258, 1284 Polymorphism 8 Polynomial interpolation 99, 102ff., 1043 Aitken's algorithm 102 in Bulirsch-Stoer method 724, 726, 1305 coefficients for 113ff., 1047f. Lagrange's formula 84, 102f. multidimensional 116ff., 1049ff. Neville's algorithm 102f., 105, 134, 182, 1043 pathology in determining coefficients for 116 in predictor-corrector method 740 smoothing filters 645 see also Interpolation Polynomials 167ff. algebraic manipulations 169, 1072 approximate roots of Hermite polynomials 1062 approximate roots of Jacobi polynomials 1064 approximate roots of Laguerre polynomials 1061 approximating modified Bessel functions 230 approximation from Chebyshev coefficients 191, 1078f. AUTODIN-II 890 CCITT 889f. characteristic 368, 1193 characteristic, for digital filters 554, 559, 1257

Index to Volumes 1 and 2

963

characteristic, for eigenvalues of matrix 449, 469 Chebyshev 184ff., 1076ff. coefficients from roots 980 CRC-16 890 cumulants of 977, 999, 1071f., 1192, 1365, 1378f. deflation 362ff., 370f., 977 derivatives of 167, 978, 1071 division 84, 169, 362, 370, 977, 1072 evaluation of 167, 972, 977, 998f., 1071, 1258, 1365, 1376ff. evaluation of derivatives 167, 978, 1071 extrapolation in Bulirsch-Stoer method 724, 726, 1305f. extrapolation in Romberg integration 134 fitting 83, 114, 191, 645, 665, 674, 1078f., 1291 generator for CRC 889 ill-conditioned 362 masked evaluation of 1378 matrix method for roots 368, 1193 minimax 186, 198, 1076 monic 142f. multiplication 169 operation count for 168 orthonormal 142, 184, 1009, 1061 parallel operations on 977ff., 998f., 1071f., 1192 primitive modulo 2 287ff., 301f., 889 roots of 178ff., 362ff., 368, 1191ff. shifting of 192f., 978, 1079 stopping criterion in root finding 366 poly term() utility function 974, 977, 989, 999, 1071f., 1192 Port, serial data 892 Portability 3, 963 Portable random number generator see Random number generator Positive definite matrix, testing for 90 Positivity constraints 423 Postal Service (U.S.), barcode 894 PostScript 1/xvi, 1/xxiii, 2/xx Powell's method 389, 402, 406ff., 1210ff. Power (in a signal) 492f. Power series 159ff., 167, 195 economization of 192f., 1061, 1080 Pade approximant of 194ff., 1080f. Д Power spectral density see Fourier transform; Spectral density Power spectrum estimation see Fourier transform; Spectral density PowerStation, Microsoft Fortran 2/xix PPM (piecewise parabolic method) 837 Precision converting to double 1362 floating point 882, 937, 1343, 1361ff. multiple 906ff., 1352ff., 1362 Preconditioned biconjugate gradient method (PBCG) 78f. Preconditioning, in conjugate gradient methods 824 Predictor-corrector methods 702, 730, 740ff. Adams-Bashforth-Moulton schemes 741 adaptive order methods 744

compared to other methods 740 fallacy of multiple correction 741 with fixed number of iterations 741 functional iteration vs. Newton's rule 742 multivalue compared with multistep 742ff. starting and stopping 742, 744 stepsize control 742f. present() intrinsic function 952 Prime numbers 915 Primitive polynomials modulo 2 287ff., 301f., 889 Principal directions 408f., 1210 Principal solution, of inverse problem 797 PRIVATE attribute 957, 1067 Prize, $1000 offered 272, 1141, 1150f. Probability see Random number generator; Statistical tests Probability density, change of variables in 278f. Procedure see Program(s); Subprogram Process loss 548 product() intrinsic function 948 Product Nystrom method 789, 1331 Program(s) as black boxes 1/xviii, 6, 26, 52, 205, 341, 406 dependencies 921ff., 1434ff. encapsulation 7 interfaces 2, 8 modularization 7f. organization 5ff. type declarations 2 typography of 2f., 12, 937 validation 3f. Programming, serial vs. parallel 965, 987 Projection onto convex sets (POCS) 805 Projection operator, nonexpansive 805 Prolongation operator 864, 1337 Protocol, for communications 888 PSD (power spectral density) see Fourier transform; Spectral density Pseudo-random numbers 266ff., 1141ff. PUBLIC attribute 957, 1067 Puns, particularly bad 167, 744, 747 PURE attribute 2/xv, 960f., 964, 986 put diag() utility function 985, 990, 1005, 1200 Pyramidal algorithm 586, 1264 Pythagoreans 392

Q L see Eigensystems QR see Eigensystems QR decomposition 91f., 382, 386, 1039f., 1199 backsubstitution 92, 1040 and least squares 668 operation count 92 pivoting 92 updating 94, 382, 386, 1041, 1199 use for orthonormal basis 58, 94 Quadratic convergence 49, 256, 351, 356, 409f., 419, 906 equations 20, 178, 391, 457

964

Index to Volumes 1 and 2

interpolation 353, 364 programming 436 Quadrature 123ff., 1052ff. adaptive 123, 190, 788 alternative extended Simpson's rule 128 arbitrary weight function 151ff., 789, 1064, 1328 automatic 154 Bode's rule 126 change of variable in 137ff., 788, 1056ff. by Chebyshev fitting 124, 189, 1078 classical formulas for 124ff. Clenshaw-Curtis 124, 190, 512f. closed formulas 125, 127f. and computer science 881 by cubic splines 124 error estimate in solution 784 extended midpoint rule 129f., 135, 1054f. extended rules 127ff., 134f., 786, 788ff., 1326, 1328 extended Simpson's rule 128 Fourier integrals 577ff., 1261ff. Fourier integrals, infinite range 583 Gauss-Chebyshev 144, 512f. Gauss-Hermite 144, 789, 1062 Gauss-Jacobi 144, 1063 Gauss-Kronrod 154 Gauss-Laguerre 144, 789, 1060 Gauss-Legendre 144, 783, 789, 1059, 1325 Gauss-Lobatto 154, 190, 512 Gauss-Radau 154 Gaussian integration 127, 140ff., 781, 783, 788f., 1009, 1059ff., 1325, 1328f. Gaussian integration, nonclassical weight function 151ff., 788f., 1064f., 1328f. for improper integrals 135ff., 789, 1055, 1328 for integral equations 781f., 786, 1325ff. Monte Carlo 124, 155ff., 295ff., 306ff., 1161ff. multidimensional 124, 155ff., 1052, 1065ff. multidimensional, by recursion 1052, 1065 Newton-Cotes formulas 125ff., 140 open formulas 125ff., 129f., 135 related to differential equations 123 related to predictor-corrector methods 740 Romberg integration 124, 134f., 137, 182, 717, 788, 1054f., 1065, 1067 semi-open formulas 130 Simpson's rule 126, 133, 136f., 583, 782, 788ff., 1053 Simpson's three-eighths rule 126, 789f. singularity removal 137ff., 788, 1057ff., 1328ff. singularity removal, worked example 792, 1328ff. trapezoidal rule 125, 127, 130ff., 134f., 579, 583, 782, 786, 1052ff., 1326f. using FFTs 124 weight function log x 153 see also Integration of functions Quadrature mirror filter 585, 593

Quantum mechanics, Uncertainty Principle 600 Quartile value 320 Quasi-Newton methods for minimization 390, 418ff., 1215 Quasi-random sequence 299ff., 318, 881, 888 Halton's 300 for Monte Carlo integration 304, 309, 318 Sobol's 300ff., 1160 see also Random number generator Quicksort 320, 323ff., 330, 333, 1169f. Quotient-difference algorithm 164

R

-estimates 694 Radioactive decay 278 Radix base for floating point arithmetic 476, 882, 907, 913, 1231, 1343, 1357 Radix conversion 902, 906, 913, 1357 radix() intrinsic function 1231 Radix sort 1172 Ramanujan's identity for 915 Random bits, generation of 287ff., 1159f. Random deviates 266ff., 1141ff. binomial 285f., 1155 exponential 278, 1151f. gamma distribution 282f., 1153 Gaussian 267, 279f., 571, 798, 1152f. normal 267, 279f., 571, 1152f. Poisson 283ff., 571, 1154f. quasi-random sequences 299ff., 881, 888, 1160f. uniform 267ff., 1158f., 1166 uniform integer 270, 274ff. Random number generator 266ff., 1141ff. bitwise operations 287 Box-Muller algorithm 279, 1152 Data Encryption Standard 290ff., 1144, 1156ff. good choices for modulus, multiplier and increment 274ff. initializing 1144ff. for integer-valued probability distribution 283f., 1154 integer vs. real implementation 273 L'Ecuyer's long period 271f. lagged Fibonacci generator 1142, 1148ff. linear congruential generator 267ff., 1142 machine language 269 Marsaglia shift register 1142, 1148ff. Minimal Standard, Park and Miller's 269, 1142 nonrandomness of low-order bits 268f. parallel 1009 perfect 272, 1141, 1150f. planes, numbers lie on 268 portable 269ff., 1142 primitive polynomials modulo 2 287ff. pseudo-DES 291, 1144, 1156ff. quasi-random sequences 299ff., 881, 888, 1160f. quick and dirty 274 quicker and dirtier 275 in Quicksort 324 random access to nth number 293

Index to Volumes 1 and 2

965

random bits 287ff., 1159f. recommendations 276f. rejection method 281ff. serial 1141f. shuffling procedure 270, 272 in simulated annealing method 438 spectral test 274 state space 1143f. state space exhaustion 1141 subtractive method 273, 1143 system-supplied 267f. timings 276f., 1151 transformation method 277ff. trick for trigonometric functions 280 Random numbers see Monte Carlo; Random deviates Random walk 20 random number() intrinsic function 1141, 1143 random seed() intrinsic function 1141 RANDU, infamous routine 268 Range 53f. Rank (matrix) 53 kernel of finite 785 Rank (sorting) 320, 332, 1176 Rank (statistics) 633ff., 694f., 1277 Kendall's tau 637ff., 1279 Spearman correlation coefficient 634f., 1277ff. sum squared differences of 634, 1277 Ratio variable (statistics) 623 Rational Chebyshev approximation 197ff., 1081f. Rational function 99, 167ff., 194ff., 1080f. approximation for Bessel functions 225 approximation for continued fraction 164, 211, 219f. Chebyshev approximation 197ff., 1081f. evaluation of 170, 1072f. extrapolation in Bulirsch-Stoer method 718ff., 726, 1306f. interpolation and extrapolation using 99, 104ff., 194ff., 718ff., 726 as power spectrum estimate 566 interpolation and extrapolation using 1043f., 1080ff., 1306 minimax 198 Re-entrant procedure 1052 real() intrinsic function, ambiguity of 947 Realizable (causal) 552, 554f. reallocate() utility function 955, 990, 992, 1070, 1302 Rearranging see Sorting Reciprocal, multiple precision 910f., 1355f. Record, in data file 329 Recurrence relation 172ff., 971ff. arithmetic progression 971f., 996 associated Legendre polynomials 247 Bessel function 172, 224, 227f., 234 binomial coefficients 209 Bulirsch-Stoer 105f. characteristic polynomial of tridiagonal matrix 469 Clenshaw's recurrence formula 176f. and continued fraction 175

continued fraction evaluation 164f. convergence 175 cosine function 172, 500 cyclic reduction 974 dominant solution 174 exponential integrals 172 gamma function 206 generation of random bits 287f. geometric progression 972, 996 Golden Mean 21 Legendre polynomials 172 minimal vs. dominant solution 174 modified Bessel function 232 Neville's 103, 182 orthonormal polynomials 142 Perron's theorems 174f. Pincherle's theorem 175 for polynomial cumulants 977, 999, 1071f. polynomial interpolation 103, 183 primitive polynomials modulo 2 287f. random number generator 268 rational function interpolation 105f., 1043 recursive doubling 973, 977, 988, 999, 1071f., 1073 second order 974f., 1074 sequence of trig functions 173 sine function 172, 500 spherical harmonics 247 stability of 21, 173ff., 177, 224f., 227f., 232, 247, 975 trig functions 572 weight of Gaussian quadrature 144f. Recursion in Fortran 90 958 in multigrid method 865, 1009, 1336 Recursive doubling 973f., 979 cumulants of polynomial 977, 999, 1071f. linear recurrences 973, 988, 1073 tridiagonal systems 976 RECURSIVE keyword 958, 1065, 1067 Recursive Monte Carlo integration 306ff., 1161 Recursive procedure 2/xiv, 958, 1065, 1067, 1166 as parallelization tool 958 base case 958 for multigrid method 1009, 1336 re-entrant 1052 Recursive stratified sampling 314ff., 1164ff. Red-black see Odd-even ordering Reduction functions 948ff. Reduction of variance in Monte Carlo integration 299, 306ff. References (explanation) 4f. References (general bibliography) 916ff., 1359f. Reflection formula for gamma function 206 Regula falsi (false position) 347ff., 1185f. Regularity condition 775 Regularization compared with optimal filtering 801 constrained linear inversion method 799ff. of inverse problems 796ff. linear 799ff. nonlinear 813

966

Index to Volumes 1 and 2

objective criterion 802 Phillips-Twomey method 799ff. Tikhonov-Miller 799ff. trade-off curve 799 two-dimensional 803 zeroth order 797 see also Inverse problems Regularizing operator 798 Reid, John 2/xiv, 2/xvi Rejection method for random number generator 281ff. Relaxation method for algebraically difficult sets 763 automated allocation of mesh points 774f., 777 computation of spheroidal harmonics 764ff., 1319ff. for differential equations 746f., 753ff., 1316ff. elliptic partial differential equations 823, 854ff., 1332f. example 764ff., 1319ff. Gauss-Seidel method 855, 864ff., 876, 1338, 1341 internal boundary conditions 775ff. internal singular points 775ff. Jacobi's method 855f., 864 successive over-relaxation (SOR) 857ff., 862, 866, 1332f. see also Multigrid method Remes algorithms exchange algorithm 553 for minimax rational function 199 reshape() intrinsic function 950 communication bottleneck 969 order keyword 1050, 1246 Residual 49, 54, 78 in multigrid method 863, 1338 Resolution function, in Backus-Gilbert method 807 Response function 531 Restriction operator 864, 1337 RESULT keyword 958, 1073 Reward, $1000 offered 272, 1141, 1150f. Richardson's deferred approach to the limit 134, 137, 182, 702, 718ff., 726, 788, 869 see also Bulirsch-Stoer method Richtmyer artificial viscosity 837 Ridders' method, for numerical derivatives 182, 1075 Ridders' method, root finding 341, 349, 351, 1187 Riemann shock problem 837 Right eigenvalues and eigenvectors 451 Rise/fall time 548f. Robust estimation 653, 694ff., 700, 1294 Andrew's sine 697 average deviation 605 double exponential errors 696 Kalman filtering 700 Lorentzian errors 696f. mean absolute deviation 605 nonparametric correlation 633ff., 1277 Tukey's biweight 697

use of a priori covariances 700 see also Statistical tests Romberg integration 124, 134f., 137, 182, 717, 788, 1054f., 1065 Root finding 143, 340ff., 1009, 1059 advanced implementations of Newton's rule 386 Bairstow's method 364, 370, 1193 bisection 343, 346f., 352f., 359, 390, 469, 698, 1184f. bracketing of roots 341, 343ff., 353f., 362, 364, 369, 1183f. Brent's method 341, 349, 660f., 1188f., 1286 Broyden's method 373, 382f., 386, 1199 compared with multidimensional minimization 375 complex analytic functions 364 in complex plane 204 convergence criteria 347, 374 deflation of polynomials 362ff., 370f., 1192 without derivatives 354 double root 341 eigenvalue methods 368, 1193 false position 347ff., 1185f. Jenkins-Traub method 369 Laguerre's method 341, 366f., 1191f. Lehmer-Schur algorithm 369 Maehly's procedure 364, 371 matrix method 368, 1193 Muller's method 364, 372 multiple roots 341 Newton's rule 143f., 180, 341, 355ff., 362, 364, 370, 372ff., 376, 469, 740, 749f., 754, 787, 874, 876, 911f., 1059, 1189, 1194, 1196, 1314ff., 1339, 1341, 1355f. pathological cases 343, 356, 362, 372 polynomials 341, 362ff., 449, 1191f. in relaxation method 754, 1316 Ridders' method 341, 349, 351, 1187 root-polishing 356, 363ff., 369ff., 1193 safe Newton's rule 359, 1190 secant method 347ff., 358, 364, 399, 1186f. in shooting method 746, 749f., 1314f. singular Jacobian in Newton's rule 386 stopping criterion for polynomials 366 use of minimum finding 341 using derivatives 355ff., 1189 zero suppression 372 see also Roots Root polishing 356, 363ff., 369ff., 1193 Roots Chebyshev polynomials 184 complex nth root of unity 999f., 1379 cubic equations 179f. Hermite polynomials, approximate 1062 Jacobi polynomials, approximate 1064 Laguerre polynomials, approximate 1061 multiple 341, 364ff., 1192 nonlinear equations 340ff. polynomials 341, 362ff., 449, 1191f. quadratic equations 178

Index to Volumes 1 and 2

967

reflection in unit circle 560, 1257 square, multiple precision 912, 1356 see also Root finding Rosenbrock method 730, 1308 compared with semi-implicit extrapolation 739 stepsize control 731, 1308f. Roundoff error 20, 881, 1362 bracketing a minimum 399 compile time vs. run time 1012 conjugate gradient method 824 eigensystems 458, 467, 470, 473, 476, 479, 483 extended trapezoidal rule 132 general linear least squares 668, 672 graceful 883, 1343 hardware aspects 882, 1343 Householder reduction 466 IEEE standard 882f., 1343 interpolation 100 least squares fitting 658, 668 Levenberg-Marquardt method 679 linear algebraic equations 23, 27, 29, 47, 56, 84, 1022 linear predictive coding (LPC) 564 magnification of 20, 47, 1022 maximum entropy method (MEM) 567 measuring 881f., 1343 multidimensional minimization 418, 422 multiple roots 362 numerical derivatives 180f. recurrence relations 173 reduction to Hessenberg form 479 series 164f. straight line fitting 658 variance 607 Row degeneracy 22 Row-indexed sparse storage 71f., 1030 transpose 73f. Row operations on matrix 28, 31f. Row totals 624 RSS algorithm 314ff., 1164 RST properties (reflexive, symmetric, transitive) 338 Runge-Kutta method 702, 704ff., 731, 740, 1297ff., 1308 Cash-Karp parameters 710, 1299f. embedded 709f., 731, 1298, 1308 high-order 705 quality control 722 stepsize control 708ff. Run-length encoding 901 Runge-Kutta method high-order 1297 stepsize control 1298f. Rybicki, G.B. 84ff., 114, 145, 252, 522, 574, 600

S

-box for Data Encryption Standard 1148 Sampling importance 306f. Latin square or hypercube 305f. recursive stratified 314ff., 1164 stratified 308f. uneven or irregular 569, 648f., 1258

Sampling theorem 495, 543 for numerical approximation 600ff. Sande-Tukey FFT algorithm 503 SAVE attribute 953f., 958f., 961, 1052, 1070, 1266, 1293 redundant use of 958f. SAVE statements 3 Savitzky-Golay filters for data smoothing 644ff., 1283f. for numerical derivatives 183, 645 scale() intrinsic function 1107 Scallop loss 548 Scatter-with-combine functions 984, 1002f., 1032, 1366, 1380f. scatter add() utility function 984, 990, 1002, 1032 scatter max() utility function 984, 990, 1003 Schonfelder, Lawrie 2/xi Schrage's algorithm 269 Schrodinger equation 842ff. ? Schultz's method for matrix inverse 49, 598 Scope 956ff., 1209, 1293, 1296 Scoping unit 939 SDLC checksum 890 Searching with correlated values 111, 1046f. an ordered table 110f., 1045f. selection 333, 1177f. Secant method 341, 347ff., 358, 364, 399, 1186f. Broyden's method 382f., 1199f. multidimensional (Broyden's) 373, 382f., 1199 Second Euler-Maclaurin summation formula 135f. Second order differential equations 726, 1307 Seed of random number generator 267, 1146f. select case statement 2/xiv, 1010, 1036 Selection 320, 333, 1177f. find m largest elements 336, 1179f. heap algorithm 336, 1179 for median 698, 1294 operation count 333 by packing 1178 parallel algorithms 1178 by partition-exchange 333, 1177f. without rearrangement 335, 1178f. timings 336 use to find median 609 Semi-implicit Euler method 730, 735f. Semi-implicit extrapolation method 730, 735f., 1310f. compared with Rosenbrock method 739 stepsize control 737, 1311f. Semi-implicit midpoint rule 735f., 1310f. Semi-invariants of a distribution 608 Sentinel, in Quicksort 324, 333 Separable kernel 785 Separation of variables 246 Serial computing convergence of quadrature 1060 random numbers 1141 sorting 1167 Serial data port 892

968

Index to Volumes 1 and 2

Series 159ff. accelerating convergence of 159ff. alternating 160f., 1070 asymptotic 161 Bessel function K 241 Bessel function Y 235 Bessel functions 160, 223 cosine integral 250 divergent 161 economization 192f., 195, 1080 Euler's transformation 160f., 1070 exponential integral 216, 218 Fresnel integral 248 hypergeometric 202, 263, 1138 incomplete beta function 219 incomplete gamma function 210, 1090f. Laurent 566 relation to continued fractions 163f. roundoff error in 164f. sine and cosine integrals 250 sine function 160 Taylor 355f., 408, 702, 709, 754, 759 transformation of 160ff., 1070 van Wijngaarden's algorithm 161, 1070 Shaft encoder 886 Shakespeare 9 Shampine's Rosenbrock parameters 732, 1308 shape() intrinsic function 938, 949 Shell algorithm (Shell's sort) 321ff., 1168 Sherman-Morrison formula 65ff., 83, 382 Shifting of eigenvalues 449, 470f., 480 Shock wave 831, 837 Shooting method computation of spheroidal harmonics 772, 1321ff. for differential equations 746, 749ff., 770ff., 1314ff., 1321ff. for difficult cases 753, 1315f. example 770ff., 1321ff. interior fitting point 752, 1315f., 1323ff. Shuffling to improve random number generator 270, 272 Side effects prevented by data hiding 957, 1209, 1293, 1296 and PURE subprograms 960 Sidelobe fall-off 548 Sidelobe level 548 sign() intrinsic function, modified in Fortran 95 961 Signal, bandwidth limited 495 Significance (numerical) 19 Significance (statistical) 609f. one- vs. two-sided 632 peak in Lomb periodogram 570 of 2-d K-S test 640, 1281 two-tailed 613 SIMD machines (Single Instruction Multiple Data) 964, 985f., 1009, 1084f. Similarity transform 452ff., 456, 476, 478, 482 Simplex defined 402 method in linear programming 389, 402, 423ff., 431ff., 1216ff.

method of Nelder and Mead 389, 402ff., 444, 697f., 1208f., 1222ff. use in simulated annealing 444, 1222ff. Simpson's rule 124ff., 128, 133, 136f., 583, 782, 788f., 1053f. Simpson's three-eighths rule 126, 789f. Simulated annealing see Annealing, method of simulated Simulation see Monte Carlo Sine function evaluated from tan(/2) 173 recurrence 172 series 160 Sine integral 248, 250ff., 1123, 1125f. continued fraction 250 series 250 see also Cosine integral Sine transform see Fast Fourier transform (FFT); Fourier transform Singleton's algorithm for FFT 525 Singular value decomposition (SVD) 23, 25, 51ff., 1022 approximation of matrices 58f. backsubstitution 56, 1022f. and bases for nullspace and range 53 confidence levels from 693f. covariance matrix 693f. fewer equations than unknowns 57 for inverse problems 797 and least squares 54ff., 199f., 668, 670ff., 1081, 1290f. in minimization 410 more equations than unknowns 57f. parallel algorithms 1026 and rational Chebyshev approximation 199f., 1081f. of square matrix 53ff., 1023 use for ill-conditioned matrices 56, 58, 449 use for orthonormal basis 58, 94 Singularities of hypergeometric function 203, 263 in integral equations 788ff., 1328 in integral equations, worked example 792, 1328ff. in integrands 135ff., 788, 1055, 1328ff. removal in numerical integration 137ff., 788, 1057ff., 1328ff. Singularity, subtraction of the 789 SIPSOL 824 Six-step framework, for FFT 983, 1240 size() intrinsic function 938, 942, 945, 948 Skew array section 2/xii, 945, 960, 985, 1284 Skewness of distribution 606, 608, 1269 Smoothing of data 114, 644ff., 1283f. of data in integral equations 781 importance in multigrid method 865 sn function 261, 1137f. Snyder, N.L. 1/xvi Sobol's quasi-random sequence 300ff., 1160f. Sonata 9 Sonnet 9 Sorting 320ff., 1167ff. bubble sort 1168

Index to Volumes 1 and 2

969

bubble sort cautioned against 321 compared to selection 333 covariance matrix 669, 681, 1289 eigenvectors 461f., 1227 Heapsort 320, 327f., 336, 1171f., 1179 index table 320, 329f., 1170, 1173ff., 1176 operation count 320ff. by packing 1171 parallel algorithms 1168, 1171f., 1176 Quicksort 320, 323ff., 330, 333, 1169f. radix sort 1172 rank table 320, 332, 1176 ranking 329, 1176 by reshaping array slices 1168 Shell's method 321ff., 1168 straight insertion 321f., 461f., 1167, 1227 SP, defined 937 SPARC or SPARCstation 1/xxii, 2/xix, 4 Sparse linear equations 23, 63ff., 732, 1030 band diagonal 43, 1019ff. biconjugate gradient method 77, 599, 1034 data type for 1030 indexed storage 71f., 1030 in inverse problems 804 minimum residual method 78 named patterns 64, 822 partial differential equations 822ff. relaxation method for boundary value problems 754, 1316 row-indexed storage 71f., 1030 wavelet transform 584, 598 see also Matrix Spearman rank-order coefficient 634f., 694f., 1277 Special functions see Function Spectral analysis see Fourier transform; Periodogram Spectral density 541 and data windowing 545ff. figures of merit for data windows 548f. normalization conventions 542f. one-sided PSD 492 periodogram 543ff., 566, 1258ff. power spectral density (PSD) 492f. power spectral density per unit time 493 power spectrum estimation by FFT 542ff., 1254ff. power spectrum estimation by MEM 565ff., 1258 two-sided PSD 493 variance reduction in spectral estimation 545 Spectral lines, how to smooth 644 Spectral methods for partial differential equations 825 Spectral radius 856ff., 862 Spectral test for random number generator 274 Spectrum see Fourier transform Spherical Bessel functions 234 routine for 245, 1121 Spherical harmonics 246ff. orthogonality 246

routine for 247f., 1122 stable recurrence for 247 table of 246 see also Associated Legendre polynomials Spheroidal harmonics 764ff., 770ff., 1319ff. boundary conditions 765 normalization 765 routine for 768ff., 1319ff., 1323ff. Spline 100 cubic 107ff., 1044f. gives tridiagonal system 109 natural 109, 1044f. operation count 109 two-dimensional (bicubic) 120f., 1050f. spread() intrinsic function 945, 950, 969, 1000, 1094, 1290f. and dimensional expansion 966ff. Spread matrix 808 Spread spectrum 290 Square root, complex 172 Square root, multiple precision 912, 1356f. Square window 546, 1254ff. SSP (small-scale parallel) machines 965ff., 972, 974, 984, 1011, 1016ff., 1021, 1059f., 1226ff., 1250 Stability 20f. of Clenshaw's recurrence 177 Courant condition 829, 832ff., 836, 846 diffusion equation 840 of Gauss-Jordan elimination 27, 29 of implicit differencing 729, 840 mesh-drift in PDEs 834f. nonlinear 831, 837 partial differential equations 820, 827f. of polynomial deflation 363 in quadrature solution of Volterra equation 787f. of recurrence relations 173ff., 177, 224f., 227f., 232, 247 and stiff differential equations 728f. von Neumann analysis for PDEs 827f., 830, 833f., 840 see also Accuracy Stabilized Kolmogorov-Smirnov test 621 Stabilizing functional 798 Staggered leapfrog method 833f. Standard (probable) errors 1288, 1290 Standard deviation of a distribution 605, 1269 of Fisher's z 632 of linear correlation coefficient 630 of sum squared difference of ranks 635, 1277 Standard (probable) errors 610, 656, 661, 667, 671, 684 Stars, as text separator 1009 Statement function, superseded by internal subprogram 1057, 1256 Statement labels 9 Statistical error 653 Statistical tests 603ff., 1269ff. Anderson-Darling 621 average deviation 605, 1269 bootstrap method 686f. chi-square 614f., 623ff., 1272, 1275f.

970

Index to Volumes 1 and 2

contingency coefficient C 625, 1275 contingency tables 622ff., 638, 1275f. correlation 603f. Cramer's V 625, 1275 difference of distributions 614ff., 1272 difference of means 609ff., 1269f. difference of variances 611, 613, 1271 entropy measures of association 626ff., 1275f. F-test 611, 613, 1271 Fisher's z-transformation 631f., 1276 general paradigm 603 Kendall's tau 634, 637ff., 1279 Kolmogorov-Smirnov 614, 617ff., 640, 694, 1273f., 1281 Kuiper's statistic 621 kurtosis 606, 608, 1269 L-estimates 694 linear correlation coefficient 630ff., 1276 M-estimates 694ff. mean 603ff., 608ff., 1269f. measures of association 604, 622ff., 1275 measures of central tendency 604ff., 1269 median 605, 694 mode 605 moments 604ff., 608, 1269 nonparametric correlation 633ff., 1277 Pearson's r 630ff., 1276 for periodic signal 570 phi statistic 625 R-estimates 694 rank correlation 633ff., 1277 robust 605, 634, 694ff. semi-invariants 608 for shift vs. for spread 620f. significance 609f., 1269ff. significance, one- vs. two-sided 613, 632 skewness 606, 608, 1269 Spearman rank-order coefficient 634f., 694f., 1277 standard deviation 605, 1269 strength vs. significance 609f., 622 Student's t 610, 631, 1269 Student's t, for correlation 631 Student's t, paired samples 612, 1271 Student's t, Spearman rank-order coefficient 634, 1277 Student's t, unequal variances 611, 1270 sum squared difference of ranks 635, 1277 Tukey's trimean 694 two-dimensional 640, 1281ff. variance 603ff., 607f., 612f., 1269ff. Wilcoxon 694 see also Error; Robust estimation Steak, without sizzle 809 Steed's method Bessel functions 234, 239 continued fractions 164f. Steepest descent method 414 in inverse problems 804 Step doubling 130, 708f., 1052 tripling 136, 1055 Stieltjes, procedure of 151

Stiff equations 703, 727ff., 1308ff. Kaps-Rentrop method 730, 1308 methods compared 739 predictor-corrector method 730 r.h.s. independent of x 729f. Rosenbrock method 730, 1308 scaling of variables 730 semi-implicit extrapolation method 730, 1310f. semi-implicit midpoint rule 735f., 1310f. Stiff functions 100, 399 Stirling's approximation 206, 812 Stoermer's rule 726, 1307 Stopping criterion, in multigrid method 875f. Stopping criterion, in polynomial root finding 366 Storage band diagonal matrix 44, 1019 sparse matrices 71f., 1030 Storage association 2/xiv Straight injection 867 Straight insertion 321f., 461f., 1167, 1227 Straight line fitting 655ff., 667f., 1285ff. errors in both coordinates 660ff., 1286ff. robust estimation 698, 1294ff. Strassen's fast matrix algorithms 96f. Stratified sampling, Monte Carlo 308f., 314 Stride (of an array) 944 communication bottleneck 969 Strongly implicit procedure (SIPSOL) 824 Structure constructor 2/xii Structured programming 5ff. Student's probability distribution 221f. Student's t-test for correlation 631 for difference of means 610, 1269 for difference of means (paired samples) 612, 1271 for difference of means (unequal variances) 611, 1270 for difference of ranks 635, 1277 Spearman rank-order coefficient 634, 1277 Sturmian sequence 469 Sub-random sequences see Quasi-random sequence Subprogram 938 for data hiding 957, 1209, 1293, 1296 internal 954, 957, 1057, 1067, 1226, 1256 in module 940 undefined variables on exit 952f., 961, 1070, 1266, 1293, 1302 Subscript triplet (for array) 944 Subtraction, multiple precision 907, 1353 Subtractive method for random number generator 273, 1143 Subvector scaling 972, 974, 996, 1000 Successive over-relaxation (SOR) 857ff., 862, 1332f. bad in multigrid method 866 Chebyshev acceleration 859f., 1332f. choice of overrelaxation parameter 858 with logical mask 1333f. parallelization 1333 sum() intrinsic function 945, 948, 966

Index to Volumes 1 and 2

971

Sum squared difference of ranks 634, 1277 Sums see Series Sun 1/xxii, 2/xix, 886 SPARCstation 1/xxii, 2/xix, 4 Supernova 1987A 640 SVD see Singular value decomposition (SVD) swap() utility function 987, 990f., 1015, 1210 Symbol, of operator 866f. Synthetic division 84, 167, 362, 370 parallel algorithms 977ff., 999, 1048, 1071f., 1079, 1192 repeated 978f. Systematic errors 653

T

ableau (interpolation) 103, 183 Tangent function, continued fraction 163 Target, for pointer 938f., 945, 952f. Taylor series 180, 355f., 408, 702, 709, 742, 754, 759 Test programs 3 Thermodynamics, analogy for simulated annealing 437 Thinking Machines, Inc. 964 Threshold multiply of sparse matrices 74, 1031 Tides 560f. Tikhonov-Miller regularization 799ff. Time domain 490 Time splitting 847f., 861 tiny() intrinsic function 952 Toeplitz matrix 82, 85ff., 195, 1038 LU decomposition 87 new, fast algorithms 88f. nonsymmetric 86ff., 1038 Tongue twisters 333 Torus 297f., 304 Trade-off curve 795, 809 Trademarks 1/xxii, 2/xixf. Transformation Gauss 256 Landen 256 method for random number generator 277ff. Transformational functions 948ff. Transforms, number theoretic 503f. Transport error 831ff. transpose() intrinsic function 950, 960, 969, 981, 1050, 1246 Transpose of sparse matrix 73f. Trapezoidal rule 125, 127, 130ff., 134f., 579, 583, 782, 786, 1052, 1326f. Traveling salesman problem 438ff., 1219ff. Tridiagonal matrix 42, 63, 150, 453f., 488, 839f., 1018f. in alternating-direction implicit method (ADI) 861f. from cubic spline 109 cyclic 67, 1030 in cyclic reduction 853 eigenvalues 469ff., 1228 with fringes 822 from operator splitting 861f. parallel algorithm 975, 1018, 1229f. recursive splitting 1229f. reduction of symmetric matrix to 462ff., 470, 1227f.

serial algorithm 1018f. see also Matrix Trigonometric functions, linear sequences 173 functions, recurrence relation 172, 572 functions, tan(/2) as minimal 173 interpolation 99 solution of cubic equation 179f. Truncation error 20f., 399, 709, 881, 1362 in multigrid method 875 in numerical derivatives 180 Tukey's biweight 697 Tukey's trimean 694 Turbo Pascal (Borland) 8 Twin errors 895 Two-dimensional see Multidimensional Two-dimensional K-S test 640, 1281ff. Two-pass algorithm for variance 607, 1269 Two-point boundary value problems 702, 745ff., 1314ff. automated allocation of mesh points 774f., 777 boundary conditions 745ff., 749, 751f., 771, 1314ff. difficult cases 753, 1315f. eigenvalue problem for differential equations 748, 764ff., 770ff., 1319ff. free boundary problem 748, 776 grid (mesh) points 746f., 754, 774f., 777 internal boundary conditions 775ff. internal singular points 775ff. linear requires no iteration 751 multiple shooting 753 problems reducible to standard form 748 regularity condition 775 relaxation method 746f., 753ff., 1316ff. relaxation method, example of 764ff., 1319 shooting to a fitting point 751ff., 1315f., 1323ff. shooting method 746, 749ff., 770ff., 1314ff., 1321ff. shooting method, example of 770ff., 1321ff. singular endpoints 751, 764, 771, 1315f., 1319ff. see also Elliptic partial differential equations Two-sided exponential error distribution 696 Two-sided power spectral density 493 Two-step Lax-Wendroff method 835ff. Two-volume edition, plan of 1/xiii Two's complement arithmetic 1144 Type declarations, explicit vs. implicit 2

bound() intrinsic function 949 LTRIX 1/xxiii, 2/xix ncertainty coefficient 628 ncertainty principle 600 ndefined status, of arrays and pointers 952f., 961, 1070, 1266, 1293, 1302 Underflow, in IEEE arithmetic 883, 1343 Underrelaxation 857 Uniform deviates see Random deviates, uniform U U U U

U

972

Index to Volumes 1 and 2

Unitary (function) 843f. Unitary (matrix) see Matrix unit matrix() utility function 985, 990, 1006, 1216, 1226, 1325 UNIX 1/xxiii, 2/viii, 2/xix, 4, 17, 276, 293, 886 Upper Hessenberg matrix see Hessenberg matrix U.S. Postal Service barcode 894 unpack() intrinsic function 950, 964 communication bottleneck 969 Upper subscript 944 upper triangle() utility function 990, 1006, 1226, 1305 Upwind differencing 832f., 837 USE statement 936, 939f., 954, 957, 1067, 1384 USES keyword in program listings 2 Utility functions 987ff., 1364ff. add vector to matrix diagonal 1004, 1234, 1366, 1381 alphabetical listing 988ff. argument checking 994f., 1370f. arithmetic progression 996, 1072, 1127, 1365, 1371f. array reallocation 992, 1070f., 1365, 1368f. assertion of numerical equality 995, 1022, 1365, 1370f. compared to intrinsics 990ff. complex nth root of unity 999f., 1379 copying arrays 991, 1034, 1327f., 1365f. create unit matrix 1006, 1382 cumulative product of an array 997f., 1072, 1086, 1375 cumulative sum of an array 997, 1280f., 1365, 1375 data types 1361 elemental functions 1364 error handling 994f., 1036, 1370f. generic functions 1364 geometric progression 996f., 1365, 1372ff. get diagonal of matrix 1005, 1226f., 1366, 1381f. length of a vector 1008, 1383 linear recurrence 996 location in an array 992ff., 1015, 1017ff. location of first logical "true" 993, 1041, 1369 location of maximum array value 993, 1015, 1017, 1365, 1369 location of minimum array value 993, 1369f. logical assertion 994, 1086, 1090, 1092, 1365, 1370 lower triangular mask 1007, 1200, 1382 masked polynomial evaluation 1378 masked swap of elements in two arrays 1368 moving data 990ff., 1015 multiply vector into matrix diagonal 1004f., 1366, 1381 nrutil.f90 (module file) 1364ff. outer difference of vectors 1001, 1366, 1380 outer logical and of vectors 1002

outer operations on vectors 1000ff., 1379f. outer product of vectors 1000f., 1076, 1365f., 1379 outer quotient of vectors 1001, 1379 outer sum of vectors 1001, 1379f. overloading 1364 partial cumulants of a polynomial 999, 1071, 1192f., 1365, 1378f. polynomial evaluation 996, 998f., 1258, 1365, 1376ff. scatter-with-add 1002f., 1032f., 1366, 1380f. scatter-with-combine 1002f., 1032f., 1380f. scatter-with-max 1003f., 1366, 1381 set diagonal elements of matrix 1005, 1200, 1366, 1382 skew operation on matrices 1004ff., 1381ff. swap elements of two arrays 991, 1015, 1365ff. upper triangular mask 1006, 1226, 1305, 1382

V -cycle 865, 1336 vabs() utility function 990, 1008, 1290 Validation of Numerical Recipes procedures 3f. Valley, long or narrow 403, 407, 410 Van Cittert's method 804 Van Wijngaarden-Dekker-Brent method see Brent's method Vandermonde matrix 82ff., 114, 1037, 1047 Variable length code 896, 1346ff. Variable metric method 390, 418ff., 1215 compared to conjugate gradient method 418 Variable step-size integration 123, 135, 703, 707ff., 720, 726, 731, 737, 742ff., 1298ff., 1303, 1308f., 1311ff. Variance(s) correlation 605 of distribution 603ff., 608, 611, 613, 1269 pooled 610 reduction of (in Monte Carlo) 299, 306ff. statistical differences between two 609, 1271 two-pass algorithm for computing 607, 1269 see also Covariance Variational methods, partial differential equations 824 VAX 275, 293 Vector(s) length 1008, 1383 norms 1036 outer difference 1001, 1366, 1380 outer operations 1000ff., 1379f. outer product 1000f., 1076, 1365f., 1379 Vector reduction 972, 977, 998 Vector subscripts 2/xiif., 984, 1002, 1032, 1034 communication bottleneck 969, 981, 1250 VEGAS algorithm for Monte Carlo 309ff., 1161 Verhoeff 's algorithm for checksums 894f., 1345

Index to Volumes 1 and 2

973

Viete's formulas for cubic roots 179 ` Vienna Fortran 2/xv Virus, computer 889 Viscosity artificial 831, 837 numerical 830f., 837 Visibility 956ff., 1209, 1293, 1296 VMS 1/xxii, 2/xix Volterra equations 780f., 1326 adaptive stepsize control 788 analogy with ODEs 786 block-by-block method 788 first kind 781, 786 nonlinear 781, 787 second kind 781, 786ff., 1326f. unstable quadrature 787f. von Neuman, John 963, 965 von Neumann-Richtmyer artificial viscosity 837 von Neumann stability analysis for PDEs 827f., 830, 833f., 840 Vowellish (coding example) 896f., 902

W

-cycle 865, 1336 Warranty, disclaimer of 1/xx, 2/xvii Wave equation 246, 818, 825f. Wavelet transform 584ff., 1264ff. appearance of wavelets 590ff. approximation condition of order p 585 coefficient values 586, 589, 1265 contrasted with Fourier transform 584, 594 Daubechies wavelet filter coefficients 584ff., 588, 590f., 594, 598, 1264ff. detail information 585 discrete wavelet transform (DWT) 586f., 1264 DWT (discrete wavelet transform) 586f., 1264ff. eliminating wrap-around 587 fast solution of linear equations 597ff. filters 592f. and Fourier domain 592f. image processing 596f. for integral equations 782 inverse 587 Lemarie's wavelet 593 of linear operator 597ff. mother-function coefficient 587 mother functions 584 multidimensional 595, 1267f. nonsmoothness of wavelets 591 pyramidal algorithm 586, 1264 quadrature mirror filter 585 smooth information 585 truncation 594f. wavelet filter coefficient 584, 587 wavelets 584, 590ff. Wavelets see Wavelet transform Weber function 204 Weighted Kolmogorov-Smirnov test 621 Weighted least-squares fitting see Least squares fitting

Weighting, full vs. half in multigrid 867 Weights for Gaussian quadrature 140ff., 788f., 1059ff., 1328f. nonclassical weight function 151ff., 788f., 1064f., 1328f. Welch window 547, 1254ff. WG5 (ISO/IEC JTC1/SC22/WG5 Committee) 2/xiff. where construct 943, 1291 contrasted with merge 1023 for iteration of a vector 1060 nested 2/xv, 943, 960, 1100 not MIMD 985 While iteration 13 Wiener filtering 535, 539ff., 558, 644 compared to regularization 801 Wiener-Khinchin theorem 492, 558, 566f. Wilcoxon test 694 Window function Bartlett 547, 1254ff. flat-topped 549 Hamming 547 Hann 547 Parzen 547 square 544, 546, 1254ff. Welch 547, 1254ff. Windowing for spectral estimation 1255f. Windows 95 2/xix Windows NT 2/xix Winograd Fourier transform algorithms 503 Woodbury formula 68ff., 83 Wordlength 18 Workspace, reallocation in Fortran 90 1070f. World Wide Web, Numerical Recipes site 1/xx, 2/xvii Wraparound in integer arithmetic 1146, 1148 order for storing spectrum 501 problem in convolution 533 Wronskian, of Bessel functions 234, 239

X .25 protocol 890 X3J3 Committee 2/viii, 2/xff., 2/xv, 947, 959, 964, 968, 990 XMODEM checksum 889 X-ray diffraction pattern, processing of 805 Y Z
ale Sparse Matrix Package 64, 71

-transform 554, 559, 565 Z-transformation, Fisher's 631f., 1276 Zaman, A. 1149 Zealots 814 Zebra relaxation 866 Zero contours 372 Zero-length array 944 Zeroth-order regularization 796ff. Zip code, barcode for 894 Ziv-Lempel compression 896 zroots unity() utility function 974, 990, 999