Search

Your search keyword '"Performance et Qualité des Algorithmes Numériques (PEQUAN)"' showing total 406 results
Start Over Author "Performance et Qualité des Algorithmes Numériques (PEQUAN)"
406 results on '"Performance et Qualité des Algorithmes Numériques (PEQUAN)"'

1. A Coq formalization of digital filters

Author

Thibault Hilaire, Diane Gallois-Wong, Sylvie Boldo, Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Formally Verified Programs, Certified Tools and Numerical Computations (TOCCATA), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-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), Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Florian Rabe, William M. Farmer, Grant O. Passmore, Abdou Youssef, CentraleSupélec-Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS), CentraleSupélec-Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS)-CentraleSupélec-Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Laboratoire de Recherche en Informatique ( LRI ), Université Paris-Sud - Paris 11 ( UP11 ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -CentraleSupélec-Centre National de la Recherche Scientifique ( CNRS ), Certified Programs, Certified Tools, Certified Floating-Point Computations ( TOCCATA ), Université Paris-Sud - Paris 11 ( UP11 ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -CentraleSupélec-Centre National de la Recherche Scientifique ( CNRS ) -Université Paris-Sud - Paris 11 ( UP11 ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -CentraleSupélec-Centre National de la Recherche Scientifique ( CNRS ) -Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique ( Inria ), Performance et Qualité des Algorithmes Numériques ( PEQUAN ), Laboratoire d'Informatique de Paris 6 ( LIP6 ), and Université Pierre et Marie Curie - Paris 6 ( UPMC ) -Centre National de la Recherche Scientifique ( CNRS ) -Université Pierre et Marie Curie - Paris 6 ( UPMC ) -Centre National de la Recherche Scientifique ( CNRS )

Subjects
0209 industrial biotechnology, Signal processing, business.industry, Computer science, [INFO.INFO-AO]Computer Science [cs]/Computer Arithmetic, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], 0102 computer and information sciences, 02 engineering and technology, Filter (signal processing), 01 natural sciences, [ INFO.INFO-AO ] Computer Science [cs]/Computer Arithmetic, 020901 industrial engineering & automation, 010201 computation theory & mathematics, Control theory, Application domain, [ INFO.INFO-LO ] Computer Science [cs]/Logic in Computer Science [cs.LO], State (computer science), business, Digital filter, Equivalence (measure theory), Algorithm, Digital signal processing
Abstract

International audience; Digital filters are small iterative algorithms, used as basic bricks in signal processing (filters) and control theory (controllers). They receive as input a stream of values, and output another stream of values, computed from their internal state and from the previous inputs. These systems can be found in communication, aeronautics, automotive, robotics, etc. As the application domain may be critical, we aim at providing a formal guarantee of the good behavior of these algorithms in time-domain. In particular, we formally proved in Coq some error analysis theorems about digital filters, namely the Worst-Case Peak Gain theorem and the existence of a filter characterizing the difference between the exact filter and the implemented one. Moreover, the digital signal processing literature provides us with many equivalent algorithms, called realizations. We formally defined and proved the equivalence of several realizations (Direct Forms and State-Space).

Published
2018

2. Fast and rigorous arbitrary-precision computation of Gauss-Legendre quadrature nodes and weights

Author

Marc Mezzarobba, Fredrik Johansson, Lithe and fast algorithmic number theory (LFANT), Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), ANR-14-CE25-0018,Fast Relax,Approximation rapide et fiable(2014), Lithe and fast algorithmic number theory ( LFANT ), Institut de Mathématiques de Bordeaux ( IMB ), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Université de Bordeaux ( UB ) -Institut Polytechnique de Bordeaux ( Bordeaux INP ) -Centre National de la Recherche Scientifique ( CNRS ) -Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Université de Bordeaux ( UB ) -Institut Polytechnique de Bordeaux ( Bordeaux INP ) -Centre National de la Recherche Scientifique ( CNRS ) -Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National de Recherche en Informatique et en Automatique ( Inria ), Performance et Qualité des Algorithmes Numériques ( PEQUAN ), Laboratoire d'Informatique de Paris 6 ( LIP6 ), Université Pierre et Marie Curie - Paris 6 ( UPMC ) -Centre National de la Recherche Scientifique ( CNRS ) -Université Pierre et Marie Curie - Paris 6 ( UPMC ) -Centre National de la Recherche Scientifique ( CNRS ), ANR-14-CE25-0018,Fast Relax,Fast Reliable Approximation ( 2014 ), and Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest

Subjects
FOS: Computer and information sciences, arbitrary-precision arithmetic, [ INFO.INFO-NA ] Computer Science [cs]/Numerical Analysis [cs.NA], interval arithmetic AMS subject classifications 65Y99, MathematicsofComputing_NUMERICALANALYSIS, AMS subject classifications. 65Y99, 65G99, 33C45, 010103 numerical & computational mathematics, interval arithmetic, 01 natural sciences, Interval arithmetic, symbols.namesake, Arbitrary-precision arithmetic, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, FOS: Mathematics, 0101 mathematics, Hypergeometric function, Legendre polynomials, Newton's method, Mathematics, 65G99, [INFO.INFO-MS]Computer Science [cs]/Mathematical Software [cs.MS], Applied Mathematics, 010102 general mathematics, Computer Science - Numerical Analysis, Gauss-Legendre quadrature, Numerical Analysis (math.NA), Gauss–Legendre quadrature, [INFO.INFO-NA]Computer Science [cs]/Numerical Analysis [cs.NA], 33C45, Numerical integration, Quadrature (mathematics), Computational Mathematics, [ INFO.INFO-MS ] Computer Science [cs]/Mathematical Software [cs.MS], symbols, Gaussian quadrature, Computer Science - Mathematical Software, Mathematical Software (cs.MS), Algorithm
Abstract

International audience; We describe a strategy for rigorous arbitrary-precision evaluation of Legendre polynomials on the unit interval and its application in the generation of Gauss-Legendre quadrature rules. Our focus is on making the evaluation practical for a wide range of realistic parameters, corresponding to the requirements of numerical integration to an accuracy of about 100 to 100 000 bits. Our algorithm combines the summation by rectangular splitting of several types of expansions in terms of hypergeometric series with a fixed-point implementation of Bonnet's three-term recurrence relation. We then compute rigorous enclosures of the Gauss-Legendre nodes and weights using the interval Newton method. We provide rigorous error bounds for all steps of the algorithm. The approach is validated by an implementation in the Arb library, which achieves order-of-magnitude speedups over previous code for computing Gauss-Legendre rules with simultaneous high degree and precision.

Published
2018

3. Scaling is all you need: quantization of butterfly matrix products via optimal rank-one quantization

Author

Gribonval, Rémi, Mary, Theo, Riccietti, Elisa, Optimisation, Connaissances pHysiques, Algorithmes et Modèles (OCKHAM), 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)-Institut Rhône-Alpin des systèmes complexes (IXXI), École normale supérieure de Lyon (ENS de Lyon)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), GDR ISIS project MOMIGS, and ANR-19-CHIA-0009,AllegroAssai,Algorithmes, Approximations, Parcimonie et Plongements pour l'IA(2019)

Subjects
butterfly, sparse matrices, Quantization, rank one, [INFO]Computer Science [cs], Floating point arithmetic
Abstract

We consider the problem of quantizing the factors of butterfly factorizations. We show how the properties of butterfly supports can be exploited to reduce the problem to the solution of a series of rank-one quantization problems. We thus propose an algorithm that, exploiting the intrinsic scaling invariance of the problem, gives the optimal solution of the rank-one quantization problem. We employ this algorithm as a building block in a heuristic procedure to solve the quantization problem of butterfly factors, which we show can be much more accurate that the naive round-to-nearest startegy of quantizing each factor independently.; On s'intéresse à la quantification des facteurs dans un produit de matrices creuses à structure papillon. On montre que les propriétés particulières es supports des facteurs papillon permettent d'aborder le problème comme une séquence de problème de quantification de rang un. On propose un algorithme optimal de quantification de rang un utilisant les invariances du problème par remise à l'échelle. Cet algorithme sert de brique de base dans une approche heuristique pour la quantification de produits papillon, qui s'avère bien plus précis qu'une approche naive basée sur la quantification de chaque facteur au plus proche voisin indépendamment.

Published
2023

4. Optimal quantization of rank-one matrices in floating-point arithmetic---with applications to butterfly factorizations

Author

Gribonval, Rémi, Mary, Theo, Riccietti, Elisa, Optimisation, Connaissances pHysiques, Algorithmes et Modèles (OCKHAM), 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)-Institut Rhône-Alpin des systèmes complexes (IXXI), École normale supérieure de Lyon (ENS de Lyon)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Université Lumière - Lyon 2 (UL2)-Université Jean Moulin - Lyon 3 (UJML), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), and ANR-19-CHIA-0009,AllegroAssai,Algorithmes, Approximations, Parcimonie et Plongements pour l'IA(2019)

Subjects
floating-point arihmetic, sparse matrices, low-rank approximations, numerical linear algebra, rank-one matrices, [INFO]Computer Science [cs], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], low precision quantization, [INFO.INFO-NA]Computer Science [cs]/Numerical Analysis [cs.NA], butterfly factorizations
Abstract

We consider the problem of optimally quantizing rank-one matrices to low precision floating-point arithmetic. We first explain that the naive strategy of separately quantizing the two rank-one factors can be far from optimal, and we provide worst case error bounds to support this observation. We characterize the optimal solution as the quantization of suitably scaled factors of the rank-one matrix and we develop an algorithm of tractable complexity to find the optimal scaling parameters. Using random rank-one matrices, we show experimentally that our algorithm can significantly reduce the quantization error. We then apply this algorithm to the quantization of butterfly factorizations, a fundamental tool that appears in many fast linear transforms. We show how the properties of butterfly supports can be exploited to approach the problem via a series of rank-one quantization problems and we employ our algorithm as a building block in a heuristic procedure to quantize a product of butterfly factors. We show that, despite being only heuristic, this strategy can be much more accurate than quantizing each factor independently or, equivalently, can achieve storage reductions of up to 30% with no loss of accuracy.

Published
2023

5. Mixed precision iterative refinement for low-rank matrix and tensor approximations

Author

Baboulin, Marc, Kaya, Oguz, Mary, Théo, Robeyns, Matthieu, Laboratoire Interdisciplinaire des Sciences du Numérique (LISN), Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS), Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), and DIM RFSI RC-TENSOR No 2021-05

Subjects
Matrix and tensor computations, Iterative refinement, Mixed precision algorithms, Tensor decompositions, 65F55, 65G50, 65Y20, 15A69, [INFO]Computer Science [cs], Low-rank approximations, Randomized SVD, [MATH]Mathematics [math]
Abstract

We present a new mixed precision algorithm to compute low-rank matrix and tensor approximations, a fundamental task in numerous applications in scientific computing and data analysis. Our algorithm is reminiscent of the iterative refinement framework for linear systems: we first compute a low-rank approximation in low precision and then refine its accuracy by iteratively updating it. We carry out an error analysis of our algorithm which proves that we can reach a high accuracy while performing most of the operations in low precision. We measure the computational cost of the algorithm, which depends on the numerical rank of the input (matrix or tensor) as well as the speed ratio between low and high precision arithmetic. We identify two situations where our method has a strong potential : when the hardware provides fast low precision matrix multiplyaccumulate units, and when the numerical rank of the input is small at low accuracy levels. We confirm experimentally the potential of our algorithm for computing various low-rank matrix and tensor decompositions such as SVD, QR, Tucker, hierarchical Tucker, and tensor-train.

Published
2023

6. Downscaling of ocean fields by fusion of heterogeneous observations using Deep Learning algorithms

Author

Sylvie Thiria, Charles Sorror, Theo Archambault, Anastase Charantonis, Dominique Bereziat, Carlos Mejia, Jean-Marc Molines, Michel Crépon, Océan et variabilité du climat (VARCLIM), Laboratoire d'Océanographie et du Climat : Expérimentations et Approches Numériques (LOCEAN), Muséum national d'Histoire naturelle (MNHN)-Institut de Recherche pour le Développement (IRD)-Institut national des sciences de l'Univers (INSU - CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Institut Pierre-Simon-Laplace (IPSL (FR_636)), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Institut national des sciences de l'Univers (INSU - CNRS)-École polytechnique (X)-Centre National d'Études Spatiales [Toulouse] (CNES)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-École polytechnique (X)-Centre National d'Études Spatiales [Toulouse] (CNES)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)-Muséum national d'Histoire naturelle (MNHN)-Institut de Recherche pour le Développement (IRD)-Institut national des sciences de l'Univers (INSU - CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Institut Pierre-Simon-Laplace (IPSL (FR_636)), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-École polytechnique (X)-Centre National d'Études Spatiales [Toulouse] (CNES)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE), Institut des Géosciences de l’Environnement (IGE), Institut de Recherche pour le Développement (IRD)-Institut national des sciences de l'Univers (INSU - CNRS)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), and Université Grenoble Alpes (UGA)

