Algorithmique 2 : Calcul Formel

Calcul Formel

Anneau commutatif non intègre $A$, tel que $2 \cdot 1_A$ soit inversible (donc $A$ est a fortiori pas de caractéristique $2$).

\[A[X]\]

Anneau quotient $A[X]/(P)$ :

\[Q \sim Q' ⟺ ∃R; \, \, Q-Q' = RP\]

On utilisera comme représentants des classes les restes de la division euclidienne :

Donc :

\[A[X]/(P) ≃ \lbrace Q \mid \deg(Q) < \deg(P) \rbrace\]

Nos polynômes préférés :

\[X^{2^n} ± 1\]

On suppose que les opérations ($+$, $×$) dans $A$ se font en $O(1)$.

Opérations classiques :

Addition en $O(n)$ (on somme les coeff)

Multiplication en $𝛳(n^2)$ :

for i in range(2*n):
  R[i] = 0

for i in range(n):
  for j in range(n):
    R[i+j] += P[i]*Q[j]

Karatsuba

\[P ≝ \underbrace{P_1}_{n/2 \text{ premiers monômes}} + X^{n/2} P_2 \\ Q ≝ Q_1 + X^{n/2} Q_2\] \[⟹ PQ = P_1 Q_1 + X^{n/2} (P_1 Q_2 + P_2 Q_1) + X^n P_2 Q_2\]

Diviser pour régner :

\[T(n) = 4T(n/2) + 𝛳(n^1) \\ = aT(n/b) + 𝛳(n^k)\]

Comme $\log_b(a) = 2 > 1 = k$ :

\[T(n)=𝛳(n^2)\]

on rien gagné, de manière naïve.

Mieux :

\[PQ = P_1 Q_1 + X^{n/2} \Big((P_1 + P_2)(Q_1 + Q_2) - P_1 Q_1 - P_2 Q_2\Big) + X^n P_2 Q_2\] \[T(n) = 3T(n/2) + 𝛳(n^1) \\ = aT(n/b) + 𝛳(n^k)\]

Comme $\log_b(a) = \log_2(3) > 1 = k$ :

\[T(n)=𝛳(n^{\log_2(3)})\]

Fast Fourier Transform

On se place dans $A[X]/(X^n-1)$

$\deg(PQ)<n$

$P,Q$

⟶ évaluation en $x_1, ⋯, x_n$ en $O(n^2)$ (linéaire, mais on a $n$ points).

⟶ produit en $𝛳(n)$ de $P(x_i)Q(x_i)$

⟶ Interpolation de Lagrange en $𝛳(n^2)$ pour avoir $PQ$

Évaluation avec Horner en $O(n)$:

\[P(x) = a_0 + X(a_1 + x(a_2 + \cdots + X(a_{n-1} + a_n X)))\]

r = P[n-1]
for i in range(n-2, -1, -1):
  r = P[i]+x*r

Comme on en fait $n$ ⟶ $O(n^2)$

Interpolation de Lagrange en $O(n^2)$ :

opération la plus coûteuse : calcul de $\prod_j (X - x_j)$ en $O(n^2)$ ($n$ coefficients demandant au plus $O(n)$ opérations chacun)

On peut faire mieux :

Rappel :

Racine $n$-ième de l’unité primitive :: $𝜔^n=1$ et pour tout $1≤j<n$, $𝜔^j-1 \not \mid 0$ ($A$ anneau où $2$ est inversible, mais qui n’est pas nécessairement intègre)

$𝜔^0, ⋯, 𝜔^{n-1}$ racine de l’unité :

\[\Bigg(\sum\limits_{j=0}^{n-1} (𝜔^i)^j \Bigg) (1-w^i) = 1 - (w^i)^n = 1 - 1 = 0\]

Nos $n$ points :

\[1 = 𝜔^0, ⋯, 𝜔^{n-1}\]

$P, Q ∈ A[X]/(X^n-1) ≃ A_{n-1}[X]$

Notations : quand on marque le produit $\cdot$, on est dans l’anneau quotient, si on ne marque pas le produit, on est dans $A$.

\[P \cdot_{A[X]/(X^n-1)} Q ∈ A[X]/(X^n-1) \\ ⟵ (P \cdot Q)(𝜔^0), ⋯, (P \cdot Q)(𝜔^{n-1}) \\ ⟵ P(𝜔^i), Q(𝜔^i) \\ ⟵ P, Q ∈ A[X]/(X^n-1) ≃ A_{n-1}[X]\]

