School Organizers :

Speakers

Carlos Beltrán,
Depto. Matemáticas, Estadística y Computación, Universidad de Cantabria.
Marc Giusti ,
CNRS, Laboratoire LIX, École Polytechnique, France.
Joos Heintz,
Depto. Matemáticas, Estadística y Computación, Universidad de Cantabria.
Gegorio Malajovich,
Depto. de Matemática Aplicada, Instituto de Matemática , Universidade Federal do Rio de Janeiro.
Klaus Meer,
Institut für Informatik, , Brandenburgisch Technische Universitát Cottbus.
Michael Shub,
IMAS, , CONICET, Universidad de Buenos Aires and CUNY Graduate School.
Jean-Claude Yakoubsohn,
Institut de Mathématiques de Toulouse, , Université Paul Sabatier, Toulouse.

Carlos Beltrán, "Stability, precision and complexity in some numerical problems".

Nowadays computers can solve extremely complicated problems for real life applications, but often the implemented methods are not fully understood: the quality of the answer (in terms, for example, of number of correct digits) and the time required by the algorithms to run are two particularly important questions that modern Mathematics try to understand. In this these talks we will summarise many of the known results concerning these problems in the context of numerical linear algebra and in the context of numerically solving systems of polynomial equations. The deep connection between these two problems yields a solution to Smale's 17th problem using an Average Las Vegas algorithm. We will discuss this algorithm, its deterministic version and related questions. This is based on several joint works with Luis M. Pardo, M. Shub and A. Leykin.

Marc Giusti, "Polar, co-polar and bipolar varieties: real solving of algebraic varieties with intrinsic complexity".

This survey covers a decade and a half of joint work with Bernd Bank, Joos Heintz, Lutz Lehmann, Guy Mbakop, and Luis M. Pardo. We address the problem of finding a smooth algebraic sample point for each connected component of an algebraic variety, being only interested in components which are generically smooth locally complete intersections. The complexity of our algorithms is essentially polynomial in the degree of suitably defined polar varieties, leading to an intrinsic behavior. Starting from our first work on compact smooth real hyper--surfaces, I will describe how we dropped successively the hypotheses on codimension, compactness and eventually smoothness. This goes through generalizations of classical polar varieties.

Joos Heintz, "On the intrinsic complexity of elimination problems in effective algebraic geometry".

After a short review of the early history of elimination theory and algorithms in the nineteenth century, starting with Kronecker´s elimination method, we shall introduce an arithmetic circuit based computation model which captures all known symbolic and semi--numeric elimination algorithms in effective algebraic geometry. This model becomes justified and motivated by considerations stemming from software engineering. Finally we exhibit an infinite sequence of simple elimination problems whose associated elimination polynomials require for their evaluation exponential size circuits in our computation model.

Gregorio Malajovich, "From the quadratic convergence of Newton's method to problems of counting of the number of solutions".

The first lecture will be a review on Smale's criteria for quadratic convergence of Newton iteration. Those allow for an effective and rigorous definition of approximate solution for a system of polynomial equations. The second lecture is on applications of those methods to complexity theory. For instance, we consider the problem of counting the number of real zeros of a system of polynomial equations. This is known to be #P-complete. However, we will give a complexity bound in terms of a condition number. This will lead to average or probabilistic complexity results, through a geometrical interpretation of average conditioning in terms of smoothed analysis.

Klaus Meer, "Real Number Complexity Theory and Probabilistically Checkable Proofs (PCP's) ".

In this series of talks we first want to give an introduction to real number complexity theory as introduced by Blum, Shub, and Smale. The focus will be on structural real complexity theory. In a second talk we survey a milestone of classical complexity theory, namely the PCP Theorem for the Turing model shown in the early 1990's by Arora et al. The final part of the lectures will concentrate on own work dealing with PCP's for real number complexity classes.

Michael Shub, "The geometry of condition and the analysis of algorithms".

The condition number of a numerical problem measures the sensitivity of the output to perturbation of the input. The condition determines a geometry which in the case of the solution of systems of polynomial equations and homotopy methods determines the most efficient paths of solutions, namely the geodesics of the geometry. In these talks we will study the topology of the solution variety , the geometry imposed by the condition Hermitian structure and as time permits how condition may intervene in more general classes of problems. This is joint work with Carlos Beltrán, Jean-Pierre Dedieu and Gregorio Malajovich.

Jean-Claude Yakoubsohn, "Tracking multiplicities".

Let us consider an analytic system of equations. It is well known the quadratic convergence of Newton method is lost in the neighborhood of an isolated multiple root. We purpose an algorithm to exhibit a regular system determined from the initial. The idea is to add equations keeping the same number of variables. To do that we use numerical evaluations to determine the equations we need to add. The number of step of this algorithm is bounded by the multiplicity of the root.