Subjects
Machine Learning, Ocean currents, Atmospheric Science, Altimeter, [SDU]Sciences of the Universe [physics], Computer Science (miscellaneous), Downscaling, Geotechnical Engineering and Engineering Geology, Oceanography, SST
Abstract

International audience; We present a deep learning method to downscale low-resolution geophysical fields by merging them with high-resolution data. The downscaling was performed using an ensemble of convolutional neural networks (CNNs), whose prediction values are the average values of the outputs of 20 CNNs. Academic experiments were conducted on simulated ocean data in the Gulf Stream region, given by the outputs of the NATL60 model. The CNNs forced with low-resolution (120 × 120 km) sea surface high (SSH) data and mesoscale resolution (12 × 12 km) sea surface temperature (SST) data allowed us to obtain mesoscale resolution sea surface currents with good accuracy. Sensitivity experiments have shown that taking SST into account significantly increases the accuracy of the high-resolution velocity retrieval, even when noise is added to the SSH data. The velocity information embedded in the transport equation modeling the SST advection is taken into account by the CNN, which greatly increases the resolution of ocean currents provided by SSH. In the present work, we only consider spatial downscaling by assuming that SSH and SST are daily observations. The method we developed is generic and can be used to improve the resolution of a wide variety of large-scale fields by merging them with high-resolution fields.

Published
2023

7. Multimodal Unsupervised Spatio-Temporal Interpolation of Satellite Ocean Altimetry Maps

Author

Archambault, Théo, Filoche, Arthur, Charantonnis, Anastase, Béréziat, Dominique, Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE), Laboratoire de Mathématiques et Modélisation d'Evry (LaMME), and Institut National de la Recherche Agronomique (INRA)-Université d'Évry-Val-d'Essonne (UEVE)-ENSIIE-Centre National de la Recherche Scientifique (CNRS)

Subjects
Satellite remote sensing, [SDE]Environmental Sciences, Image inverse problems, Multimodal observations, [INFO.INFO-CV]Computer Science [cs]/Computer Vision and Pattern Recognition [cs.CV], Deep neural network, Spatio Temporal interpolation, Unsupervised neural network
Abstract

International audience; Satellite remote sensing is a key technique to understand Ocean dynamics. Due to measurement difficulties, various ill-posed image inverse problems occur, and among them, gridding satellite Ocean altimetry maps is a challenging interpolation of sparse along-tracks data. In this work, we show that it is possible to take advantage of better-resolved physical data to enhance Sea Surface Height (SSH) gridding using only partial data acquired via satellites. For instance, the Sea Surface Temperature (SST) is easier to measure through satellite and has an underlying physical link with altimetry. We train a deep neural network to estimate a time series of SSH using a time series of SST in an unsupervised way. We compare to state-of-the-art methods and report a 13% RMSE decrease compared to the operational altimetry algorithm.

Published
2023

8. Does 3D frequency-domain FWI of full-azimuth/long-offset OBN data feasible? The Gorgon case study

Author

Operto, S., Amestoy, Patrick, Aghamiry, Hossein, Beller, Stephen, Buttari, Alfredo, Combe, L., Dolean, Victorita, Gerest, Matthieu, Guo, Gaoshan, Jolivet, Pierre, L'Excellent, Jean-Yves, Mamfoumbi, Frichnel, Mary, Théo, Puglisi, Chiara, Ribodetti, Alessandra, Tournier, Pierre-Henri, Université Côte d'Azur (UCA), Mumps Technologies [Lyon], Géoazur (GEOAZUR 7329), Institut national des sciences de l'Univers (INSU - CNRS)-Observatoire de la Côte d'Azur, COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Université Côte d'Azur (UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Université Côte d'Azur (UCA)-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche pour le Développement (IRD [France-Sud]), Centre National de la Recherche Scientifique (CNRS), Algorithmes Parallèles et Optimisation (IRIT-APO), Institut de recherche en informatique de Toulouse (IRIT), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-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)-Toulouse Mind & Brain Institut (TMBI), Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Laboratoire Jean Alexandre Dieudonné (JAD), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS), Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), EDF R&D (EDF R&D), EDF (EDF), Laboratoire Jacques-Louis Lions (LJLL (UMR_7598)), and Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)

Subjects
Optimization and Control (math.OC), FOS: Mathematics, [PHYS.PHYS.PHYS-GEO-PH]Physics [physics]/Physics [physics]/Geophysics [physics.geo-ph], [INFO.INFO-NA]Computer Science [cs]/Numerical Analysis [cs.NA], Mathematics - Optimization and Control
Abstract

Frequency-domain Full Waveform Inversion (FWI) is potentially amenable to efficient processing of full-azimuth long-offset stationary-recording seabed acquisition carried out with sparse layout of ocean bottom nodes (OBNs) and broadband sources because the inversion can be performed with a few discrete frequencies. However, computing efficiently the solution of the forward (boundary-value) problem in the frequency domain with linear algebra solvers remains a challenge for large computational domains involving tens to hundreds of millions of parameters. We illustrate the feasibility of 3D frequency-domain FWI with the 2015/16 Gorgon OBN case study in the NorthWestern shelf, Australia. We solve the forward problem with the massively-parallel multifrontal direct solver MUMPS, which includes four key features to reach high computational efficiency: An efficient parallelism combining message-passing interface and multithreading, block low-rank compression, mixed precision arithmetic and efficient processing of sparse sources. The Gorgon subdataset involves 650 OBNs that are processed as reciprocal sources and 400,000 sources. Mono-parameter FWI for vertical wavespeed is performed in the visco-acoustic VTI approximation with a classical frequency continuation approach proceeding from a starting frequency of 1.7 Hz to a final frequency of 13 Hz. The target covers an area ranging from 260 km2 (frequency > 8.5 Hz) to 705 km2 (frequency < 8.5 Hz) for a maximum depth of 8 km. Compared to the starting model, FWI dramatically improves the reconstruction of the bounding faults of the Gorgon horst at reservoir depths as well as several intra-horst faults and several horizons of the Mungaroo formation down to a depth of 7 km.

Published
2022

9. Statistics-free interpolation of ocean observations with deep spatio-temporal prior

Author

