% $Id: texkb,v 1.1.1.1 2006/08/01 16:39:15 kb Exp $
\documentclass[a4paper,11pt]{amsart}
\usepackage{kb}
\usepackage[theo]{kbexo}
\course{Préparation à l'agrégation}

\author{Karim Belabas}

\def\IN{\noindent\textsc{Entrée} : }
\def\OUT{\noindent\textsc{Sortie} : }

\begin{document}
\simpletitle{Multiplication sous-quadratique}
\section{Diviser pour régner}

\noindent On rappelle tout d'abord le lemme permettant d'estimer la
complexité d'un algorithme récursif, de type «diviser pour régner»:
\begin{lemme}\label{le:div} On fixe $a \geq 1$, $b > 1$ et $c\in \RM$. Soit
$f:\RM^+\to \RM^+$ une fonction vérifiant, pour tout $x > x_0 \geq 1$
suffisamment grand, l'inégalité
\begin{equation}\label{eq:div}
f(x)\leq a f(x/b) + c x,
\end{equation}
et $f(x) = 1$ pour $x \leq x_0$.
Alors, il existe une constante effective $C(a, b, c, x_0)$ telle que pour tout
$x\geq x_0$, on ait
$$
f(x) \leq C(a,b,c, x_0)
\begin{cases}
x^{\log_b a} & \text{si $a>b$},\\
x\log x      & \text{si $a=b$},\\
x            & \text{si $a<b$}.\\
\end{cases}
$$
\end{lemme}
\begin{proof}
Soit $x\geq x_0$, et soit $\ell := \ceil{\log_b(x/x_0)}$ le plus petit entier
tel que $x/b^\ell \leq x_0$. En itérant l'inégalité \eqref{eq:div}, on obtient
\begin{align*}
f(x)
& \leq a f(x/b) + c x 
  \leq a \big(a f(x/b^2) + c x/b\big) + cx\\
& \leq \dots \leq a^\ell f(x/b^\ell) + c x \sum_{i = 0}^{\ell-1} (a/b)^i.
\end{align*}
Par le choix de $\ell$, on a $f(x/b^\ell) = 1$; de plus, $\ell\leq \log_b x + 1$, soit
pour tout $y \geq 1$,
$$y^l\leq y \times y^{\log_b x} = y x^{\log_b y}.$$
On majore donc $a^\ell$ par $a x^{\log_b a}$;
la majoration de la somme géométrique dépend de la valeur de $r = a/b$:
\begin{itemize}
\item si $r > 1$, elle vaut $(r^\ell - 1)/(r-1)$, et $r^l\leq r x^{\log_b r}
= O(x^{\log_b a - 1})$;
\item si $r = 1$, elle vaut $\ell \leq 1 + \log_b x$;
\item si $r < 1$, elle vaut $(r^\ell - 1)/(r-1) = O(1)$.
\end{itemize}
\end{proof}
\noindent Il faut interpréter $f$ comme une fonction de coût, fonction d'une
taille $x$; l'inégalité \eqref{eq:div} est typique d'une fonction récursive
coupant un problème de taille initiale $x$ en $a$ sous-problèmes de taille
$b$ fois plus faible, et utilisant un temps linéaire pour recombiner
l'information ainsi obtenue.
\smallskip

L'exemple le plus simple est le tri-fusion: si $n$ est une puissance de $2$,
pour trier un tableau d'au plus $n$ entiers, on trie récursivement la
première et la seconde moitié du tableau, avant de recombiner en temps
linéaire les deux sous-tableaux triés. D'après le lemme (avec $a = b = 2$),
cet algorithme utilise $O(n\log n)$ comparaisons.

On va maintenant appliquer ce principe à la multiplication des polynômes.

\section{Karatsuba}

\begin{algo}[Multiplication de Karatsuba]

\IN $a,b\in R[X]$ de degrés $< n$, où $R$ est un anneau commutatif,
et $n$ est une puissance de $2$.

\OUT $ab\in R[X]$.

\begin{enumerate}
\item Si $n = 1$, renvoyer $ab\in R$.
\item Soit $a = A_1 X^{n/2} + A_0$ et $b = B_1 X^{n/2} + B_0$, où 
$A_0, A_1, B_0, B_1\in R[x]$ de degrés $< n/2$.
\item Calculer $A_0\times B_0$, $A_1\times B_1$ et $(A_0+A_1)\times
(B_0+B_1)$ en utilisant $3$ appels récursifs.

\item Renvoyer 
$A_1B_1 X^n + \big((A_0+A_1)(B_0+B_1) - A_0B_0 - A_1B_1\big)X^{n/2} + A_0 B_0$.
\end{enumerate}
\end{algo}
Puisque l'addition de deux polynômes de degré $\leq n$ utilise $O(n)$
opérations dans $R$, on peut appliquer le Lemme~\ref{le:div}, avec $a = 3$ et
$b = 2$; donc cet algorithme utilise $O(n^{\log_2 3})$ opérations dans $R$
pour calculer le produit. Un net progrès par rapport à l'algorithme naïf en
$O(n^2)$.

La condition «n est une puissance de $2$» n'est pas gênante, puisque on
peut toujours remplacer $n$ par $2^{\ceil{\log_2 n}}$ la puissance de $2$
immédiatement supérieure, ce qui se traduit au pire par l'apparition
dans la complexité d'un facteur $2^{\log_2 3} = 3$, une constante.
\medskip

La formule de Karatsuba n'a rien de magique; avec les mêmes notations, on
aurait tout aussi bien pu calculer
$$A_1B_1 X^n + \big(-(A_0-A_1)(B_0-B_1) + A_0B_0 + A_1B_1\big)X^{n/2}
 + A_0 B_0.$$
Plus généralement, si on décide d'utiliser le produit des coefficients
dominants $C(\infty) = A_1B_1$ (qu'on peut interpréter comme une évaluation à
l'infini), et deux autres points d'interpolation $u\neq v$ tels que $u-v$
soit inversible, on a la «jolie» formule
\begin{multline*}
C(\infty) X^n
   + \paren{\frac{1}{u-v} C(u) - \frac{1}{u-v}C(v) - (u+v)C(\infty)}X^{n/2}\\
 + \paren{-\frac{v}{u-v}C(u) + \frac{u}{u-v} C(v) + uv C(\infty)},$$
\end{multline*}
où $C(u) = (A_1 u + A_0)(B_1u + B_0)$ et $C(v) = (A_1 v + A_0)(B_1v + B_0)$.
Ceci résulte du calcul de $(C_0,C_1,C_2)$ dans l'identité $C(Y) = C_2 Y^2 +
C_1 Y + C_0 = (A_1 Y + A_0)(B_1 Y + B_0)$, à partir de $C(\infty)$, $C(u)$ et
$C(v)$, par identification ou par interpolation.

Pour $u,v$ fixés, ces formules n'utilisent que 
\begin{itemize}
\item $3$ multiplications de polynômes de degré $\leq n/2$,
\item $O(1)$ multiplications de polynômes de degré $\leq n$ par une
constante, en $O(n)$ opérations dans $R$.
\item $O(1)$ additions de polynômes de degré $\leq n$,
en $O(n)$ opérations dans $R$.
\end{itemize}
Les algorithmes à la Karatsuba utilisant ces formules nécessitent donc tous
$O(n^{\log_2 3})$ opérations.

\section{Toom-Cook}

Pour ne pas être embêté par les dénominateurs, on suppose dorénavant que $R$
est un corps: tout élément non nul est donc inversible. En particulier, la
condition «$u-v$ inversible» du paragraphe précédent est automatiquement
vérifiée pour $u\neq v$.

Cette méthode se généralise sans difficulté en découpant, pour $n = r^k$ une
puissance de $r \geq 2$, les polynômes $a,b$ de degrés $< n$ en $r$ blocs de
taille $n/r$:
$$ a = \sum_{0\leq i < r} A_i X^{(n/r)i},\quad
   b = \sum_{0\leq i < r} B_i X^{(n/r)i},$$
où les $A_i,B_i\in R[X]$ sont de degré $< n/r$. On écrit 
$$ab = c = \sum_{0\leq i < 2r - 1} C_i X^{(n/r)i},$$
où les $C_i\in R[X]$ sont de degré $< n/r$. Dans $R[X][Y]$, le polynôme
$$C(Y) = \sum_{0\leq i < 2r - 1} C_i Y^i = \paren{\sum_{0\leq i < r} A_i Y^i}
                 \paren{\sum_{0\leq i < r} B_i Y^i} = A(Y)B(Y)$$
est de degré en $Y$ inférieur ou égal à $2(r - 1)$. Si on choisit
$2r - 1$ points d'évaluations distincts dans $R$ -- ce qui suppose que $R$
est assez gros --, $(u_0,\dots,u_{2r-2})$, on peut calculer $C(u_i) =
A(u_i)B(u_i)$ pour tout $i$ en utilisant 
\begin{itemize}
\item $O(r)$ multiplications de polynômes de degré $< n/r$ par une constante;
\item $O(r)$ additions de polynômes de degré $< n/r$;
\item $2r-1$ multiplications de polynômes de degré $< n/r$;
\end{itemize}
les 2 premiers points prennent en compte le calcul des polynômes $A(u_i)$
et $B(u_i)$ dans $R[X]$.

Par interpolation, les coefficients $C_i$ sont déterminés de façon unique en
fonction des $C(u_i)$, par une formule qui est linéaire à coefficients dans
$R$. Explicitement, soit
$$Q(Y) = \prod_{0 \leq i < 2r-1} (Y - u_i),\quad\text{et}\quad
L_i(Y) = \frac{Q(Y)}{Q'(u_i)(Y - u_i)},\quad i = 0,\dots, 2r-2,$$
les projecteurs de Lagrange, tous dans $R[Y]$; alors 
$$ C(Y) = \sum_{0\leq i < 2r-1} C(u_i) L_i(Y) = \sum_{0\leq i < 2r-1}C_i Y^i.$$
Pour des points d'évaluation fixés, on peut développer les $L_i(Y)$ dans
cette formule pour obtenir une expression explicite des $C_i$.

Toujours d'après le Lemme, avec $a = 2r-1$ et $b = r$, le nombre d'opérations
dans $R$ utilisées pour calculer le produit $ab$ par cette méthode est
$O_r(n^{\log_r (2r - 1)})$. Pour $r = 2$, on retrouve bien le résultat de
Karatsuba.

Comme $\lim_{r\to+\infty}  \log_r (2r - 1) = 1$, on peut rendre l'exposant
aussi proche de $1$ que l'on veut. En travaillant plus précisément, on peut
ecrire la dépendance explicite des constantes en $r$; mais la complexité
combinatoire des formules obtenues pour les $C_i$ devient vite trop
pénalisante. En pratique, seuls les cas $r = 2$ ou $3$ sont utilisés.

\section{FFT}
\def\w{\omega}
\def\F{\mathcal{F}}

Pour aller plus loin, on choisit des points d'évaluations astucieux, ce qui
évite de précalculer d'horribles formules d'interpolation : on se contente de
les générer implicitement lors de l'exécution de l'algorithme.

Pour multiplier deux polynômes de degré $< n/2$, où $n = 2^k$ est une
puissance de $2$, on fait l'hypothèse que $R$ est un corps contenant une
racine primitive $n$-ème de l'unité $\omega$. La
transformée de Fourier discrète
\begin{align*}
\F(\cdot,\omega):  R[X]/(X^n - 1) & \to R^n \\
     T &\mapsto \big(T(\w^i)\big)_{0\leq i < n}
\end{align*}
établit un isomorphisme de $R$-algèbres, qui permet de calculer le produit
$ab$ comme $\F^{-1}(\F(a) \cdot \F(b))$. Bien sûr, si $a,b\in R[X]$ sont tels
que $\deg ab < n$, il revient au même d'obtenir le représentant normalisé de
la classe de $ab$ dans $R[X]/(X^n-1)$, ou directement le produit $ab$.

Sous l'hypothèse que $\omega\in R$, il existe un algorithme simple utilisant
$O(n\log n)$ opérations dans $R$ pour calculer $\F$:
\begin{algo}
\IN $T\in R[X]$, $\deg T < n = 2^k$, $\w$ d'ordre $n$ dans $R$.

\OUT $\F(T, \w)$.
\begin{enumerate}

\item Si $n < 1$, retourner le vecteur $(T)$.

\item Décomposer $T$ en somme de ses parties paires et impaires $T(X) =
T_0(X^2) + X T_1(X^2)$.

\item Calculer $(a_0, \dots, a_{n/2-1}) = \F(T_0, \w^2)$, par un appel
récursif.
\item Calculer $(b_0, \dots, b_{n/2-1}) = \F(T_1, \w^2)$.
\item Retourner $(a_i + \w^i b_i)_{i < n}$.\hint{On étend $a_i$ et $b_i$ par
périodicité : $a_{n/2+i} := a_i$.}
\end{enumerate}
\end{algo}
La décomposition $T = T_0(X^2) + XT_1(X^2)$ n'utilise pas d'opérations dans
$R$, c'est un jeu d'écriture sur les coefficients. La dernière étape
utilise $O(n)$ opérations dans $R$, si on calcule les $\w^i = \w^{i-1}\cdot
\w$ successivement. (Alternativement, le vecteur $(1,\w,\dots,\w^{n-1})$ peut
être précalculé.) On peut donc appliquer le Lemme avec $a = b = 2$.

Calculer $\F^{-1}$ se fait avec la même complexité puisque on démontre que
cette transformée inverse s'interprète comme une transformée directe pour un
autre choix de $\omega$; explicitement, on vérifie que
$\F(\F(T,\w), \w^{-1}) = n T$ pour tout $T \in R[X]/(X^n-1)$.

En rassemblant tous ces éléments, on multiplie deux polynômes de $R[X]$ de
degré $< n$ en $O(n\log n)$ opérations dans $R$, sous l'hypothèse très
restrictive de la présence de racines de l'unité d'ordre arbitrairement
élevé dans $R$.

La méthode de Schönhage-Strassen permet de s'en affranchir, en remplaçant $R$
par une extension convenable; de même, il n'est pas nécessaire de supposer
que $R$ est corps. On démontre ainsi:
\begin{theo}[Cantor-Kaltofen]
Si $R$ est un anneau commutatif, on peut multiplier deux polynômes de degré
$< n$ dans $R[X]$ en utilisant $O(n\log n \log\log n)$ opérations
($+,\times$) dans $R$.
\end{theo}
\end{document}

