Search

Your search keyword '"Brisebarre, Nicolas"' showing total 136 results
Start Over Author "Brisebarre, Nicolas"
136 results on '"Brisebarre, Nicolas"'

1. Path-metrics, pruning, and generalization

Author

Gonon, Antoine, Brisebarre, Nicolas, Riccietti, Elisa, and Gribonval, Rémi

Subjects
Computer Science - Machine Learning, Statistics - Machine Learning
Abstract

Analyzing the behavior of ReLU neural networks often hinges on understanding the relationships between their parameters and the functions they implement. This paper proves a new bound on function distances in terms of the so-called path-metrics of the parameters. Since this bound is intrinsically invariant with respect to the rescaling symmetries of the networks, it sharpens previously known bounds. It is also, to the best of our knowledge, the first bound of its kind that is broadly applicable to modern networks such as ResNets, VGGs, U-nets, and many more. In contexts such as network pruning and quantization, the proposed path-metrics can be efficiently computed using only two forward passes. Besides its intrinsic theoretical interest, the bound yields not only novel theoretical generalization bounds, but also a promising proof of concept for rescaling-invariant pruning.

Published
2024

2. A path-norm toolkit for modern networks: consequences, promises and challenges

Author

Gonon, Antoine, Brisebarre, Nicolas, Riccietti, Elisa, and Gribonval, Rémi

Subjects
Statistics - Machine Learning, Computer Science - Machine Learning, Mathematics - Statistics Theory
Abstract

This work introduces the first toolkit around path-norms that fully encompasses general DAG ReLU networks with biases, skip connections and any operation based on the extraction of order statistics: max pooling, GroupSort etc. This toolkit notably allows us to establish generalization bounds for modern neural networks that are not only the most widely applicable path-norm based ones, but also recover or beat the sharpest known bounds of this type. These extended path-norms further enjoy the usual benefits of path-norms: ease of computation, invariance under the symmetries of the network, and improved sharpness on layered fully-connected networks compared to the product of operator norms, another complexity measure most commonly used. The versatility of the toolkit and its ease of implementation allow us to challenge the concrete promises of path-norm-based generalization bounds, by numerically evaluating the sharpest known bounds for ResNets on ImageNet.

Published
2023

3. Differential-Difference Properties of Hypergeometric Series

Author

Brisebarre, Nicolas and Salvy, Bruno

Subjects
Mathematics - Classical Analysis and ODEs
Abstract

Six families of generalized hypergeometric series in a variable $x$ and an arbitrary number of parameters are considered. Each of them is indexed by an integer $n$. Linear recurrence relations in $n$ relate these functions and their product by the variable $x$. We give explicit factorizations of these equations as products of first order recurrence operators. Related recurrences are also derived for the derivative with respect to $x$. These formulas generalize well-known properties of the classical orthogonal polynomials., Comment: 14 pages. Revised version to appear in Proc. AMS

Published
2022

4. Approximation speed of quantized vs. unquantized ReLU neural networks and beyond

Author

Gonon, Antoine, Brisebarre, Nicolas, Gribonval, Rémi, and Riccietti, Elisa

Subjects
Computer Science - Information Theory, Computer Science - Neural and Evolutionary Computing
Abstract

We deal with two complementary questions about approximation properties of ReLU networks. First, we study how the uniform quantization of ReLU networks with real-valued weights impacts their approximation properties. We establish an upper-bound on the minimal number of bits per coordinate needed for uniformly quantized ReLU networks to keep the same polynomial asymptotic approximation speeds as unquantized ones. We also characterize the error of nearest-neighbour uniform quantization of ReLU networks. This is achieved using a new lower-bound on the Lipschitz constant of the map that associates the parameters of ReLU networks to their realization, and an upper-bound generalizing classical results. Second, we investigate when ReLU networks can be expected, or not, to have better approximation properties than other classical approximation families. Indeed, several approximation families share the following common limitation: their polynomial asymptotic approximation speed of any set is bounded from above by the encoding speed of this set. We introduce a new abstract property of approximation families, called infinite-encodability, which implies this upper-bound. Many classical approximation families, defined with dictionaries or ReLU networks, are shown to be infinite-encodable. This unifies and generalizes several situations where this upper-bound is known.

