Dérivation numérique | EPFL Graph Search

En analyse numérique, les algorithmes de dérivation numérique évaluent la dérivée d'une fonction mathématique ou d'un sous-programme de fonction en utilisant les valeurs de la fonction et peut-être d'autres propriétés connues sur la fonction. droite|255x255px Différences finies La méthode la plus simple consiste à utiliser des approximations de différences finies. Une simple estimation à deux points consiste à calculer la pente d'une droite sécante proche passant par les points et . On choisit un petit nombre h, qui représente une petite variation autour de x, qui peut être positive ou négative. La pente de cette droite est : \frac{f(x + h) - f(x)}{h}. Cette expression est le quotient de différence de Newton (également connu sous le nom de différence divisée du premier ordre). La pente de cette sécante diffère de la pente de la ligne tangente d'une quantité approximativement proportionnelle à h. Lorsque h

Computational Aspects of Jacobians of Hyperelliptic Curves

Alina Dudeanu

Nowadays, one area of research in cryptanalysis is solving the Discrete Logarithm Problem (DLP) in finite groups whose group representation is not yet exploited. For such groups, the best one can do is using a generic method to attack the DLP, the fastest of which remains the Pollard rho algorithm with

r

-adding walks. For the first time, we rigorously analyze the Pollard rho method with

r

-adding walks and prove a complexity bound that differs from the birthday bound observed in practice by a relatively small factor. There exist a multitude of open questions in genus

2

cryptography. In this case, the DLP is defined in large prime order subgroups of rational points that are situated on the Jacobian of a genus~

2

curve defined over a large characteristic finite field. We focus on one main topic, namely we present a new efficient algorithm for computing cyclic isogenies between Jacobians. Comparing to previous work that computes non cyclic isogenies in genus~

2

, we need to restrict to certain cases of polarized abelian varieties with specific complex multiplication and real multiplication. The algorithm has multiple applications related to the structure of the isogeny graph in genus~

2

, including random self-reducibility of DLP. It helps support the widespread intuition of choosing \emph{any} curve in a class of curves that satisfy certain public and well studied security parameters. Another topic of interest is generating hyperelliptic curves for cryptographic applications via the CM method that is based on the numerical estimation of the rational Igusa class polynomials. A recent development relates the denominators of the Igusa class polynomials to counting ideal classes in non maximal real quadratic orders whose norm is not prime to the conductor. Besides counting, our new algorithm provides precise representations of such ideal classes for all real quadratic fields and is part of an implementation in Magma of the recent theoretic work in the literature on the topic of denominators.

EPFL2016

Compressive sensing adaptation for polynomial chaos expansions

Panagiotis Tsilifis

Basis adaptation in Homogeneous Chaos spaces rely on a suitable rotation of the underlying Gaussian germ. Several rotations have been proposed in the literature resulting in adaptations with different convergence properties. In this paper we present a new adaptation mechanism that builds on compressive sensing algorithms, resulting in a reduced polynomial chaos approximation with optimal sparsity. The developed adaptation algorithm consists of a two-step optimization procedure that computes the optimal coefficients and the input projection matrix of a low dimensional chaos expansion with respect to an optimally rotated basis. We demonstrate the attractive features of our algorithm through several numerical examples including the application on Large-Eddy Simulation (LES) calculations of turbulent combustion in a HIFiRE scramjet engine. (C) 2018 Elsevier Inc. All rights reserved.

ACADEMIC PRESS INC ELSEVIER SCIENCE2019

MATHICSE Technical Report: Stability properties of a projector-splitting scheme for the dynamical low rank approximation of random parabolic equations

Yoshihito Kazashi, Fabio Nobile, Eva Vidlicková

We consider the Dynamical Low Rank (DLR) approximation of random parabolic equations and propose a class of fully discrete numerical schemes. Similarly to the continuous DLR approximation, our schemes are shown to satisfy a discrete variational formulation. By exploiting this property, we establish stability of our schemes: we show that our explicit and semi-implicit versions are conditionally stable under a parabolic type CFL condition which does not depend on the smallest singular value of the DLR solution; whereas our implicit scheme is unconditionally stable. Moreover, we show that, in certain cases, the semi-implicit scheme can be unconditionally stable if the randomness in the system is sufficiently small. Furthermore, we show that these schemes can be interpreted as projector-splitting integrators and are strongly related to the scheme proposed by Lubich et al. [BIT Num. Math., 54:171-188, 2014; SIAM J. on Num. Anal., 53:917-941, 2015], to which our stability analysis applies as well. The analysis is supported by numerical results showing the sharpness of the obtained stability conditions.

MATHICSE2020