Filoche, Arthur, Archambault, Théo, Charantonis, Anastase Alexandre, Béréziat, Dominique, Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Océanographie et du Climat : Expérimentations et Approches Numériques (LOCEAN), Muséum national d'Histoire naturelle (MNHN)-Institut de Recherche pour le Développement (IRD)-Institut national des sciences de l'Univers (INSU - CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Institut Pierre-Simon-Laplace (IPSL (FR_636)), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Institut national des sciences de l'Univers (INSU - CNRS)-École polytechnique (X)-Centre National d'Études Spatiales [Toulouse] (CNES)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-École polytechnique (X)-Centre National d'Études Spatiales [Toulouse] (CNES)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), and Béréziat, Dominique

Subjects
[INFO.INFO-TI] Computer Science [cs]/Image Processing [eess.IV], [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], inverse problem, deep prior, satellite altimetry, space-time interpolation, sea surface height
Abstract

International audience; Interpolating sea surface height satellite measurements is a challenging inverse problem as altimeter observation can be very sparse in space and time. Operational methods rely on second-order statistics of ocean evolution which are difficult to estimate due to the high dimensionality of the studied system. In this work, we investigate a statistics-free and unsupervised variational method using a deep spatio-temporal prior, a neural network optimized on only one observational window. Results are aligned with state-of-the-art operational methods.

Published
2022

10. Combining leak–resistant arithmetic for elliptic curves defined over Fp and RNS representation

Author

Bajard, Jean-Claude, Duquesne, Sylvain, Ercegovac, Milos, Performance et Qualité des Algorithmes Numériques (PEQUAN), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS), Institut de Recherche Mathématique de Rennes (IRMAR), 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)-École normale supérieure - Rennes (ENS Rennes)-Université de Rennes 2 (UR2)-Centre National de la Recherche Scientifique (CNRS)-INSTITUT AGRO Agrocampus Ouest, Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro), Laboratoire International de Recherche en Informatique et Mathématiques Appliquées (LIRIMA), Université de Yaoundé I-Université Badji Mokhtar Annaba (UBMA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Joseph Ki-Zerbo [Ouagadougou] (UJZK)-Université d'Antananarivo-Université Gaston Bergé Sénégal-Centre National de la Recherche Scientifique et Technologique (CNRST), Digital Arithmetic and Reconfigurable Architecture Laboratory, University of California [Los Angeles] (UCLA), University of California (UC)-University of California (UC), Performance et Qualité des Algorithmes Numériques ( PEQUAN ), Laboratoire d'Informatique de Paris 6 ( LIP6 ), Université Pierre et Marie Curie - Paris 6 ( UPMC ) -Centre National de la Recherche Scientifique ( CNRS ) -Université Pierre et Marie Curie - Paris 6 ( UPMC ) -Centre National de la Recherche Scientifique ( CNRS ), Institut de Recherche Mathématique de Rennes ( IRMAR ), Université de Rennes 1 ( UR1 ), Université de Rennes ( UNIV-RENNES ) -Université de Rennes ( UNIV-RENNES ) -AGROCAMPUS OUEST-École normale supérieure - Rennes ( ENS Rennes ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National des Sciences Appliquées ( INSA ) -Université de Rennes 2 ( UR2 ), Université de Rennes ( UNIV-RENNES ) -Centre National de la Recherche Scientifique ( CNRS ), Laboratoire International de Recherche en Informatique et Mathématiques Appliquées ( LIRIMA ), Université de Yaoundé I [Yaoundé]-Université Badji Mokhtar - Annaba [Annaba] ( UBMA ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -Université de Ouagadougou-Université d'Antananarivo-Université Gaston Bergé Sénégal-Centre National pour la recherche scientifique et Technique, University of California at Los Angeles [Los Angeles] ( UCLA ), AGROCAMPUS OUEST, Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Université de Rennes 2 (UR2), Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA), Université de Yaoundé I-Université Badji Mokhtar - Annaba [Annaba] (UBMA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Joseph Ki-Zerbo [Ouagadougou] (UJZK)-Université d'Antananarivo-Université Gaston Bergé Sénégal-Centre National de la Recherche Scientifique et Technologique (CNRST), and University of California-University of California

Subjects
[ MATH ] Mathematics [math], residue number sys-tem (RNS), [ INFO ] Computer Science [cs], modular multiplication, and phrases — Elliptic curves, modular reduction, [INFO]Computer Science [cs], leak-resistance, [MATH]Mathematics [math], Montgomery ladder
Abstract

International audience; — In this paper we give a survey of a method combining the residue number system (RNS) representation and the leak-resistant arithmetic on elliptic curves. These two techniques are relevant for implementation of elliptic curve cryptography on embedded devices. It is well known that the RNS multiplication is very efficient whereas the reduction step is costly. Hence, we optimize formulae for basic operations arising in leak-resistant arithmetic on elliptic curves (unified addition, Montgomery ladder) in order to minimize the number of modular reductions. We also improve the complexity of the RNS modular reduction step. As a result, we show how to obtain a competitive secured implementation. Finally, we show that, contrary to other approaches, this method takes optimally the advan-tage of a dedicated parallel architecture. Résumé. — Dans cet article, nous donnons un survol d'une méthode qui combine le système de représentation des nombres basé sur les restes chinois (RNS) avec les formules de loi de groupe sur les courbes elliptiques qui sont résistantes aux attaques par fuites. Ces deux techniques sont particulièrement intéressantes pour l'implémentation de cryptosystèmes basés sur les courbes elliptiques dans des systèmes embarqués. Dans le système de représentation RNS, la multiplication de grands entiers est très efficace contrairement à la réduction modulaire. Nous réécrivons donc ici les formules de la loi de groupe pour les modèles de courbes elliptiques résistant aux fuites (loi d'addition unifiée, forme de Mont-gomery) dans le but de minimiser le nombre de réductions modulaires. Nous améliorons aussi la complexité de l'étape de réduction. Ces deux aspects permettent d'obtenir des implémentations sécurisées compétitives. Finalement, nous montrons que, contrairement aux autres approches, cette méthode peut profiter pleinement d'une architecture parallèle dédiée. 2010 Mathematics Subject Classification. — 14G50.

Published
2013

11. Block low-rank compression in mixed precision for the solution of sparse linear systems

Author

Gerest, Matthieu, Amestoy, Patrick, Boiteau, Olivier, Buttari, Alfredo, Jézéquel, Fabienne, L'Excellent, Jean-Yves, Mary, Théo, Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), EDF R&D (EDF R&D), EDF (EDF), Mumps Technologies [Lyon], Algorithmes Parallèles et Optimisation (IRIT-APO), Institut de recherche en informatique de Toulouse (IRIT), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-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)-Toulouse Mind & Brain Institut (TMBI), Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Centre National de la Recherche Scientifique (CNRS), Université Paris-Panthéon-Assas, 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), and JEZEQUEL, Fabienne

Subjects
[INFO]Computer Science [cs], [INFO] Computer Science [cs]
Abstract

International audience

Published
2022

12. Tight Interval Inclusions with Compensated Algorithms

Author

Fabienne Jézéquel, Stef Graillat, Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Université Panthéon-Assas (UP2), JEZEQUEL, Fabienne, and ANR-14-CE25-0018,Fast Relax,Approximation rapide et fiable(2014)

Subjects
Polynomial, Floating point, floating-point arithmetic, Computer science, error-free transformations, 02 engineering and technology, Interval (mathematics), [INFO] Computer Science [cs], interval arithmetic, Theoretical Computer Science, Interval arithmetic, summation algorithms, rounding errors, 0202 electrical engineering, electronic engineering, information engineering, numerical validation, [INFO]Computer Science [cs], [INFO.INFO-AO]Computer Science [cs]/Computer Arithmetic, Rounding, Dot product, 020202 computer hardware & architecture, Index Terms-interval arithmetic, Transformation (function), Computational Theory and Mathematics, Hardware and Architecture, dot product, directed rounding, [INFO.INFO-AO] Computer Science [cs]/Computer Arithmetic, compensated algorithms, Round-off error, Algorithm, Software, Horner scheme
Abstract

International audience; Compensated algorithms consist in computing the rounding errors of individual operations and then adding them later on to the computed result. This makes it possible to increase the accuracy of the computed result efficiently. Computing the rounding error of an individual operation is possible through the use of a so-called error-free transformation. In this article, we show that it is possible to use compensated algorithms for having tight interval inclusion. We study compensated algorithms for summation, dot product and polynomial evaluation. We prove that the use of directed rounding makes it possible to get narrow inclusions with compensated algorithms. This is due to the fact that error-free transformations are no more exact but still sufficiently accurate to improve the numerical quality of results.

Published
2020

13. Deep prior in variational assimilation to estimate ocean circulation without explicit regularization

Author

Filoche, Arthur, Béréziat, Dominique, Charantonis, Anastase Alexandre, Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Océan et variabilité du climat (VARCLIM), Laboratoire d'Océanographie et du Climat : Expérimentations et Approches Numériques (LOCEAN), Muséum national d'Histoire naturelle (MNHN)-Institut de Recherche pour le Développement (IRD)-Institut national des sciences de l'Univers (INSU - CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Institut Pierre-Simon-Laplace (IPSL (FR_636)), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Institut national des sciences de l'Univers (INSU - CNRS)-École polytechnique (X)-Centre National d'Études Spatiales [Toulouse] (CNES)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-École polytechnique (X)-Centre National d'Études Spatiales [Toulouse] (CNES)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)-Muséum national d'Histoire naturelle (MNHN)-Institut de Recherche pour le Développement (IRD)-Institut national des sciences de l'Univers (INSU - CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Institut Pierre-Simon-Laplace (IPSL (FR_636)), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-École polytechnique (X)-Centre National d'Études Spatiales [Toulouse] (CNES)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), and Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)

Subjects
regularization, [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], [SDE.IE]Environmental Sciences/Environmental Engineering, [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], variational data assimilation, ocean circulation, deep prior, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], twin experiment
Abstract

International audience; Many applications in geosciences require solving inverse problems to estimate the state of a physical system. Data assimilation provides a strong framework to do so when the system is partially observed and its underlying dynamics is known to some extent. In the variational flavor, it can be seen as an optimal control problem where initial conditions are the control parameters. Such problems being often ill-posed, regularization may be needed using explicit prior knowledge to enforce satisfying solution. In this work we propose to use a deep prior, a neural architecture that generates potential solution and acts as implicit regularization. The architecture is trained in an fully-unsupervised manner using the variational data assimilation cost so that gradients are backpropagated through the dynamical model and then through the neural network. To demonstrate its use, we set a twin experiment using a shallow-water toy model, where we test various variational assimilation algorithms on a ocean-like circulation estimation.

Published
2022

14. SSH Super-Resolution using high resolution SST with a Subpixel Convolutional Residual Network

Author

Archambault, Théo, Charantonis, Anastase Alexandre, Béréziat, Dominique, Mejia, Carlos, Thiria, Sylvie, Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE), Océan et variabilité du climat (VARCLIM), Laboratoire d'Océanographie et du Climat : Expérimentations et Approches Numériques (LOCEAN), Muséum national d'Histoire naturelle (MNHN)-Institut de Recherche pour le Développement (IRD)-Institut national des sciences de l'Univers (INSU - CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Institut Pierre-Simon-Laplace (IPSL (FR_636)), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Institut national des sciences de l'Univers (INSU - CNRS)-École polytechnique (X)-Centre National d'Études Spatiales [Toulouse] (CNES)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-École polytechnique (X)-Centre National d'Études Spatiales [Toulouse] (CNES)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)-Muséum national d'Histoire naturelle (MNHN)-Institut de Recherche pour le Développement (IRD)-Institut national des sciences de l'Univers (INSU - CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Institut Pierre-Simon-Laplace (IPSL (FR_636)), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-École polytechnique (X)-Centre National d'Études Spatiales [Toulouse] (CNES)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), and Béréziat, Dominique

Subjects
[SDE] Environmental Sciences, [INFO.INFO-AI] Computer Science [cs]/Artificial Intelligence [cs.AI], [INFO.INFO-TI] Computer Science [cs]/Image Processing [eess.IV], Super-Resolution, [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], Satellite Image, [SDE]Environmental Sciences, Subpixel convolution, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Abstract

International audience; The oceans have a very important role in climate regulation due to its massive heat storage capacity. Thus, for the past decades oceans have been observed by satellites in order to better understand its dynamics. Satellites retrieve several data with various spatial resolution. For instance Sea Surface Height (SSH) is a low-resolution data field where Sea Surface Temperature (SST) can be retrieved in a much higher one. These two physical parameters are linked by a physical relation that can be learned by a Super-Resolution machine learning algorithm. In this work we present a Subpixel Convolutional Deep learning model that takes advantage of the higher resolution SST field to guide the downscaling of the SSH one. The data fields that we use are simulated by a physic based ocean model at a higher sampling rate than the satellites provide. We compared our approach with a convolutional neural network (CNN) model. Our architecture generalized well with validation performances of 3.94 cm RMSE and training performances of 2.65 cm RMSE.

Published
2022

15. Unlearned Downscaling of sea surface height with Deep Image Prior

Author

Archambault, Théo, Filoche, Arthur, Charantonis, Anastase Alexandre, Béréziat, Dominique, Laboratoire d'Océanographie et du Climat : Expérimentations et Approches Numériques (LOCEAN), Muséum national d'Histoire naturelle (MNHN)-Institut de Recherche pour le Développement (IRD)-Institut national des sciences de l'Univers (INSU - CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Institut Pierre-Simon-Laplace (IPSL (FR_636)), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Institut national des sciences de l'Univers (INSU - CNRS)-École polytechnique (X)-Centre National d'Études Spatiales [Toulouse] (CNES)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-École polytechnique (X)-Centre National d'Études Spatiales [Toulouse] (CNES)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, and Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)

Subjects
[INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], [SDE.ES]Environmental Sciences/Environmental and Society, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Abstract

International audience

Published
2022

16. Stochastic rounding: implementation, error analysis and applications

Author

Matteo Croci, Massimiliano Fasi, Nicholas J. Higham, Theo Mary, Mantas Mikaitis, Mary, Theo, Plateforme d'analyse pour l'arithmétique flottante - - INTERFLOP2020 - ANR-20-CE46-0009 - AAPG2020 - VALID, University of Oxford [Oxford], Durham University, University of Manchester [Manchester], Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), and ANR-20-CE46-0009,INTERFLOP,Plateforme d'analyse pour l'arithmétique flottante(2020)

Subjects
Multidisciplinary, Computer Science Floating-point Arithmetic, Partial Differential Equations, [MATH] Mathematics [math], [INFO] Computer Science [cs], Rounding Error Analysis, Ordinary Differential Equations, IEEE 754, [INFO]Computer Science [cs], Computer Arithmetic, Low Precision, [MATH]Mathematics [math], binary16, bfloat16, Mathematics
Abstract

Stochastic rounding (SR) randomly maps a real number x to one of the two nearest values in a finite precision number system. The probability of choosing either of these two numbers is 1 minus their relative distance to x . This rounding mode was first proposed for use in computer arithmetic in the 1950s and it is currently experiencing a resurgence of interest. If used to compute the inner product of two vectors of length n in floating-point arithmetic, it yields an error bound with constant n u with high probability, where u is the unit round-off. This is not necessarily the case for round to nearest (RN), for which the worst-case error bound has constant nu . A particular attraction of SR is that, unlike RN, it is immune to the phenomenon of stagnation, whereby a sequence of tiny updates to a relatively large quantity is lost. We survey SR by discussing its mathematical properties and probabilistic error analysis, its implementation, and its use in applications, with a focus on machine learning and the numerical solution of differential equations.

Published
2022

17. Reproducibility of parallel preconditioned conjugate gradient in hybrid programming environments

Author

Roman Iakymchuk, José Ignacio Aliaga, Stef Graillat, Maria Barreda, Enrique S. Quintana-Ortí, Publica, Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Fraunhofer Institute of Industrial Mathematics (Fraunhofer ITWM), Fraunhofer (Fraunhofer-Gesellschaft), Universidad Jaime I de Catellon, Universitat Politècnica de València (UPV), and Iakymchuk, Roman

Subjects
FOS: Computer and information sciences, fused multiply-add, Computer science, 010103 numerical & computational mathematics, 02 engineering and technology, Parallel computing, Residual, 01 natural sciences, floating-point expansion, Theoretical Computer Science, Preconditioned Conjugate Gradient, long accumulator, Conjugate gradient method, [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], 0202 electrical engineering, electronic engineering, information engineering, Overhead (computing), preconditioned conjugate gradient, 0101 mathematics, Fused multiply-add, reproducibility, [INFO.INFO-MS]Computer Science [cs]/Mathematical Software [cs.MS], 020203 distributed computing, Reproducibility, Multiply–accumulate operation, accuracy, [INFO.INFO-AO]Computer Science [cs]/Computer Arithmetic, Rounding, Linear system, fused multiply–add, OpenMP tasks, [MATH.MATH-NA] Mathematics [math]/Numerical Analysis [math.NA], Solver, ARQUITECTURA Y TECNOLOGIA DE COMPUTADORES, Computer Science - Distributed, Parallel, and Cluster Computing, [INFO.INFO-MS] Computer Science [cs]/Mathematical Software [cs.MS], Hardware and Architecture, Computer Science - Mathematical Software, [INFO.INFO-AO] Computer Science [cs]/Computer Arithmetic, MPI, Distributed, Parallel, and Cluster Computing (cs.DC), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Mathematical Software (cs.MS), [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA], Software
Abstract

[EN] The Preconditioned Conjugate Gradient method is often employed for the solution of linear systems of equations arising in numerical simulations of physical phenomena. While being widely used, the solver is also known for its lack of accuracy while computing the residual. In this article, we propose two algorithmic solutions that originate from the ExBLAS project to enhance the accuracy of the solver as well as to ensure its reproducibility in a hybrid MPI + OpenMP tasks programming environment. One is based on ExBLAS and preserves every bit of information until the final rounding, while the other relies upon floating-point expansions and, hence, expands the intermediate precision. Instead of converting the entire solver into its ExBLAS-related implementation, we identify those parts that violate reproducibility/non-associativity, secure them, and combine this with the sequential executions. These algorithmic strategies are reinforced with programmability suggestions to assure deterministic executions. Finally, we verify these approaches on two modern HPC systems: both versions deliver reproducible number of iterations, residuals, direct errors, and vector-solutions for the overhead of less than 37.7% on 768 cores., The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This research was partially supported by the European Union's Horizon 2020 research, innovation program under the Marie Sklodowska-Curie grant agreement via the Robust project No. 842528 as well as the Project HPC-EUROPA3 (INFRAIA-2016-1-730897), with the support of the H2020 EC RIA Programme; in particular, the author gratefully acknowledges the support of Vicenc comma Beltran and the computer resources and technical support provided by BSC. The researchers from Universitat Jaume I (UJI) and Universitat Polit ' ecnica de Valencia (UPV) were supported by MINECO project TIN2017-82972-R. Maria Barreda was also supported by the POSDOC-A/2017/11 project from the Universitat Jaume I.

Published
2020

18. A Directional Equispaced interpolation-based Fast Multipole Method for oscillatory kernels

Author

