|
BOOKSBOOKSBOOKS
Numerical Recipes: The art of scientific computing. 3rd edition
by William H. Press, Saul A. Teukolsky, William T. Vetterling, and Brian P. Flannery Cambridge University Press, 2007
Reviewed by |
|
This book is the third edition of one of the most practical and interesting books I’ve used in my research and study. Written by a team of high profile academics, numerical recipes is bursting at the covers with a huge range of topics in 1235 pages consisting of 22 chapters. This new edition contains two entirely new chapters, 25 new sections, over a hundred new routines, and many other updates to the text. An older 2nd edition of the book in C is freely available on the web at www.nr.com/oldverswitcher.html . In the following paragraphs I’ll attempt to quickly summarize the contents of this book. Most of these chapters could be a textbook by themselves, so some of the coverage is fairly brief. Note that each of these topics mentioned is accompanied by code examples. The first chapter of the book provides information on floating point representations in computers, round-off and truncation errors, and stability. This is followed by a brief overview of C and C++ programming concepts. Chapter 2 focuses on solutions of linear algebraic equations and covers Gauss-Jordan elimination; Gaussian elimination with back-substitution; LU decomposition; tri-diagonal and band-diagonal systems of equations; iterative improvements to solutions; singular value decomposition, sparse linear systems, Vandermonde and Toeplitz matrices; Cholesky and QR decomposition. The authors also briefly mention LAPACK here as well. The third chapter moves on to interpolation and extrapolation (polynomial, cubic spline, rational functions and Laplacian). There is also a useful section on interpolation on a grid in multiple dimensions. The next three chapters are concerned with functions and include topics on integration (from classical formulas and elementary algorithms through to multidimensional integrals)and evaluation (polynomials and rational functions, continued fractions, series and their convergence, recurrence relations, complex arithmetic, quadratic and cubic equations, numerical derivatives, topics relating to Chebyshev approximation, economization of power series, Padé approximants and evaluation by path integration). Finally there is a chapter containing a huge list of special functions, each with a clear description and associated code listings. These include the gamma and beta functions, factorials, Bessel functions, spherical harmonics, Fresnel, cosine and sine integrals, Jacobian elliptic functions and many useful statistical functions. Chapter seven contains 78 pages on random numbers from basic pseudo-random number generation to adaptive and recursive Monte Carlo methods. Of note in this chapter are the sections on hash tables and hash memories. The next chapter provides a review of sorting and searching algorithms (Quicksort, Heapsort, finding the Mth largest elements in an array, etc). Root finding and nonlinear sets of equations are the topic of the next chapter, commencing with bracketing and bisection, secant, false positive, Ridders’, Brent’s, and Newton-Raphson methods. These are followed by sections on finding roots of polynomials using Newton-Raphson for nonlinear systems of equations and globally convergent methods. This leads into what I think is one of the most useful chapters in the book focussing on optimization in one dimension (golden search, parabolic interpolation, and one-dimensional search with first derivatives) and then multiple dimensions (downhill simplex, Powell’s, conjugate gradient and quasi-Newton methods). This chapter then introduces linear programming and describes the simplex and interior point methods. Finally there are fairly brief sections on simulated annealing methods and dynamic programming. Chapter eleven discusses eigensystems, from introductory topics to Jacobi transformations of symmetric matrices, eigenvalues and eigenvectors of tridiagonal matrices, Hermitian and real nonsymmetric matrices, and more. The next two chapters move into the frequency domain with a good introduction to the Fourier transform and the fast Fourier transform (FFT) in one, two (e.g. for image processing) and three dimensions. This is followed by sections applying the FFT including: convolution/deconvolution, correlation and autocorrelation, Wiener filtering, power spectrum estimation, and computing Fourier integrals. An interesting section on wavelets and the discrete wavelet transform (DWT) is also included. The next three chapters of the book (178 pages) cover statistical description of data (moments various statistical tests, correlation, information, a good section on theoretic properties of distributions such as entropy and mutual information, and smoothing filters), then modelling of data (least squares as a maximum likelihood estimator, data fitting to a line, general linear least squares, nonlinear models, confidence limits on estimated model parameters, Markov Chain Monte Carlo, and Gaussian process regression), and finally classification and inference (Bayesian networks, Gaussian mixture models and k-means clustering, Viterbi decoding, Markov models and hidden Markov models, hierarchical clustering by Phylogenetic trees, and support vector machines). The book returns to calculus in chapters 17-20. These chapters discuss the integration of ordinary differential equations, two-point boundary value problems, integral equations and inverse theory, and partial differential equations. Chapter 21 targets useful topics in computational geometry including tree data structures for sets of points, nearest-neighbour problems, line segments, polygons, spheres, triangulation, Voronoi diagrams, and convex hulls. The final chapter contains an eclectic selection of algorithms ranging from plotting simple PostScript® graphs, diagnosing machine parameters, gray codes, cyclic redundancy, data compression, arithmetic coding, and arithmetic at an arbitrary precision. The layout of the book is consistent, with colour used to highlight program code. The header filename is shown in the margin next to each function. The index and general editing appear to be excellent. The CD-ROM (which does not come with the book by default) contains all of the source code. Index pages are provided listing the code by section, identifier, and filename. The CD-ROM also contains all code from the 1st and 2nd book editions and some historical libraries of code (mainly in C). There is also a very good web site associated with the book at www.nr.com which includes an online version of the book (license required), extra information (e.g. a tutorial on using NRR to extend Matlab), active user forums (which amongst other topics contains a thread on alternates to the book such as www.netlib.org and www.gnu.org/software/gsl/gsl.html). The online dependencies tool at www.nr.com/dependencies/ is useful for working out which header files need to be included to use each function. The license for the numerical recipes code has attracted some criticism. In a nutshell, purchasing the book only provides a single user license which allows the distribution of compiled code for non-commercial use only. However, in the book’s defence, it does appear to be designed to teach a reader how to understand the solution to a numerical problem. As the authors state in the preface (p. xx), readers are free to develop their own implementations of solutions and include them in commercial applications. This seems fair to me. Of interest to readers in developing countries is the recent announcement on www.nr.com that “Numerical Recipes Third Edition (on-line book and code) is now available by open access to users in developing countries. This free resource is hosted by ICTP, a UNESCO and IAEA organization”. It’s hard to fault such a classic book. I think in general the code could be made easier to understand by updating single letter variable names to something meaningful. The authors don’t appear to make use of the C++ standard template library. Also, the 2nd edition of numerical recipes had example driver code for each class which might have been a useful addition on the CD-ROM. In summary, I think this is an incredibly valuable book for both learning and reference, and I recommend it for any scientists or student in a numerate discipline who need to understand and/or program numerical algorithms. |
|
Click above to go to the publisher’s web page for Numerical Recipes. |
|
Book Reviews Published in the IAPR Newsletter
Feature Extraction and Image Processing, 2nd ed. by Nixon and Aguado
Digital Watermarking and Steganography: Fundamentals and Techniques by Shih
Springer Handbook of Speech Processing by Benesty, Sondhi, and Huang, eds.
Digital Image Processing: An Algorithmic Introduction Using Java by Burger and Burge
Bézier and Splines in Image Processing and Machine Vision by Biswas and Lovell
Practical Algorithms for Image Analysis, 2 ed. by O’Gorman, Sammon and Seul
The Dissimilarity Representation for Pattern Recognition: Foundations and Applications by Pekalska and Duin
Handbook of Biometrics by Jain, Flynn, and Ross (Editors)
Advances in Biometrics – Sensors, Algorithms, and Systems by Ratha and Govindaraju, (Editors)
Dynamic Vision for Perception and Control of Motion by Dickmanns
Bioinformatics by Polanski and Kimmel
Introduction to clustering large and high-dimensional data by Kogan
The Text Mining Handbook by Feldman and Sanger
Information Theory, Inference, and Learning Algorithms by Makay
Geometric Tomography by Gardner
“Foundations and Trends in Computer Graphics and Vision” Curless, Van Gool, and Szeliski., Editors
Applied Combinatorics on Words by M. Lothaire
Human Identification Based on Gait by Nixon, Tan and Chellappar
Mathematics of Digital Images by Stuart Hogan
Advances in Image and Video Segmentation Zhang, Editor
Graph-Theoretic Techniques for Web Content Mining by Schenker, Bunke, Last and Kandel
Handbook of Mathematical Models in Computer Vision by Paragios, Chen, and Faugeras (Editors)
The Geometry of Information Retrieval by van Rijsbergen
Biometric Inverse Problems by Yanushkevich, Stoica, Shmerko and Popel
Correlation Pattern Recognition by Kumar, Mahalanobis, and Juday
Pattern Recognition 3rd Edition by Theodoridis and Koutroumbas
Dictionary of Computer Vision and Image Processing by R.B. Fisher, et. Al
Kernel Methods for Pattern Analysis by Shawe-Taylor and Cristianini
Machine Vision Books
CVonline: an overview
The Guide to Biometrics by Bolle, et al
Pattern Recognition Books Jul. ‘04 [pdf] |
