Improved method for finding optimal formulae for bilinear maps in a finite field

Autor: Covanov, Svyatoslav

In 2012, Barbulescu, Detrey, Estibals and Zimmermann proposed a new framework to exhaustively search for optimal formulae for evaluating bilinear maps, such as Strassen or Karatsuba formulae. The main contribution of this work is a new criterion to a

Externí odkaz: http://arxiv.org/abs/1705.07728

Fast integer multiplication using generalized Fermat primes

Autor: Covanov, Svyatoslav, Thomé, Emmanuel

For almost 35 years, Sch{\"o}nhage-Strassen's algorithm has been the fastest algorithm known for multiplying integers, with a time complexity O(n $\times$ log n $\times$ log log n) for multiplying n-bit inputs. In 2007, F{\"u}rer proved that there ex

Externí odkaz: http://arxiv.org/abs/1502.02800

Multiplication algorithms : bilinear complexity and fast asymptotic methods

Autor: Covanov, Svyatoslav

Publikováno v: Symbolic Computation [cs.SC]. Université de Lorraine, 2018. English. ⟨NNT : 2018LORR0057⟩

Since 1960 and the result of Karatsuba, we know that the complexity of the multiplication (of integers or polynomials) is sub-quadratic: given a ring R, the product in R[X] of polynomials a_0 + a_1 X and b_0 + b_1 X, for any a_0, a_1, b_0 and b_1 in

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=dedup_wf_001::89203b7c7631097b67c4136cfc976809
https://theses.hal.science/tel-01825744

The Basic Polynomial Algebra Subprograms

Autor: Chen, Changbo, Covanov, Svyatoslav, Mansouri, Farnam, Moir, Robert, Moreno Maza, Marc, Xie, Ning, Xie, Yuzhen

Publikováno v: ACM Communications in Computer Algebra
ACM Communications in Computer Algebra, Association for Computing Machinery (ACM), 2016, 50 (3), pp.97--100. ⟨10.1145/3015306.3015312⟩
ACM Communications in Computer Algebra, 2016, 50 (3), pp.97--100. ⟨10.1145/3015306.3015312⟩

International audience; The Basic Polynomial Algebra Subprograms (BPAS) provides arithmetic operations (multiplication, division, root isolation, etc.) for univariate and multivariate polynomials over common types of coefficients (prime fields, compl

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::a21ba17a15295828ba7326e9ec5429b4
https://hal.archives-ouvertes.fr/hal-01404718/file/ISSAC_Software_Demo_CCMMXX.pdf

Basic Polynomial Algebra Subprograms

Autor: Chen, Changbo, Covanov, Svyatoslav, Mansouri, Farnam, Maza, Marc, Xie, Ning, Xie, Yuzhen

Publikováno v: ACM Communications in Computer Algebra; February 2015, Vol. 48 Issue: 4 p197-201, 5p