On veut :

\[PQ(𝜔^i) = (P \cdot_{A[X]/(X^n-1)} Q)(𝜔^i)\]

NB : Pas vrai dans le cas général !

Or :

\[PQ = A (X^n -1) + (P \cdot_{A[X]/(X^n-1)} Q)\]

Donc évalué en $𝜔^i$ :

\[PQ(𝜔^i) = (P \cdot_{A[X]/(X^n-1)} Q)(𝜔^i)\]

\[P = \sum\limits_{ i<n } P_i X^i \\ Q = \sum\limits_{ i<n } Q_i X^i \\ P = \underbrace{\sum\limits_{ i< \lfloor n/2 \rfloor } P_{2i} X^{2i}}_{ ≝ P_0(X^2)} + X\underbrace{\sum\limits_{ i< \lfloor n/2 \rfloor } P_{2i+1} X^{2i}}_{≝ P_1(X^2)}\]

Puis : idem avec $Q$

Donc :

\[P(𝜔^i) = \underbrace{P_0(𝜔^{2i})}_{y_0} + 𝜔^i \underbrace{P_1(𝜔^{2i})}_{y_1}\]

$𝜔^{2i}$ est une racine $n/2$-ième de l’unité
$𝜔^{n/2} = ± 1$, mais $𝜔^{n/2} = 1$ impossible (racine primitive), donc $𝜔^{n/2} = - 1$

\[P(𝜔^{i+n/2}) = P_0(𝜔^{2i}) - 𝜔^i P_1(𝜔^{2i})\]

