\documentclass[12pt]{amsart} \usepackage{amssymb, amsmath} \usepackage[author-year]{amsrefs} \usepackage[utf8]{inputenc} \newcommand{\Hd}{\mathcal H_{\mathbf d}} \newcommand{\dd}{\mathrm d} \newcommand{\tr}{\mathrm {tr}} \newcommand{\ev}{\mathrm {ev}} \newcommand{\sigmin}{\sigma_{\mathrm {min}}} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{openproblem}[theorem]{Open Problem} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \author{Gregorio Malajovich} \address{ Departamento de Matemática Aplicada, Instituto de Matemática, Universidade Federal do Rio de Janeiro. Av. Athos da Silveira Ramos 149, Centro de Tecnologia - Bloco C Cidade Universitária - Ilha do Fundão. Caixa Postal 68530 21941-909 Rio de Janeiro - RJ - Brasil } \email{gregorio.malajovich@gmail.com} \thanks{Talk at the Fields Institute, on the occasion of the Workshop {\em From Dynamics to Complexity: A conference celebrating the work of Mike Shub.}} \thanks{Partially supported by CNPq and CAPES (Brazil), by MathAmSud grant {\em Complexity}. Part of the work was done while visiting the Fields institute.} \title{Condition metric, self-convexity and Smale's 17th problem} \date{May 11,2012} \begin{document} \maketitle \begin{abstract} I will focus on recent developments about the condition metric in the solution variety for systems of homogeneous polynomial equations. First I will review the basic algebraic-geometric construction of the solution variety and the condition number, and explain what is the condition metric. Then I will explain how the complexity of path-following can be bounded in terms of the condition-metric of the path. This will suggest a geometric version for Smale's 17-th problem: finding short homotopy paths. As a tentative to understand the condition metric, we studied the linear case: systems of polynomials of degree 1. In this context, the logarithm of the condition number is convex along geodesics. This self-convexity property is conjectured to be true for higher degrees. (This is joint work with Carlos Beltrán, Jean-Pierre Dedieu and Mike Shub). \end{abstract} \tableofcontents \section{What is self-convexity} Through this talk, $(\mathcal M, \langle \cdot,\cdot \rangle_x)$ is always a {\bf smooth} Riemannian manifold and $\alpha: \mathcal M \rightarrow \mathbb R_{>0}$ is a {\bf Lipschitz} function. We can endow the manifold $M$ with a new metric, namely \[ \langle \cdot , \cdot \rangle'_x = \alpha(x) \langle \cdot , \cdot \rangle_x \] which is conformally equivalent to the previous one. This new norm will be called the {\bf $\alpha$-metric} and sometimes the {\bf condition metric}. It defines a {\bf Riemann- Lipschitz} structure on $\mathcal M$. \begin{definition} We say that $\alpha$ is {\bf self-convex} if and only if, for any {\bf geodesic} $\gamma$ in the $\alpha$-structure, $t \mapsto \log \alpha(\gamma(t))$ is a convex function. \end{definition} This definition makes sense when $\alpha$ is of class $\mathcal C^1$ so that the geodesic differential equation has a solution. When $\alpha$ is merely Lipschitz, a {\bf geodesic} is a locally minimizing absolutely continuous ($C^{1+\mathrm{Lip}}=W^{2,\infty}$) path, parametrized by arc length a.e. (For a discussion, see \ocite{BD10} and \fullocite{BDMS2}). \section{Known examples of self-convexity} \begin{theorem}\label{li-niremberg} Let $C \subset \mathbb R^n$ a (closed) convex body. Let $\mathcal M=(\mathbb R^n \setminus C$ and let $\alpha:\mathbf x \mapsto d(\mathbf x,C)^{-2}$. Then $\alpha$ is self-convex. \end{theorem} \begin{theorem}[\fullocite{BDMS1}, Th.2] Let $N \subset \mathbb R^m$ be an embedded submanifold (without border of course). Let $\mathcal M$ be the largest open set in $\mathbb R^m \setminus N$ such that every point of $\mathcal M$ has a unique closest point in $N$. Let $\alpha: \mathbf x \mapsto d(\mathbf x,\mathcal N)^{-2}$. Then $\alpha$ is self-convex. \end{theorem} Theorem~\ref{li-niremberg} follows immediately from \ocite{Li-Niremberg} and the result above. \begin{theorem}[\fullocite{BDMS2}, Th.1] Let $\mathbb K= \mathbb R$ or $\mathbb C$. Let $L(m,n) = \mathbb K^{m \times n}$ where we assume that $m \ge n$, endowed with the trace inner product, and let $M=L(m,n) \setminus \{A: \mathrm{Rank}(A) < n\}$. Let $\alpha: A \mapsto \|(A^* A)^{-1}\|$. Then $\alpha$ is self-convex. \end{theorem} More examples are known, and also some counterexamples \cite{BDMS1,BDMS2}. Since proofs can get extremely technical, I will not attempt to sketch any argument. Instead, I intend to explain in the rest of the talk why are we investigating such issues. Our main motivation is Smale's 17-th problem. This is a long story, that started with the {\bf B\'ezout saga} \cites{Bezout1,Bezout2,Bezout3,Bezout4,Bezout5,Bezout6,Bezout7}. As this is a conference in honor of Mike Shub, it would be appropriate to tell this story. However, I will spoil it: after introducing the basic language, I will tell the end. \section{The algebra} Let $\mathcal H_d$ be the space of complex homogeneous polynomials of degree $d$, in $n$ variables. There are many standard ways to represent polynomials, here are two: \[ F(\mathbf X) = \sum_{\sum \mathbf a_i=d} F_{\mathbf a} X_1^{a_1} X_2^{a_2} \cdots X_n^{a_n} = \sum_{0 \le j_1,\dots, j_d \le n} S_{\mathbf j} X_{j_1} X_{j_2} \dots X_{j_n} . \] In the last representation, we assume that the $S_{\mathbf j}$ are coefficients of a symmetric $d$-contravariant tensor $S(\mathbf X,\mathbf Y, \dots, \mathbf Z)$ and $F(\mathbf X) = S(\mathbf X, \dots, \mathbf X)$. The quantity \[ \|\mathbf S\|^2 = \sum_{0 \le j_1,\dots, j_d \le n} |S_{\mathbf j}|^2 \] is invariant by unitary rotations. This is actually an exercise in my book \cite{NONLINEAR-EQUATIONS}. The corresponding norm in the polynomial representation \[ \|\mathbf F\|^2 =\sum_{\sum a_i=d} {|F_{\mathbf a}|^2}\frac{a_1! \dots a_n!}{d!} \] is known as the {\bf Weyl} norm or sometimes {\bf Bombieri} norm. Both come with an inner product. This is the inner product $\mathcal H_d$ is endowed with. Moreover, $\mathcal H_d$ is a {\bf reproducing kernel space}. If $K_{d}(\mathbf X,\mathbf Y) = \langle \mathbf X,\mathbf Y \rangle^d$ then \[ F(\mathbf Y) = \langle F(\cdot), K_d(\cdot, \mathbf Y) \rangle . \] If $\mathbf d=(d_1,\dots, d_n)$, the space of systems of polynomials \[ \Hd = \mathcal H_{d_1} \times \cdots \times \mathcal H_{d_n} \] is also endowed with the unitarily invariant, product space inner product. \section{The algebraic geometry} \par The {\em solution variety} is the set of pairs (problem, solution). Formally, \[ \mathcal V = \left\{ (\mathbf f,\mathbf x) \in \mathbb P(\Hd) \times \mathbb P^n: \mathbf f(\mathbf x)=0 \right\} . \] This compactification is not {\bf always} necessary, but it is extremely convenient. Through this talk I follow the convention that vectors are upper case ($\mathbf X$) and the corresponding projective points are lower case ($\mathbf x$). Let $\ev(\mathbf F,\mathbf X)$ denote the evaluation of $\mathbf F$ at $\mathbf X$, \[ \ev(\mathbf F,\mathbf X) = \left[ \begin{matrix} F_1(\mathbf X) \\ \vdots \\ F_n(\mathbf X) \end{matrix} \right] = \left[ \begin{matrix} \langle F_1(\cdot), K_{d_1}(\cdot, \mathbf X) \rangle\\ \vdots \\ \langle F_n(\cdot), K_{d_n}(\cdot, \mathbf X) \rangle\\ \end{matrix} \right] \] The $i$-th coordinate of the evaluation function is a polynomial in $F \in \mathcal H_{d_i}$ and $\mathbf X \in \mathbb C^n$, and it is an easy exercise to show that $D\ev(\mathbf F,\mathbf X)$ is surjective. Thus $\mathcal V$ is a smooth algebraic variety. Consider now the two canonical projections \[ \pi_1: \mathcal V \rightarrow \mathbb P(\Hd) \hspace{2em} \text{and} \hspace{2em} \pi_2: \mathcal V \rightarrow \mathbb P^n \] Let $\Sigma$ be the set of critical values of $\pi_1$. It follows from Sard's theorem that $\Sigma$ has measure zero, and from elimination theory that $\Sigma$ is an algebraic set. Moreover, $\pi_1$ is onto. Therefore, for {\bf generic} $\mathbf F_0$ and $\mathbf F_1$, the complex line \[ (1-t) \mathbf F_0 + t \mathbf F_1 \] cuts $\Sigma$ in finitely many (complex) values of $t$. Therefore if we require $t\in[0,1]$, the event of $(\mathbf F_t)_{t \in [0,1]}$ hitting $\Sigma$ has probability zero. Therefore the lifting theorem applies and can be used to solve polynomial systems. This is where the B\'ezout saga begins. \section{The calculus} Assume that $(\mathbf F_0, \mathbf X_0) \in \mathcal V$, $\mathbf F_0 \not \in \Sigma$. Then we are under the hypotheses of the implicit function theorem: there are $\delta>0$ and a function $G:B(f_0,\delta) \rightarrow \mathbb P^n$ such that \begin{eqnarray*} \ev(\mathbf F,G(\mathbf F)) &\equiv& 0 \\ G(\mathbf F_0) &=& \mathbf X_0 \end{eqnarray*} In order to design path-following algorithms, it is important to give bounds for $\delta$. In the early B\'ezout saga, this was ultimately done in terms of condition numbers. There are two current definitions of the condition number. The {\bf unnormalized condition number} measures the sensitivity of the (projectivized) solution $\mathbf x$ to the (projectivized) input $\mathbf f$. It is defined as $ \| DG(\mathbf f,\mathbf x) \|$, where the operator norm of $DG(\mathbf f,\mathbf x): T_f\mathbb P(\Hd) \rightarrow T_x\mathbb P^ n$ is assumed. \begin{lemma} In the context above, let $F \in \Hd$, $X \in \mathbb C^ {n+1}$ be representatives of $(\mathbf f,\mathbf x) \in \mathcal V$. \begin{equation}\label{eq-cond} \| DG(\mathbf f,\mathbf x) \| = \|\mathbf F\| \left\| \left( \left[ \begin{matrix} \|\mathbf X\|^{-d_1+1} \\ \ddots \\ \|\mathbf X\|^{-d_n+1} \\ \end{matrix} \right] D\mathbf F(\mathbf X)_{\mathbf X^{\perp}} \right) ^{-1} \right\| \end{equation} (Again, operator norm is assumed). \end{lemma} \begin{proof} We first differentiate $G$. Let $(\mathbf F_t, \mathbf X_t)$ be a smooth path. Differentiating $\mathbf F_t(\mathbf X_t) \equiv 0$, one gets \[ D\mathbf F_t(\mathbf X_t) \dot {\mathbf X}_t + \dot {\mathbf F}_t(\mathbf X_t) = 0 \] Therefore, \[ DG(\mathbf X_t): \dot {\mathbf F} \rightarrow -D\mathbf F_t(\mathbf X_t)^{-1} \left[ \begin{matrix} K_{d_1} (\cdot, \mathbf X_t)^* \\ & \ddots \\ & & K_{d_n} (\cdot, \mathbf X_t)^* \\ \end{matrix} \right] \dot {\mathbf F} \] The condition number and the right hand side of \eqref{eq-mu} are invariant by scalings in $\Hd$, in $\mathbb C^ {n+1}$ and also by unitary action $(\mathbf f,\mathbf x) \mapsto (\mathbf f \circ U^*, U \mathbf x)$. Therefore we can assume without loss of generality that $\|\mathbf F\|=1$ and that $\mathbf X = \mathrm e_0$. Calculations are immediate. \end{proof} Shub and Smale introduced the {\bf normalized condition number} \[ \mu(\mathbf f,\mathbf x)= \|\mathbf F\| \left\| \left( \left[ \begin{matrix} d_1^{-1/2} \|\mathbf X\|^{-d_1+1} \\ \ddots \\ d_n^{-1/2} \|\mathbf X\|^{-d_n+1} \\ \end{matrix} \right] D\mathbf F(\mathbf X)_{\mathbf X^{\perp}} \right) ^{-1} \right\| . \] The operator $\Hd \mapsto \mathcal H_{(1,\cdots,1)}$ given by \[ \mathbf F \mapsto \left[ \begin{matrix} d_1^{-1/2} \|\mathbf X\|^{-d_1+1} \\ \ddots \\ d_n^{-1/2} \|\mathbf X\|^{-d_n+1} \\ \end{matrix} \right] D\mathbf F(\mathbf X)_{\mathbf X^{\perp}} \] is an isometric projection. This definition makes the condition theorem true: \begin{theorem}\cite{Bezout1} The condition number $\mu(f,x)$ equal to the reciprocal of the distance of $f$ to the discriminant variety $\Sigma$ along the fiber of systems vanishing at $x$. \end{theorem} (See~\ocite{Bezout1} or \ocite{BCSS} for the original version and ~\ocite{NONLINEAR-EQUATIONS} for generalizations). Notice that \[ \| DG(\mathbf f,\mathbf x) \| \le \mu(\mathbf f,\mathbf x) \le \sqrt{\max d_i} \| DG(\mathbf f,\mathbf x) \| \] \section{The numerical analysis} One of the main results of the early B\'ezout saga was a family of path-following methods, with number of homotopy steps of \[ \mathcal O\left(d(\mathbf f_0, \mathbf f_1) \max_{t\in [0,1]} \mu(\mathbf f_t,\mathbf x_t)^2 \ dt \right). \] The general procedure was of the form: \begin{equation}\label{homotopy} \mathbf x_{i+1} = N( \mathbf f_{t_{i+1}}, \mathbf x_{t_i}) \end{equation} where $N$ denotes certain Newton iteration in projective space. I must say now what is an approximate zero. Let $d(\mathbf x,\mathbf y)=\min \|\mathbf X-\lambda \mathbf Y\|/\|\mathbf X\|$ be the projective metric in projective space, that is the sine of the Riemannian distance. \begin{definition}[Smale] An {\bf approximate zero} for $\mathbf F \in \Hd$ is a point $0 \ne \mathbf Y \in \mathbb C^{n+1}$ so that the sequence $\mathbf y_{i+1}=N(\mathbf f,\mathbf y_i)$ satisfies \[ d(\mathbf y_i, \mathbf y_{i+1}) \le 2^{-2^i+1} d(\mathbf y_0,\mathbf y_1) . \] \end{definition} It turns out that approximate zeros exist~\cite{Smale-PE} and can be numerically certified through Smale' s {\bf alpha theory}. (Again see my book, ~\ocite{NONLINEAR-EQUATIONS}). The outcome of ~\ocite{Bezout5} is that for every $\Hd$, there is a pair $(\mathbf F_0, \mathbf X_0)$ such that, for every $\mathbf F_1$, there is a sequence $t_i$, so that \eqref{homotopy} produces $t_N = 1$ and $\mathbf X_N$ so that $\mathbf X_N$ is an {\bf approximate zero} for $\mathbf F_1$. The following problems where left mostly open. \begin{enumerate} \item How to find a good starting pair $(\mathbf F_0, \mathbf X_0)$. \item How to generate the sequence of $t_i$'s. \end{enumerate} \section{Smale's 17-th problem} \begin{openproblem}\cite{Smale-next-century}\label{Smale17} \em Can a zero of $n$ complex polynomial equations in $n$ unknowns be found approximately , on the average, in polynomial time with a uniform algorithm? \end{openproblem} All the terms above are technical. Here is my translation: \medskip {\em Does there exist a deterministic algorithm $M$ (BSS machine over $\mathbb R$ or a similar model) with input $(n \in \mathbb N,d_1 \in \mathbb N, \dots, d_n \in \mathbb N, \mathbf F \in \Hd)$ producing $\mathbf X \in \mathbb C^{n+1}\setminus\{0\}$ so that \begin{enumerate} \item $\mathbf x$ is an approximate zero for $\mathbf f$, and \item There is a polynomial $p$ such that for any fixed $\mathbf d$, \[ \mathrm{AVG}_{\mathbf F \in N(0,1; \Hd)} R(\mathbf d,\mathbf F) \le p(\dim(\Hd)) \] where $R(\mathbf d,\mathbf F)$ is the running time of $M$ with input $\mathbf F$? \end{enumerate} } Two major advances in this subject are a polynomial time {\bf randomized} algorithm ~\cite{Beltran-Pardo} and a deterministic algorithm ~\cite{Buergisser-Cucker} that runs in time \[ (\dim \Hd)^{\log \log \dim \Hd} . \] \section{The fast homotopy} Most path-lifting homotopy algorithms until now prescribed an upper bound for the time mesh $t_{i+1}-t_i$. In~\fullocite{DMS}, we constructed an algorithm with a lower bound for the time mesh, in terms of a certain integral. (The existence of that time mesh appeared in~\ocite{Bezout6}, and another algorithm can be found in~\ocite{Beltran-homotopia}. The algorithm in~\ocite{DMS} performs path-lifting in at most \[ 1+ 0.65 (\max d_i)^{3/2} \epsilon^{-2} \mathcal L(\mathbf f_t,\mathbf x_t;0,1) \] homotopy steps, where \begin{equation} \int_0^1 \mu(f_t,z_t) \left( \|\dot {\mathbf f}_t\|_{\mathbf f_t} + \|\dot {\mathbf x}_t\|_{\mathbf x_t} \right) \end{equation} The algorithm is robust, and the accuracy parameter $\epsilon$ allows for approximate computations. This is where the idea of the $\alpha$-structure comes from. \section{Geometric forms of Smale's 17-th problem} Let $\alpha(\mathbf f,\mathbf x) = \mu(\mathbf f,\mathbf x)^ 2$ and let $M = \{ (\mathbf f,\mathbf x) \in V: \alpha(\mathbf f,\mathbf x) < \infty$. \begin{conjecture} $\alpha$ is self-convex in $M$. \end{conjecture} In particular, $\mu$ would be convex along the geodesics of the $\alpha$-structure. The maximum of $\mu$ along a geodesic would be found at an extremity. Moreover, a short geodesic (in the condition-structure) between an arbitrary $(\mathbf f,\mathbf x)$ and a global minimum for $\mu$ is guaranteed to exist~\cite{Bezout7}. At this time we do not know how to approximate such a geodesic in polynomial time. Here is a possible approach for Smale's 17-th problem. {\em For every $f \in \mathbb P(\Hd)$, produce a {\bf path} $f_t \in \mathbb P(\Hd)$ with $f_1=f$, and produce $\mathbf z_0 \in \mathbb P^n$ so that the $\alpha$-length of the lifting of $\mathbf f_t$ passing through $(\mathbf f_0,\mathbf z_0)$ is $\le \dim(\Hd)^k$ (where $k$ must be a universal constant).} The most technical algorithmic issues are gone. What we have above is a geometrical or variational problem. \medskip \noindent HAPPY MAY'68, MIKE! \begin{bibsection} \begin{biblist} \bib{Beltran-homotopia}{article}{ author={Beltr{\'a}n, Carlos}, title={A continuation method to solve polynomial systems and its complexity}, journal={Numer. Math.}, volume={117}, date={2011}, number={1}, pages={89--113}, issn={0029-599X}, review={\MR{2754220}}, doi={10.1007/s00211-010-0334-3}, } \bib{Beltran-homotopia}{article}{ author={Beltr{\'a}n, Carlos}, title={A continuation method to solve polynomial systems and its complexity}, journal={Numer. Math.}, volume={117}, date={2011}, number={1}, pages={89--113}, issn={0029-599X}, review={\MR{2754220}}, doi={10.1007/s00211-010-0334-3}, } \bib{BDMS1}{article}{ author = {Beltrán, Carlos}, author = {Dedieu,Jean-Pierre}, author = {Malajovich, Gregorio}, author = {Shub, Mike}, title = {Convexity properties of the condition number}, journal = {SIAM Journal on Matrix Analysis and Applications}, volume = {31}, number = {3}, pages = {1491-1506}, year = {2010}, doi = {10.1137/080718681}} \bib{BDMS2}{article}{ author = {Beltrán, Carlos}, author = {Dedieu,Jean-Pierre}, author = {Malajovich, Gregorio}, author = {Shub, Mike}, journal={SIAM J. on Matrix Analysis}, year={TA}, title = {Convexity properties of the condition number}, note = {Preprint, ArXiV, 30 oct 2009, \url{http://arxiv.org/abs/0910.5936}}} \bib{BeltranLeykin2009}{article}{ author = {Beltrán,Carlos}, author = {Leykin,Anton}, title = {Certified numerical homotopy tracking}, note = {Preprint, ArXiV, \url{http://arxiv.org/abs/0912.0920}}, date = {30 oct 2009}} \bib{Beltran-Pardo}{article}{ author = {Beltrán, Carlos}, author = {Pardo, Luis Miguel}, title = {Fast linear homotopy to find approximate zeros of polynomial systems}, journal={Foundations of Computational Mathematics}, volume={11}, pages={95--129}, year={2011}} \bib{Bezout7}{article}{ author={Beltr{\'a}n, Carlos}, author={Shub, Michael}, title={Complexity of Bezout's theorem. VII. Distance estimates in the condition metric}, journal={Found. Comput. Math.}, volume={9}, date={2009}, number={2}, pages={179--195}, issn={1615-3375}, review={\MR{2496559 (2010f:65100)}}, doi={10.1007/s10208-007-9018-5}, } \bib{BeltranShub-topology}{article}{ author={Beltr{\'a}n, Carlos}, author={Shub, Michael}, title={On the geometry and topology of the solution variety for polynomial system solving}, note={to appear} } \bib{BCSS}{book}{ author={Blum, Lenore}, author={Cucker, Felipe}, author={Shub, Michael}, author={Smale, Steve}, title={Complexity and real computation}, note={With a foreword by Richard M. Karp}, publisher={Springer-Verlag}, place={New York}, date={1998}, pages={xvi+453}, isbn={0-387-98281-7}, review={\MR{1479636 (99a:68070)}}, } \bib{BD10}{article}{ author={Boito, Paola}, author={Dedieu, Jean-Pierre}, title={The condition metric in the space of rectangular full rank matrices}, journal={SIAM J. Matrix Anal. Appl.}, volume={31}, date={2010}, number={5}, pages={2580--2602}, issn={0895-4798}, review={\MR{2740622}}, doi={10.1137/08073874X}, } \bib{Buergisser-Cucker}{article}{ author={B{\"u}rgisser, Peter}, author={Cucker, Felipe}, title={On a problem posed by Steve Smale}, journal={Ann. of Math. (2)}, volume={174}, date={2011}, number={3}, pages={1785--1836}, issn={0003-486X}, review={\MR{2846491}}, doi={10.4007/annals.2011.174.3.8}, } \bib{DMS}{article}{ author = {Dedieu,Jean-Pierre}, author = {Malajovich, Gregorio}, author = {Shub, Mike}, title = {Adaptative Step Size Selection for Homotopy Methods to Solve Polynomial Equations}, journal={IMA J. on Numerical Analysis}, date={to appear}, note = {Preprint, ArXiV, 11 apr 2011, \url{http://arxiv.org/abs/1104.2084}}, } \bib{Li-Niremberg}{article}{ author={Li, Yanyan}, author={Nirenberg, Louis}, title={Regularity of the distance function to the boundary}, journal={Rend. Accad. Naz. Sci. XL Mem. Mat. Appl. (5)}, volume={29}, date={2005}, pages={257--264}, issn={0392-4106}, review={\MR{2305073 (2008d:35021)}}, } \bib{NONLINEAR-EQUATIONS}{book}{ author={Malajovich, Gregorio}, title={Nonlinear equations}, series={Publica\c c\~oes Matem\'aticas do IMPA. [IMPA Mathematical Publications]}, note={With an appendix by Carlos Beltr\'an, Jean-Pierre Dedieu, Luis Miguel Pardo and Mike Shub; 28$^{\rm o}$ Col\'oquio Brasileiro de Matem\'atica. [28th Brazilian Mathematics Colloquium]}, publisher={Instituto Nacional de Matem\'atica Pura e Aplicada (IMPA), Rio de Janeiro}, date={2011}, pages={xiv+177}, isbn={978-85-244-0329-3}, review={\MR{2798351}}, } \bib{Bezout6}{article}{ author={Shub, Michael}, title={Complexity of Bezout's theorem. VI. Geodesics in the condition (number) metric}, journal={Found. Comput. Math.}, volume={9}, date={2009}, number={2}, pages={171--178}, issn={1615-3375}, review={\MR{2496558 (2010f:65103)}}, doi={10.1007/s10208-007-9017-6}, } \bib{Bezout1}{article}{ author={Shub, Michael}, author={Smale, Steve}, title={Complexity of B\'ezout's theorem. I. Geometric aspects}, journal={J. Amer. Math. Soc.}, volume={6}, date={1993}, number={2}, pages={459--501}, issn={0894-0347}, review={\MR{1175980 (93k:65045)}}, doi={10.2307/2152805}, } \bib{Bezout2}{article}{ author={Shub, M.}, author={Smale, S.}, title={Complexity of Bezout's theorem. II. Volumes and probabilities}, conference={ title={Computational algebraic geometry}, address={Nice}, date={1992}, }, book={ series={Progr. Math.}, volume={109}, publisher={Birkh\"auser Boston}, place={Boston, MA}, }, date={1993}, pages={267--285}, review={\MR{1230872 (94m:68086)}}, } \bib{Bezout3}{article}{ author={Shub, Michael}, author={Smale, Steve}, title={Complexity of Bezout's theorem. III. Condition number and packing}, note={Festschrift for Joseph F. Traub, Part I}, journal={J. Complexity}, volume={9}, date={1993}, number={1}, pages={4--14}, issn={0885-064X}, review={\MR{1213484 (94g:65152)}}, doi={10.1006/jcom.1993.1002}, } \bib{Bezout4}{article}{ author={Shub, Michael}, author={Smale, Steve}, title={Complexity of Bezout's theorem. IV. Probability of success; extensions}, journal={SIAM J. Numer. Anal.}, volume={33}, date={1996}, number={1}, pages={128--148}, issn={0036-1429}, review={\MR{1377247 (97k:65310)}}, doi={10.1137/0733008}, } \bib{Bezout5}{article}{ author={Shub, M.}, author={Smale, S.}, title={Complexity of Bezout's theorem. V. Polynomial time}, note={Selected papers of the Workshop on Continuous Algorithms and Complexity (Barcelona, 1993)}, journal={Theoret. Comput. Sci.}, volume={133}, date={1994}, number={1}, pages={141--164}, issn={0304-3975}, review={\MR{1294430 (96d:65091)}}, doi={10.1016/0304-3975(94)90122-8}, } \bib{Smale-PE}{article}{ author={Smale, Steve}, title={Newton's method estimates from data at one point}, conference={ title={ computational mathematics}, address={Laramie, Wyo.}, date={1985}, }, book={ publisher={Springer}, place={New York}, }, date={1986}, pages={185--196}, review={\MR{870648 (88e:65076)}}, } \bib{Smale-next-century}{article}{ author={Smale, Steve}, title={Mathematical problems for the next century}, journal={Math. Intelligencer}, volume={20}, date={1998}, number={2}, pages={7--15}, issn={0343-6993}, review={\MR{1631413 (99h:01033)}}, doi={10.1007/BF03025291}, } \end{biblist} \end{bibsection} \end{document}