Published
2022

6. On a two-valued sequence and related continued fractions in power series fields

Author

Allombert, Bill, Brisebarre, Nicolas, and Lasjaunias, Alain

Subjects
Mathematics - Number Theory
Abstract

We explicitly describe a noteworthy transcendental continued fraction in the field of power series over Q, having irrationality measure equal to 3. This continued fraction is a generating function of a particular sequence in the set {1, 2}. The origin of this sequence, whose study was initiated in a recent paper, is to be found in another continued fraction, in the field of power series over $\mathbb{F}\_3$, which satisfies a simple algebraic equation of degree 4, introduced thirty years ago by D. Robbins.

Published
2016

10. Testing The Sharpness of Known Error Bounds on The Fast Fourier Transform

Author

Brisebarre, Nicolas, Muller, Jean-Michel, Picot, Joris, Arithmétiques des ordinateurs, méthodes formelles, génération de code (ARIC), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS), École normale supérieure de Lyon (ENS de Lyon), and ANR-20-CE48-0014,NuSCAP,Sûreté numérique pour les preuves assistées par ordinateur(2020)

Subjects
Fast Fourier Transform (FFT), Error analysis, [INFO.INFO-AO]Computer Science [cs]/Computer Arithmetic, Floating-Point arithmetic, [INFO.INFO-MS]Computer Science [cs]/Mathematical Software [cs.MS]
Abstract

International audience; The computation of Fast Fourier Transforms (FFTs) in floating-point arithmetic is inexact due to roundings, and for some applications it can prove very useful to know a tight bound on the final error. Although it can be almost attained by specifically built input values, the best known error bound for the Cooley-Tukey FFT seems to be much larger than most actually obtained errors. Also, interval arithmetic can be used to compute a bound on the error committed with a given set of input values, but it is in general considered hampered with large overestimation. We report results of intensive computations to test the two approaches, in order to estimate the numerical performance of state-of-the-art bounds. Surprisingly enough, we observe that while interval arithmetic-based bounds are overestimated, they remain, in our computations, tighter than general known bounds.

Published
2023

12. Finding the 'truncated' polynomial that is closest to a function

Author

Brisebarre, Nicolas and Muller, Jean-Michel

Subjects
Computer Science - Mathematical Software, G.1.0, G.1.2, B.2.4
Abstract

When implementing regular enough functions (e.g., elementary or special functions) on a computing system, we frequently use polynomial approximations. In most cases, the polynomial that best approximates (for a given distance and in a given interval) a function has coefficients that are not exactly representable with a finite number of bits. And yet, the polynomial approximations that are actually implemented do have coefficients that are represented with a finite - and sometimes small - number of bits: this is due to the finiteness of the floating-point representations (for software implementations), and to the need to have small, hence fast and/or inexpensive, multipliers (for hardware implementations). We then have to consider polynomial approximations for which the degree-$i$ coefficient has at most $m_i$ fractional bits (in other words, it is a rational number with denominator $2^{m_i}$). We provide a general method for finding the best polynomial approximation under this constraint. Then, we suggest refinements than can be used to accelerate our method., Comment: 14 pages, 1 figure

Published
2003

13. Towards Machine-Efficient Rational L ∞ -Approximations of Mathematical Functions

Author

Brisebarre, Nicolas, Filip, Silviu-Ioan, Arithmétiques des ordinateurs, méthodes formelles, génération de code (ARIC), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS), Architectures matérielles spécialisées pour l’ère post loi-de-Moore (TARAN), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-ARCHITECTURE (IRISA-D3), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), COMIN Labs LeanAI, ANR-20-CE48-0014,NuSCAP,Sûreté numérique pour les preuves assistées par ordinateur(2020), and ANR-10-LABX-0007,COMIN Labs,Digital Communication and Information Sciences for the Future Internet(2010)

