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 )
 
 
Numerical Algorithms (G.1.0 ... )
 
 
Complexity Measures And Classes (F.1.3 )
 
Would you recommend this review?
yes
no
Other reviews under "Numerical Algorithms And Problems": Date
On the computational complexity of ordinary differential equations
Ko K. (ed) Information and Control 58(1-3): 157-194, 1984. Type: Article
Jun 1 1985
The computational complexity of simultaneous diophantine approximation problems
Lagarias J. SIAM Journal on Computing 14(1): 196-209, 1985. Type: Article
Jan 1 1986
Parallel and distributed computation: numerical methods
Bertsekas D., Tsitsiklis J., Prentice-Hall, Inc., Upper Saddle River, NJ, 1989. Type: Book (9789780136487005)
Apr 1 1990
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy