Numerical Problems

If most problems you encounter are numerical in nature, there is a good chance that you are reading the wrong book. Numerical Recipes [PFTV86] gives a terrific overview to the fundamental problems in numerical computing, including linear algebra, numerical   integration, statistics, and differential equations. Different flavors of the book include source code for all the algorithms in C, Pascal, and Fortran. Their coverage is skimpier on the combinatorial/numerical problems we consider in this section, but you should be aware of that book.

Numerical algorithms tend to be different beasts than combinatorial algorithms, for at least two distinct reasons:

• Issues of Precision and Error - Numerical algorithms typically perform repeated floating-point computations, which accumulate error at each operation until, eventually, the results are meaningless. An amusing example [SK93] concerns the Vancouver Stock Exchange, which over a twenty-two month period accumulated sufficient round-off error to reduce its index from the correct value of 1098.982 to 574.081.       

  A simple and dependable way to test for round-off errors in numerical     programs is to run them both at single and double precision, and then think hard whenever there is a disagreement.

• Extensive Libraries of Codes -       Large, high-quality libraries of numerical routines have existed since the 1960s, which is still not the case for combinatorial algorithms. This is true for several reasons, including (1) the early emergence of Fortran as a standard for numerical computation, (2) the nature of numerical computations to remain independent rather than be embedded within large applications, and (3)   the existence of large scientific communities needing general numerical libraries.

  Regardless of why, you should exploit this software base. There is probably no reason to implement algorithms for any of the problems in this section instead of stealing existing codes.   Searching Netlib (see Section ) is always a good place to start.

Most scientist's and engineer's ideas about algorithms derive from Fortran programming and numerical methods, while computer scientists grew up programming with pointers and recursion, and so are comfortable with the more sophisticated data structures required for combinatorial algorithms. Both sides can and should learn from each other, since several problems such as pattern recognition can be modeled either numerically or combinatorially.

There is a vast literature on numerical algorithms. In addition to Numerical Recipes, recommended books include:

• Skeel and Keiper [SK93] - A readable and interesting treatment of basic numerical methods, avoiding overly detailed algorithm descriptions through its use of the computer algebra system Mathematica.   I like it.
• Pizer and Wallace [PW83] - A numerical analysis book written for computer scientists, not engineers. The organization is by issues instead of problems. A different but interesting perspective.
• Cheney and Kincaid [CK80] - A traditional Fortran-based numerical analysis text, with discussions of optimization and Monte Carlo methods in addition to such standard topics as root-finding, numerical integration, linear systems, splines, and differential equations.   
• Buchanan and Turner [BT92] - Thorough language-independent treatment of all standard topics, including parallel algorithms. Most comprehensive of the texts described here.

• Solving Linear Equations
• Bandwidth Reduction
• Matrix Multiplication
• Determinants and Permanents
• Constrained and Unconstrained Optimization
• Linear Programming
• Random Number Generation
• Factoring and Primality Testing
• Arbitrary-Precision Arithmetic
• Knapsack Problem
• Discrete Fourier Transform