Hostname: page-component-586b7cd67f-gb8f7 Total loading time: 0 Render date: 2024-11-25T19:13:50.339Z Has data issue: false hasContentIssue false
  • English
  • Français

Probabilistic analyses of condition numbers*

Published online by Cambridge University Press:  23 May 2016

Felipe Cucker
Felipe Cucker*
Affiliation:
Department of Mathematics, City University of Hong Kong E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

In recent decades, condition numbers have joined forces with probabilistic analysis to give rise to a form of condition-based analysis of algorithms. In this paper we survey how this analysis is done via a number of examples. We precede this catalogue of examples with short primers on both condition numbers and probabilistic analyses.

Type
Research Article
Information
Acta Numerica , Volume 25 , 01 May 2016 , pp. 321 - 382
Copyright
© Cambridge University Press, 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES1

Amelunxen, D. and Bürgisser, P. (2012), ‘Robust smoothed analysis of a condition number for linear programming’, Math. Program. 131, 221–251.Google Scholar
Armentano, D. (2010), ‘Stochastic perturbations and smooth condition numbers’, J. Complexity 26, 161–171.CrossRefGoogle Scholar
Armentano, D. (2014), ‘Complexity of path-following methods for the eigenvalue problem’, Found. Comput. Math. 14, 185–236.CrossRefGoogle Scholar
Armentano, D., Beltrán, C., Bürgisser, P., Cucker, F. and Shub, M. (2015a), ‘Condition length and complexity for the solution of polynomial systems’, accepted by J. Found. Comput. Math.Google Scholar
Armentano, D., Beltrán, C., Bürgisser, P., Cucker, F. and Shub, M. (2015b), A stable, polynomial-time algorithm for the eigenpair problem. Preprint. arXiv:1505.03290Google Scholar
Beltrán, C. and Pardo, L. (2009), ‘Smale’s 17th problem: average polynomial time to compute affine and projective solutions’, J. Amer. Math. Soc. 22, 363–385.CrossRefGoogle Scholar
Beltrán, C. and Pardo, L. (2011), ‘Fast linear homotopy to find approximate zeros of polynomial systems’, Found. Comput. Math. 11, 95–129.Google Scholar
Bürgisser, P. and Cucker, F. (2011), ‘On a problem posed by Steve Smale’, Ann. of Math. 174, 1785–1836.Google Scholar
Bürgisser, P. and Cucker, F. (2013), Condition, Vol. 349 of Grundlehren der Mathematischen Wissenschaften, Springer.Google Scholar
Bürgisser, P., Cucker, F. and Lotz, M. (2006), ‘Smoothed analysis of complex conic condition numbers’, J. Math. Pures Appl. 86, 293–309.CrossRefGoogle Scholar
Bürgisser, P., Cucker, F. and Lotz, M. (2008), ‘The probability that a slightly perturbed numerical analysis problem is difficult’, Math. Comp. 77, 1559–1583.Google Scholar
Bürgisser, P., Cucker, F. and Lotz, M. (2010), ‘Coverage processes on spheres and condition numbers for linear programming’, Ann. Probab. 38, 570–604.CrossRefGoogle Scholar
Cheung, D. and Cucker, F. (2004), ‘Solving linear programs with finite precision I: Condition numbers and random programs’, Math. Program. 99, 175–196.CrossRefGoogle Scholar
Cheung, D. and Cucker, F. (2005), ‘A note on level-2 condition numbers’, J. Complexity 21, 314–319.CrossRefGoogle Scholar
Cheung, D. and Cucker, F. (2006), ‘Solving linear programs with finite precision II: Algorithms’, J. Complexity 22, 305–335.Google Scholar
Cheung, D. and Cucker, F. (2013), ‘On the average condition of random linear programs’, SIAM J. Optim. 23, 799–810.Google Scholar
Cheung, D. and Cucker, F. (2015), ‘Smoothed analysis of componentwise condition numbers for sparse matrices’, IMA J. Numer. Anal. 35, 74–88.Google Scholar
Cucker, F. and Peña, J. (2002), ‘A primal–dual algorithm for solving polyhedral conic systems with a finite-precision machine’, SIAM J. Optim. 12, 522–554.CrossRefGoogle Scholar
Demmel, J. (1987), ‘On condition numbers and the distance to the nearest ill-posed problem’, Numer. Math. 51, 251–289.CrossRefGoogle Scholar
Demmel, J. (1988), ‘The probability that a numerical analysis problem is difficult’, Math. Comp. 50, 449–480.Google Scholar
Demmel, J. (1997), Appl. Numer. Linear Algebra, SIAM.CrossRefGoogle Scholar
Eckart, C. and Young, G. (1936), ‘The approximation of one matrix by another of lower rank’, Psychometrika 1, 211–218.Google Scholar
Edelman, A. (1988), ‘Eigenvalues and condition numbers of random matrices’, SIAM J. Matrix Anal. Appl. 9, 543–556.Google Scholar
Fletcher, R. (1985), ‘Expected conditioning’, IMA J. Numer. Anal. 5, 247–273.Google Scholar
Goldstine, H. and von Neumann, J. (1951), ‘Numerical inverting matrices of high order II’, Proc. Amer. Math. Soc. 2, 188–202.CrossRefGoogle Scholar
Hestenes, M. and Stiefel, E. (1952), ‘Methods of conjugate gradients for solving linear systems’, J. Res. Nat. Bur. Standards 49, 409–436.Google Scholar
Higham, N. (1989), ‘The accuracy of solutions to triangular systems’, SIAM J. Numer. Anal. 26, 1252–1265.Google Scholar
Higham, N. (1996), Accuracy and Stability of Numerical Algorithms, SIAM.Google Scholar
Caesar, Julius (Ed.) (1917), De Bello Gallico (with an English translation by H. J. Edwards), Harvard University Press.Google Scholar
Li, T.-Y. and Sauer, T. (1987), ‘Homotopy method for generalized eigenvalue problems $Ax={\it\lambda}Bx$’, Linear Algebra Appl. 91, 65–74.Google Scholar
Lotz, M. (2015), ‘On the volume of tubular neighborhoods of real algebraic varieties’, Proc. Amer. Math. Soc. 143, 1875–1889.Google Scholar
von Neumann, J. and Goldstine, H. (1947), ‘Numerical inverting matrices of high order’, Bull. Amer. Math. Soc. 53, 1021–1099.Google Scholar
Renegar, J. (1987), ‘On the worst case arithmetic complexity of approximating zeros of polynomials’, J. Complexity 3, 90–113.Google Scholar
Renegar, J. (1994a), ‘Is it possible to know a problem instance is ill-posed?’, J. Complexity 10, 1–56.CrossRefGoogle Scholar
Renegar, J. (1994b), ‘Some perturbation theory for linear programming’, Math. Program. 65, 73–91.CrossRefGoogle Scholar
Renegar, J. (1995a), ‘Incorporating condition measures into the complexity theory of linear programming’, SIAM J. Optim. 5, 506–524.Google Scholar
Renegar, J. (1995b), ‘Linear programming, complexity theory and elementary functional analysis’, Math. Program. 70, 279–351.Google Scholar
Renegar, J. (2000), A Mathematical View of Interior-Point Methods in Convex Optimization, SIAM.Google Scholar
Shub, M. (1993), Some remarks on Bézout’s theorem and complexity theory. In From Topology to Computation: Proceedings of the Smalefest (Hirsch, M., Marsden, J. and Shub, M., eds), Springer, pp. 443–455.Google Scholar
Smale, S. (1997), Complexity theory and numerical analysis. In Acta Numerica (Iserles, A., ed.), Vol. 6, Cambridge University Press, pp. 523–551.Google Scholar
Smale, S. (2000), Mathematical problems for the next century. In Mathematics: Frontiers and Perspectives (Arnold, V., Atiyah, M., Lax, P. and Mazur, B., eds), AMS, pp. 271–294.Google Scholar
Spielman, D. and Teng, S.-H. (2002), Smoothed analysis of algorithms. In Proceedings of the International Congress of Mathematicians,Vol. I, pp. 597–606.Google Scholar
Stewart, G. (1990), ‘Stochastic perturbation theory’, SIAM Rev. 32, 579–610.Google Scholar
Turing, A. (1948), ‘Rounding-off errors in matrix processes’, Quart. J. Mech. Appl. Math. 1, 287–308.Google Scholar
Van Loan, G. (1987), ‘On estimating the condition of eigenvalues and eigenvectors’, Linear Algebra Appl. 88–89, 715–732.Google Scholar
Viswanath, D. and Trefethen, L. (1998), ‘Condition numbers of random triangular matrices’, SIAM J. Matrix Anal. Appl. 19, 564–581.Google Scholar
Wedin, P.-Å (1973), ‘Perturbation theory for pseudo-inverses’, Nordisk Tidskr. Informationsbehandling (BIT) 13, 217–232.Google Scholar
Weiss, N., Wasilkowski, G., Woźniakowski, H. and Shub, M. (1986), ‘Average condition number for solving linear equations’, Linear Algebra Appl. 83, 79–102.Google Scholar
Wilkinson, J. (1963), Rounding Errors in Algebraic Processes, Prentice Hall.Google Scholar
Wilkinson, J. (1971), ‘Some comments from a numerical analyst’, J. Assoc. Comput. Mach. 18, 137–147.Google Scholar
Wschebor, M. (2004), ‘Smoothed analysis of ${\it\kappa}(a)$’, J. Complexity 20, 97–107.Google Scholar