Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Condition : the geometry of numerical algorithms
Bürgisser P., Cucker F., Springer Publishing Company, Incorporated, New York, NY, 2013. 583 pp.  Type: Book (978-3-642388-95-8)
Date Reviewed: Nov 26 2013

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.

Reviewer:  Tanbir Ahmed Review #: CR141762 (1402-0111)
Bookmark and Share
 
Numerical Algorithms And Problems (F.2.1 )
 
 
Complexity Measures And Classes (F.1.3 )
 
 
Numerical Algorithms (G.1.0 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Numerical Algorithms And Problems": Date
Quadratic maps are hard to sample
Viola E.  ACM Transactions on Computation Theory 8(4): 1-4, 2016. Type: Article
Jul 26 2016
Truthfulness and stochastic dominance with monetary transfers
Hoefer M., Kesselheim T., Vöcking B.  ACM Transactions on Economics and Computation 4(2): 1-18, 2016. Type: Article
Apr 29 2016
Numerical algorithms: methods for computer vision, machine learning, and graphics
Solomon J.,  CRC Press, Inc., Boca Raton, FL, 2015. 400 pp. Type: Book (978-1-482251-88-3)
Mar 31 2016
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright © 2000-2017 ThinkLoud, Inc.
Terms of Use
| Privacy Policy