Loading Events

« All Events

  • This event has passed.

PhD thesis defense : Svyatoslav Covanov

June 5, 2018 @ 1:30 pm - 2:30 pm

Svyatoslav Covanov invites you to his PhD thesis defense “Multiplication algorithms: bilinear complexity and fast asymptotic methods“.
It will take place on June 5, at 1:30 PM in the C005 room.

Abstract:

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 R, can be computed with three and not four multiplications over R: (a_0 + a_1X)(b_0 + b_1X) = m_0 + (m_2 – m_0 – m_1)X + m_1X^2, with the three multiplications m_0 = a_0b_0, m_1 = a_1b_1 et m_2 = (a_0 + a_1)(b_0 + b_1).
In the same manner, Strassen’s algorithm allows one to multiply two matrices 2nx2n with only seven products of matrices nxn.

The two previous examples fall in the category of bilinear maps: these are functions of the form Phi : K^m x K^n -> K^l, given a field K, linear in each variable. Among the most classical bilinear maps, we have the multiplication of polynomials, matrices, or even elements of algebraic extension of finite fields. Given a bilinear map Phi, computing the minimal number of multiplications necessary to the evaluation of this map is a NP-hard problem. The purpose of this thesis is to propose algorithms minimizing this number of multiplications. Two angles of attack have been studied.

The first aspect of this thesis is to study the problem of the computation of the bilinear complexity under the angle of the reformulation of this problem in terms of research of matrix subspaces of a given rank. This work led to an algorithm taking into account intrinsic properties
of the considered products such as matrix or polynomial products over finite fields. This algorithm allows one to find all the possible decompositions, over F_2, for the product of polynomials modulo X^5 and the product of matrices 3×2 by 2×3.

Another aspect of this thesis was the development of fast asymptotic methods for the integer multiplication. There is a particular family of algorithms that has been proposed after an article by Fürer published in 2007. This article proposed a first algorithm, relying on fast Fourier transform (FFT), allowing one to multiply n-bit integers in O(n log n 2^{O(log^* n)}), where log^* is the iterated logarithm function. In this thesis, an algorithm, relying on a number theoretical conjecture, has been proposed, involving the use of FFT and generalized Fermat primes.
With a careful complexity analysis of this algorithm, we obtain a complexity in O(nlog n 4^{log^* n}).

Details

Date:
June 5, 2018
Time:
1:30 pm - 2:30 pm
Event Category:

Logo du CNRS

Logo d'Inria

Logo Université de Lorraine