Subjects
[INFO.INFO-AO]Computer Science [cs]/Computer Arithmetic, [INFO.INFO-NA]Computer Science [cs]/Numerical Analysis [cs.NA]
Abstract

To appear in the proceedings of the 30th IEEE Symposium on Computer Arithmetic (ARITH-30), Portland (Oregon, USA), September 2023.; International audience; Software implementations of mathematical functions often use approximations that can be either polynomial or rational in nature. While polynomials are the preferred approximation in most cases, rational approximations are nevertheless an interesting alternative when dealing with functions that have a pronounced "nonpolynomial behavior" (such as poles close to the approximation domain, asymptotes or finite limits at ±∞). The major challenge is that of computing good rational approximations with machine number coefficients (e.g. floatingpoint or fixed-point) with respect to the supremum norm, a key step in most procedures for evaluating a mathematical function. This is made more complicated by the fact that even when dealing with real-valued coefficients, optimal supremum norm solutions are sometimes difficult to obtain. Here, we introduce flexible and fast algorithms for computing such rational approximations with both real and machine number coefficients. Their effectiveness is explored on several examples.

Published
2023

14. Error in ulps of the multiplication or division by a correctly-rounded function or constant in binary floating-point arithmetic

Author

Brisebarre, Nicolas, Muller, Jean-Michel, Picot, Joris, Arithmétiques des ordinateurs, méthodes formelles, génération de code (ARIC), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS), École normale supérieure de Lyon (ENS de Lyon), and ANR-20-CE48-0014,NuSCAP,Sûreté numérique pour les preuves assistées par ordinateur(2020)

Subjects
numerical error, ulp, [INFO.INFO-AO]Computer Science [cs]/Computer Arithmetic, Floating-point arithmetic, correct rounding, multiplication by a constant
Abstract

International audience; Assume we use a binary floating-point arithmetic and that RN is the round-to-nearest function. Also assume that c is a constant or a real function of one or more variables, and that we have at our disposal a correctly rounded implementation of c, say ĉ = RN(c). For evaluating x • c (resp. x/c or c/x), the natural way is to replace it by RN(x • ĉ) (resp. RN(x/ĉ) or RN(ĉ/x)), that is, to call function ĉ and to perform a floatingpoint multiplication or division. This can be generalized to the approximation of n/d by RN(^n/ ^d) and the approximation of n • d by RN(^n • ^d), where ^n = RN(n) and ^d = RN(d), and n and d are functions for which we have at our disposal a correctly rounded implementation. We discuss tight error bounds in ulps of such approximations. From our results, one immediately obtains tight error bounds for calculations such as x * pi, ln(2)/x, x/(y + z), (x + y) * z, x/sqrt(y), sqrt(x)/y, (x + y)(z + t), (x + y)/(z + t), (x + y)/(zt), etc. in floating-point arithmetic.

Published
2023

16. Le dilemme du fabricant de tables

Author

Boldo, Sylvie, Brisebarre, Nicolas, Muller, Jean-Michel, Formally Verified Programs, Certified Tools and Numerical Computations (TOCCATA), Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Méthodes Formelles (LMF), Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Ecole Normale Supérieure Paris-Saclay (ENS Paris Saclay)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-Ecole Normale Supérieure Paris-Saclay (ENS Paris Saclay), Arithmétiques des ordinateurs, méthodes formelles, génération de code (ARIC), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS), ANR-20-CE48-0014,NuSCAP,Sûreté numérique pour les preuves assistées par ordinateur(2020), and European Project: 810367,EMC2(2019)

Subjects
[INFO.INFO-AO]Computer Science [cs]/Computer Arithmetic
Abstract

National audience

Published
2023

17. Appendix: Number Theory Tools for Floating-Point Arithmetic

Author

Muller, Jean-Michel, Brisebarre, Nicolas, de Dinechin, Florent, Jeannerod, Claude-Pierre, Lefèvre, Vincent, Melquiond, Guillaume, Revol, Nathalie, Stehlé, Damien, Torres, Serge, Muller, Jean-Michel, Brisebarre, Nicolas, de Dinechin, Florent, Jeannerod, Claude-Pierre, Lefèvre, Vincent, Melquiond, Guillaume, Revol, Nathalie, Stehlé, Damien, and Torres, Serge