Igor Chollet, Xavier Claeys, Pierre Fortin, Laura Grigori, Institut des Sciences du Calcul et des Données (ISCD), Sorbonne Université (SU), Algorithms and parallel tools for integrated numerical simulations (ALPINES), Institut National des Sciences Mathématiques et de leurs Interactions (INSMI)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Jacques-Louis Lions (LJLL (UMR_7598)), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), Laboratoire Jacques-Louis Lions (LJLL (UMR_7598)), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), 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), Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, and Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Computational Mathematics, Applied Mathematics, High performance computing on one CPU core, FOS: Mathematics, Non-uniform particle distributions, Fast multipole method FMM, Numerical Analysis (math.NA), Mathematics - Numerical Analysis, Fast Fourier Transform FFT, [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA], Symmetries, Highly oscillatory kernels
Abstract

Fast Multipole Methods (FMMs) based on the oscillatory Helmholtz kernel can reduce the cost of solving N-body problems arising from Boundary Integral Equations (BIEs) in acoustic or electromagnetics. However, their cost strongly increases in the high-frequency regime. This paper introduces a new directional FMM for oscillatory kernels (defmm - directional equispaced interpolation-based fmm), whose precomputation and application are FFT-accelerated due to polynomial interpolations on equispaced grids. We demonstrate the consistency of our FFT approach, and show how symmetries can be exploited in the Fourier domain. We also describe the algorithmic design of defmm, well-suited for the BIE non-uniform particle distributions, and present performance optimizations on one CPU core. Finally, we exhibit important performance gains on all test cases for defmm over a state-of-the-art FMM library for oscillatory kernels.

Published
2022

19. Unsupervised Downscaling of sea surface height with Deep Image Prior

Author

Archambault, Théo, Filoche, Arthur, Charantonis, Anastase Alexandre, Béréziat, Dominique, Béréziat, Dominique, Laboratoire d'Océanographie et du Climat : Expérimentations et Approches Numériques (LOCEAN), Muséum national d'Histoire naturelle (MNHN)-Institut de Recherche pour le Développement (IRD)-Institut national des sciences de l'Univers (INSU - CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Institut Pierre-Simon-Laplace (IPSL (FR_636)), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Institut national des sciences de l'Univers (INSU - CNRS)-École polytechnique (X)-Centre National d'Études Spatiales [Toulouse] (CNES)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-École polytechnique (X)-Centre National d'Études Spatiales [Toulouse] (CNES)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, and Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)

Subjects
[INFO.INFO-AI] Computer Science [cs]/Artificial Intelligence [cs.AI], [INFO.INFO-TI] Computer Science [cs]/Image Processing [eess.IV], [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], [SDE.ES] Environmental Sciences/Environmental and Society, [SDE.ES]Environmental Sciences/Environmental and Society, ComputingMilieux_MISCELLANEOUS, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Abstract

International audience

Published
2022

20. Learning 4DVAR inversion directly from observations

Author

Filoche, Arthur, Brajard, Julien, Charantonis, Anastase, Béréziat, Dominique, Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Océanographie et du Climat : Expérimentations et Approches Numériques (LOCEAN), Muséum national d'Histoire naturelle (MNHN)-Institut de Recherche pour le Développement (IRD)-Institut national des sciences de l'Univers (INSU - CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Institut Pierre-Simon-Laplace (IPSL (FR_636)), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Institut national des sciences de l'Univers (INSU - CNRS)-École polytechnique (X)-Centre National d'Études Spatiales [Toulouse] (CNES)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-École polytechnique (X)-Centre National d'Études Spatiales [Toulouse] (CNES)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), Nansen Environmental and Remote Sensing Center [Bergen] (NERSC), Laboratoire de Mathématiques et Modélisation d'Evry (LaMME), Institut National de la Recherche Agronomique (INRA)-Université d'Évry-Val-d'Essonne (UEVE)-ENSIIE-Centre National de la Recherche Scientifique (CNRS), and Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)

Subjects
FOS: Computer and information sciences, Computer Science - Machine Learning, Learning Simulation, [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], Unsupervised Inversion, Differentiable Physics, Data Assimilation, Machine Learning (cs.LG)
Abstract

Variational data assimilation and deep learning share many algorithmic aspects in common. While the former focuses on system state estimation, the latter provides great inductive biases to learn complex relationships. We here design a hybrid architecture learning the assimilation task directly from partial and noisy observations, using the mechanistic constraint of the 4DVAR algorithm. Finally, we show in an experiment that the proposed method was able to learn the desired inversion with interesting regularizing properties and that it also has computational interests., Comment: submitted to ICASSP 2023

Published
2022
Full Text
View/download PDF

21. General framework for deriving reproducible Krylov subspace algorithms: A BiCGStab case study

Author

Iakymchuk, Roman, Graillat, Stef, Aliaga, José, Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Fraunhofer Institute of Industrial Mathematics (Fraunhofer ITWM), Fraunhofer (Fraunhofer-Gesellschaft), Universitat Jaime I (UJI), ANR-20-CE46-0009,INTERFLOP,Plateforme d'analyse pour l'arithmétique flottante(2020), European Project: 842528,Robust, Iakymchuk, Roman, Plateforme d'analyse pour l'arithmétique flottante - - INTERFLOP2020 - ANR-20-CE46-0009 - AAPG2020 - VALID, Robust and Energy-Efficient Numerical Solvers Towards Reliable and Sustainable Scientific Computations - Robust - 842528 - INCOMING, Department of Computing Science [Umeå, Sweden], and Umeå University

Subjects
fused multiply-add, accuracy, [INFO.INFO-AO]Computer Science [cs]/Computer Arithmetic, [MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], [MATH.MATH-NA] Mathematics [math]/Numerical Analysis [math.NA], Reproducibility, floating-point expansion, High-Performance Computing, [INFO.INFO-MS] Computer Science [cs]/Mathematical Software [cs.MS], long accumulator, [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], [INFO.INFO-AO] Computer Science [cs]/Computer Arithmetic, preconditioned BiCGStab, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA], [INFO.INFO-MS]Computer Science [cs]/Mathematical Software [cs.MS]
Abstract

Parallel implementations of Krylov subspace algorithms often help to accelerate the procedure to find the solution of a linear system. However, from the other side, such parallelization coupled with asynchronous and out-of-order execution often enlarge the non-associativity of floating-point operations. This results in non-reproducibility on the same or different settings. This paper proposes a general framework for deriving reproducible and accurate variants of a Krylov subspace algorithm. The proposed algorithmic strategies are reinforced by programmability suggestions to assure deterministic and accurate executions. The framework is illustrated on the preconditioned BiCGStab method for the solution of non-symmetric linear systems in parallel environments with message-passing. Finally, we verify the two reproducible variants of PBiCGStab on a set matrices from the SuiteSparse Matrix Collection.

Published
2021

22. Resiliency in numerical algorithm design for extreme scale simulations

Author

Emmanuel Agullo, Mirco Altenbernd, Hartwig Anzt, Leonardo Bautista-Gomez, Tommaso Benacchio, Luca Bonaventura, Hans-Joachim Bungartz, Sanjay Chatterjee, Florina M Ciorba, Nathan DeBardeleben, Daniel Drzisga, Sebastian Eibl, Christian Engelmann, Wilfried N Gansterer, Luc Giraud, Dominik Göddeke, Marco Heisig, Fabienne Jézéquel, Nils Kohl, Xiaoye Sherry Li, Romain Lion, Miriam Mehl, Paul Mycek, Michael Obersteiner, Enrique S Quintana-Ortí, Francesco Rizzi, Ulrich Rüde, Martin Schulz, Fred Fung, Robert Speck, Linda Stals, Keita Teranishi, Samuel Thibault, Dominik Thönnes, Andreas Wagner, Barbara Wohlmuth, High-End Parallel Algorithms for Challenging Numerical Simulations (HiePACS), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Universität Stuttgart [Stuttgart], Karlsruher Institut für Technologie (KIT), Barcelona Supercomputing Center - Centro Nacional de Supercomputacion (BSC - CNS), Politecnico di Milano [Milan] (POLIMI), Technische Universität Munchen - Université Technique de Munich [Munich, Allemagne] (TUM), NVIDIA Corporation [Bangalore], NVIDIA Research [Austin], University Hospital Basel [Basel], Los Alamos National Laboratory (LANL), Friedrich-Alexander Universität Erlangen-Nürnberg (FAU), Oak Ridge National Laboratory [Oak Ridge] (ORNL), UT-Battelle, LLC, University of Vienna [Vienna], Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Université Panthéon-Assas (UP2), Lawrence Berkeley National Laboratory [Berkeley] (LBNL), Université de Bordeaux (UB), CERFACS, Universitat Politècnica de València (UPV), NexGen Analytics (NGA), Australian National University (ANU), Jülich Supercomputing Centre (JSC), Forschungszentrum Jülich GmbH | Centre de recherche de Juliers, Helmholtz-Gemeinschaft = Helmholtz Association-Helmholtz-Gemeinschaft = Helmholtz Association, Sandia National Laboratories - Corporation, Technische Universität München [München] (TUM), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, STatic Optimizations, Runtime Methods (STORM), Centre Européen de Recherche et de Formation Avancée en Calcul Scientifique (CERFACS), and Barcelona Supercomputing Center

Subjects
G.4, FOS: Computer and information sciences, Numerical algorithms, Large scale systems, G.1, 010103 numerical & computational mathematics, 02 engineering and technology, 01 natural sciences, Theoretical Computer Science, Simulació per ordinador, 0202 electrical engineering, electronic engineering, information engineering, parallel computer architecture, 0101 mathematics, Informàtica::Arquitectura de computadors::Arquitectures paral·leles [Àrees temàtiques de la UPC], resilience, D.4.5, D.4.4, 020203 distributed computing, Parallel computer architecture, Resilience, Fault tolerance, Computer Science - Distributed, Parallel, and Cluster Computing, Hardware and Architecture, Fault tolerance (Engineering), Distributed, Parallel, and Cluster Computing (cs.DC), fault tolerance, ddc:004, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Software, [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA]
Abstract

This work is based on the seminar titled ``Resiliency in Numerical Algorithm Design for Extreme Scale Simulations'' held March 1-6, 2020 at Schloss Dagstuhl, that was attended by all the authors. Naive versions of conventional resilience techniques will not scale to the exascale regime: with a main memory footprint of tens of Petabytes, synchronously writing checkpoint data all the way to background storage at frequent intervals will create intolerable overheads in runtime and energy consumption. Forecasts show that the mean time between failures could be lower than the time to recover from such a checkpoint, so that large calculations at scale might not make any progress if robust alternatives are not investigated. More advanced resilience techniques must be devised. The key may lie in exploiting both advanced system features as well as specific application knowledge. Research will face two essential questions: (1) what are the reliability requirements for a particular computation and (2) how do we best design the algorithms and software to meet these requirements? One avenue would be to refine and improve on system- or application-level checkpointing and rollback strategies in the case an error is detected. Developers might use fault notification interfaces and flexible runtime systems to respond to node failures in an application-dependent fashion. Novel numerical algorithms or more stochastic computational approaches may be required to meet accuracy requirements in the face of undetectable soft errors. The goal of this Dagstuhl Seminar was to bring together a diverse group of scientists with expertise in exascale computing to discuss novel ways to make applications resilient against detected and undetected faults. In particular, participants explored the role that algorithms and applications play in the holistic approach needed to tackle this challenge., Comment: 45 pages, 3 figures, submitted to The International Journal of High Performance Computing Applications

Published
2021

23. Variational assimilation of Geophysical images leveraging deep learning tools

Author

Filoche, Arthur, Béréziat, Dominique, Charantonis, Anastase Alexandre, Brajard, Julien, Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Océanographie et du Climat : Expérimentations et Approches Numériques (LOCEAN), Muséum national d'Histoire naturelle (MNHN)-Institut de Recherche pour le Développement (IRD)-Institut national des sciences de l'Univers (INSU - CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Institut Pierre-Simon-Laplace (IPSL (FR_636)), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Institut national des sciences de l'Univers (INSU - CNRS)-École polytechnique (X)-Centre National d'Études Spatiales [Toulouse] (CNES)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-École polytechnique (X)-Centre National d'Études Spatiales [Toulouse] (CNES)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), Nansen Environmental and Remote Sensing Center [Bergen] (NERSC), Centre National de la Recherche Scientifique [CNRS], Institut Pierre-Simon-Laplace (IPSL (FR_636)), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Institut national des sciences de l'Univers (INSU - CNRS)-École polytechnique (X)-Centre National d'Études Spatiales [Toulouse] (CNES)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Institut national des sciences de l'Univers (INSU - CNRS)-École polytechnique (X)-Centre National d'Études Spatiales [Toulouse] (CNES)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP)-Institut de Recherche pour le Développement (IRD)-Muséum national d'Histoire naturelle (MNHN)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU), Sorbonne Université (SU)-Institut national des sciences de l'Univers (INSU - CNRS)-Centre National de la Recherche Scientifique (CNRS)-Muséum national d'Histoire naturelle (MNHN)-Institut de Recherche pour le Développement (IRD)-Institut Pierre-Simon-Laplace (IPSL (FR_636)), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-École polytechnique (X)-Centre National d'Études Spatiales [Toulouse] (CNES)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE), and Sciencesconf.org, CCSD

