number of A, while the original algorithm may fail due to large growth
factors. For example, the following is
a fragment of Matlab code that first
solves a linear system whose matrix is
the 70 × 70 matrix Wilkinson designed
to trip up partial pivoting, using the
Matlab linear solver. We then perturb the system, and apply the Matlab
>> Using the Matlab Solver
>> n = 70; A = 2*eye(n)-
tril(ones(n) ); A(:,n)= 1;
>> b = randn( 70, 1); x = A\b;
>> norm (A*x-b)
>> FAILED because of large
>> %Using the new solver
>> Ap = A + randn(n)/10^ 9;
y = Ap\b;
Note that while the Matlab linear
solver fails to find a good solution to the
linear system, our new perturbation-based algorithm finds a good solution.
While there are standard algorithms
for solving linear equations that do not
have the poor worst-case performance
of partial pivoting, they are rarely used
as they are less efficient.
For more examples of algorithm
design inspired by smoothed analysis
and perturbation theory, see Teng. 37
We would like to thank Alan Edelman
for suggesting the name “Smoothed
Analysis” and thank Heiko Röglin and
Don Knuth for helpful comments on
Due to Communications space con-strainsts, we have had to restrict our
bibliography to 40 references. We
apologize to those whose work we have
been forced not to reference.
1. adler, i. the expected number of pivots needed
to solve parametric linear programs and the
efficiency of the self-dual simplex method.
technical report, university of california at Berkeley
2. andoni, a. and Krauthgamer, r. the smoothed
complexity of edit distance. in Proceedings of ICALP,
volume 5125 of Lecture Notes in Computer Science
(springer, 2008) 357–369.
3. arthur, D. and vassilvitskii, s. how slow is the
k-means method? in SOCG ’06, the 22nd Annual
ACM Symposium on Computational Geometry (2006)
4. arthur, D. and vassilvitskii, s. Worst-case and
smoothed analysis of the icP algorithm, with an
application to the k-means method. in FOCS ’06,
the 47th Annual IEEE Symposium on Foundations of
Computer Science (2006) 153–164.
5. Becchetti, l., leonardi, s., Marchetti-spaccamela,
a., schfer, g., and vredeveld, t. average-case and
smoothed competitive analysis of the multilevel
feedback algorithm. Math. Oper. Res. 31, 1 (2006),
6. Beier, r. and vöcking, B. typical properties of winners
and losers in discrete optimization. in S TOC ’04:
the 36th Annual ACM Symposium on Theory of
Computing (2004), 343–352.
7. Blum, a. and Dunagan, J. smoothed analysis of
the perceptron algorithm for linear programming.
in SODA ’02 (2002), 905–914.
8. Blum, a. and spencer, J. coloring random and
semi-random k-colorable graphs. J. Algorithms 19, 2
9. Bohman, t., frieze, a. and Martin, r. how many
random edges make a dense graph hamiltonian?
Random Struct. Algorithms 22, 1 (2003), 33–42.
10. Bürgisser, P., cucker, f., and lotz, M. smoothed
analysis of complex conic condition numbers. J.
de Mathématiques Pures Appliqués 86 4 (2006),
11. Damerow, v., Meyer auf der heide, f., räcke, h.,
scheideler, c., and sohler, c. smoothed motion
complexity. in Proceedings of the 11th Annual
European Symposium on Algorithms (2003), 161–171.
12. Dantzig, g.B. Maximization of linear function of
variables subject to linear inequalities. Activity
Analysis of Production and Allocation.
t.c. Koopmans, ed. 1951, 339–347.
13. Dunagan, J., spielman, D.a., and teng, s.-h.
smoothed analysis of condition numbers and
complexity implications for linear programming.
Mathematical Programming, Series A, 2009. to
appear. Preliminary version available at http://arxiv.
14. edelman, a. eigenvalue roulette and random test
matrices. Linear Algebra for Large Scale and
Real- Time Applications. Marc s. Moonen, gene h.
golub, and Bart l. r. De Moor, eds. nato asi series,
15. englert, M., röglin, h., and vöcking, B. Worst case
and probabilistic analysis of the 2-opt algorithm
for the tsP: extended abstract. in SODA ’07: The
18th Annual ACM-SIAM Symposium on Discrete
Algorithms (2007), 1295–1304.
16. feige, u. refuting smoothed 3cnf formulas. in The
48th Annual IEEE Symposium on Foundations of
Computer Science (2007), 407–417.
17. flaxman, a. and frieze, a.M. the diameter of
randomly perturbed digraphs and some applications.
in APPROX-RANDOM (2004), 345–356.
18. gass, s. and saaty, t. the computational algorithm
for the parametric objective function. Naval Res.
Logist. Quart. 2, (1955), 39–45.
19. haimovich, M. the simplex algorithm is very
good!: on the expected number of pivot steps and
related properties of random linear programs.
technical report, columbia university (april 1983).
20. huang, l.-s. and teng, s.-h. on the approximation
and smoothed complexity of leontief market
equilibria. in Frontiers of Algorithms Workshop
21. Kalai, a. and teng, s.-h. Decision trees are Pac-learnable from most product distributions: a
smoothed analysis. ArXiv e-prints (December 2008).
22. Karger, D. and onak, K. Polynomial approximation
schemes for smoothed and random instances of
multidimensional packing problems. in SODA ’07:
the 18th Annual ACM-SIAM Symposium on Discrete
Algorithms (2007), 1207–1216.
23. Kelner, J.a. and nikolova, e. on the hardness and
smoothed complexity of quasi-concave minimization.
in The 48th Annual IEEE Symposium on Foundations
of Computer Science (2007), 472–482.
24. Kelner, J.a. and spielman, D.a. a randomized
polynomial-time simplex algorithm for linear
programming. in The 38th Annual ACM Symposium
on Theory of Computing (2006), 51–60.
25. Klee, v. and Minty, g.J. how good is the simplex
algorithm? Inequalities – III. o. shisha, ed.
academic Press, 1972, 159–175.
26. Krivelevich, M., sudakov, B. and tetali, P. on
smoothed analysis in dense graphs and formulas.
Random Struct. Algorithms 29 (2005), 180–193.
27. Ma, B. Why greed works for shortest common
superstring problem. in CPM ’08: Proceedings of the
19th Annual Symposium on Combinatorial Pattern
Matching (2008), 244–254.
28. Manthey, B. and röglin, h. improved smoothed
analysis of the k-means method. in SODA ’09
29. Mehlhorn, K. and näher, s. The LEDA Platform of
Combinatorial and Geometric Computing. cambridge
university Press, new york, 1999.
30. Mitzenmacher, M. and vadhan, s. Why simple hash
functions work: exploiting the entropy in a data
stream. in SODA ’08: Proceedings of the Nineteenth
Annual ACM-SIAM Symposium on Discrete
Algorithms (2008), 746–755.
31. röglin, h. and vöcking, B. smoothed analysis of
integer programming. Proceedings of the 11th
International Conference on Integer Programming
and Combinatorial Optimization. M. Junger and
v. Kaibel, eds. volume 3509 of lecture notes in
computer science, springer, 2005, 276–290.
32. rudelson, M. and vershynin, r. the littlewood-offord
problem and invertibility of random matrices. Adv.
Math. 218, (June 2008), 600–633.
33. sankar, a. smoothed analysis of gaussian
elimination. Ph.D. thesis, Mit, 2004.
34. sankar, a., spielman, D.a., and teng, s.-h. smoothed
analysis of the condition numbers and growth factors
of matrices. SIAM J. Matrix Anal. Appl. 28, 2 (2006),
35. spielman, D.a. and teng, s.-h. smoothed analysis
of algorithms. in Proceedings of the International
Congress of Mathematicians (2002), 597–606.
36. spielman, D.a. and teng, s.-h. smoothed analysis
of algorithms: Why the simplex algorithm usually
takes polynomial time. J. ACM 51, 3 (20040,
37. teng, s.-h. algorithm design and analysis with
perburbations. in Fourth International Congress of
Chinese Mathematicans (2007).
38. vershynin, r. Beyond hirsch conjecture: Walks on
random polytopes and smoothed complexity of the
simplex method. in Proceedings of the 47th Annual
IEEE Symposium on Foundations of Computer
Science (2006), 133–142.
39. vu, v.h. and tao, t. the condition number of a
randomly perturbed matrix. in STOC ’07: the 39th
Annual ACM Symposium on Theory of Computing
40. Wschebor, M. smoothed analysis of k (a).
J. Complexity 20, 1 (february 2004), 97–107.
Daniel A. Spielman ( email@example.com) is a
professor of applied Mathematics and computer science
at yale university, new haven, ct.
Shang-hua Teng ( firstname.lastname@example.org) is a
professor of Department of computer science, at Boston
university, and senior research scientist at akamai
© acM 0001-0782/09/1000 $10.00.