Published
2010
Full Text
View/download PDF

18. Extending the Precision

Author

Muller, Jean-Michel, Brisebarre, Nicolas, de Dinechin, Florent, Jeannerod, Claude-Pierre, Lefèvre, Vincent, Melquiond, Guillaume, Revol, Nathalie, Stehlé, Damien, Torres, Serge, Muller, Jean-Michel, Brisebarre, Nicolas, de Dinechin, Florent, Jeannerod, Claude-Pierre, Lefèvre, Vincent, Melquiond, Guillaume, Revol, Nathalie, Stehlé, Damien, and Torres, Serge

Published
2010
Full Text
View/download PDF

19. Formalisms for Certifying Floating-Point Algorithms

Author

Muller, Jean-Michel, Brisebarre, Nicolas, de Dinechin, Florent, Jeannerod, Claude-Pierre, Lefèvre, Vincent, Melquiond, Guillaume, Revol, Nathalie, Stehlé, Damien, Torres, Serge, Muller, Jean-Michel, Brisebarre, Nicolas, de Dinechin, Florent, Jeannerod, Claude-Pierre, Lefèvre, Vincent, Melquiond, Guillaume, Revol, Nathalie, Stehlé, Damien, and Torres, Serge

Published
2010
Full Text
View/download PDF

20. Evaluating Floating-Point Elementary Functions

Author

Muller, Jean-Michel, Brisebarre, Nicolas, de Dinechin, Florent, Jeannerod, Claude-Pierre, Lefèvre, Vincent, Melquiond, Guillaume, Revol, Nathalie, Stehlé, Damien, Torres, Serge, Muller, Jean-Michel, Brisebarre, Nicolas, de Dinechin, Florent, Jeannerod, Claude-Pierre, Lefèvre, Vincent, Melquiond, Guillaume, Revol, Nathalie, Stehlé, Damien, and Torres, Serge

Published
2010
Full Text
View/download PDF

21. Solving the Table Maker’s Dilemma

Author

Muller, Jean-Michel, Brisebarre, Nicolas, de Dinechin, Florent, Jeannerod, Claude-Pierre, Lefèvre, Vincent, Melquiond, Guillaume, Revol, Nathalie, Stehlé, Damien, Torres, Serge, Muller, Jean-Michel, Brisebarre, Nicolas, de Dinechin, Florent, Jeannerod, Claude-Pierre, Lefèvre, Vincent, Melquiond, Guillaume, Revol, Nathalie, Stehlé, Damien, and Torres, Serge

Published
2010
Full Text
View/download PDF

22. Software Implementation of Floating-Point Arithmetic

Author

Muller, Jean-Michel, Brisebarre, Nicolas, de Dinechin, Florent, Jeannerod, Claude-Pierre, Lefèvre, Vincent, Melquiond, Guillaume, Revol, Nathalie, Stehlé, Damien, Torres, Serge, Muller, Jean-Michel, Brisebarre, Nicolas, de Dinechin, Florent, Jeannerod, Claude-Pierre, Lefèvre, Vincent, Melquiond, Guillaume, Revol, Nathalie, Stehlé, Damien, and Torres, Serge

Published
2010
Full Text
View/download PDF

23. Hardware Implementation of Floating-Point Arithmetic

Author

Muller, Jean-Michel, Brisebarre, Nicolas, de Dinechin, Florent, Jeannerod, Claude-Pierre, Lefèvre, Vincent, Melquiond, Guillaume, Revol, Nathalie, Stehlé, Damien, Torres, Serge, Muller, Jean-Michel, Brisebarre, Nicolas, de Dinechin, Florent, Jeannerod, Claude-Pierre, Lefèvre, Vincent, Melquiond, Guillaume, Revol, Nathalie, Stehlé, Damien, and Torres, Serge

Published
2010
Full Text
View/download PDF

24. Basic Properties and Algorithms