Subjects
[INFO.INFO-CV] Computer Science [cs]/Computer Vision and Pattern Recognition [cs.CV], [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], geoscience informatics, variational data assimilation, deep learning, [INFO.INFO-CV]Computer Science [cs]/Computer Vision and Pattern Recognition [cs.CV], [INFO]Computer Science [cs], [INFO] Computer Science [cs], automatic differentiation
Abstract

International audience; Many applications in Earth Sciences require the estimation of a physical system state. Data Assimilation provides a strong framework to do so when knowledge about a governing dynamics and observations of such system are available. If this kind of inverse problem is solved in a variational form, the optimization process involves the adjoint state method for efficient gradient computing. From a computational perspective, this method is equivalent to the backpropagation algorithm and is implemented using automatic differentiation. The ongoing development of deep learning tools allows flexible implementation of such methods and opens the door to hybrid data-knowledge driven modeling. This is illustrated on two geophysical image assimilation problems.; De nombreuses applications en géoscience nécessitent d'estimer l'état d'un système physique. L'assimilation de données fournit un cadre rigoureux pour le faire lorsque des connaissances de la dynamique qui régit le système et des observations de ce système sont disponibles. Quand ce type de problème inverse est résolu sous une forme variationnelle, le processus d'optimisation implique la méthode de l'état adjoint pour un calcul efficace du gradient. D'un point de vue informatique, cette méthode est équivalente à l'algorithme de rétropropagation et est mise en oeuvre en utilisant la différenciation automatique. Le récent développement des outils d'apprentissage profond permet une mise en oeuvre flexible de ces méthodes et ouvre la porte à une modélisation hybride axée sur les données et la connaissance. Ceci est illustré sur deux problèmes d'assimilation d'images géophysiques.

Published
2021

24. On a compensated Ehrlich-Aberth method for the accurate computation of all polynomial roots

Author

Cameron, Thomas, Graillat, Stef, Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), and ANR-20-CE48-0014,NuSCAP,Sûreté numérique pour les preuves assistées par ordinateur(2020)

Subjects
polynomial evaluation, [INFO.INFO-AO]Computer Science [cs]/Computer Arithmetic, error-free transformations, polynomial roots, backward error, [INFO.INFO-NA]Computer Science [cs]/Numerical Analysis [cs.NA], forward error, rounding error analysis
Abstract

In this article, we use the complex compensated Horner's method to derive a compensated Ehrlich-Aberth method for the accurate computation of all roots of a polynomial. In particular, under suitable conditions, we prove that the limiting accuracy for the compensated Ehrlich-Aberth iterations is as accurate as if computed in twice the working precision and then rounded into the working precision. Moreover, we derive a running error bound for the complex compensated Horner's and use it to form robust stopping criteria for the compensated Ehrlich-Aberth iterations. Finally, extensive numerical experiments illustrate that the backward and forward errors of the root approximations computed via the compensated Ehrlich-Aberth method are similar to those obtained with a quadruple precision implementation of the Ehrlich-Aberth method with a significant speed-up in terms of the computation time.

Published
2021

25. Block Low Rank Single Precision Coarse Grid Solvers for Extreme Scale Multigrid Methods

Author

Buttari, Alfredo, Huber, Markus, Leleux, Philippe, Mary, Théo, Ruede, Ulrich, Wohlmuth, Barbara, Algorithmes Parallèles et Optimisation (IRIT-APO), Institut de recherche en informatique de Toulouse (IRIT), Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Centre National de la Recherche Scientifique (CNRS), Technische Universität Munchen - Université Technique de Munich [Munich, Allemagne] (TUM), Centre Européen de Recherche et de Formation Avancée en Calcul Scientifique (CERFACS), CERFACS, Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), and Friedrich-Alexander Universität Erlangen-Nürnberg (FAU)

Subjects
sparse direct solver, high-performance computing, [MATH.MATH-AP]Mathematics [math]/Analysis of PDEs [math.AP], hierarchical hybrid grids, block low-rank, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], MUMPS, geometric multigrid, multifrontal, efficient coarse level solver
Abstract

International audience; Extreme scale simulation requires fast and scalable algorithms, such as multigrid methods. To achieve asymptotically optimal complexity it is essential to employ a hierarchy of grids. The cost to solve the coarsest grid system can often be neglected in sequential computings, but cannot be ignored in massively parallel executions. In this case, the coarsest grid can be large and its efficient solution becomes a challenging task. We propose solving the coarse grid system using modern, approximate sparse direct methods and investigate the expected gains compared with traditional iterative methods. Since the coarse grid system only requires an approximate solution, we show that we can leverage block low-rank techniques, combined with the use of single precision arithmetic, to significantly reduce the computational requirements of the direct solver. In the case of extreme scale computing, the coarse grid system is too large for a sequential solution, but too small to permit massively parallel efficiency. We show that the agglomeration of the coarse grid system to a subset of processors is necessary for the sparse direct solver to achieve performance. We demonstrate the efficiency of the proposed method on a Stokes-type saddle point system. We employ a monolithic Uzawa multigrid method. In particular, we show that the use of an approximate sparse direct solver for the coarse grid system can outperform that of a preconditioned minimal residual iterative method. This is demonstrated for the multigrid solution of systems of order up to 1+e11 degrees of freedom on a petascale supercomputer using 43 200 processes.

Published
2021

26. Adversarial attacks via backward error analysis

Author

Beuzeville, Théo, Boudier, Pierre, Buttari, Alfredo, Gratton, Serge, Mary, Théo, Pralet, Stéphane, Algorithmes Parallèles et Optimisation (IRIT-APO), Institut de recherche en informatique de Toulouse (IRIT), Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Atos [Bezons], ATOS Origin, NVIDIA (NVIDIA), Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019), Beuzeville, Théo, and Artificial and Natural Intelligence Toulouse Institute - - ANITI2019 - ANR-19-P3IA-0004 - P3IA - VALID

Subjects
[INFO.INFO-AI] Computer Science [cs]/Artificial Intelligence [cs.AI], [INFO]Computer Science [cs], [MATH]Mathematics [math], [MATH.MATH-NA] Mathematics [math]/Numerical Analysis [math.NA], [SHS.LANGUE.TRAI.AUTR]Humanities and Social Sciences/Linguistics/domain_shs.langue.trai/domain_shs.langue.trai.autr, [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA], [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Abstract

Backward error (BE) analysis was developed and popularized by James Wilkinson in the 1950s and 1960s, with origins in the works of Neumann and Goldstine (1947) and Turing (1948). It is a fundamental notion used in numerical linear algebra software, both as a theoretical and a practical tool for the rounding error analysis of numerical algorithms. Broadly speaking the backward error quantifies, in terms of perturbation of input data, by how much the output of an algorithm fails to be equal to an expected quantity. For a given computed solution y, this amounts to computing the norm of the smallest perturbation ∆x of the input data x such that y is an exact solution of a perturbed system: f (x + ∆x) = y. Up to now, BE analysis has been applied to numerous linear algebra problems, always with the objective of quantifying the robustness of algebraic processes with respect to rounding errors stemming from finite precision computations. While deep neural networks (DNN) have achieved an unprecedented success in numerous machine learning tasks in various domains, their robustness to adversarial attacks, rounding errors, or quantization processes has raised considerable concerns from the machine learning community. In this work, we generalize BE analysis to DNN. This enables us to obtain closed formulas and a numerical algorithm for computing adversarial attacks. By construction, these attacks are optimal, and thereby smaller, in norm, than perturbations obtained with existing gradient-based approaches. We produce numerical results that support our theoretical findings and illustrate the relevance of our approach on well-known datasets.

Published
2021

27. Gauss–Newton–Secant Method for Solving Nonlinear Least Squares Problems under Generalized Lipschitz Conditions

Author

Ioannis K. Argyros, Michael I. Argyros, Roman Iakymchuk, Halyna Yarmola, Stepan Shakhno, Ivan Franko National University of Lviv, Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), and University of Oklahoma (OU)

Subjects
Logic, Iterative method, 02 engineering and technology, 01 natural sciences, residual, Convergence (routing), 0202 electrical engineering, electronic engineering, information engineering, QA1-939, divided differences, Applied mathematics, radius of convergence, 0101 mathematics, Divided differences, [MATH]Mathematics [math], Mathematical Physics, Mathematics, Algebra and Number Theory, nonlinear least squares problem, 010102 general mathematics, Lipschitz continuity, differential-difference method, Local convergence, Secant method, error estimates, Non-linear least squares, 020201 artificial intelligence & image processing, Geometry and Topology, Radius of convergence, Analysis
Abstract

International audience; We develop a local convergence of an iterative method for solving nonlinear least squares problems with operator decomposition under the classical and generalized Lipschitz conditions. We consider the case of both zero and nonzero residuals and determine their convergence orders. We use two types of Lipschitz conditions (center and restricted region conditions) to study the convergence of the method. Moreover, we obtain a larger radius of convergence and tighter error estimates than in previous works. Hence, we extend the applicability of this method under the same computational effort.

Published
2021

28. Computing multiple roots of polynomials in stochastic arithmetic with Newton method and approximate GCD

Author

Graillat, Stef, Jézéquel, Fabienne, Queiros Martins, Enzo, Spyropoulos, Maxime, Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Université paris 2 Panthéon-Assas, JEZEQUEL, Fabienne, Plateforme d'analyse pour l'arithmétique flottante - - INTERFLOP2020 - ANR-20-CE46-0009 - AAPG2020 - VALID, and ANR-20-CE46-0009,INTERFLOP,Plateforme d'analyse pour l'arithmétique flottante(2020)

Subjects
Discrete Stochastic Arithmetic, floating-point arithmetic, [INFO.INFO-AO]Computer Science [cs]/Computer Arithmetic, MathematicsofComputing_NUMERICALANALYSIS, [MATH.MATH-NA] Mathematics [math]/Numerical Analysis [math.NA], [INFO.INFO-NA]Computer Science [cs]/Numerical Analysis [cs.NA], approximate GCD, Newton method, [INFO.INFO-NA] Computer Science [cs]/Numerical Analysis [cs.NA], ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, rounding errors, [INFO.INFO-AO] Computer Science [cs]/Computer Arithmetic, numerical validation, [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA]
Abstract

In this article, we propose new methods to compute multiple roots of polynomials in floating-point arithmetic. We rely on stochastic arithmetic that makes it possible to deal with rounding errors. We develop the concept of stochastic GCD that we use to deflate a polynomial in order to obtain a polynomial with single roots. We can then apply Newton method to get fast and accurate approximations of the roots. Numerical experiments show the effectiveness and efficiency of our methods.

Published
2021

29. Mixed Precision Low Rank Approximations and their Application to Block Low Rank LU Factorization

Author

Patrick Amestoy, Olivier Boiteau, Alfredo Buttari, Matthieu Gerest, Fabienne Jézéquel, Jean-Yves L’Excellent, Theo Mary, Mumps Technologies, Algorithmes Parallèles et Optimisation (IRIT-APO), Institut de recherche en informatique de Toulouse (IRIT), Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, EDF R&D (EDF R&D), EDF (EDF), Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), 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), CIFRE PhDthesis of Matthieu Gerest funded by EDF, Mumps Technologies [Lyon], Centre National de la Recherche Scientifique (CNRS), and Université Paris-Panthéon-Assas

Subjects
floating-point arithmetic, multiprecision algorithms, Applied Mathematics, General Mathematics, [INFO.INFO-AO]Computer Science [cs]/Computer Arithmetic, block low-rank matrices, linear systems, singular value decomposition, [INFO.INFO-NA]Computer Science [cs]/Numerical Analysis [cs.NA], rounding error analysis, Computational Mathematics, LU factorization, low-rank approximations, numerical linear algebra, data sparse matrices, mixed precision algorithms, [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA]
Abstract

We introduce a novel approach to exploit mixed precision arithmetic for low-rank approximations. Our approach is based on the observation that singular vectors associated with small singular values can be stored in lower precisions while preserving high accuracy overall. We provide an explicit criterion to determine which level of precision is needed for each singular vector. We apply this approach to block low-rank (BLR) matrices, most of whose off-diagonal blocks have low rank. We propose a new BLR LU factorization algorithm that exploits the mixed precision representation of the blocks. We carry out the rounding error analysis of this algorithm and prove that the use of mixed precision arithmetic does not compromise the numerical stability of the BLR LU factorization. Moreover, our analysis determines which level of precision is needed for each floating-point operation (flop), and therefore guides us toward an implementation that is both robust and efficient. We evaluate the potential of this new algorithm on a range of matrices coming from real-life problems in industrial and academic applications. We show that a large fraction of the entries in the LU factors and flops to perform the BLR LU factorization can be safely switched to lower precisions, leading to significant reductions of the storage and expected time costs, of up to a factor three using fp64, fp32, and bfloat16 arithmetics.

