You are here

American Mathematical Monthly - December 1998

Articles

The Idea Behind Krylov Methods
by Ilse C. F. Ipsen and Carl D. Meyer
ipsen@math.ncsu.edu, meyer@math.ncsu.edu
We explain why Krylov methods make sense, and why it is natural to represent a solution to a linear system as a member of a Krylov space. We show that the solution to a nonsingular linear system lies in a Krylov space whose dimension is the degree of the minimal polynomial of the matrix. Therefore, if the minimal polynomial has low degree then the space in which a Krylov method searches for the solution can be small. In this case a Krylov method has the opportunity to converge fast.

When the matrix is singular, however, Krylov methods can fail. Even if the linear system does have a solution, it might not lie in a Krylov space. In this case we describe a class of right-hand sides for which a solution lies in a Krylov space. As it happens, only one solution lies in a Krylov space, and it can be obtained from the Drazin inverse.

Our discussion demonstrates that eigenvalues play a central role when it comes to ensuring existence and uniqueness of Krylov solutions; they are not merely an artifact of convergence analyses.

 

Product-Free Subsets of Groups
by Kiran S. Kedlaya
kedlaya@math.mit.edu
A subset of a group is product-free if the product of two of its elements is never itself an element of the subset. We survey the problem of finding large product-free subsets for three types of groups: finite abelian groups, where the optimal subsets are known in most cases; arbitrary abelian groups, where a construction previously introduced by the author is the best known partial result; and compact topological groups, where almost nothing is known.

 

Polynomial Equations and Convex Polytopes
by Bernd Sturmfels
bernd@math.berkeley.edu
This article gives an elementary introduction to the use of Newton polytopes for solving systems of polynomial equations. Topics discussed include Bernstein's Theorem (relating the number of roots to the mixed volume of convex polytopes) and Khovanskii's Fewnomial Theorem (which explains why the number of real roots is typically much smaller than the number of complex roots). The emphasis is on algorithms and open problems.

 

Multivision: An Intractable Impartial Game With a Linear Winning Strategy
by Aviezri S. Fraenkel
fraenkel@wisdom.weizmann.ac.il
Something is definitely wrong. If the game has a linear winning strategy, then it is tractable. What's going on? We describe a two-person game that has a definite winner, that is, a player who can force a win in a finite number of moves, and we determine the winner in linear time. Moreover, the winner's winning moves can be computed in linear time, yet the game is highly intractable. In particular, at each step, except the very last ones, a player can make the length of play arbitrarily long.

 

Seven Deadly Sins of Numerical Computation
by Brian J. McCartin
bmccarti@kettering.edu
Nowhere is the old adage "a little knowledge is a dangerous thing" more apropos than in numerical computation. With minimal expertise and a powerful computer, the novice may now boldly attempt to simulate the physical world in which we are all embedded. However, this is essentially an invitation to 'shoot oneself in the foot' unless certain subtle pitfalls inherent in passing from continuum models of reality to the discrete domain of the digital computer are studiously avoided. We discuss seven of the most egregious such transgressions.

 

NOTES

Generating Integrals and an Elementary Proof of the Finite Harmonic Series Theorem by Fractional Calculus
by S. C. Woon
s.c.woon@damtp.cam.ac.uk

Monotonicity of the Maxima
by Raymond M. Redheffer
rr@math.ucla.edu

A Simple Proof of Farkas' Lemma
by Vilmos Komornik
komornik@math.u-strasbg.fr

UNSOLVED PROBLEMS

Nothing's New in Number Theory?
by Richard K. Guy
rkg@cpsc.ucalgary.ca

PROBLEMS AND SOLUTIONS

REVIEWS

Julia, A Life in Mathematics.
By Constance Reid

Reviewed by Lenore Blum
lblum@icsi.berkeley.edu

Would-be Worlds
By John L. Casti

Reviewed by Daniel P. Maki
maki@indiana.edu

The Number Sense: How the Mind Creates Mathematics
By Stanislas Dehaene

Reviewed by Reuben Hersh
rhersh@math.unm.edu

TELEGRAPHIC REVIEWS

INDEX TO VOLUME 105