Author

Muller, Jean-Michel, Brisebarre, Nicolas, de Dinechin, Florent, Jeannerod, Claude-Pierre, Lefèvre, Vincent, Melquiond, Guillaume, Revol, Nathalie, Stehlé, Damien, Torres, Serge, Muller, Jean-Michel, Brisebarre, Nicolas, de Dinechin, Florent, Jeannerod, Claude-Pierre, Lefèvre, Vincent, Melquiond, Guillaume, Revol, Nathalie, Stehlé, Damien, and Torres, Serge

Published
2010
Full Text
View/download PDF

25. Algorithms for the Five Basic Operations

Author

Muller, Jean-Michel, Brisebarre, Nicolas, de Dinechin, Florent, Jeannerod, Claude-Pierre, Lefèvre, Vincent, Melquiond, Guillaume, Revol, Nathalie, Stehlé, Damien, Torres, Serge, Muller, Jean-Michel, Brisebarre, Nicolas, de Dinechin, Florent, Jeannerod, Claude-Pierre, Lefèvre, Vincent, Melquiond, Guillaume, Revol, Nathalie, Stehlé, Damien, and Torres, Serge

Published
2010
Full Text
View/download PDF

26. Languages and Compilers

Author

Muller, Jean-Michel, Brisebarre, Nicolas, de Dinechin, Florent, Jeannerod, Claude-Pierre, Lefèvre, Vincent, Melquiond, Guillaume, Revol, Nathalie, Stehlé, Damien, Torres, Serge, Muller, Jean-Michel, Brisebarre, Nicolas, de Dinechin, Florent, Jeannerod, Claude-Pierre, Lefèvre, Vincent, Melquiond, Guillaume, Revol, Nathalie, Stehlé, Damien, and Torres, Serge

Published
2010
Full Text
View/download PDF

27. Enhanced Floating-Point Sums, Dot Products, and Polynomial Values

Author

Muller, Jean-Michel, Brisebarre, Nicolas, de Dinechin, Florent, Jeannerod, Claude-Pierre, Lefèvre, Vincent, Melquiond, Guillaume, Revol, Nathalie, Stehlé, Damien, Torres, Serge, Muller, Jean-Michel, Brisebarre, Nicolas, de Dinechin, Florent, Jeannerod, Claude-Pierre, Lefèvre, Vincent, Melquiond, Guillaume, Revol, Nathalie, Stehlé, Damien, and Torres, Serge

Published
2010
Full Text
View/download PDF

28. Floating-Point Formats and Environment

Author

Muller, Jean-Michel, Brisebarre, Nicolas, de Dinechin, Florent, Jeannerod, Claude-Pierre, Lefèvre, Vincent, Melquiond, Guillaume, Revol, Nathalie, Stehlé, Damien, Torres, Serge, Muller, Jean-Michel, Brisebarre, Nicolas, de Dinechin, Florent, Jeannerod, Claude-Pierre, Lefèvre, Vincent, Melquiond, Guillaume, Revol, Nathalie, Stehlé, Damien, and Torres, Serge

Published
2010
Full Text
View/download PDF

29. The Fused Multiply-Add Instruction

Author

Muller, Jean-Michel, Brisebarre, Nicolas, de Dinechin, Florent, Jeannerod, Claude-Pierre, Lefèvre, Vincent, Melquiond, Guillaume, Revol, Nathalie, Stehlé, Damien, Torres, Serge, Muller, Jean-Michel, Brisebarre, Nicolas, de Dinechin, Florent, Jeannerod, Claude-Pierre, Lefèvre, Vincent, Melquiond, Guillaume, Revol, Nathalie, Stehlé, Damien, and Torres, Serge

Published
2010
Full Text
View/download PDF

30. Definitions and Basic Notions

Author

Muller, Jean-Michel, Brisebarre, Nicolas, de Dinechin, Florent, Jeannerod, Claude-Pierre, Lefèvre, Vincent, Melquiond, Guillaume, Revol, Nathalie, Stehlé, Damien, Torres, Serge, Muller, Jean-Michel, Brisebarre, Nicolas, de Dinechin, Florent, Jeannerod, Claude-Pierre, Lefèvre, Vincent, Melquiond, Guillaume, Revol, Nathalie, Stehlé, Damien, and Torres, Serge