Published
2021

30. Dual tree traversal on integrated GPUs for astrophysical N-body simulations

Author

Maxime Touche, Pierre Fortin, Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), and Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)

Subjects
hybrid CPU-GPU algorithm, astrophysics, 010304 chemical physics, Computer science, Fast multipole method, [SCCO.COMP]Cognitive science/Computer science, fast multipole method, integrated GPU, 01 natural sciences, 7. Clean energy, Theoretical Computer Science, Computational science, Computer Science::Performance, Tree traversal, Hardware and Architecture, 0103 physical sciences, Computer Science::Mathematical Software, Dual tree, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Multipole expansion, dual tree traversal, Computer Science::Operating Systems, 010303 astronomy & astrophysics, Time complexity, Software
Abstract

International audience; In astrophysical N-body simulations, O(N) fast multipole methods (FMMs) with dual tree traversal (DTT) on multi-core CPUs are faster than O(N log N) CPU tree-codes but can still be outperformed by GPU ones. In this paper, we aim at combining the best algorithm , namely FMM with DTT, with the most powerful hardware currently available, namely GPUs. In the astrophysical context requiring low accuracies and non-uniform particle distributions, we show that such combination can be achieved thanks to an hybrid CPU-GPU algorithm on integrated GPUs: while the DTT is performed on the CPU cores, the far-and near-field computations are all performed on the GPU cores. We show how to efficiently expose the interactions resulting from the DTT to the GPU cores, how to deploy both the far-and near-field computations on GPU and how to overlap the parallel DTT on CPU with GPU computations. Based on the falcON code and using OpenCL on AMD Accelerated Processing Units and on Intel integrated GPUs, this first heterogeneous deployment of DTT for FMM outperforms standard multi-core CPUs, and matches GPU and high-end CPU performance, being hence more cost-and power-efficient.

Published
2019

31. Motion and acceleration from image assimilation with evolution models

Author

Dominique Béréziat, Isabelle Herlin, Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Inria Lille - Nord Europe, and Institut National de Recherche en Informatique et en Automatique (Inria)

Subjects
fluid flow, Discretization, Computer science, Optical flow, Image processing, 010103 numerical & computational mathematics, 02 engineering and technology, 01 natural sciences, data assimilation fluid flow, Acceleration, Artificial Intelligence, motion, Motion estimation, 0202 electrical engineering, electronic engineering, information engineering, 0101 mathematics, Electrical and Electronic Engineering, Coriolis force, gravity force, data assimilation, Sequence, Applied Mathematics, Dynamics (mechanics), shallow water, acceleration, Real image, Computational Theory and Mathematics, [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], Signal Processing, 020201 artificial intelligence & image processing, Computer Vision and Pattern Recognition, Statistics, Probability and Uncertainty, Algorithm
Abstract

International audience; Image sequences allow visualizing dynamic systems and understanding their intrinsic characteristics. One first component of this dynamics is retrieved from the estimation of the velocity displayed on the sequence. Motion estimation has been extensively studied in the literature of image processing and computer vision. In this paper, we step beyond the traditional optical flow methods and address the problem of recovering the acceleration from the whole temporal sequence. This issue has been poorly investigated, even if this is of major importance for major data types, such as fluid flow images. Acceleration is defined as the space-time function resulting from the forces applied to the studied system. To estimate its value, we propose a variational approach where an energy function is designed to model both the motion and the acceleration fields. The contributions of the paper are twofold: first, we introduce a unified variational formulation of motion and acceleration under space-time constraints; second, we describe the minimization scheme, which allows retrieving the estimations, and provide the full information on the discretization schemes. Last, experiments illustrate the potentiality of the method on synthetic and real image sequences, visualizing fluid-like flows, where direct and precise calculation of acceleration is of primary importance.

Published
2018

32. Numerical validation of half precision simulations

Author

Sara sadat Hoseininasab, Thibault Hilaire, Fabienne Jézéquel, Université Panthéon-Assas (UP2), Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), and JEZEQUEL, Fabienne

Subjects
Floating point, floating-point arithmetic, Computer science, Computation, auto-tuning, Double-precision floating-point format, 010103 numerical & computational mathematics, 02 engineering and technology, [INFO] Computer Science [cs], 01 natural sciences, Quality (physics), half precision, Robustness (computer science), Arbitrary-precision arithmetic, 0202 electrical engineering, electronic engineering, information engineering, Code (cryptography), rounding errors, numerical validation, [INFO]Computer Science [cs], 0101 mathematics, ComputingMilieux_MISCELLANEOUS, mixed precision, Rounding, [INFO.INFO-AO]Computer Science [cs]/Computer Arithmetic, discrete stochastic arithmetic, 020202 computer hardware & architecture, [INFO.INFO-AO] Computer Science [cs]/Computer Arithmetic, Algorithm, numerical quality
Abstract

International audience; In this article, we show how to control the numerical quality of half precision computations using stochastic arithmetic. The CADNA library that is used to estimate rounding errors and detect numerical instabilities in floating-point codes has been improved and extended to support half precision. A performance gain up to a factor 20 has been observed w.r.t. accuracy estimation in arbitrary precision. Furthermore we present how to generate codes mixing half, single, and double precision with a requested accuracy on results providing a user-defined numerical quality of the code. Control of robustness and floating-point auto-tuning taking into account half precision have been successfully performed on various numerical simulations, in particular a control application.

Published
2021

33. Fast rounding error estimation for compute-intensive operations using standard floating-point arithmetic

Author

Jézéquel, Fabienne, Graillat, Stef, Mukunoki, Daichi, Imamura, Toshiyuki, Iakymchuk, Roman, JEZEQUEL, Fabienne, Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Université Panthéon-Assas (UP2), RIKEN Center for Computational Science [Kobe] (RIKEN CCS), RIKEN - Institute of Physical and Chemical Research [Japon] (RIKEN), Fraunhofer Institute of Industrial Mathematics (Fraunhofer ITWM), and Fraunhofer (Fraunhofer-Gesellschaft)

Subjects
[INFO.INFO-AO]Computer Science [cs]/Computer Arithmetic, [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], [INFO.INFO-AO] Computer Science [cs]/Computer Arithmetic, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
2021

34. Benefits of stochastic arithmetic in high performance simulations and arbitrary precision codes

Author

Jézéquel, Fabienne, JEZEQUEL, Fabienne, Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), and Université Panthéon-Assas (UP2)

Subjects
Discrete Stochastic Arithmetic, floating-point arithmetic, BLAS, Newton method, [INFO.INFO-AO]Computer Science [cs]/Computer Arithmetic, rounding errors, [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], numerical validation, polynomial roots, [INFO.INFO-AO] Computer Science [cs]/Computer Arithmetic, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], approximate GCD, ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
2021

35. Precision auto-tuning and control of accuracy in high performance simulations

Author

Jézéquel, Fabienne, JEZEQUEL, Fabienne, Université Panthéon-Assas (UP2), Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, and Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)

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

International audience

Published
2021

36. Block Low-Rank Matrices with Shared Bases: Potential and Limitations of the BLR^2 Format

Author

Alfredo Buttari, Théo Mary, Cleve Ashcraft, ANSYS, Algorithmes Parallèles et Optimisation (IRIT-APO), Institut de recherche en informatique de Toulouse (IRIT), Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1)-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées, Performance et Qualité des Algorithmes Numériques (PEQUAN), Laboratoire d'Informatique de Paris 6 (LIP6), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1), Centre National de la Recherche Scientifique (CNRS), and LIP6

Subjects
Rank (linear algebra), Astrophysics::High Energy Astrophysical Phenomena, 010103 numerical & computational mathematics, Astrophysics::Cosmology and Extragalactic Astrophysics, computer.software_genre, 01 natural sciences, law.invention, Separable space, Matrix (mathematics), law, numerical linear algebra, [INFO]Computer Science [cs], 0101 mathematics, [MATH]Mathematics [math], Column (data store), Astrophysics::Galaxy Astrophysics, Mathematics, Block (data storage), Discrete mathematics, hierarchical matrices, Numerical linear algebra, block low-rank matrices, Special class, LU decomposition, Data sparse matrices, LU factorization, computer, Analysis, block separable matrices
Abstract

International audience; We investigate a special class of data sparse rank-structured matrices that combine a flat block low-rank (BLR) partitioning with the use of shared (called nested in the hierarchical case) bases. This format is to H 2 matrices what BLR is to H matrices: we therefore call it the BLR 2 matrix format. We present algorithms for the construction and LU factorization of BLR 2 matrices, and perform their cost analysis-both asymptotically and for a fixed problem size. With weak admissibility, BLR 2 matrices reduce to block separable matrices (the flat version of HBS/HSS). Our analysis and numerical experiments reveal some limitations of BLR 2 matrices with weak admissibility, which we propose to overcome with two approaches: strong admissibility, and the use of multiple shared bases per row and column.

Published
2020

37. Fusion of rain radar images and wind forecasts in a deep learning model applied to rain nowcasting

Author

Julien Brajard, Arthur Filoche, Vincent Bouget, Anastase Alexandre Charantonis, Dominique Béréziat, Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Nansen Environmental and Remote Sensing Center [Bergen] (NERSC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE), Laboratoire d'Océanographie et du Climat : Expérimentations et Approches Numériques (LOCEAN), Institut Pierre-Simon-Laplace (IPSL (FR_636)), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Institut national des sciences de l'Univers (INSU - CNRS)-École polytechnique (X)-Centre National d'Études Spatiales [Toulouse] (CNES)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Institut national des sciences de l'Univers (INSU - CNRS)-École polytechnique (X)-Centre National d'Études Spatiales [Toulouse] (CNES)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP)-Institut de Recherche pour le Développement (IRD)-Muséum national d'Histoire naturelle (MNHN)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU), Muséum national d'Histoire naturelle (MNHN)-Institut de Recherche pour le Développement (IRD)-Institut national des sciences de l'Univers (INSU - CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Institut Pierre-Simon-Laplace (IPSL (FR_636)), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Institut national des sciences de l'Univers (INSU - CNRS)-École polytechnique (X)-Centre National d'Études Spatiales [Toulouse] (CNES)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)-École normale supérieure - Paris (ENS-PSL), and Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-École polytechnique (X)-Centre National d'Études Spatiales [Toulouse] (CNES)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)

Subjects
Signal Processing (eess.SP), FOS: Computer and information sciences, Computer Science - Machine Learning, Meteorology, Nowcasting, Science, Optical flow, radar data, FOS: Physical sciences, rain nowcasting, 02 engineering and technology, Wind speed, law.invention, Machine Learning (cs.LG), law, 020204 information systems, Radar imaging, 0202 electrical engineering, electronic engineering, information engineering, FOS: Electrical engineering, electronic engineering, information engineering, [INFO]Computer Science [cs], Precipitation, Radar, Electrical Engineering and Systems Science - Signal Processing, deep learning, business.industry, Deep learning, Training (meteorology), Physics - Atmospheric and Oceanic Physics, 13. Climate action, [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV], Atmospheric and Oceanic Physics (physics.ao-ph), General Earth and Planetary Sciences, Environmental science, 020201 artificial intelligence & image processing, Artificial intelligence, business
Abstract

Short- or mid-term rainfall forecasting is a major task with several environmental applications such as agricultural management or flood risk monitoring. Existing data-driven approaches, especially deep learning models, have shown significant skill at this task, using only rainfall radar images as inputs. In order to determine whether using other meteorological parameters such as wind would improve forecasts, we trained a deep learning model on a fusion of rainfall radar images and wind velocity produced by a weather forecast model. The network was compared to a similar architecture trained only on radar data, to a basic persistence model and to an approach based on optical flow. Our network outperforms by 8% the F1-score calculated for the optical flow on moderate and higher rain events for forecasts at a horizon time of 30 min. Furthermore, it outperforms by 7% the same architecture trained using only rainfall radar images. Merging rain and wind data has also proven to stabilize the training process and enabled significant improvement especially on the difficult-to-predict high precipitation rainfalls., In press in Remote Sensing (MDPI)

Published
2020

38. A fast parallel high-precision summation algorithm based on AccSumK

Author

Xiaojun Lei, Tongxiang Gu, Stef Graillat, Hao Jiang, Jin Qi, Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), and ANR-20-CE48-0014,NuSCAP,Sûreté numérique pour les preuves assistées par ordinateur(2020)

Subjects
010101 applied mathematics, Higher precision, Computational Mathematics, Accurate summation, Parallel algorithms, [INFO.INFO-AO]Computer Science [cs]/Computer Arithmetic, Applied Mathematics, Floating-point arithmetic, 010103 numerical & computational mathematics, [INFO.INFO-NA]Computer Science [cs]/Numerical Analysis [cs.NA], 0101 mathematics, 01 natural sciences
Abstract

