In this work, we propose and study an Asynchronous parallel Greedy Coordinate Descent (Asy-GCD) algorithm for minimizing a smooth function with bounded constraints. At each iteration, workers asynchronously conduct greedy coordinate descent updates on a block of variables. In the first part of the paper, we analyze the theoretical behavior of Asy-GCD and prove a linear convergence rate. In the second part, we develop an efficient kernel SVM solver based on Asy-GCD in the shared memory multi-core setting. Since our algorithm is fully asynchronous—each core does not need to idle and wait for the other cores—the resulting algorithm enjoys good speedup and outperforms existing multi-core kernel SVM solvers including asynchronous stochastic coordinate descent and multi-core LIBSVM.

In a spiking neural network (SNN), individual neurons operate autonomously and only communicate with other neurons sparingly and asynchronously via spike signals. These characteristics render a massively parallel hardware implementation of SNN a potentially powerful computer, albeit a non von Neumann one. But can one guarantee that a SNN computer solves some important problems reliably? In this presentation, I formulate a mathematical model of one SNN that can be configured for a sparse coding problem for feature extraction. With a moderate but well-defined assumption, we prove that the SNN indeed solves sparse coding. To the best of our knowledge, this is the first rigorous result of this kind. This work is done jointly with Intel colleagues Tsung-han Lin and Mike Davies.

The structure and dynamics of interactions is crucial for many phenomena of interest, like contacts between individuals, data transfers, commercial exchanges, mobility, and many others. Analyzing such interactions classicaly relies on graph analysis, which captures the structure of interactions, or on temporal series, which captures their dynamics. Both approaches have been extended in various ways to cope with the both structural and temporal nature of interactions, but current situation remains unsatisfactory. I will present here the modeling of interactions over time by stream graphs and link streams, which aims at unifying both aspects into a simple, efficient and intuitive way. It provides a language to deal with interactions over time, in a way similar to the language provided by graph theory for relations.

To model recurrent interaction events in continuous time, we propose an extension of the stochastic block model where each individual belongs to a latent group and interactions between two individuals follow a conditional inhomogeneous Poisson process whose intensity is driven by the individuals' latent groups. The model is shown to be identifiable and an estimation procedure is proposed based on a semiparametric variational expectation-maximization algorithm. Two versions of the method are developed, using either a nonparametric histogram approach (with an adaptive choice of the partition size) or kernel intensity estimators. The number of latent groups can be selected by an integrated classification likelihood criterion. Finally, we demonstrate the performance of our procedure on synthetic experiments and the analysis of several real datasets illustrates the utility of our approach.
Joint work with Tabea Rebafka et Fanny Villers, UPMC.

In this talk we present an algorithm for computing a low rank approximation of a sparse matrix based on a truncated LU factorization with column and row permutations. We present various approaches for determining the column and row permutations that show a trade-off between speed versus deterministic/probabilistic accuracy. We show that if the permutations are chosen by using tournament pivoting based on QR factorization, then the obtained truncated LU factorization with column/row tournament pivoting, LU_CRTP, satisfies bounds on the singular values which have similarities with the ones obtained by a communication avoiding rank revealing QR factorization. Experiments on challenging matrices show that LU_CRTP provides a good low rank approximation of the input matrix, it is less expensive than the rank revealing QR factorization in terms of computational and memory usage costs, while also minimizing the communication cost. We also compare the computational complexity of our algorithm with randomized algorithms and show that for sparse matrices and certain accuracy, our approach is faster.