Eval(P, 𝜔, n):
  for i in range(n/2):
    P_0[i] = P[2i]
    P_1[i] = P[2i+1]

  Y_0 = Eval(P_0, 𝜔^2, n/2)
  Y_1 = Eval(P_1, 𝜔^2, n/2)
  𝛼 = 1
  for i in range(n//2):
    Y[i] = Y_0[i] + 𝛼 Y_1[i] # 𝛼 = 𝜔^i
    Y[n/2+i] = Y_0[i]-𝛼 Y_1[i]
    𝛼 = 𝛼𝜔

  return Y

En $O(n\log n)$

Si $deg P, \deg Q < n$ :

\[\begin{cases} A^n ≃ A[X]/(X^n-1) ⟶ A^n \\ P = (P_0, ⋯, P_{n-1}) \mapsto (P(𝜔^0), ⋯, P(𝜔^{n-1})) \end{cases}\]

On veut inverser la matrice de cette application linéaire :

\[A_𝜔 ≝ (𝜔^{ij})_{0≤i, j≤n-1}\]

On pose :

\[A_𝜔 A_{-𝜔} [i, j] = \sum\limits_{ 0≤k≤n-1 } 𝜔^{ik}𝜔^{-kj} = \sum\limits_{ 0≤k≤n-1 } (𝜔^{i-j})^k = \begin{cases} 0 \text{ si } i≠j \\ n \text{ sinon} \end{cases}\]

Donc l’inverse de $A_𝜔$ est :

\[\frac 1 n A_{-𝜔}\]

NB : On peut diviser par $n$, car $n$ est une puissance de deux (donc inversible, par hypothèse).

Donc interpoler, ça revient à évaluer ! ⟶ on peut interpoler en $O(n \log n)$ !

NB : Comment faire de manière générale (pas dans l’anneau quotient) ?

Si $deg P, \deg Q < n$ :

\[PQ = P \cdot_{A[X]/(X^{2n}-1)} Q\]

donc on se ramène au cas précédent, avec $2n$.

Problème : on veut faire du calcul exact, et pas avec des flottants ⟶ quid des racines de l’unité ?

Un complexe ≃ Un couple de réels ⟶ mais on veut éviter les flottants !

On veut donc

Une racine $n$-ième de l’unité ≃ Un couple de rationnels ≃ Un couple d’entiers

⟹ On ne va pas réussir à faire du $O(n \log n)$ dans les entiers, mais du $𝛳(n \log \log \log n)$

Considérons $A[X]/(X^n+1)$ :

\[\underbrace{P}_{≝\sum\limits_{ i <n } P_i X^i} \cdot_{A[X]/(X^n+1)} \underbrace{Q}_{≝\sum\limits_{ i <n } Q_i X^i} = \underbrace{R}_{≝\sum\limits_{ i <n } R_i X^i}\]

⟶ coeff $k<2n$ ?

\[R_k = \sum\limits_{ i+j =k } P_i Q_j\]

On remarque que, dans l’anneau quotient : $X^n = -1$, donc

\[\underbrace{P}_{≝\sum\limits_{ i <n } P_i X^i} \cdot_{A[X]/(X^n+1)} \underbrace{Q}_{≝\sum\limits_{ i <n } Q_i X^i} = \underbrace{R}_{≝\sum\limits_{ i <n } R_i X^i} = \sum\limits_{ k < n} \Bigg( \sum\limits_{ i+j =k } P_i Q_j - \sum\limits_{ i+j = n + k } P_i Q_j \Bigg) X^k\]

$𝜔$ racine primitive $n$-ième
$𝜃$ racine primitive $2n$-ième ($𝜃^n = -1$)

À tout $P$, on associe

\[\widehat{P} ≝ \sum\limits_{ i < n } (P_i 𝜃^i)X^i\]

Mq :

\[\widehat{P} \cdot_{A[X]/(X^n-1)} \widehat{Q} = \widehat{P \cdot_{A[X]/(X^n+1)} Q}\]

en $𝛳(n \log n)$

Dém : car

Coeff en $k$ de $\widehat{P} \cdot_{A[X]/(X^n-1)} \widehat{Q}$ :

\[\sum\limits_{ i+j =k } P_i Q_j - \underbrace{𝜃^{n+k}}_{-𝜃^{k} }\sum\limits_{ i+j = n + k } P_i Q_j \\ = 𝜃^k \Bigg( \sum\limits_{ i+j =k } P_i Q_j - \sum\limits_{ i+j = n + k } P_i Q_j \Bigg)\]

\[P, Q \\ ⟶ \widehat{P}, \widehat{Q} \text{ en } 𝛳(n) \\ ⟶ \widehat{P}(𝜔^i), \widehat{Q}(𝜔^i) \text{ en } 𝛳(n \log n) \\ ⟶ \widehat{PQ}(𝜔^i) \text{ en } 𝛳( n) \\ ⟶ \widehat{P} \cdot_{X^n-1} \widehat{Q} \text{ en } 𝛳( n \log n) \\ ⟶ P \cdot_{X^n+1} Q \text{ en } 𝛳( n) \\\]

Si $P∈\Big(A[X]/(X^n+1)\Big)[Y]/(Y^m±1)$ où $m≤n$ :

$\deg P<m$
$P_i∈A[X]/(X^n+1)$

Il nous faut, de plus :

des racines $2m$-ièmes primitives dans $A[X]/(X^n+1)$.
$m$, $n$ sont des puissances de $2$
Cas 1 : $n=m$

$X$ est une racine $2n$-ièmes primitive dans $A[X]/(X^n+1)$, car
- $X^n = -1 ⟹ X^{2n} = 1$
- Montrons que $∀ 1≤k≤2n, X^k - 1 \not \vert 0$ :
  
  Supposons que $X^{pq}-1$ divise $0$ (pour $q≥0$) :
  \[X^{pq}-1 = (X^p-1)(X^{p(q-1)} + X^{p(q-2)} + ⋯ + 1)\]
  donc $X^p-1$ est aussi un diviseur de $0$
  
  On pose $g ≝ pgcd(k, 2n) = uk + 2vn$ ⟶ c’est une puissance de $2$ divisant $n$.
  
  $X^n -1 = -2$ est inversible par hypothèse ⟶ pas un diviseur de $0$
  
  $X^g-1 = X^{uk + 2vn} - 1 = X^{uk} - 1$ n’est pas un diviseur de $0$, car $g$ divise $n$, et $X^n - 1$ est inversible.
  
  Donc comme $X^{uk} - 1$ n’est pas un diviseur de $0$, $X^{k} - 1$ non plus !

$P, Q$ ⟶ évaluation en $O(nm \log m)$

car dans

Y[i] = Y_0[i] + X Y_1[i]

addition en $O(n)$
Multiplication par $X$ ⟶ ce n’est qu’un décalage modulo $n$, donc en $O(n)$

$A[X]/(X^n+1)$ : $n$ puissance de $2$

$P \cdot_{X^n+1} Q$

$n=2^k$

$k$ pair : $n = 2^k$, $k$ pair $\sqrt{n} = 2^{k/2}$, $d=d’= \sqrt{n}$, $n=dd’$
$k$ impair : $d = \sqrt{2n}, d’ = \sqrt{n/2}$

\[P∈A[X]/(X^n+1) ⟹ P'∈ (A[X]/(X^{2d}+1))[Y]/(Y^{d'}+1)\]

