Implementing numerical algorithms may require the approximation of numerical quantities, given that computers have only a finite number of bits and real numbers cannot be encoded with a finite number of bits. Growth in computational power has enabled an increase in the size of data as well as in the length of computations, which in turn may lead to a significant deviation from the expected output due to accumulation of round-off errors.
The authors of this book discuss the ways that such errors are produced in a computer, and consider the use of condition numbers to understand the performance of numerical algorithms. The condition number of an input is “the worst possible magnification of the [error in output] with respect to a small input perturbation.”
The book contains three parts. Part 1 focuses on condition in linear algebra at an undergraduate level. Part 2 discusses condition in linear programming to try to fill the gap between current elementary expositions on the simplex method and convex programming. The authors recommend Part 2 for an advanced undergraduate course. Part 3 deals with condition in polynomial equation solving and describes recent developments, including partial solutions for Smale’s 17th problem.
To deal with the prominent use of probabilistic estimates in this area, the authors introduce a “Crash Course in Probability,” split into six installments that readers encounter as they progress from Part 1 to Part 3. Instead of delving into the vastness of probability theory, the authors maintain brevity by presenting only required information, and include proofs to make the crash course self-contained. They also provide detailed preparatory materials on Euclidean and spherical convexity, and some basic properties of projective spaces.
Part 3 recounts recent advances in the subject in depth. It should be noted that solving systems of polynomial equations is one of the central problems in mathematics. One outstanding question that has recently seen significant progress is Smale’s 17th problem, which asks: “Can a zero of n complex polynomial equations in n unknowns be found approximately, on average, in polynomial time with a uniform algorithm?” The authors provide a comprehensive survey, considering publications as recent as 2013, to document the partial solutions for this problem obtained so far.
Numerous questions remain unanswered, even though the subject has recently seen phenomenal growth in the understanding of the role of condition in the performance of numerical algorithms. The authors conclude with a set of relevant open problems, each with a brief description and a clear statement.
In my opinion, this monograph not only offers a well-organized and systematic introduction to the subject, but also works as a useful reference for advanced researchers.