Les résultats de simulations numériques peuvent différer d’une architecture à l’autre ou même au sein d’une même architecture, s’ils sont obtenus avec des compilateurs différents. Dans les environnements séquentiels ou parallèles, différents ordres dans la suite des opérations arithmétiques peuvent entraîner différentes erreurs d’arrondi et donc des problèmes de reproductibilité numérique. On peut remarquer de telles différences en particulier dans les architectures massivement parallèles telles les GPU (Graphics Processing Units). Néanmoins les différences dans les résultats sont parfois difficiles à expliquer : erreurs d’arrondi ou bug ? Dans cet exposé, nous présentons les principes de l’arithmétique stochastique qui permet d’estimer la propagation des erreurs d’arrondi dans les programmes. Nous montrons qu’elle peut être utilisée pour identifier dans les résultats de simulation les chiffres qui diffèrent d’un environnement à l’autre du fait des erreurs d’arrondi. Nous décrivons la bibliothèque CADNA (http://cadna.lip6.fr) qui implémente l’arithmétique stochastique et en particulier une version de CADNA qui permet le contrôle de la qualité numérique dans les environnements hybrides CPU-GPU. L’estimation de la reproductibilité numérique grâce à l’arithmétique stochastique est illustrée par un code de propagation d’ondes dont les résultats peuvent différer selon l’architecture utilisée.

In a financial transaction, the risk implied by the default of the counterparty is quite difficult to evaluate especially when the exchanged derivatives include early exercises. The first part of this presentation concerns the formulation of this risk using a BSDE (Backward stochastic differential equation) as well as its simulation using a nested Monte Carlo. This latter point is further developed through the study of the relation between the number of the inner trajectories and the number of the outer trajectories that should be simulated for a better asymptotic convergence of the overall algorithm. The second part focuses on the resolution of the large number of small symmetric linear systems produced by the nested Monte Carlo algorithm. The computations involved by each linear system are independent from the others and the number of unknowns does not exceed 64. For this purpose, we present the adaptation to our context of largely used methods that include: LDLt, Householder reduction to a tridiagonal matrix, parallel cyclic reduction that is not a power of two and the divide and conquer algorithm for tridiagonal eigenproblems. We not only detail the implementation and the optimization of each method but we also compare the sustainability of each solution and its performance which includes both parallel complexity and cache memory occupation.

Much of our research aims at helping tool designers rather than providing tools for application experts: we strive to improve the productivity of programming language engineers and library developers. Starting from concrete examples in parallelizing compilation, we will discuss recent advances in the theory, algorithms and practice of polyhedral compilation. We will highlight the generation of high-performance stencil codes, the automatic optimization of storage mappings, and the optimization of parallel programs. These are three research areas where surprisingly novel geometrical, linear and polynomial optimization problems arise. We will conclude with recent progresses towards the adoption of polyhedral techniques in larger classes of applications. One particularly interesting area being the design of safety-critical control systems with a strong computational component.

Due to non-associativity of floating-point operations and dynamic scheduling on parallel architectures, getting a bit-wise reproducible floating-point result for multiple executions of the same code on different or even similar parallel architectures is challenging. In this talk, we will address the problem of reproducibility in the context of fundamental linear algebra operations – like the ones included in the BLAS library. We will present a review of existing solutions and we will propose new algorithms that yield both reproducible and accurate results (correct rounding). We will present implementations of these algorithms for the BLAS routines along with the performance results in parallel environments such as Intel desktop and server CPUs, Intel Xeon Phi, and both NVIDIA and AMD GPUs.

FreeFem++ est un logiciel libre permettant de résoudre numériquement des EDP en utilisant la méthode des éléments finis base sur un langage utilisateur (DSL) sur de machine allant du telephone portale au super calculation Après une courte présentation des possibilités du logiciel sur des exemples , je donnerai les idées principales du développement logiciel :

• La machine virtuelle,
• La syntaxe,
• Quelques problèmes informatiques ,
• Des Contraintes
• La distribution,
• Le outil de développement,
• Le calcul parallele.

In a world where the amount of produced data is growing exponentially, conventional Machine Learning (ML) models should be rethought. They have been developed on a centralized paradigm where information can be stored on a single computer (or a cluster of computers) and can be processed as a whole. Since, ML models have been adapted to the increase of the amount of information by using techniques like parallelization or sampling that do not directly integrate constraints like CPU or memory consumption. Indeed, because the quantity of produced information is growing, and because the way we access information is changing, there is right now a huge need to propose learning approaches able to integrate during learning and inference processes both, how information has to be acquired and also realistic budgeted constraints. The presentation will focus on the recent advances in the development of sequential learning models able to simultaneously learn which information to acquire for any particular task, which representation to build upon the acquired information, and to compute a prediction. Applications to image recognition, text classification, recommender systems and robotics will be presented.

Tensors are rich structures for modeling complex higher order relationships in data rich domains such as social networks, computer vision, internet of things, and so on. Tensor decomposition methods are embarrassingly parallel and scalable to enormous datasets. They are guaranteed to converge to the global optimum and yield consistent estimates of parameters for many probabilistic models such as topic models, community models, hidden Markov models, and so on. I will show the results of these methods for learning topics from text data, communities in social networks, disease hierarchies from healthcare records, cell types from mouse brain data, etc. I will also demonstrate how tensor methods can yield rich discriminative features for classification tasks and can serve as an alternative method for training neural networks.

Dans ce double exposé (Emmanuel Trélat puis Didier Henrion) présenteront le contrôle optimal, ils donneront des exemples auxquels s'applique cette théorie. De manière générale, on parle de contrôle optimal lorsqu'on veut agir sur un système, pour l'emmener vers un état final désiré, tout en minimisant un certain critère. Les applications sont très nombreuses dans des domaines variés. Ils présenteront les diverses approches numériques existant pour résoudre de tels problèmes. D'abord, les approches classiques: méthodes directes, basées sur l'optimisation numérique ou la résolution de l'équation de Hamilton-Jacobi; méthodes indirectes, basées sur le principe du maximum de Pontryagin et consistant à résoudre un problème de tir. Ils présenteront ensuite une approche beaucoup plus récente, consistant à traduire le problème de contrôle optimal par un problème de moments, en relaxant ce problème dans des espaces de mesures, et ils présenteront les approches numériques de résolution basee sur une hierarchie de problemes convexes d'optimisation semi-definie.

We describe a seriation algorithm for ranking a set of n items given pairwise comparisons between these items. Intuitively, the algorithm assigns similar rankings to items that compare similarly with all others. It does so by constructing a similarity matrix from pairwise comparisons, using seriation methods to reorder this matrix and construct a ranking. We first show that this spectral seriation algorithm recovers the true ranking when all pairwise comparisons are observed and consistent with a total order. We then show that ranking reconstruction is still exact even when some pairwise comparisons are corrupted or missing, and that seriation based spectral ranking is more robust to noise than other scoring methods. An additional benefit of the seriation formulation is that it allows us to solve semi-supervised ranking problems. Experiments on both synthetic and real datasets demonstrate that seriation based spectral ranking achieves competitive and in some cases superior performance compared to classical ranking methods.

Les données se présentent souvent sous une forme complexe (multimodale, hétérogène, ..) et relationnelle (biologie, réseaux sociaux, …). Une des approches exploitée en apprentissage pour les modéliser ou pour traiter différentes tâches est d’apprendre des représentations latentes de ces données dans des espaces continus, de façon à rendre possible l’utilisation de méthodes classiques de l’apprentissage sur ces espaces. Plusieurs directions de recherche parfois conduites indépendamment dans différentes communautés ont développé des idées similaires et se retrouvent aujourd’hui dans une thématique « apprentissage de représentations ». Les outils déployés reposent sur des méthodes d’algèbre linéaire, statistiques ou plus récemment des réseaux de neurones. La présentation donnera un aperçu de ces méthodes et développera des applications pour le traitement de données sémantiques.

The 0-dimensional version of topological persistence theory, also known as size theory, is naturally tied to hierarchical clustering. However, there is also a less obvious connection to mode-seeking. In this talk we will stress both connections and derive a robust clustering method that enjoys theoretical guarantees on the number of clusters and on the stability of the output. Soft variants can also be derived naturally. We will illustrate the effectiveness of the approach through several practical examples.

Computational topology has recently seen an important development toward data analysis, giving birth to Topological Data Analysis. Persistent homology appears as a fundamental tool in this field. It is usually computed from filtrations built on top of data sets sampled from some unknown (metric) space, providing "topological signatures" revealing the structure of the underlying space. To ensure the relevance of such signatures, it is necessary to prove that they come with stability properties with respect to the way data are sampled. In this talk, after a short introduction to persistent homology, we will present a few results on the stability of persistence diagrams (the mathematical objects encoding the persistent homology information) built on top of general metric spaces. We will show that the use of persistent homology can be naturally considered in general statistical frameworks and persistence diagrams can be used as statistics with interesting convergence properties.
The results presented in this talk are joint works with V. de Silva, B. Fasy, M. Glisse, C. Labru\`ere, F. Lecci, B. Michel, S. Oudot, A. Rinaldo and L. Wasserman.

A long term goal in complexity theory is to prove lower bounds - natural problems like satisfiability or permanent are 'hard'. The convenient way to study this is via arithmetic circuits. The lower bound questions here allow a flip to upper bound ones; the key being that of designing hitting-sets (or blackbox identity testing). Such designs are known only for restricted circuit models; the restriction being on the depth and shape. The proofs almost always also give a notion of rank for the corresponding model. In this talk we will briefly define these circuits and the associated notions of rank. The rank notions are algebraic in nature, and generalize the basic 'vector space rank' to higher algebraic concepts.

We study the arithmetic complexity of iterated matrix product, a fundamental family of polynomials whose complexity is equivalent to that of the determinant. We show lower bounds on the size of multilinear homogeneous depth-4 formulas computing these polynomials. The proof is based on a variant of the partial derivatives technique: a small formula cannot compute a polynomial whose partial derivatives span a high dimensional space. We also study formulas with bounded fan-in multiplication gates, and the lower bound we get shows the optimality of Tavenas' depth reduction result (MFCS, 2013). (Joint work with Nutan Limaye, Guillaume Malod and Srikanth Srinivasan.)

Nous établissons un lien entre les racines réelles de polynômes "de type creux" et une version algébrique du problème "P=NP ?" due à Leslie Valiant. Plus précisément, nous proposons la conjecture suivante: le nombre de racines réelles d'un polynôme en une variable exprimé comme somme de produits de polynômes creux est polynomialement borné en la taille d'une telle expression. Cette "tau-conjecture réelle" peut-être vue comme une généralisation de la règle des signes de Descartes, qui implique qu'un polynôme a plus de monômes non nuls que que de racines réelles positives. Nous montrons que cette conjecture implique que le permanent (contrairement par exemple au déterminant) ne peut pas être pas être évalué en un nombre polynomial d'opérations arithmétiques.

La borne de Descartes tient compte du nombre de monômes présents pour majorer le nombre de racines réelles d'un polynôme réel en une variable. Dans les années 80, A. Khovanskii a obtenu des bornes de ce type pour les systèmes polynomiaux en plusieurs variables. Depuis, ces bornes ont été améliorées, et les bornes obtenues sont même optimales dans certains cas. Néanmoins, une généralisation de la règle de Descartes prenant en compte les signes des coefficients présents est encore largement ouverte. Nous présenterons un panorama des diverses avancées récentes sur le sujet. Nous terminerons par la présentation des toutes premières généralisations de la règle de Descartes au cas multivarié obtenues l'année dernière.

Dans les méthodes de résolution par sous-domaines de type FETI, le principal coût de calcul réside dans la résolution, par descente-remontée, des problèmes locaux dans les différents sous-domaines, à chaque itération sur le problème condensé aux interfaces. Le parallélisme entre sous-domaines se prête bien à des calculateurs distribués et de la programmation par échanges de messages. Pour augmenter le degré de parallélisme, et utiliser au mieux des architectures hybrides avec des nœuds de calcul multi-cœurs, il semble naturel d'allouer chaque sous-domaine à un nœud et d'utiliser du parallélisme à mémoire partagée pour le solveur direct local. Cependant, autant les logiciels de résolution en parallèle de systèmes linéaires creux arrivent à être efficaces dans la phase de factorisation, autant les performances sont très limitées dans la phase de descente-remontée, pour cause de localisation temporelle des données insuffisante. En revanche, la résolution simultanée pour plusieurs seconds membres ne présente pas la même difficulté. Dans cet exposé, nous montrerons différentes voies pour travailler simultanément avec plusieurs directions de descente, afin de réaliser des résolutions locales multiples, aussi bien dans des cas de problèmes à seconds membres multiples que de problèmes à second membre unique, pour des mises en œuvre de méthodes FETI-1LM ou FETI-2LM pour des applications en mécanique des structures ou en électromagnétisme.

The solution of sparse systems of linear equations of the form A x = b is at the heart of many numerical simulation applications. In several cases (e.g. industrial), direct methods are preferred to iterative methods because of their numerical accuracy and robustness. Direct methods consist in decomposing a matrix A under the form LU (or LDLt, if the matrix is symmetric), before applying triangular solves in order to obtain the solution. However, they are also characterized by a high memory consumption (especially for large 3D problems) and a large amount of computations. The quality of the computed solution, the numerical features and the computation time are essential parameters for the applications, while the material resources available (number of processors, memory) are constrained and should be used efficiently. In this presentation, we describe some work to pursue these objectives in the context of the sparse direct solver MUMPS, developed in Toulouse, Lyon-Grenoble and Bordeaux. The approach relies on an original parallelization of the so called multifrontal method, where the factorization of a sparse matrix is achieved by applying successively partial factorizations on smaller, dense matrices, and where tasks are scheduled in a dynamic, distributed, asynchronous manner. This approach to parallelism allows dynamic datastructures and dynamic numerical pivoting. We will discuss our main research directions to face the evolution of the application needs on one side, and of computer architectures on the other side: parallelization and collective communication issues in an asynchronous environment on large numbers of cores, memory consumption and memory scalability, and low-rank compression which enable a decrease of the computational complexity of sparse direct methods on some classes of problems arising from partial differential equations. We finally mention some software issues, since our objective is to constantly transfer research in the software package MUMPS, which in turn can be widely used by applications who provide feedback to influence future research directions.

With the onset of extreme-scale computing (at Exascale for example), challenges related to extreme data, energy and I/O constraints are becoming dominating concerns. It will become impossible for scientists to save a sufficient amount of raw simulation data to persistent storage for subsequent processing. Algorithms must adapt to machines with extreme concurrency, low communication bandwidth, and high memory latency, while operating within the time constraints prescribed by the simulation. So, it is necessary to move away from an only post-process centric data analysis paradigm towards a complementary as close as possible to real time concurrent analysis framework, in which raw simulation data is processed as it is computed. In this context computations are considered in-situ if they utilize the primary compute resources, while in-transit processing refers to offloading computations to a set of secondary resources using asynchronous data transfers. Both approaches are intermediate steps towards the end goal of achieving real-time extreme data analysis in high-performance computing systems. This conference does not have the ambition to define and give efficient solutions but to set the present state of art and to present R&D possible ways and actions to explore in order to tackle the objectives.

• A power model based on system power and data exchange patterns, Real Time (In situ) data-related energy/performance trade-offs
• The design and implementation of common and new analysis techniques typically performed on large-scale scientific simulations: topological analysis, descriptive statistics, surrogate data model, filtering, compression, pattern/feature discovery, error analysis …
• The approximations which will be used to adaptively determine frequency at which full (no compression) analyses are computed, …
• The promising new approach of sub-linear algorithms addressing the fundamental mathematical problem of understanding global features of a data set using limited resources. The algorithmic developments, co-scheduling system to coordinate the execution of various analysis workflows.
• The ultra scalable and the most flexible implementation of a framework that support efficient data movement between in-situ and in-transit computations taking into account tiered storage architectures and asynchronous data transfers.
• The use of multi-precision computations, reconsidering most algorithms and studying (using e.g. backward error analysis) places where such data compression can be safely implemented, and providing necessary error indicators for these optimized routines, as currently done in sparse direct solvers.
• The use of in situ data analysis for tracking and checking fault or error propagation into the simulation, associating a resilience aspect with the execution of workflows on parallel systems.

Scientific Visualization aims at helping users represent, explore, analyze and interpret simulated or acquired geometrical data. Among existing techniques, algorithms inspired by Morse theory have shown to be useful in order to capture and summarize the structure of the studied phenomena. In this setting, the data is typically represented by a piecewise-linear scalar field defined over a triangulation, whose critical points often correspond to features of interest application-wise: center of atoms and bonds in chemistry, vortices in CFD, hot spots in thermodynamics, etc. Then, constructions such as the Reeb graph or the Morse-Smale complex can encode at multiple scales the structural relation of these critical points. In this talk, I will give an overview of existing algorithms for the topological analysis and visualization of scalar data. Then, I will present recent results for the analysis of "uncertain" scalar fields, which map each vertex of the triangulation to a random variable. In particular, given reliable estimations of the bounds of the support of the probability density function of each vertex, our algorithm identifies minimal connected components and value-intervals for which critical points must appear for any realization field of the input uncertain data. Thus, despite the uncertainty, our technique enables to identify admissible regions for atoms in chemistry, vortices in CFD, etc. I will conclude with the persepectives of this work and the remaining scientific challenges.

General purpose (GP)GPU programming is a popular solution to achieve high performance. It couples inexpensive highly parallel computing units with classic CPUs. These heterogenous systems lead to complex designs combining multiple paradigms and programming languages to manage each hardware architecture. This talk will present a set of tools to harness GPGPU programming through the OCaml programming language. It will describe the SPOC library, which handles GPGPU subprograms (kernels) and data transfers between devices. Then, It will show how SPOC expresses GPGPU kernels: through interoperability with common low-level extensions (from Cuda and OpenCL frameworks) but also via an embedded DSL for OCaml. Finally, It will present how to manage those kernels through parallel skeletons. Performance tests show that our solution achieves a high level of performance for simple examples, as well as with the translation of a realistic numerical application from Fortran and Cuda, to OCaml. We show that by increasing the level of abstraction to handle kernels, programs are easier to write and that some optimizations (kernel generation and transfers scheduling) become possible. Thus, we win on both sides : expressiveness and efficiency.

Classifying lattice walks in restricted lattices is an important problem in enumerative combinatorics. Recently, computer algebra methods have been used to explore and solve a number of difficult questions related to lattice walks. In this talk, we will give an overview of recent results on structural properties and explicit formulas for generating functions of walks in the quarter plane, with an emphasis on the algorithmic methodology.

Je montrerai comment construire explicitement des approximations polynomiales simultanées (de type Padé) pour les fonctions log(1-z) et exp(z), qui appartiennent à des niveaux différents de la hiérarchie hypergéométrique. La méthode consiste à "mélanger" diverses classes de polynômes orthogonaux. La motivation initiale de ce travail se trouve en théorie des nombres : bien qu'aucun résultat diophantien ne semble pouvoir se déduire des approximations présentées, on peut espérer que des variations permettront d'étudier l'indépendance linéaire sur Q des nombres 1, pi et e, par exemple.

We present a novel strategy to perform estimation for mechanical systems, and more generally for evolution equations with uncertain initial conditions and parameters. We adopt a filtering approach on the dynamical system formulation to construct a joint state-parameter estimator that uses some measurements available in standard operating conditions. Namely, the aim is to obtain a modified dynamical system converging to the reference by incorporating correction terms using the data. First, in the case of known parameters, state estimation is performed using a Luenberger observer inspired from feedback control theory. This type of state estimator is chosen for its particular effectiveness and robustness. In particular, unlike the classical Kalman approach, this filter is computationally tractable for numerical systems arising from the discretization of PDEs and – although optimality is lost – the exponential stability of the corresponding error system gives exponential convergence of the estimator/observer. With uncertain parameters we extend the estimator by incorporating the parameters in an augmented dynamical system. The effect of the first stage state filter then consists in essence in circumscribing the uncertainty to the parameter space – which is usually much “smaller” than the parameter space – and allows for an H2 type filter in the resulting low rank space. This second step is related to “reduced rank filtering” procedures in data assimilation. The convergence of the resulting joint state-parameter estimator can be mathematically established , and we demonstrate its effectiveness by identifying localized parameters. The applications considered are motivated by cardiology where identifying adequate parameters – using measurements of a type that is available in medical imaging – in the mechanical model of a beating heart or a deforming aorta can provide patient specific simulations that can be used by clinicians in their diagnosis.

Transparents Dans cet exposé, nous présenterons le cadre algébrique de la morphologie mathématique. Les transformations de base de morphologie mathématique (dilatation et érosion) dans des treillis complets sont définies à partir de la notion d'adjonction dont elles héritent les propriétés. Elles sont utiles dans des domaines aussi divers que les ensembles, les ensembles flous, la logique, pour des applications en traitement d'images, raisonnement spatial, modélisation de préférences, traitement d'informations imparfaites. Nous discuterons en particulier du cas d'informations floues et d'informations bipolaires, comprenant une partie positive (préférences par exemple) et une partie négative (contraintes). Nous illustrerons leur intérêt sur des exemples en interprétation d'images et raisonnement spatial.

Après avoir situé les méthodes hybrides dans le panorama du calcul haute performance, nous ferons le point sur l’analyse et la mise en oeuvre de méthodes de décomposition à deux niveaux robustes vis à vis de la taille du système matriciel à inverser et des hétérogénéités dans les coefficients de la matrice.

We illustrate how dense linear algebra computations can be enhanced using randomized algorithms by performing less communication and/or computation. A first application concerns the solution of general or symmetric indefinite linear systems where randomization prevents the communication overhead due to pivoting. The second application is related to statistical condition estimation for least squares problems or linear systems. For each application, we provide accuracy and performance results on current hybrid multicore-GPU parallel machines.

Dans quelle mesure puis-je résoudre efficacement un problème d'optimisation combinatoire donné ? La théorie de la complexité s est développée autour de cette question, avec en premier lieu les problèmes NP-complets bien connus. Un large domaine de recherche (les algorithmes approchés) s'est ensuite développé dès les années 70 pour explorer certains compromis possibles entre temps de calcul et qualité de solutions. Portés notamment par des résultats négatifs forts en termes d algorithmes approchés, de nouveaux champs de recherche se sont développés plus récemment autour d approches complémentaires. Le but de cet exposé est de présenter dans un premier temps les deux approches principales, les algorithmes exponentiels et la complexité paramétrée (algorithmes FPT), puis dans un deuxième temps quelques éléments sur des questions récentes mêlant algorithmes exponentiels ou FPT et algorithmes approchés.

In this talk, we investigate in a unified way the structural properties of a large class of convex regularizers for linear inverse problems. These penalty functionals are crucial to force the regularized solution to conform to some notion of simplicity/low complexity. Classical priors of this kind includes sparsity, piecewise regularity and low-rank. These are natural assumptions for many applications, ranging from medical imaging to machine learning. Our main set of contributions gives a theoretical assessment of the recovery performances of these regularizations, which includes robustness to noise in the measurements. This extends previous works focused both on model estimation (see for instance [1,2]), L^2 stability (see [3]), and share links with the compressed sensing literature when considering randomized measurements [4]. This is a joint work with S. Vaiter, C. Deledalle, M. Golbabaee and J. Fadili. For more details, see [5]. Bibliography:
[1] J.J. Fuchs, On sparse representations in arbitrary redundant bases. IEEE Transactions on Information Theory, 50(6):1341-1344, 2004.
[2] F. Bach, Consistency of trace norm minimization, Journal of Machine Learning Research, 9, 1019-1048, 2008.
[3] M. Grasmair, Linear convergence rates for Tikhonov regularization with positively homogeneous functionals. Inverse Problems, 27(7):075014, 2011.
[4] V. Chandrasekaran, B. Recht, P.A. Parrilo, A. S. Willsky, The Convex Geometry of Linear Inverse Problems, FoCM, 12(6):805-849, 2012
[5] S. Vaiter, M. Golbabaee, J. Fadili, G. Peyré, Model Selection with Piecewise Regular Gauges, Preprint hal-00842603, 2013

Longtemps, l'arithmétique virgule flottante n'a pas vraiment été spécifiée. Tout ce qu'on savait était que le résultat d'une opération arithmétique n'était en général "pas trop loin" du résultat exact. La norme IEEE 754, de 1985 n'a pas résolu tous les problèmes, même si elle a constitué un très gros progrès. Nous montrons à la fois les progrès dans ce domaine, leur grand intérêt, et le chemin qu'il reste à parcourir.

The cellular tree classifier model addresses a fundamental problem in the design of classifiers for a parallel or distributed computing world: Given a data set, is it sufficient to apply a majority rule for classification, or shall one split the data into two or more parts and send each part to a potentially different computer (or cell) for further processing? At first sight, it seems impossible to define with this paradigm a consistent classifier as no cell knows the ``original data size'', n. However, I show that this is not so by exhibiting two different consistent classifiers. If there is enough time left, I will discuss a related tree aggregation model called "random forests".
(joint work with L. Devroye, McGill University)

Many machine learning and signal processing problems are traditionally cast as convex optimization problems. A common difficulty in solving these problems is the size of the data, where there are many observations ("large n") and each of these is large ("large p"). In this setting, online algorithms such as stochastic gradient descent which pass over the data only once, are usually preferred over batch algorithms, which require multiple passes over the data. Given n observations/iterations, the optimal convergence rates of these algorithms are O(1/\sqrt{n}) for general convex functions and reaches O(1/n) for strongly-convex functions. In this talk, I will show how the smoothness of loss functions may be used to design novel algorithms with improved behavior, both in theory and practice: in the ideal infinite-data setting, an efficient novel Newton-based stochastic approximation algorithm leads to a convergence rate of O(1/n) without strong convexity assumptions, while in the practical finite-data setting, an appropriate combination of batch and online algorithms leads to unexpected behaviors, such as a linear convergence rate for strongly convex problems, with an iteration cost similar to stochastic gradient descent. (joint work with Nicolas Le Roux, Eric Moulines and Mark Schmidt)

Online algorithms deal with settings where the input data arrives over time and the current decision must be made by the algorithm without the knowledge of future input. In the last few years, the online primal-dual approach, pioneered by Buchbinder and Naor, has emerged as a very powerful and general method to systematically design and analyze online algorithms. In this talk, I will give an overview of the method and show how it unifies and simplifies various previous results. I will also describe the recent successes of this approach in addressing some classic problems such as weighted paging and the randomized k-server problem. Finally, we will also see some recent extensions of the method.

We begin the talk with a a short overview of non-cooperative game theory and of population propagation models. In the game theory part, a particular attention will be given to potential games. We shall focus in particular on congestion games and on the game version of the generalilzed Kelly mechanism problem, both of which are known to be potential games. We shall then use these tools to study (1) the question of what type of content should service providers specialise in, which will be solved by transforming it into an equivalent congestion game, (2) issues related to viral marketing and competition issues in social networks. In these problems the generalized Kelly mechanism will be frequently used. The game theoretic analyis will allow us to get insight on how much to spend on advertizing products and on what product should we advertize. Both journal and conference papers as well as video presentations covering this talk are availalble at here

We consider numerical schemes for Hamilton-Jacobi equations based on a direct discretization of the Lax-Oleinik semi-group which represents the solution as a minimizer of the action over continuous curves. We prove that this method is convergent with respect to the time and space stepsizes provided the solution is Lipschitz. Moreover, we prove that the numerical scheme is a geometric integrator satisfying a discrete weak-KAM theorem which allows to control its long time behavior. Taking advantage of a fast algorithm for computing min-plus convolutions based on the decompo- sition of the function into concave and convex parts, we show that the numerical scheme can be implemented in a very efficient way.
This is a joint work with Anne Bouillard (ENS Paris) and Maxime Zavidovique (Univ. Paris 6)

How long does it take to either allay or confirm suspicions, should they arise, about the accuracy of a computed result? Often diagnosis has been overtaken by the end of a computing platform's service life. Diagnosis could be sped up by at least an order of magnitude if more users and developers of numerical software knew enough to demand the needed software tools. Almost all these have existed though not all of them together in one place at one time. These tools cope with vulnerabilities peculiar to Floating-Point, namely roundoff and arithmetic exceptions. Programming languages tend to turn exceptions into branches which are prone to error. In particular, unanticipated events deemed ERRORs are handled in obsolete ways inherited from the era of batch computing. There are better ways. They would have prevented the crash of Air France #447 in June 2009, among other things.

Je présenterai deux problèmes algorithmiques importants pour la cryptologie à clés publiques : la factorisation des entiers naturels, et le calcul de logarithmes discrets. J'expliquerai comment la cryptographie exploite l'asymétrie calculatoire de ces problèmes. Je présenterai quelques algorithmes d'exponentiation rapide, de factorisation, et de calcul de logarithmes discrets.

La notion de crible est un outil crucial pour accélérer les algorithmes modernes pour la factorisation d'entiers et les calculs de logarithmes discrets dans les corps finis. Le principe général reste élémentaire, puisqu'il est directement inspiré du crible d'Eratosthène. La mise en œuvre au sein des deux algorithmes phares que sont le crible algébrique et le crible de corps de functions est toutefois l'occasion de belles astuces aussi bien mathématiques qu'informatiques, dont nous donnerons quelques exemples. Nous concluerons en mentionnant les derniers gros calculs en date pour la factorisation et le logarithme discret.

Un arrangement de double pseudo-droites est une famille finie de lacets simples triviaux du plan projectif s'intersectant deux-à-deux en quatre points d'intersection transverse et induisant deux-à-deux une décomposition cellulaire du plan projectif. L'exposé portera sur la combinatoire de ces arrangements en lien avec l'algorithmique des graphes de visibilité.

Exact Geometric Computation (EGC) has provided a powerful paradigm for correct implementation of geometric algorithms for two decades. It is the most successful technique in Computational Geometry, and has led to successful libraries (e.g., CGAL) and many practical robust algorithms. We now have a fairly good understanding of the key techniques and what can be achieved under this paradigm. We review some strong reasons to extend this paradigm:

• The existence of EGC solutions may not be known (e.g., analytic roots)
• EGC is too inefficient (e.g., shortest path amidst discs)
• EGC entails numerous and difficult algebraic analysis (e.g., Vor diagram of polyhedra)
• Exactness is inappropriate (e.g., motion planning)
• Degeneracy requires zero bounds

In each case, the intuitive idea of introducing an epsilon-parameter suggests itself. But how to use this parameter is not always clear; one thing is clear -- we must not abuse the epsilon by treating it as an exact algebraic quantity. Ultimately, our goal is to develop purely numerical approaches for solving these problems. The introduction of numerical techniques in Computational Geometry will allow us to solve new problems which were previously untouchable because of our exactness outlook. We will illustrate with several examples.

The first part of the talk will briefly summarize the historical development and current status of formal languages for open-universe probability models, which allow for uncertain reasoning about unknown objects and events. The second part will focus on examples and advocates the use of "vertically integrated" generative models for real-world machine learning problems.
The speaker is supported by, and this talk is given under the auspices of, the Blaise Pascal International Research Chair, funded by l'État et la Région d'Ile de France and administered by the Fondation de l'École Normale Supérieure.

We tackle the problem of quantum state tomography using the tools of compressed sensing. Unlike classical compressed sensing, the dimension of the problem is more significant, so we turn to a class of hard-thresholding techniques that allows an algorithm with low-memory requirements. Large-scale eigenvalue decompositions are handled with new randomized methods. Our analysis shows provable recovery guarantees even in the presence of noise and approximate calculations.

The cost of moving data in an algorithm can surpass by several orders of magnitude the cost of performing arithmetics, and this gap has been steadily and exponentially growing over time. This talk will argue that this communication problem needs to be addressed by the numerical software community directly at the mathematical formulation and the algorithmic design level. This requires a paradigm shift in the way the numerical algorithms are devised, which now need to aim at keeping the number of communication instances to a minimum, while retaining their numerical efficiency. Communication avoiding algorithms provide such a novel perspective on designing algorithms that provably minimize communication in numerical linear algebra. The novel numerical schemes employed, the speedups obtained with respect to conventional algorithms, as well as their impact on applications in computational science will be also discussed.

Dans une première partie de cet exposé nous présentons le domaine du Calcul Formel lié à la résolution des systèmes polynomiaux en utilisant les bases de Gröbner. Le calcul de bases de Gröbner (Buchberger) est, en effet, un outil fondamental pour la résolution des systèmes polynomiaux par des techniques algébriques; il est à la base de nombreux solveurs exacts et permet de retrouver toutes les solutions. Nous montrerons aussi quelques grands domaines d’application de ces méthodes où l'usage de méthodes exactes est déterminant. Parmi les applications on distingue le cas discret et le cas continue. Dans le premier cas les solutions sont à rechercher dans un corps fini ; les applications sont alors nombreuses en cryptographie (cryptanalyse algébrique). Dans le deuxième cas les solutions recherchées sont réelles avec des applications dans de nombreux domaines (optimisation globale, robotique, biologie, analyse numérique, …). Dans une deuxième partie nous décrivons brièvement les algorithmes de calcul des bases de Gröbner. L’efficacité des meilleurs algorithmes repose fortement sur des techniques d’algèbre linéaire. Les matrices générées par ces algorithmes sont de grandes tailles (plusieurs millions de lignes et de colonnes) et présentent des propriétés inhabituelles (structure quasi-triangulaires par blocs, creuses, singulières). Il a donc été nécessaire de développer une algorithmique permettant de tirer partie des ces structures. Nous présentons également des librairies d’algèbre linéaire pour architecture multi-cœurs et parallèles. Ces bibliothèques contiennent des algorithmes spécifiques (élimination Gaussienne structurée par exemple) ainsi que des représentations spécifiques des matrices.