% $Id: texkb,v 1.1.1.1 2006/08/01 16:39:15 kb Exp $
\documentclass[a4paper,12pt]{amsart}
\usepackage{kb,a4wide}
\usepackage{kbexo}
\course{Préparation à l'agrégation}
\def\arraystretch{1.4}
\def\M{\textsf{M}}
\def\Ot{\widetilde{O}}

\author{Karim Belabas}
\begin{document}
\simpletitle{Mémento complexité}
\smallskip

\misctitle{Rappel} Soit $g$ une fonction strictement positive; on écrit 

\begin{itemize}
\item $f = O(g)$ s'il existe $C > 0$ et $x_0$ tel que $f(x) \leq C\cdot g(x)$
pour tout $x>x_0$.

\item $f = \Ot(g)$ s'il existe $C > 0$ et $x_0$ tel que $f(x) \leq g(x) \cdot
\big(\log g(x)\big)^C$ pour tout $x>x_0$.
\end{itemize}

\section{Tri}
\noindent Le tri de $n$ éléments s'effectue en utilisant $O(n\log n)$
comparaisons (tri fusion).

\section{Exponentiation binaire}
\noindent Le calcul de $x^n$ s'effectue en utilisant $O(\log n)$
multiplications (écriture de $n=\sum_{i\leq t} n_i 2^i$ en base $2$ et
calcul des $x^{2^i}$ en utilisant $t$ carrés successifs).

\section{Dans $\ZM$}
\noindent La \emph{taille} (binaire) d'un entier $a$ est le nombre de
bits\footnote{Il n'y a pas d'inconvénient à compter les chiffres en base
$\beta \geq 2$, avec $t(a) := \floor{\log_\beta(|a|+1)}$. Pas vraiment
d'intérêt théorique non plus.} utilisé pour l'écrire, en d'autres termes
$t(a) := \floor{\log_2(|a|+1)} + 1$. En général, $a > 1$ tend vers l'infini
et on utilise simplement $\log_2(a)$. On suppose que tous les opérandes sont
de taille $\leq n$:
\begin{center}
\begin{tabular}{|r|c|c|c|}\hline
Opération & Naïf & Rapide \\
\hline
$a+b$ & $ O(n) $ & $O(n)$ \\
\hline
$a\times b$ & $ O(n^2)$ & $\M_\ZM(n) = \Ot(n)$ \\
\hline
$a=bq+r$ & $O(n^2)$ & $O(\M_\ZM(n))$ \\
\hline
Relation de Bézout  & $O(n^2)$ & $O(\M_\ZM(n) \cdot\log{n})$ \\
\hline
Restes chinois & $ O(n^2)$ & $ O(\M_\ZM(n) \cdot\log{n})$ \\
\hline
\end{tabular}
\end{center}
Pour tous ces algorithmes, on compte le nombre d'opérations élémentaires sur
les bits, supposé proportionnel au temps d'exécution (complexité en
\emph{temps}). La complexité en \emph{espace} est de $\Ot(n)$ bits.

\begin{itemize}
\item Multiplication : $\M_\ZM(n)$ est par définition le temps d'une
multiplication dans $\ZM$ pour deux opérandes de taille $\leq n$.
L'algorithme rapide (Harley et van der Hoeven, 2019), en temps $O(n\log n)$,
utilise la Transformée de Fourier Discrète.
  
Moins rapide mais beaucoup plus simple : l'algorithme de Karatsuba utilise
$O(n^{\log_2 3})$ opérations.

\misctitle{Remarque} Pour des opérantes de tailles différentes, $s(a)\leq n$,
$s(b)\leq m $, l'algorithme naïf (quadratique) utilise $O((n+1)(m+1))$
opérations.

\item Division euclidienne : l'entrée est $(a,b)$, $b\neq 0$, et la sortie
$(q,r)$ avec $0 \leq r < \abs{b}$. L'algorithme rapide
résout l'équation $b - a/x=0$ en utilisant l'itération de Newton
$$x_{n+1} = x_n - x_n(x_n b - a)\;.$$
(Calcul effectué en doublant la précision à chaque étape; soit dans un modèle
flottant, soit modulo $2^k$.)
On pose $q=\floor{x}$, puis $r = a - bq$. L'énoncé de complexité
suppose que $\M_\ZM(n)$ vérifie des propriétés du type $M(n)/n \geq M(m)/m$
pour $n\geq m$, et $M(mn) \leq m^2M(n)$. Qui sont vraies
aussi bien pour l'algorithme naïf que pour Karatsuba ou Harley - van der
Hoeven.

  \misctitle{Remarque}
Si $t(a)\leq n$, $t(b)\leq m$, $n \geq m$, l'algorithme naïf (quadratique)
utilise $O((n-m+1)(m+1))$ opérations élémentaires.

\item Bézout : l'entrée est $(a,b)$ et la sortie consiste
  en $\pgcd(a,b)$ et deux entiers $u,v$ tels que $au + bv
= \gcd(a,b)$.

\item Restes chinois : l'entrée consiste en $N$ congruences $ x \equiv
a_k \pmod{b_k}$  où les ${b_k}$ sont 2 à 2 premiers entre eux, et la
sortie attendue est une solution de ce système de congruences. On suppose
$t(a_k) \leq t(b_k)$ and $\sum_k t(b_k) \leq n$.
\end{itemize}

\section{Dans $\ZM/N\ZM$}
\noindent On choisit un représentant canonique dans chaque classe de
congruence: les entiers de $[0,N-1]$, pour représenter les éléments de
$\ZM/N\ZM$. La taille des opérandes est $\leq n := t(N)$.
\smallskip

\noindent L'addition est implantée comme une addition dans $\ZM$, suivie
d'une (possible) soustraction: temps $O(n)$.
La multiplication est une multiplication in $\ZM$, suivie par
une division euclidienne par $N$ : temps $O(n^2)$ ou $O(\M_\ZM(n))$.
L'inversion utilise une relation de Bézout  : temps $O(n^2)$ ou
$O(\M_\ZM(n) \cdot \log n)$.

\section{Dans $K[X]$,  $K$ un corps} 
\noindent La \emph{taille} (algébrique) d'un polynône $h \in K[X]$ est son
nombre de coefficients: $t(h) := \deg h + 1 \leq n$. \smallskip

\noindent Pour la complexité, on choisit de compter les opérations dans $K$
(complexité algébrique) : $+$, $-$, $\times$, $/$ dans $K$. Pour estimer plus
réalistement le temps de calcul, on peut multiplier par le coût d'une
opération élémentaire dans $K$ quand celui-ci est borné uniformément (c'est
le cas si $K$ est un corps fini); sinon il faut tenir compte de la taille
des coefficients. \smallskip

\noindent
Soient $f,g$ deux polynômes dans $K[X]$, de tailles $\leq n$.

\begin{center}
\begin{tabular}{|r|c|c|}\hline
Opération & Naïf & Rapide\\
\hline
$ f + g $ & $ O(n)~[+] $ & $ O(n)~[+]$  \\
\hline
$ f\times g$ & $O(n^2)~[+,\times] $ & $\M_{K[X]}(n) = \Ot(n)$ \\
\hline
$f=gh + r$ & $O(n^2)$ & $O(\M_{K[X]}(n))$ \\
\hline
Bézout & $O(n^2)$ & $O(\M_{K[X]}(n)\cdot\log n)$ \\
\hline
Restes chinois & $O(n^2)$ & $O(\M_{K[X]}(n)\cdot\log n)$ \\
\hline
\end{tabular}
\end{center}

\section{Dans $K[X]/(T)$:}
\noindent
Deux cas particuliers importants : définitions des corps finis non premiers
$\FM_q$ comme extension algébrique de $\FM_p = \ZM/p\ZM$ et des extensions
de~$\QM$ (nombres algébriques). De façon analogue à $\ZM/N\ZM$ nous
travaillons avec des polynômes de taille $\leq t(T)$, avec les coûts
ci-dessus. L'inversion utilise de nouveau une relation de Bézout.

\section{Dans $M_{n\times n}(K)$:}
\noindent
On se place de nouveau dans le modèle de complexité algébrique : on
compte les opérations dans le corps $K$. Pour $A \in M_{n\times n}(K)$, sa
\emph{taille} est $t(A)=n^2$; pour $v\in K^n$ sa taille est $t(v):=n$.
On note $A,B$ deux matrices dans $M_n(K)$.
\begin{center}
\begin{tabular}{|r|c|c|}\hline
Opérations & Naïf & Rapide\\
\hline
$A+B$ & $ O(n^2)$ & $O(n^2)$ \\
\hline
$Av$, $v\in K^n$ & $ O(n^2) $ & $ O(n^2)$ \\
\hline
$A\times B$ & $ O(n^3) $ & $ O(n^\omega), \omega=2.3729$ \\
\hline
$A^{-1}$ & $ O(n^3)$ & $ O(n^\omega)$ \\
\hline
$PA=LU $ & $ O(n^3)$ & $ O(n^\omega)$ \\
\hline
$\text{Char $A$} $ & $ O(n^3)$ & $ O(n^\omega)$ \\
\hline
\end{tabular}
\end{center}
La factorisation $LU$ (pivot de Gauss) permet de résoudre la plupart des
problèmes d'algèbre linéaire sur $K$: noyau, image, rang, déterminant,
inverse, système linéaire ($LU$ + résolution de systèmes triangulaires en
$O(n^2)$ opérations supplémentaires dans $K$).

La constante $\omega\leq 3$ qui apparaît ci-dessus est appelé \emph{exposant
de la multiplication matricielle}. La valeur utilisée en pratique (pour des
matrices physiquement représentables par les ordinateurs actuels) est $\omega
= \log _2{7}\approx 2.8$ (Strassen).
\smallskip

\misctitle{Algèbre linéaire «Boîte Noire»} Dans ce modèle, les coûts
sont exprimés en terme du nombre d'évaluations $v\mapsto A \cdot v$ pour
un ``opérateur boîte noire'' $A$. (Un opérateur linéaire dont on ne suppose
pas qu'il est donné par une matrice. On sait simplement calculer l'image
de tout vecteur $v\in K^n$.)
En général, une multiplication matrice-vecteur pour $A\in M_{n\times n}(K)$
et $v\in K^n$ utilise $O(n^2)$ opérations dans~$K$ mais la plupart 
des matrices rencontrées en pratique sont «structurées» et
permettent une évaluation plus économique: matrices par bandes,
plus généralement matrices creuses (comme dans l'algorithme de Dixon
de factorisation dans~$\ZM$); matrice de Sylvester définissant le résultant;
matrice de Berlekamp (pour factoriser les polynômes sur les corps finis);
matrices de van der Monde  (comme les matrices de FFT), etc.

Dans ce modèle il existe des algorithmes \emph{probabilistes} (Lanczos,
Wiedemann) qui résolvent efficacement des problèmes d'algèbre linéaire comme
le calcul du polynôme caractéristique ou du rang de $A$ (avec faible
probabilité d'erreur dans les 2 cas), ou trouve \emph{une} solution du
système linéaire $Ax = b$.  Ils utilisent en moyenne $O(n)$ evaluations
$A\cdot v$, plus $O(n^2)$ opérations dans $K$. On ne gagne rien sur une
matrice dense générale ($A\cdot v$ utilise $O(n^2)$ opérations dans $K$);
mais le gain est significatif si $A\cdot v$ se calcule plus rapidement.
\end{document}
