BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//LORIA - ECPv5.9.1//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:LORIA
X-ORIGINAL-URL:https://www-qualif.loria.fr
X-WR-CALDESC:Events for LORIA
BEGIN:VTIMEZONE
TZID:Europe/Paris
BEGIN:DAYLIGHT
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
DTSTART:20180325T010000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
DTSTART:20181028T010000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Europe/Paris:20180605T133000
DTEND;TZID=Europe/Paris:20180605T143000
DTSTAMP:20220122T055634
CREATED:20180531T061830Z
LAST-MODIFIED:20180531T061830Z
UID:5731-1528205400-1528209000@www-qualif.loria.fr
SUMMARY:PhD thesis defense : Svyatoslav Covanov
DESCRIPTION:Svyatoslav Covanov invites you to his PhD thesis defense “Multiplication algorithms: bilinear complexity and fast asymptotic methods“.\nIt will take place on June 5\, at 1:30 PM in the C005 room. \nAbstract: \nSince 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).\nIn the same manner\, Strassen’s algorithm allows one to multiply two matrices 2nx2n with only seven products of matrices nxn. \nThe 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. \nThe 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\nof 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. \nAnother 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.\nWith a careful complexity analysis of this algorithm\, we obtain a complexity in O(nlog n 4^{log^* n}).
URL:https://www-qualif.loria.fr/event/phd-thesis-defense-svyatoslav-covanov/
CATEGORIES:Soutenances
END:VEVENT
END:VCALENDAR