Publications associées à Approximation diophantienne

Adaptive Symplectic Model Order Reduction Of Parametric Particle-Based Vlasov-Poisson Equation

Jan Sickmann Hesthaven, Nicolò Ripamonti, Cecilia Pagliantini

. High-resolution simulations of particle-based kinetic plasma models typically require a high number of particles and thus often become computationally intractable. This is exacerbated in multi-query simulations, where the problem depends on a set of para ...

AMER MATHEMATICAL SOC2023

Fairness and Explainability in Clustering Problems

Xinrui Jia

In this thesis we present and analyze approximation algorithms for three different clustering problems. The formulations of these problems are motivated by fairness and explainability considerations, two issues that have recently received attention in the ...

EPFL2023

Approximation Algorithms for Allocation and Network Design

Etienne Michel François Bamas

In this thesis, we give new approximation algorithms for some NP-hard problems arising in resource allocation and network design. As a resource allocation problem, we study the Santa Claus problem (also known as the MaxMin Fair Allocation problem) in which ...

EPFL2023

Fast deterministic and randomized algorithms for low-rank approximation, matrix functions, and trace estimation

Alice Cortinovis

In this thesis we propose and analyze algorithms for some numerical linear algebra tasks: finding low-rank approximations of matrices, computing matrix functions, and estimating the trace of matrices. In the first part, we consider algorithms for building ...

EPFL2022

DIVIDE-AND-CONQUER METHODS FOR FUNCTIONS OF MATRICES WITH BANDED OR HIERARCHICAL LOW-RANK STRUCTURE\ast

Daniel Kressner, Stefano Massei, Alice Cortinovis

This work is concerned with approximating matrix functions for banded matrices, hierarchically semiseparable matrices, and related structures. We develop a new divide-and-conquer method based on (rational) Krylov subspace methods for performing low-rank up ...

SIAM PUBLICATIONS2022

A PCP Theorem for Interactive Proofs and Applications

Alessandro Chiesa

The celebrated PCP Theorem states that any language in NP can be decided via a verifier that reads O(1) bits from a polynomially long proof. Interactive oracle proofs (IOP), a generalization of PCPs, allow the verifier to interact with the prover for multi ...

SPRINGER INTERNATIONAL PUBLISHING AG2022

Model order reduction based on functional rational approximants for parametric PDEs with meromorphic structure

Davide Pradovera

Many engineering fields rely on frequency-domain dynamical systems for the mathematical modeling of physical (electrical/mechanical/etc.) structures. With the growing need for more accurate and reliable results, the computational burden incurred by frequen ...

EPFL2021

Optimal Adversarial Policies in the Multiplicative Learning System With a Malicious Expert

Negar Kiyavash, Seyed Jalal Etesami

We consider a learning system based on the conventional multiplicative weight ( MW) rule that combines experts' advice to predict a sequence of true outcomes. It is assumed that one of the experts is malicious and aims to impose the maximum loss on the sys ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2021

A (2+epsilon)-Approximation Algorithm for Preemptive Weighted Flow Time on a Single Machine

Lars Rohwedder

Weighted flow time is a fundamental and very well-studied objective function in scheduling. In this paper, we study the setting of a single machine with preemptions. ...

ASSOC COMPUTING MACHINERY2021

Interpolatory Rational Model Order Reduction of Parametric Problems Lacking Uniform Inf-Sup Stability

Davide Pradovera

We present a technique for the approximation of a class of Hilbert space--valued maps which arise within the framework of model order reduction (MOR) for parametric partial differential equations, whose solution map has a meromorphic structure. Our MOR str ...

2020

Fast Least-Squares Padé approximation of problems with normal operators and meromorphic structure

Fabio Nobile, Francesca Bonizzoni, Davide Pradovera

In this work, we consider the approximation of Hilbert space-valued meromorphic functions that arise as solution maps of parametric PDEs whose operator is the shift of an operator with normal and compact resolvent, e.g., the Helmholtz equation. In this res ...

2020

Local approximation of the Maximum Cut in regular graphs

Etienne Michel François Bamas

This paper is devoted to the distributed complexity of finding an approximation of the maximum cut (MAXCUT) in graphs. A classical algorithm consists in letting each vertex choose its side of the cut uniformly at random. This does not require any communica ...

ELSEVIER2020

Generating Sparse Stochastic Processes Using Matched Splines

Michaël Unser, Leello Tadesse Dadi, Shayan Aziznejad

We provide an algorithm to generate trajectories of sparse stochastic processes that are solutions of linear ordinary differential equations driven by Levy white noises. A recent paper showed that these processes are limits in law of generalized compound-P ...

2020

Least-Squares Padé approximation of parametric and stochastic Helmholtz maps

Fabio Nobile, Francesca Bonizzoni, Davide Pradovera

The present work deals with rational model order reduction methods based on the single-point Least-Square (LS) Padé approximation techniques introduced in Bonizzoni et al. (ESAIM Math. Model. Numer. Anal., 52(4), 1261–1284 2018, Math. Comput. 89, 1229–1257 ...

2020

A p-weighted limiter for the discontinuous Galerkin method on one-dimensional and two-dimensional triangular grids

Qian Wang, Qian Wang

This paper presents an accuracy-preserving p-weighted limiter for discontinuous Galerkin methods on one-dimensional and two-dimensional triangular grids. The p-weighted limiter is the extension of the second-order WENO limiter by Li et al. [W. Li, J. Pan a ...

2020

Machine learning of multiscale active force generation models for the efficient simulation of cardiac electromechanics

Alfio Quarteroni, Francesco Regazzoni

High fidelity (HF) mathematical models describing the generation of active force in the cardiac muscle tissue typically feature a large number of state variables to capture the intrinsically complex underlying subcellular mechanisms. With the aim of drasti ...

2020

Energy-based comparison between the Fourier-Galerkin method and the finite element method

Thomas Willem Jan de Geus

The Fourier-Galerkin method (in short FFTH) has gained popularity in numerical homogenisation because it can treat problems with a huge number of degrees of freedom. Because the method incorporates the fast Fourier transform (FFT) in the linear solver, it ...

ELSEVIER2020

Adaptive algorithms for two fluids flows with anisotropic finite elements and order two time discretizations

Samuel Dubuis

This thesis is devoted to the derivation of a posteriori error estimates for the numerical approximation of fluids flows separated by a free surface. Based on these estimates, error indicators are introduced and adaptive algorithms are proposed to solve th ...

EPFL2020

Differentially Private Release of Synthetic Graphs

Mikhail Kapralov, Marek Elias

We propose a (epsilon, delta)-differentially private mechanism that, given an input graph G with n vertices and m edges, in polynomial time generates a synthetic graph G' approximating all cuts of the input graph up to an additive error of O (root mn/epsil ...

ASSOC COMPUTING MACHINERY2020

Distributed sampling for rational approximation of the acoustic scattering of an airfoil

Francesca Bonizzoni, Davide Pradovera

In this paper we compute a reduced order model for a time‐harmonic external acoustic scattering problem with parametric frequency. The employed technique is minimal rational interpolation, an explicit moment‐matching method for Hilbert space‐valued meromor ...

2019