Published
2010
Full Text
View/download PDF

31. Introduction

Author

Muller, Jean-Michel, Brisebarre, Nicolas, de Dinechin, Florent, Jeannerod, Claude-Pierre, Lefèvre, Vincent, Melquiond, Guillaume, Revol, Nathalie, Stehlé, Damien, Torres, Serge, Muller, Jean-Michel, Brisebarre, Nicolas, de Dinechin, Florent, Jeannerod, Claude-Pierre, Lefèvre, Vincent, Melquiond, Guillaume, Revol, Nathalie, Stehlé, Damien, and Torres, Serge

Published
2010
Full Text
View/download PDF

32. Differential-difference properties of hypergeometric series.

Author

Brisebarre, Nicolas and Salvy, Bruno

Subjects
*YANG-Baxter equation, *ORTHOGONAL polynomials, *HYPERGEOMETRIC functions, *ARBITRARY constants, *HYPERGEOMETRIC series, *INTEGERS
Abstract

Six families of generalized hypergeometric series in a variable x and an arbitrary number of parameters are considered. Each of them is indexed by an integer n. Linear recurrence relations in n relate these functions and their product by the variable x. We give explicit factorizations of these equations as products of first order recurrence operators. Related recurrences are also derived for the derivative with respect to x. These formulas generalize well-known properties of the classical orthogonal polynomials. [ABSTRACT FROM AUTHOR]

Published
2023
Full Text
View/download PDF

34. Efficient and Validated Numerical Evaluation of Abelian Integrals

Author

Bréhard, Florent, Brisebarre, Nicolas, Joldeş, Mioara, Tucker, Warwick, Centre National de la Recherche Scientifique (CNRS), Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Arithmetic and Computing (ARIC), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes (LAAS-ROC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), School of Mathematics [Australia], Monash University [Melbourne], ANR-20-CE48-0014,NuSCAP,Sûreté numérique pour les preuves assistées par ordinateur(2020), Brisebarre, Nicolas, and Sûreté numérique pour les preuves assistées par ordinateur - - NuSCAP2020 - ANR-20-CE48-0014 - AAPG2020 - VALID

Subjects
[INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], limit cycles, [INFO.INFO-SC] Computer Science [cs]/Symbolic Computation [cs.SC], [INFO.INFO-AO]Computer Science [cs]/Computer Arithmetic, Abelian integral, [MATH.MATH-DS]Mathematics [math]/Dynamical Systems [math.DS], Newton-like operator, [MATH.MATH-DS] Mathematics [math]/Dynamical Systems [math.DS], rigorous numerics, Hilbert's 16th problem, [INFO.INFO-NA]Computer Science [cs]/Numerical Analysis [cs.NA], 2020 AMS classification: Primary: 34C07, Secondary: 37G15, 37M20, 42A10, 42A15, 65G20, [INFO.INFO-NA] Computer Science [cs]/Numerical Analysis [cs.NA], ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, [INFO.INFO-AO] Computer Science [cs]/Computer Arithmetic, trigonometric polynomial interpolation
Abstract

Abelian integrals play a key role in the infinitesimal version of Hilbert's 16th problem. Being able to evaluate such integrals - with guaranteed error bounds - is a fundamental step in computer-aided proofs aimed at this problem. Using interpolation by trigonometric polynomials and quasi-Newton-Kantorovitch validation, we develop a validated numerics method for computing Abelian integrals in a quasi-linear number of arithmetic operations. Our approach is both effective, as exemplified on two practical perturbed integrable systems, and amenable to an implementation in a formal proof assistant, which is key to provide fully reliable computer-aided proofs.

Published
2022

35. Rigorous Polynomial Approximation Using Taylor Models in Coq

Author

