English
Condition: the geometry of numerical algorithms - Lecture 1
Post-edited
Auteurs : Bürgisser, Peter (Auteur de la conférence)
CIRM (Editeur )
15A12 - Conditioning of matrices
65F10 - Iterative methods for linear systems
65F35 - Matrix norms, conditioning, scaling (numerical linear algebra)
65H10 - Systems of equations
65K05 - Mathematical programming methods
68Q15 - Complexity classes (hierarchies, relations among complexity classes, etc.)
90C51 - Interior-point methods
CIRM (Editeur )
Résumé :
The performance of numerical algorithms, both regarding stability and complexity, can be understood in a unified way in terms of condition numbers. This requires to identify the appropriate geometric settings and to characterize condition in geometric ways.
A probabilistic analysis of numerical algorithms can be reduced to a corresponding analysis of condition numbers, which leads to fascinating problems of geometric probability and integral geometry. The most well known example is Smale's 17th problem, which asks to find a solution of a given system of n complex homogeneous polynomial equations in $n$ + 1 unknowns. This problem can be solved in average (and even smoothed) polynomial time.
In the course we will explain the concepts necessary to state and solve Smale's 17th problem. We also show how these ideas lead to new numerical algorithms for computing eigenpairs of matrices that provably run in average polynomial time. Making these algorithms more efficient or adapting them to structured settings are challenging and rewarding research problems. We intend to address some of these issues at the end of the course.
Codes MSC : A probabilistic analysis of numerical algorithms can be reduced to a corresponding analysis of condition numbers, which leads to fascinating problems of geometric probability and integral geometry. The most well known example is Smale's 17th problem, which asks to find a solution of a given system of n complex homogeneous polynomial equations in $n$ + 1 unknowns. This problem can be solved in average (and even smoothed) polynomial time.
In the course we will explain the concepts necessary to state and solve Smale's 17th problem. We also show how these ideas lead to new numerical algorithms for computing eigenpairs of matrices that provably run in average polynomial time. Making these algorithms more efficient or adapting them to structured settings are challenging and rewarding research problems. We intend to address some of these issues at the end of the course.
15A12 - Conditioning of matrices
65F10 - Iterative methods for linear systems
65F35 - Matrix norms, conditioning, scaling (numerical linear algebra)
65H10 - Systems of equations
65K05 - Mathematical programming methods
68Q15 - Complexity classes (hierarchies, relations among complexity classes, etc.)
90C51 - Interior-point methods
|
Informations sur la Vidéo
Réalisateur : Hennenfent, GuillaumeLangue : Anglais Date de Publication : 26/01/2017 Date de Captation : 16/01/2017 Collection : Exposés de recherche Sous Collection : Research talks Catégorie arXiv : Numerical Analysis ; Computer Science Domaine(s) : Informatique ; Analyse Numérique & Calcul Formel Format : MP4 (.mp4) - HD Durée : 01:32:36 Audience : Chercheurs Download : https://videos.cirm-math.fr/2017-01-16_Burgisser_part1.mp4 
|
Informations sur la Rencontre
Nom de la Rencontre : French computer algebra days / JNCF - Journées nationales de calcul formelOrganisateurs de la Rencontre : Brisebarre, Nicolas ; El Bacha, Carole ; Giorgi, Pascal ; Mezzarobba, Marc ; Moroz, Guillaume Dates : 16/01/17 - 20/01/17 Année de la rencontre : 2017 URL de la Rencontre : http://conferences.cirm-math.fr/1584.html
Données de citation
DOI : 10.24350/CIRM.V.19110103Citer cette vidéo: Bürgisser, Peter (2017). Condition: the geometry of numerical algorithms - Lecture 1. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.19110103 URI : http://dx.doi.org/10.24350/CIRM.V.19110103 |
Voir Aussi
- [Multi angle] Condition: the geometry of numerical algorithms - Lecture 2 / Auteur de la conférence Bürgisser, Peter.
Bibliographie
- Bürgisser, P., Cucker, F. (2013). Condition. The geometry of numerical algorithms. Berlin: Springer - http://dx.doi.org/10.1007/978-3-642-38896-5
