Déposez votre fichier ici pour le déplacer vers cet enregistrement.

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.

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 ...

65F35 ; 65K05 ; 68Q15 ; 15A12 ; 65F10 ; 90C51 ; 65H10

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

This talk focuses on challenges that we address when designing linear solvers that aim at achieving scalability on large scale computers, while also preserving numerical robustness. We will consider preconditioned Krylov subspace solvers. Getting scalability relies on reducing global synchronizations between processors, while also increasing the arithmetic intensity on one processor. Achieving robustness relies on ensuring that the condition number of the preconditioned matrix is bounded. We will discuss two different approaches for this. The first approach relies on enlarged Krylov subspace methods that aim at computing an enlarged subspace and obtain a faster convergence of the iterative method. The second approach relies on a multilevel Schwarz preconditioner, a multilevel extension of the GenEO preconditioner, that is basedon constructing robustly a hierarchy of coarse spaces. Numerical results on large scale computers, in particular for linear systems arising from solving linear elasticity problems, will discuss the efficiency of the proposed methods.

This talk focuses on challenges that we address when designing linear solvers that aim at achieving scalability on large scale computers, while also preserving numerical robustness. We will consider preconditioned Krylov subspace solvers. Getting scalability relies on reducing global synchronizations between processors, while also increasing the arithmetic intensity on one processor. Achieving robustness relies on ensuring that the condition ...

65F08 ; 65F10 ; 65N55

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

In this presentation, we will first present the main goals and principles of reservoir simulation. Then we will focus on linear systems that arise in such simulation. The main HPC challenge is to solve those systems efficiently on massively parallel computers. The specificity of those systems is that their convergence is mostly governed by the elliptic part of the equations and the linear solver needs to take advantage of it to be efficient. The reference method in reservoir simulation is CPR-AMG which usually relies on AMG to solve the quasi elliptic part of the system. We will present some works on improving AMG scalability for the reservoir linear systems (work done in collaboration with CERFACS). We will then introduce an on-going work with INRIA to take advantage of their enlarged Krylov method (EGMRES) in the CPR method.

In this presentation, we will first present the main goals and principles of reservoir simulation. Then we will focus on linear systems that arise in such simulation. The main HPC challenge is to solve those systems efficiently on massively parallel computers. The specificity of those systems is that their convergence is mostly governed by the elliptic part of the equations and the linear solver needs to take advantage of it to be efficient. The ...

65F10 ; 65N22 ; 65Y05

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

In domain decomposition methods, most of the computational cost lies in the successive solutions of the local problems in subdomains via forward-backward substitutions and in the orthogonalization of interface search directions. All these operations are performed, in the best case, via BLAS-1 or BLAS-2 routines which are inefficient on multicore systems with hierarchical memory. A way to improve the parallel efficiency of the method consists in working with several search directions, since multiple forward-backward substitutions and reorthogonalizations involve BLAS-3 routines. In the case of a problem with several right-hand-sides, using a block Krylov method is a straightforward way to work with multiple search directions. This will be illustrated with an application in electromagnetism using FETI-2LM method. For problems with a single right-hand-side, deriving several search directions that make sense from the optimal one constructed by the Krylov method is not so easy. The recently developed S-FETI method gives a very good approach that does not only improve parallel efficiency but can also reduce the global computational cost in the case of very heterogeneous problems.

In domain decomposition methods, most of the computational cost lies in the successive solutions of the local problems in subdomains via forward-backward substitutions and in the orthogonalization of interface search directions. All these operations are performed, in the best case, via BLAS-1 or BLAS-2 routines which are inefficient on multicore systems with hierarchical memory. A way to improve the parallel efficiency of the method consists in ...

65N22 ; 65N30 ; 65N55 ; 65Y05 ; 65F10

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Multigrid is an iterative method for solving large linear systems of equations whose Toeplitz system matrix is positive definite. One of the crucial steps of any Multigrid method is based on multivariate subdivision. We derive sufficient conditions for convergence and optimality of Multigrid in terms of trigonometric polynomials associated with the corresponding subdivision schemes.

(This is a joint work with Marco Donatelli, Lucia Romani and Valentina Turati).

Multigrid is an iterative method for solving large linear systems of equations whose Toeplitz system matrix is positive definite. One of the crucial steps of any Multigrid method is based on multivariate subdivision. We derive sufficient conditions for convergence and optimality of Multigrid in terms of trigonometric polynomials associated with the corresponding subdivision schemes.

(This is a joint work with Marco Donatelli, Lucia Romani and ...

65N55 ; 65N30 ; 65F10 ; 65F35

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

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.

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 ...

65F35 ; 65K05 ; 68Q15 ; 15A12 ; 65F10 ; 90C51 ; 65H10

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Linear matrix equations such as the Lyapunov and Sylvester equations and their generalizations have classically played an important role in the analysis of dynamical systems, in control theory and in eigenvalue computation. More recently, matrix equations have emerged as a natural linear algebra framework for the discretized version of (systems of) partial differential equations (PDEs), possibly evolving in time. In this new framework, new challenges have arisen. In this talk we review some of the key methodologies for solving large scale linear and quadratic matrix equations. We will also discuss recent matrix-based strategies for the numerical solution of time-dependent problems arising in control and in the analysis of spatial pattern formations in certain electrodeposition models.

Linear matrix equations such as the Lyapunov and Sylvester equations and their generalizations have classically played an important role in the analysis of dynamical systems, in control theory and in eigenvalue computation. More recently, matrix equations have emerged as a natural linear algebra framework for the discretized version of (systems of) partial differential equations (PDEs), possibly evolving in time. In this new framework, new ...

65F10 ; 15A24

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Both multigrid and domain decomposition methods are so called optimal solvers for Laplace type problems, but how do they compare? I will start by showing in what sense these methods are optimal for the Laplace equation, which will reveal that while both multigrid and domain decomposition are iterative solvers, there are fundamental differences between them. Multigrid for Laplace’s equation is a standalone solver, while classical domain decomposition methods like the additive Schwarz method or Neumann-Neumann and FETI methods need Krylov acceleration to work. I will explain in detail for each case why this is so, and then also present modifications so that Krylov acceleration is not necessary any more. For overlapping methods, this leads to the use of partitions of unity, while for non-overlapping methods, the coarse space can be a remedy. Good coarse spaces in domain decomposition methods are very different from coarse spaces in multigrid, due to the very aggressive coarsening in domain decomposition. I will introduce the concept of optimal coarse spaces for domain decomposition in a sense very different from the optimal above, and then present approximations of this coarse space. Together with optimized transmission conditions, this leads to a two level domain decomposition method of Schwarz type which is competitive with multigrid for Laplace’s equation in wallclock time.

Both multigrid and domain decomposition methods are so called optimal solvers for Laplace type problems, but how do they compare? I will start by showing in what sense these methods are optimal for the Laplace equation, which will reveal that while both multigrid and domain decomposition are iterative solvers, there are fundamental differences between them. Multigrid for Laplace’s equation is a standalone solver, while classical domain ...

65N55 ; 65N22 ; 65F10