Notations : $P’$ n’a rien à voir avec la dérivée de $P$ : il s’agit juste d’une transformation, qu’on aurait pu noter $\widetilde{P}$

On regroupe par “blocs de taille $d$” :

Ex : $n =8 ⟹ d’=2, d=4

\[P = (P_0 + P_1 X + P_2 X^2 + P_3 X^3) + X^4(P_4 + P_5 X + P_6 X^2 + P_7 X^3) \\ P' = (P_0 + P_1 X + P_2 X^2 + P_3 X^3) + Y(P_4 + P_5 X + P_6 X^2 + P_7 X^3)\]

Les coeff $P_i$ sont de $\deg < d$

⟹ Multiplication se fait dans $A[X]$ ___

\[P,Q ∈ A[X]/(X^n+1) \\ ⟶ P', Q'∈(A[X]/(X^{2d}+1))[Y]/(Y^{d'}+1) \\ ⟶ P', Q', 𝜔 = X^{2n/m}, 𝜃= X^{n/m} \\ ⟶ P'(𝜔^i), Q'(𝜔^i)∈A[X]/(X^{2d}+1) \\ ⟶ P'Q'(𝜔^i) : d' \text{ produit par appels récursifs} \\ ⟶ P' \cdot_{Y^{d'}+1} Q'∈ (A[X]/(X^{2d}+1))[Y]/(Y^{d'}+1) \text{ interpolation} \\ ⟶ PQ ∈ A[X]/(X^n+1)\]

\[P' \cdot_{Y^{d'}+1} Q'\]

⟶ $d’$ coeffs, tous de $\deg ≤ 2d$ :

$0 ≤ a ≤ d-1$
$C’_a$ coeff de $Y^d$ : polynôme de $\deg ≤ 2d$
$C’_{ab}$, pour $0≤ b≤2d-1$

\[PQ\]

$0≤ C_u ≤ n-1$
$u =ad +b$
$0≤b≤d-1$
$0≤d ≤ d’-1$

\[C_u = \sum\limits_{ i+j = a } \sum\limits_{ h+l = b} P_{id + b} Q_{jd + l} - \sum\limits_{ i+j = d'+ a } \sum\limits_{ h+l = b} P_{id + b} Q_{jd + l} \\ +\sum\limits_{ i+j = a-1 } \sum\limits_{ h+l = d+b} P_{id + b} Q_{jd + l} - \sum\limits_{ i+j = d'+ a-1 } \sum\limits_{ h+l = d+b} P_{id + b} Q_{jd + l}\] \[C'_u = \sum\limits_{ i+j = a } P'_{i} Q'_{j} -\sum\limits_{ i+j = d'+a } P'_{i} Q'_{j} \\ = \sum\limits_{ i+j = a }\Bigg(\sum\limits_{ h<d} P_{id +h} X^h\Bigg)\Bigg(\sum\limits_{ l<d} P_{jd +l} X^l\Bigg) - \sum\limits_{ i+j = d'+a }\Bigg(\sum\limits_{ h<d} P_{id +h} X^h\Bigg)\Bigg(\sum\limits_{ l<d} P_{jd +l} X^l\Bigg)\] \[C'_{ab} = \sum\limits_{ i+j = a } \sum\limits_{ h+l = b } P_{id + h} Q_{jd+l} - \sum\limits_{ i+j = a + d'} \sum\limits_{ h+l = b } P_{id + h} Q_{jd+l}\] \[⟹ C_u = C'_{ab} + C'_{a_1, d+b}\]

NB : D’où le $n \log n \log \log n$ ? On doit faire $\sqrt{n} × T(2 \sqrt{n})$ appels récursifs en plus lors de l’évaluation.

Share on

Twitter Facebook Google+ LinkedIn

Calcul Formel

Karatsuba

Fast Fourier Transform

Share on

Leave a comment