Brisebarre, Nicolas, Joldeş, Mioara, Martin-Dorel, Érik, Mayero, Micaela, Muller, Jean-Michel, Paşca, Ioana, Rideau, Laurence, Théry, Laurent, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Goodloe, Alwyn E., editor, and Person, Suzette, editor

Published
2012
Full Text
View/download PDF

36. A Comparison between Hardware Accelerators for the Modified Tate Pairing over

Author

Beuchat, Jean-Luc, Brisebarre, Nicolas, Detrey, Jérémie, Okamoto, Eiji, Rodríguez-Henríquez, Francisco, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Galbraith, Steven D., editor, and Paterson, Kenneth G., editor

Published
2008
Full Text
View/download PDF

37. Arithmetic Operators for Pairing-Based Cryptography

Author

Beuchat, Jean-Luc, Brisebarre, Nicolas, Detrey, Jérémie, Okamoto, Eiji, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Paillier, Pascal, editor, and Verbauwhede, Ingrid, editor

Published
2007
Full Text
View/download PDF

38. A Coprocessor for the Final Exponentiation of the η T Pairing in Characteristic Three

Author

Beuchat, Jean-Luc, Brisebarre, Nicolas, Shirase, Masaaki, Takagi, Tsuyoshi, Okamoto, Eiji, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Carlet, Claude, editor, and Sunar, Berk, editor

Published
2007
Full Text
View/download PDF

39. Integer points close to a transcendental curve and correctly-rounded evaluation of a function

Author

Brisebarre, Nicolas, Hanrot, Guillaume, Arithmetic and Computing (ARIC), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Lyon (ENS Lyon), ANR-20-CE48-0014,NuSCAP,Sûreté numérique pour les preuves assistées par ordinateur(2020), ANR-10-BLAN-0203,TaMaDi,Dilemme du Fabricant de Tables(2010), ANR-14-CE25-0018,Fast Relax,Approximation rapide et fiable(2014), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Arithmétiques des ordinateurs, méthodes formelles, génération de code (ARIC), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), and École normale supérieure de Lyon (ENS de Lyon)

Subjects
algorithmic number theory, AMS 2020 : Primary 11Y99, 41A05, 65G50, Secondary 11D75, 11J25, [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], [INFO.INFO-AO]Computer Science [cs]/Computer Arithmetic, lattice basis reduction, LLL algorithm, correct rounding, Computer arithmetic, approximation theory, [MATH.MATH-NT]Mathematics [math]/Number Theory [math.NT]
Abstract

Despite several significant advances over the last 30 years, guaranteeing the correctly rounded evaluation of elementary functions, such as $\cos, \exp, \sqrt[3]{\cdot}$ for instance, is still a difficult issue. This can be formulated as a Diophantine approximation problem, called the Table Maker’s Dilemma, which consists in determining points with integer coordinates that are close to a curve. In this article, we propose two algorithmic approaches to tackle this problem, closely related to a celebrated work by Bombieri and Pila and to the so-called Coppersmith's method. We establish the underlying theoretical foundations, prove the algorithms, study their complexity and present practical experiments; we also compare our approach with previously existing ones. In particular, our results show that the development of a correctly rounded mathematical library for the binary128 format is now possible at a much smaller cost than with previously existing approaches.

Published
2021

40. Conclusion and Perspectives

Author

Muller, Jean-Michel, Brisebarre, Nicolas, de Dinechin, Florent, Jeannerod, Claude-Pierre, Lefèvre, Vincent, Melquiond, Guillaume, Revol, Nathalie, Stehlé, Damien, Torres, Serge, Muller, Jean-Michel, Brisebarre, Nicolas, de Dinechin, Florent, Jeannerod, Claude-Pierre, Lefèvre, Vincent, Melquiond, Guillaume, Revol, Nathalie, Stehlé, Damien, and Torres, Serge

Published
2010
Full Text
View/download PDF

41. Algorithms and arithmetic operators for computing the eta-T pairing in characteristic three

Author

Beuchat, Jean-Luc, Brisebarre, Nicolas, Detrey, Jeremie, Okamoto, Eiji, Shirase, Masaaki, and Takagi, Tsuyoshi