In this paper, we present a new parallel accurate algorithm called PAccSumK for computing summation of floating-point numbers. It is based on AccSumK algorithm. In the experiment, for the summation problems with large condition numbers, our algorithm outperforms in term of accuracy and computing time the PSumK algorithm. The reason is that our algorithm is based on a more accurate algorithm called AccSumK algorithm compared to the SumL algorithm used in PSumK. The proposed parallel algorithms in this paper is designed to compute a result as if computed internally in K-fold the working precision. Numerical results are presented showing the performance and the accuracy of our new parallel algorithm for calculating summation.

Published
2022

39. Conjugate Gradient Solvers with High Accuracy and Bit-wise Reproducibility between CPU and GPU using Ozaki Scheme

Author

Takeshi Ogita, Daichi Mukunoki, Katsuhisa Ozaki, Roman Iakymchuk, RIKEN Center for Computational Science [Kobe] (RIKEN CCS), RIKEN - Institute of Physical and Chemical Research [Japon] (RIKEN), Shibaura Institute of Technology, Tokyo Woman's Christian University, Department of Mathematics, Tokyo Woman's Christian University (TWCU), Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), and Iakymchuk, Roman

Subjects
Computer science, Computation, GPU, 010103 numerical & computational mathematics, 02 engineering and technology, Parallel computing, 01 natural sciences, Basic Linear Algebra Subprograms, Conjugate gradient method, Convergence (routing), [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], 0202 electrical engineering, electronic engineering, information engineering, Conjugate Gradient, 0101 mathematics, Bitwise operation, Accuracy, [INFO.INFO-MS]Computer Science [cs]/Mathematical Software [cs.MS], 020203 distributed computing, Rounding, [INFO.INFO-AO]Computer Science [cs]/Computer Arithmetic, Krylov subspace, [MATH.MATH-NA] Mathematics [math]/Numerical Analysis [math.NA], Reproducibility, Nondeterministic algorithm, Heterogenous computing, [INFO.INFO-MS] Computer Science [cs]/Mathematical Software [cs.MS], [INFO.INFO-AO] Computer Science [cs]/Computer Arithmetic, CPU, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA]
Abstract

On Krylov subspace methods such as the Conjugate Gradient (CG), the number of iterations until convergence may increase due to the loss of computation accuracy caused by rounding errors in floating-point computations. Besides, as the order of operations is non-deterministic on parallel computations, the result and the behavior of the convergence may be non-identical in different environments, even for the same input. This paper presents a new approach for the CG method with high accuracy as well as bit-level reproducibility of computed solutions on many-core processors, including both x86 CPUs and NVIDIA GPUs. In our proposed approach, accurate and reproducible operations are installed into all the inner-product based operations such as matrix-vector multiplication and dot-product, which are the main sources that may disturb reproducibility in the CG method. The accurate and reproducible operations are performed using the Ozaki scheme, which is the error-free transformation for dot-product that can ensure the correct-rounding. As this method can be built upon vendor-provided linear algebra libraries such as Intel Math Kernel Library and NVIDIA cuBLAS/ cuSparse, it reduces the development cost. In this paper, showing some examples with the non-identical conver-gences and computed solutions on different platforms, we demonstrate the applicability and the effectiveness of the proposed approach as well as its performance on both CPUs and GPUs. Besides, we compare against an existing accurate and reproducible CG implementation based on the Exact BLAS (ExBLAS) on CPUs.

Published
2020

40. Rounding Error Analysis of Linear Recurrences Using Generating Series

Author

Mezzarobba, Marc, Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), and ANR-14-CE25-0018,Fast Relax,Approximation rapide et fiable(2014)

Subjects
FOS: Computer and information sciences, Computer Science - Symbolic Computation, [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], Applied Mathematics, [INFO.INFO-AO]Computer Science [cs]/Computer Arithmetic, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, FOS: Mathematics, Numerical Analysis (math.NA), Mathematics - Numerical Analysis, Symbolic Computation (cs.SC), [INFO.INFO-NA]Computer Science [cs]/Numerical Analysis [cs.NA], Analysis
Abstract

We develop a toolbox for the error analysis of linear recurrences with constant or polynomial coefficients, based on generating series, Cauchy's method of majorants, and simple results from analytic combinatorics. We illustrate the power of the approach by several nontrivial application examples. Among these examples are a new worst-case analysis of an algorithm for computing Bernoulli numbers, and a new algorithm for evaluating differentially finite functions in interval arithmetic while avoiding interval blow-up.

Published
2020

41. Solving Block Low-Rank Linear Systems by LU Factorization is Numerically Stable

Author

Nicholas J. Higham, Théo Mary, Department of Mathematics [Manchester] (School of Mathematics), University of Manchester [Manchester], Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS), and Sorbonne Université (SU)

Subjects
Rank (linear algebra), floating-point arithmetic, General Mathematics, 010103 numerical & computational mathematics, computer.software_genre, 01 natural sciences, Stability (probability), law.invention, Factorization, law, Applied mathematics, [INFO]Computer Science [cs], 0101 mathematics, [MATH]Mathematics [math], Mathematics, Numerical linear algebra, Applied Mathematics, Linear system, [INFO.INFO-NA]Computer Science [cs]/Numerical Analysis [cs.NA], LU decomposition, rounding error analysis, 010101 applied mathematics, Computational Mathematics, numerical stability, Block low-rank matrices, LU factorization, Round-off error, computer, [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA], Numerical stability
Abstract

Block low-rank (BLR) matrices possess a blockwise low-rank property that can be exploited to reduce the complexity of numerical linear algebra algorithms. The impact of these low-rank approximations on the numerical stability of the algorithms in floating-point arithmetic has not previously been analysed. We present rounding error analysis for the solution of a linear system by LU factorization of BLR matrices. Assuming that a stable pivoting scheme is used, we prove backward stability: the relative backward error is bounded by a modest constant times $\varepsilon $, where the low-rank threshold $\varepsilon $ is the parameter controlling the accuracy of the blockwise low-rank approximations. In addition to this key result, our analysis offers three new insights into the numerical behaviour of BLR algorithms. First, we compare the use of a global or local low-rank threshold and find that a global one should be preferred. Second, we show that performing intermediate recompressions during the factorization can significantly reduce its cost without compromising numerical stability. Third, we consider different BLR factorization variants and determine the update–compress–factor variant to be the best. Tests on a wide range of matrices from various real-life applications show that the predictions from the analysis are realized in practice.

Published
2020

42. Stochastic Rounding and its Probabilistic Backward Error Analysis

Author

Nicholas J. Higham, Théo Mary, Michael P. Connolly, Department of Mathematics [Manchester] (School of Mathematics), University of Manchester [Manchester], Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS), and Sorbonne Université (SU)

Subjects
Floating point, floating-point arithmetic, 010103 numerical & computational mathematics, computer.software_genre, 01 natural sciences, Error analysis, numerical linear algebra, stochastic rounding, [INFO]Computer Science [cs], 0101 mathematics, [MATH]Mathematics [math], probabilistic backward error analysis, Mathematics, Real number, Numerical linear algebra, Applied Mathematics, Rounding, stagnation, Probabilistic logic, TheoryofComputation_GENERAL, round to nearest, [INFO.INFO-NA]Computer Science [cs]/Numerical Analysis [cs.NA], rounding error analysis, Computational Mathematics, computer, Algorithm, [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA]
Abstract

International audience; Stochastic rounding rounds a real number to the next larger or smaller floating-point number with probabilities 1 minus the relative distances to those numbers. It is gaining attention in deep learning because it can increase the success of low precision computations. We compare basic properties of stochastic rounding with those for round to nearest, finding properties in common as well as significant differences. We prove that for stochastic rounding the rounding errors are mean independent random variables with zero mean. We derive a new version of our probabilistic error analysis theorem from [SIAM J. Sci. Comput., 41 (2019), pp. A2815-A2835], weakening the assumption of independence of the random variables to mean independence. These results imply that for a wide range of linear algebra computations the backward error for stochastic rounding is unconditionally bounded by a multiple of √ nu to first order, with a certain probability, where n is the problem size and u is the unit roundoff. This is the first scenario where the rule of thumb that one can replace nu by √ nu in a rounding error bound has been shown to hold without any additional assumptions on the rounding errors. We also explain how stochastic rounding avoids the phenomenon of stagnation in sums, whereby small addends are obliterated by round to nearest when they are too small relative to the sum.

Published
2020

43. Sharper Probabilistic Backward Error Analysis for Basic Linear Algebra Kernels with Random Data

Author

Nicholas J. Higham, Théo Mary, Department of Mathematics [Manchester] (School of Mathematics), University of Manchester [Manchester], Centre National de la Recherche Scientifique (CNRS), Sorbonne Université (SU), Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, and Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Basic linear algebra, Numerical linear algebra, Floating point, Applied Mathematics, Probabilistic logic, 010103 numerical & computational mathematics, [INFO.INFO-NA]Computer Science [cs]/Numerical Analysis [cs.NA], computer.software_genre, 01 natural sciences, Matrix multiplication, Computational Mathematics, Error analysis, Applied mathematics, [INFO]Computer Science [cs], 0101 mathematics, Concentration inequality, [MATH]Mathematics [math], Martingale (probability theory), computer, ComputingMilieux_MISCELLANEOUS, [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA], Mathematics
Abstract

Standard backward error analyses for numerical linear algebra algorithms provide worst-case bounds that can significantly overestimate the backward error. Our recent probabilistic error analysis, w...

Published
2020

44. Estimation de la dynamique atmosphérique à partir de l’assimilation d’images radars multi-échelles. Application à la prévision des taux de précipitation à courte échéance, à partir des images radars

Author

Zebiri, Aniss, Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Sorbonne Université, Isabelle Herlin, Dominique Béréziat (co-directeur), and Emmanuel Buisson (co-directeur)

Subjects
Multiscale, Images Radar, [INFO.INFO-TS]Computer Science [cs]/Signal and Image Processing, Multi-échelle, Prévision à court terme des précipitations, Rain nowcasting, Radar images, Assimilation de donnée, Data Assimilation
Abstract

The forecast of precipitation takes a special place, in view of their direct economic impact. These forecasts allow, on the one hand, to anticipate environmental constraints and optimize, for example, the management of water resources, and, on the other hand, to anticipate flood risks. The aim of this study is to improve the nowcasting of precipitation rate of the Rain Nowcast (RN) algorithm that previously provides relevant forecasts for a time horizon of 30 minutes. A multi-scale approach is suggested to merge two types of radar data, with different spatial resolutions, in order to increase the time horizon of the forecast while ensuring a forecast of quality in terms of both location and quantity of precipitation.We propose two multi-scales algorithms, the first one is sequential "Sequential Motion RN": a global estimation with regional data to guide a local estimation with local data. The second is parallel "Parallel Motion RN": using both local and regional data simultaneously. Two other methods dedicated to forecasting have been proposed: geostrophic wind hypothesis, which involves correcting the underestimation of motion intensity for low contrast structures in radar images. The second method: histogram correction, which involves correcting the smoothing effect caused by the numerical scheme by using a widely described technique in literature, to correct rain gauge measurements estimated from radar images.; La prévision du taux de précipitations occupe une place particulière, compte tenu de leur impact direct sur l'économie. Ces prévisions permettent, d’une part, d’anticiper les contraintes environnementales et d’optimiser par exemple la gestion des ressources en eau, et, d’autre part, d'anticiper les risques d’inondations.L'objectif de ces travaux est d'améliorer la prévision à court terme de taux de précipitation de l'algorithme Rain Nowcast (RN) qui fournissait auparavant des prévisions pertinentes pour un horizon temporel de 30 minutes. Une approche multi-échelle a été proposée qui permet de fusionner deux types de données radars, de résolutions spatiales différentes afin d'augmenter l'horizon temporel de prévision tout en garantissant une prévision de qualité en terme de localisation et quantité de précipitation. Nous proposons deux algorithmes multi-échelles , le premier est séquentiel «Sequential Motion RN» : une estimation globale avec les données régionales pour guider une estimation locale avec des données locales. Le second est parallèle «Parallel Motion RN»: utilisation simultanée des données locales et régionales.Deux autres méthodes dédiées à la prévision sont proposées : l'hypothèse de vent géostrophique, consiste à corriger la sous-estimation de l'intensité du mouvement pour les structures peu contrastées dans les images radars. La deuxième méthode : la correction d’histogramme, consiste à corriger l’effet de lissage causé par le schéma numérique en utilisant une technique largement décrite dans la littérature, pour corriger les mesures de pluviométrie estimées à partir d’images radar."

Published
2020

45. Estimation of dynamics from multiscale image assimilation : application to Rain nowcasting from ground radar images

Author

Zebiri, Aniss, Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Sorbonne Université, Isabelle Herlin, Dominique Béréziat, and Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Rainfall, Multiscale, Précipitation, [INFO.INFO-TS]Computer Science [cs]/Signal and Image Processing, Observation radar, Multi-échelle, Data assimilation, Estimation du mouvement, Prévision, Prevision, Radar acquisition, Motion estimation, Assimilation de données
Abstract

