Problème de flot maximum | EPFL Graph Search

thumb|right|Un exemple de graphe de flot avec un flot maximum. la source est s, et le puits t. Les nombres indiquent le flot et la capacité. Le problème de flot maximum consiste à trouver, dans un réseau de flot, un flot réalisable depuis une source unique et vers un puits unique qui soit maximum. Quelquefois, on ne s'intéresse qu'à la valeur de ce flot. Le s-t flot maximum (depuis la source s vers le puits t) est égal à la s-t coupe minimum du graphe, comme l'indique le théorème flot-max/coupe-min. Applications Ce type de problème est proche de ce qui est rencontré dans le remplissage optimisé de boîtes. Algorithmes Étant donné un graphe orienté G = (V,E), où chaque arc u,v a une capacité c(u,v), on cherche un flot maximum f depuis la source s vers le puits t, sous contrainte de capacité. Différents algorithmes ont été développés pour résoudre ce problème

Numerical Methods for First and Second Order Fully Nonlinear Partial Differential Equations

Dimitrios Gourzoulidis

This thesis focuses on the numerical analysis of partial differential equations (PDEs) with an emphasis on first and second-order fully nonlinear PDEs. The main goal is the design of numerical methods to solve a variety of equations such as orthogonal maps, the prescribed Jacobian equation and inequality, the elliptic and parabolic Monge-Ampère equations. For orthogonal map we develop an \emph{operator-splitting/finite element} approach for the numerical solution of the Dirichlet problem. This approach is built on the variational principle, the introduction of an associated flow problem, and a time-stepping splitting algorithm. Moreover, we propose an extension of this method with an \emph{anisotropic mesh adaptation algorithm}. This extension allows us to track singularities of the solution's gradient more accurately. Various numerical experiments demonstrate the accuracy and the robustness of the proposed method for both constant and adaptive mesh. For the prescribed Jacobian equation and the three-dimensional Monge-Ampère equation, we consider a \emph{least-squares/relaxation finite element method} for the numerical solution of the Dirichlet problems. We then introduce a relaxation algorithm that splits the least-square problem, which stems from a reformulation of the original equations, into local nonlinear and variational problems. We develop dedicated solvers for the algebraic problems based on Newton method and we solve the differential problems using mixed low-order finite element method. Overall the least squares approach exhibits appropriate convergence orders in

L^2(\Omega)

and

H^1(\Omega)

error norms for various numerical tests. We also design a \emph{second-order time integration method} for the approximation of a parabolic two-dimensional Monge-Ampère equation. The space discretization of this method is based on low-order finite elements, and the time discretization is achieved by the implicit Crank-Nicolson type scheme. We verify the efficiency of the proposed method on time-dependent and stationary problems. The results of numerical experiments show that the method achieves nearly optimal orders for the

L^2(\Omega)

and

H^1(\Omega)

error norms when smooth solutions are approximated. Finally, we present an adaptive mesh refinement algorithm for the elliptic Monge-Ampere equation based on the residual error estimate. The robustness of the proposed algorithm is verified using various test cases and two different solvers which are inspired by the two previous proposed numerical methods.

EPFL2021

Numerical Approximation Of Orthogonal Maps

Alexandre Caboussat, Dimitrios Gourzoulidis, Marco Picasso

Orthogonal maps are the solutions of the mathematical model of paper-folding, also called the origami problem. They consist of a system of first-order fully nonlinear equations involving the gradient of the solution. The Dirichlet problem for orthogonal maps is considered here. A variational approach is advocated for the numerical approximation of the maps. The introduction of a suitable objective function allows us to enforce the uniqueness of the solution. A strategy based on a splitting algorithm for the corresponding flow problem is presented and leads to decoupling the time-dependent problem into a sequence of local nonlinear problems and a global linear variational problem at each time step. Numerical experiments validate the accuracy and the efficiency of the method for various domains and meshes.

2019

Minkowski sums of polytopes

Christophe Weibel

Minkowski sums are a very simple geometrical operation, with applications in many different fields. In particular, Minkowski sums of polytopes have shown to be of interest to both industry and the academic world. This thesis presents a study of these sums, both on combinatorial properties and on computational aspects. In particular, we give an unexpected linear relation between the f-vectors of a Minkowski sum and that of its summands, provided these are relatively in general position. We further establish some bounds on the maximum number of faces of Minkowski sums with relation to the summands, depending on the dimension and the number of summands. We then study a particular family of Minkowski sums, which consists in summing polytopes we call perfectly centered with their own duals. We show that the face lattice of the result can be completely deduced from that of the summands. Finally, we present an algorithm for efficiently computing the vertices of a Minkowski sum of polytopes. We show that the time complexity is linear in terms of the output for fixed size of the input, and that the required memory size is independent of the size of the output. We also review various algorithms computing different faces of the sum, comparing their strong and weak points.

EPFL2007

Numerical Methods for First and Second Order Fully Nonlinear Partial Differential Equations

Dimitrios Gourzoulidis

L^2(\Omega)

and

H^1(\Omega)

L^2(\Omega)

and

H^1(\Omega)

EPFL2021