Publications associées à Factorisation

K3 surfaces, cyclotomic polynomials and orthogonal groups

Let X be a complex projective K3 surface and let T-X be its transcendental lattice; the characteristic polynomials of isometries of T-X induced by automorphisms of X are powers of cyclotomic polynomials. Which powers of cyclotomic polynomials occur? The ai ...

Springer Int Publ Ag2024

Spectral Estimators for High-Dimensional Matrix Inference

Farzad Pourkamali

A key challenge across many disciplines is to extract meaningful information from data which is often obscured by noise. These datasets are typically represented as large matrices. Given the current trend of ever-increasing data volumes, with datasets grow ...

EPFL2024

Revisiting Offline Compression: Going Beyond Factorization-based Methods for Transformer Language Models

Karl Aberer, Rémi Philippe Lebret, Mohammadreza Banaei

Recent transformer language models achieve outstanding results in many natural language processing (NLP) tasks. However, their enormous size often makes them impractical on memory-constrained devices, requiring practitioners to compress them to smaller net ...

Assoc Computational Linguistics-Acl2023

The double exponential runtime is tight for 2-stage stochastic ILPs

Kim-Manuel Klein, Klaus Jansen, Alexandra Anna Lassota

We consider fundamental algorithmic number theoretic problems and their relation to a class of block structured Integer Linear Programs (ILPs) called 2-stage stochastic. A 2-stage stochastic ILP is an integer program of the form min{c(T)x vertical bar Ax = ...

SPRINGER HEIDELBERG2022

Optimal denoising of rotationally invariant rectangular matrices

Florent Gérard Krzakala, Lenka Zdeborová, Emanuele Troiani, Vittorio Erba

In this manuscript we consider denoising of large rectangular matrices: given a noisy observation of a signal matrix, what is the best way of recovering the signal matrix itself? For Gaussian noise and rotationally-invariant signal priors, we completely ch ...

2022

Recoloring subgraphs of K-2n for sports scheduling

Dominique de Werra

The exploration of one-factorizations of complete graphs is the foundation of some classical sports scheduling problems. One has to traverse the landscape of such one-factorizations by moving from one of those to a so-called neighbor one-factorization. Thi ...

ELSEVIER2021

Discrete-Choice Mining of Social Processes

Victor Kristof

Poor decisions and selfish behaviors give rise to seemingly intractable global problems, such as the lack of transparency in democratic processes, the spread of conspiracy theories, and the rise in greenhouse gas emissions. However, people are more predict ...

EPFL2021

Revisiting Multivariate Ring Learning with Errors and Its Applications on Lattice-Based Cryptography

Juan Ramón Troncoso-Pastoriza

The “Multivariate Ring Learning with Errors” problem was presented as a generalization of Ring Learning with Errors (RLWE), introducing efficiency improvements with respect to the RLWE counterpart thanks to its multivariate structure. Nevertheless, the rec ...

2021

Polynomial Evaluation on Superscalar Architecture, Applied to the Elementary Function e(x)

Felix Schürmann, Francesco Cremonesi, Timothée Ewart, Fabien Jonathan Delalondre

The evaluation of small degree polynomials is critical for the computation of elementary functions. It has been extensively studied and is well documented. In this article, we evaluate existing methods for polynomial evaluation on superscalar architecture. ...

2020

A hierarchical preconditioner for wave problems in quasilinear complexity

Jan Sickmann Hesthaven, Boris Bonev

The paper introduces a novel, hierarchical preconditioner based on nested dissection and hierarchical matrix compression. The preconditioner is intended for continuous and discontinuous Galerkin formulations of elliptic problems. We exploit the property th ...

2022

Kinetic Euclidean Distance Matrices

Martin Vetterli, Ivan Dokmanic, Puoya Tabaghi

Euclidean distance matrices (EDMs) are a major tool for localization from distances, with applications ranging from protein structure determination to global positioning and manifold learning. They are, however, static objects which serve to localize point ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2020

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

Mutual Information for Low-Rank Even-Order Symmetric Tensor Factorization

Nicolas Macris, Jean François Emmanuel Barbier, Clément Dominique Luneau

We consider a statistical model for finite-rank symmetric tensor factorization and prove a single-letter variational expression for its mutual information when the tensor is of even order. The proof uses the adaptive interpolation method, for which rank-on ...

IEEE2019

High-Resolution Data Sets Unravel the Effects of Sources and Meteorological Conditions on Nitrate and Its Gas-Particle Partitioning

Athanasios Nenes, Qianyu Zhao, Yan Feng

Nitrate is one of the most abundant inorganic water-soluble ions in fine particulate matter (PM2.5). However, the formation mechanism of nitrate in the ambient atmosphere, especially the impacts of its semivolatility and the various existing forms of nitro ...

2019

Petersson inner products of weight-one modular forms

Maryna Viazovska

In this paper we study the regularized Petersson product between a holomorphic theta series associated to a positive definite binary quadratic form and a weakly holomorphic weight-one modular form with integral Fourier coefficients. In [18], we proved that ...

2019

Efficient Preconditioning of hp-FEM Matrices by Hierarchical Low-Rank Approximations

Jan Sickmann Hesthaven, Paolo Gatto

We introduce a preconditioner based on a hierarchical low-rank compression scheme of Schur complements. The construction is inspired by standard nested dissection, and relies on the assumption that the Schur complements can be approximated, to high precisi ...

Springer Verlag2017

MRI artifact correction using sparse plus low-rank decomposition of annihilating filter-based hankel matrix

Kyong Hwan Jin

PurposeMagnetic resonance imaging (MRI) artifacts are originated from various sources including instability of an magnetic resonance (MR) system, patient motion, inhomogeneities of gradient fields, and so on. Such MRI artifacts are usually considered as ir ...

Wiley2017

FaCSI: A block parallel preconditioner for fluid-structure interaction in hemodynamics

Alfio Quarteroni, Simone Deparis, Davide Forti, Gwenol Grandperrin

Modeling Fluid-Structure Interaction (FSI) in the vascular system is mandatory to reliably compute mechanical indicators in vessels undergoing large deformations. In order to cope with the computational complexity of the coupled 3D FSI problem after discre ...

Academic Press Inc Elsevier Science2016

Efficient Incremental Data Analysis

Milos Nikolic

Many data-intensive applications require real-time analytics over streaming data. In a growing number of domains -- sensor network monitoring, social web applications, clickstream analysis, high-frequency algorithmic trading, and fraud detections to name a ...

EPFL2016

Fast Robust PCA on Graphs

Pierre Vandergheynst, Gilles Puy, Nathanaël Perraudin, Nauman Shahid, Vasilis Kalofolias

Mining useful clusters from high dimensional data has received significant attention of the computer vision and pattern recognition community in the recent years. Linear and non-linear dimensionality reduction has played an important role to overcome the c ...

Ieee-Inst Electrical Electronics Engineers Inc2016