The forecast of precipitation takes a special place, in view of their direct economic impact. These forecasts allow, on the one hand, to anticipate environmental constraints and optimise, for example, the management of water resources, and, on the other hand, to anticipate flood risks. The aim of this study is to improve the nowcasting of precipitation rate of the Rain Nowcast (RN) algorithm that previously provides relevant forecasts for a time horizon of 30 minutes. A multi-scale approach is suggested to merge two types of radar data, with different spatial resolutions, in order to increase the time horizon of the forecast while ensuring a forecast of quality in terms of both location and quantity of precipitation. We propose two multi-scales algorithms, the first one is sequential "Sequential Motion RN" : a globale estimation with regional data to guide a local estimation with local data. The second is parallel "Parallel Motion RN": using both local and regional data simultaneously. Two other methods dedicated to forecast have been proposed: geostrophic wind hypothesis, which involves correcting the underestimation motion intensity for low contrast structures in radar images. The second method: histogram correction, which involves correcting the smoothing effect caused by the numerical scheme by using a widely described technique in literature, to correct raingauge measurements estimated from radar images.; La prévision du taux de précipitations occupe une place particulière, compte tenu de leur impact direct sur l'économie. Ces prévisions permettent, d’une part, d’anticiper les contraintes environnementales et d’optimiser par exemple la gestion des ressources en eau, et, d’autre part, d'anticiper les risques d’inondations. L'objectif de ces travaux est d'améliorer la prévision à court terme de taux de précipitation de l'algorithme Rain Nowcast (RN) qui fournissait auparavant des prévisions pertinentes pour un horizon temporel de 30 minutes. Une approche multi-échelle a été proposée qui permet de fusionner deux types de données radars, de résolutions spatiales différentes afin d'augmenter l'horizon temporel de prévision tout en garantissant une prévision de qualité en terme de localisation et quantité de précipitation. Nous proposons deux algorithmes multi-échelles , le premier est séquentiel «Sequential Motion RN» : une estimation globale avec les données régionales pour guider une estimation locale avec des données locales. Le second est parallèle «Parallel Motion RN»: utilisation simultanée des données locales et régionales. Deux autres méthodes dédiées à la prévision sont proposées : l'hypothèse de vent géostrophique, consiste à corriger la sous-estimation de l'intensité du mouvement pour les structures peu contrastées dans les images radars. La deuxième méthode : la correction d’histogramme, consiste à corriger l’effet de lissage causé par le schéma numérique en utilisant une technique largement décrite dans la littérature, pour corriger les mesures de pluviométrie estimées à partir d’images radar.

Published
2020

46. Estimation of atmospheric dynamics from the assimilation of multi-scale radar images. Application to the nowcasting of rain precipitation from radar images

Author

Zebiri, Aniss, Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Sorbonne Université, Isabelle Herlin, Dominique Béréziat (co-directeur), and Emmanuel Buisson (co-directeur)

Subjects
Multiscale, Images Radar, [INFO.INFO-TS]Computer Science [cs]/Signal and Image Processing, Multi-échelle, Prévision à court terme des précipitations, Rain nowcasting, Radar images, Assimilation de donnée, Data Assimilation
Abstract

The forecast of precipitation takes a special place, in view of their direct economic impact. These forecasts allow, on the one hand, to anticipate environmental constraints and optimize, for example, the management of water resources, and, on the other hand, to anticipate flood risks. The aim of this study is to improve the nowcasting of precipitation rate of the Rain Nowcast (RN) algorithm that previously provides relevant forecasts for a time horizon of 30 minutes. A multi-scale approach is suggested to merge two types of radar data, with different spatial resolutions, in order to increase the time horizon of the forecast while ensuring a forecast of quality in terms of both location and quantity of precipitation.We propose two multi-scales algorithms, the first one is sequential "Sequential Motion RN": a global estimation with regional data to guide a local estimation with local data. The second is parallel "Parallel Motion RN": using both local and regional data simultaneously. Two other methods dedicated to forecasting have been proposed: geostrophic wind hypothesis, which involves correcting the underestimation of motion intensity for low contrast structures in radar images. The second method: histogram correction, which involves correcting the smoothing effect caused by the numerical scheme by using a widely described technique in literature, to correct rain gauge measurements estimated from radar images.; La prévision du taux de précipitations occupe une place particulière, compte tenu de leur impact direct sur l'économie. Ces prévisions permettent, d’une part, d’anticiper les contraintes environnementales et d’optimiser par exemple la gestion des ressources en eau, et, d’autre part, d'anticiper les risques d’inondations.L'objectif de ces travaux est d'améliorer la prévision à court terme de taux de précipitation de l'algorithme Rain Nowcast (RN) qui fournissait auparavant des prévisions pertinentes pour un horizon temporel de 30 minutes. Une approche multi-échelle a été proposée qui permet de fusionner deux types de données radars, de résolutions spatiales différentes afin d'augmenter l'horizon temporel de prévision tout en garantissant une prévision de qualité en terme de localisation et quantité de précipitation. Nous proposons deux algorithmes multi-échelles , le premier est séquentiel «Sequential Motion RN» : une estimation globale avec les données régionales pour guider une estimation locale avec des données locales. Le second est parallèle «Parallel Motion RN»: utilisation simultanée des données locales et régionales.Deux autres méthodes dédiées à la prévision sont proposées : l'hypothèse de vent géostrophique, consiste à corriger la sous-estimation de l'intensité du mouvement pour les structures peu contrastées dans les images radars. La deuxième méthode : la correction d’histogramme, consiste à corriger l’effet de lissage causé par le schéma numérique en utilisant une technique largement décrite dans la littérature, pour corriger les mesures de pluviométrie estimées à partir d’images radar."

Published
2020

47. A Correctly-Rounded Fixed-Point-Arithmetic Dot-Product Algorithm

Author

Sylvie Boldo, Thibault Hilaire, Diane Gallois-Wong, 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 de Recherche en Informatique (LRI), CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS)-CentraleSupélec-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS), Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, and Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Signal processing, Sum-of-Products, Computer science, Fixed-Point Arithmetic, Rounding, [INFO.INFO-AO]Computer Science [cs]/Computer Arithmetic, Sorting, Canonical normal form, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], Dot product, 010103 numerical & computational mathematics, 02 engineering and technology, 01 natural sciences, 020202 computer hardware & architecture, Dot Product, Correct Round- ing, 0202 electrical engineering, electronic engineering, information engineering, 0101 mathematics, Focus (optics), Fixed-point arithmetic, Digital filter, Algorithm, Odd Rounding
Abstract

International audience; Dot products (also called sums of products) are ubiquitous in matrix computations, for instance in signal processing. We are especially interested in digital filters, where they are the core operation. We therefore focus on fixed-point arithmetic, used in embedded systems for time and energy efficiency. Common dot product algorithms ensure faithful rounding. For the sake of accuracy and reproducibility, we want to ensure correct rounding. This article describes an algorithm that computes a correctly-rounded sum of products from inputs whose format is known in advance. This algorithm relies on odd rounding (that is easily implemented in hardware) and comes with a careful proof and some cost analysis.

Published
2020

48. Mixed Precision Block Fused Multiply-Add: Error Analysis and Application to GPU Tensor Cores

Author

Nicholas J. Higham, Srikara Pranesh, Florent Lopez, Pierre Blanchard, Théo Mary, Department of Mathematics [Manchester] (School of Mathematics), University of Manchester [Manchester], Innovative Computing Laboratory [Knoxville] (ICL), The University of Tennessee [Knoxville], Centre National de la Recherche Scientifique (CNRS), Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, and Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)

Subjects
fused multiply-add, Floating point, floating-point arithmetic, Carry (arithmetic), matrix multiplication, 010103 numerical & computational mathematics, 01 natural sciences, law.invention, Computational science, Matrix (mathematics), law, Tensor (intrinsic definition), [INFO]Computer Science [cs], 0101 mathematics, [MATH]Mathematics [math], NVIDIA GPU, Mathematics, Block (data storage), Multiply–accumulate operation, Applied Mathematics, [INFO.INFO-NA]Computer Science [cs]/Numerical Analysis [cs.NA], LU decomposition, Matrix multiplication, rounding error analysis, Computational Mathematics, tensor cores, LU factorization, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA]
Abstract

International audience; Computing units that carry out a fused multiply-add (FMA) operation with matrix arguments, referred to as tensor units by some vendors, have great potential for use in scientific computing. However, these units are inherently mixed precision and existing rounding error analyses do not support them. We consider a mixed precision block FMA that generalizes both the usual scalar FMA and existing tensor units. We describe how to exploit such a block FMA in the numerical linear algebra kernels of matrix multiplication and LU factorization and give detailed rounding error analyses of both kernels. An important application is to GMRES-based iterative refinement with block FMAs, for which our analysis provides new insight. Our framework is applicable to the tensor core units in the NVIDIA Volta and Turing GPUs. For these we compare matrix multiplication and LU factorization with TC16 and TC32 forms of FMA, which differ in the precision used for the output of the tensor cores. Our experiments on an NVDIA V100 GPU confirm the predictions of the analysis that the TC32 variant is much more accurate than the TC16 one, and they show that the accuracy boost is obtained with almost no performance loss.

Published
2020

49. High performance SIMD modular arithmetic for polynomial evaluation

Author

Pierre Fortin, Ambroise Fleury, Michael Monagan, François Lemaire, Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-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), Department of Mathematics [Burnaby] (SFU), and Simon Fraser University (SFU.ca)

Subjects
FOS: Computer and information sciences, Computer Science - Symbolic Computation, Polynomial, Computer Networks and Communications, Computer science, modular arithmetic, 02 engineering and technology, instruction-level parallelism, Symbolic Computation (cs.SC), SIMD, Theoretical Computer Science, polynomial evaluation, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, 0202 electrical engineering, electronic engineering, information engineering, Polynomial greatest common divisor, Arithmetic, [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], operational intensity, Modular arithmetic, 020206 networking & telecommunications, Intrinsics, Symbolic computation, Computer Science Applications, Computational Theory and Mathematics, Computer Science - Distributed, Parallel, and Cluster Computing, Factorization of polynomials, 020201 artificial intelligence & image processing, Distributed, Parallel, and Cluster Computing (cs.DC), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Instruction-level parallelism, Software
Abstract

International audience; Two essential problems in Computer Algebra, namely polynomial factorization and polynomial greatest common divisor computation, can be efficiently solved thanks to multiple polynomial evaluations in two variables using modular arithmetic. In this article, we focus on the efficient computation of such polynomial evaluations on one single CPU core. We first show how to leverage SIMD computing for modular arithmetic on AVX2 and AVX-512 units, using both intrinsics and OpenMP compiler directives. Then we manage to increase the operational intensity and to exploit instruction-level parallelism in order to increase the compute efficiency of these polynomial evaluations. All this results in the end to performance gains up to about 5x on AVX2 and 10x on AVX-512.

Published
2020

50. Can we avoid rounding-error estimation in HPC codes and still get trustful results?

Author

Jézéquel, Fabienne, Graillat, Stef, Mukunoki, Daichi, Imamura, Toshiyuki, Iakymchuk, Roman, Performance et Qualité des Algorithmes Numériques (PEQUAN), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Université Panthéon-Assas (UP2), RIKEN Center for Computational Science [Kobe] (RIKEN CCS), RIKEN - Institute of Physical and Chemical Research [Japon] (RIKEN), Fraunhofer Institute of Industrial Mathematics (Fraunhofer ITWM), Fraunhofer (Fraunhofer-Gesellschaft), European Union’s Horizon 2020 research, innovation programme under the Marie Curie grant agreement via the Robust project No. 842528Japan Society for the Promotion of Science (JSPS) KAKENHI Grant No. 19K20286, and JEZEQUEL, Fabienne

Subjects
floating-point arithmetic, BLAS, rounding errors, numerical validation, [INFO]Computer Science [cs], Discrete Stochastic Arithmetic (DSA), [INFO] Computer Science [cs]
Abstract

Numerical validation enables one to improve the reliability of numerical computations that rely upon floating-point operations through obtaining trustful results. Discrete Stochastic Arithmetic (DSA) makes it possible to validate the accuracy of floating-point computations using random rounding. However, it may bring a large performance overhead compared with the standard floating-point operations. In this article, we show that with perturbed data it is possible to use standard floating-point arithmetic instead of DSA for the purpose of numerical validation. For instance, for codes including matrix multiplications, we can directly utilize the matrix multiplication routine (GEMM) of level-3 BLAS that is performed with standard floating-point arithmetic. Consequently, we can achieve a significant performance improvement by avoiding the performance overhead of DSA operations as well as by exploiting the speed of highly-optimized BLAS implementations. Finally, we demonstrate the performance gain using Intel MKL routines compared against the DSA version of BLAS routines.

Published
2020

Catalog

Books, media, physical & digital resources
See catalog results