Subjects
Programmable logic array, Curves, Elliptic -- Research, Ellipse -- Research, Modular arithmetic -- Research, Digital integrated circuits -- Research, Arithmetic logic unit -- Research, Computer arithmetic and logic units -- Research
Published
2008

43. Computing machine-efficient polynomial approximations

Author

Brisebarre, Nicolas, Muller, Jean-Michel, and Inria, Arnaud Tisserand

Subjects
Chebyshev approximation -- Research, Computational complexity -- Research, Polynomials -- Usage, Polynomials -- Methods
Abstract

Polynomial approximations are almost always used when implementing functions on a computing system. In most cases, the polynomial that best approximates (for a given distance and in a given interval) a function has coefficients that are not exactly representable with a finite number of bits. And yet, the polynomial approximations that are actually implemented do have coefficients that are represented with a finite--and sometimes small--number of bits. This is due to the finiteness of the floating-point representations (for software implementations), and to the need to have small, hence fast and/or inexpensive, multipliers (for hardware implementations). We then have to consider polynomial approximations for which the degree-i coefficient has at most [m.sub.i] fractional bits; in other words, it is a rational number with denominator [2.sup.m.sub.i]. We provide a general and efficient method for finding the best polynomial approximation under this constraint. Moreover, our method also applies if some other constraints (such as requiring some coefficients to be equal to some predefined constants or minimizing relative error instead of absolute error) are required. Categories and Subject Descriptors: G.1.0 [Numerical Analysis]: General--Computer arithmetic; G.1.2 [Numerical Analysis]: Approximation; B.2.4 [Arithmetic and Logic Structures]: High-Speed Arithmetic General Terms: Algorithms, Performance Additional Key Words and Phrases: Polynomial approximation, minimax approximation, floating-point arithmetic, Chebyshev polynomials, polytopes, linear programming

Published
2006

45. Handbook of Floating-Point Arithmetic

Author

Muller, Jean-Michel, primary, Brisebarre, Nicolas, additional, de Dinechin, Florent, additional, Jeannerod, Claude-Pierre, additional, Lefèvre, Vincent, additional, Melquiond, Guillaume, additional, Revol, Nathalie, additional, Stehlé, Damien, additional, and Torres, Serge, additional

Published
2010
Full Text
View/download PDF

46. The Fused Multiply-Add Instruction

Author

Muller, Jean-Michel, primary, Brisebarre, Nicolas, additional, de Dinechin, Florent, additional, Jeannerod, Claude-Pierre, additional, Lefèvre, Vincent, additional, Melquiond, Guillaume, additional, Revol, Nathalie, additional, Stehlé, Damien, additional, and Torres, Serge, additional

Published
2009
Full Text
View/download PDF

47. Evaluating Floating-Point Elementary Functions

Author

Muller, Jean-Michel, primary, Brisebarre, Nicolas, additional, de Dinechin, Florent, additional, Jeannerod, Claude-Pierre, additional, Lefèvre, Vincent, additional, Melquiond, Guillaume, additional, Revol, Nathalie, additional, Stehlé, Damien, additional, and Torres, Serge, additional

Published
2009
Full Text
View/download PDF

49. Formalisms for Certifying Floating-Point Algorithms

Author

Muller, Jean-Michel, primary, Brisebarre, Nicolas, additional, de Dinechin, Florent, additional, Jeannerod, Claude-Pierre, additional, Lefèvre, Vincent, additional, Melquiond, Guillaume, additional, Revol, Nathalie, additional, Stehlé, Damien, additional, and Torres, Serge, additional

Published
2009
Full Text
View/download PDF

50. Floating-Point Formats and Environment

Author

Muller, Jean-Michel, primary, Brisebarre, Nicolas, additional, de Dinechin, Florent, additional, Jeannerod, Claude-Pierre, additional, Lefèvre, Vincent, additional, Melquiond, Guillaume, additional, Revol, Nathalie, additional, Stehlé, Damien, additional, and Torres, Serge, additional

Published
2009
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results