TD12 : Bornes de compexité et FFT

Énoncé

I. Borne inférieure de complexité

1.

f_1 = a * c
f_2 = b * d
f_3 = f_1 - f_2
f_4 = a*d
f_5 = b*c
f_6 = f_4 + f_5

f_1 = a + c
f_2 = b + d
f_3 = f_1 * f_2
f_4 = a*c
f_5 = b*d
f_6 = f_4 - f_5
f_7 = f_3 - f_4
f_8 = f_7 - f_5

2.

On note $f_1, ⋯, f_r$ les résultats.

Clairement : $f_i∈𝕂[a_1, ⋯, a_n]$

Le vecteur $e$ est de la forme

\begin{pmatrix} f_{i_1} \\ \vdots \\ f_{i_s} \\ \end{pmatrix}

où chaque $f_{ij}$ est de la forme $o × o’$

On sait que les autres résultats du calcul sont des combinaisons linéaires de ces termes + des valeurs de la forme $c_0 + \sum\limits_{1≤i≤n}c_i a_i$

3.

On veut mq le nb de multiplications de ce calcul est au moins $r$.

On se place dans le pire des cas : On suppose que $A$ est de rang ligne modulo $𝕂$ égal à $r$, et on suppose que $r>s$ où $s$ est le nombre de multiplications que l’on a fait dans le calcul.

\underbrace{Ax}_{𝕸_{r,1}(𝕂)} = \underbrace{M}_{𝕸_{r,s}(𝕂)}\underbrace{e}_{𝕸_{s,1}(𝕂[a_1, ⋯, a_n, x_1, ⋯, x_n])} + h

Comme $M∈𝕸_{r,s}(𝕂)$ et que $r>s$, on sait que $rang(M)≤s$.

Par conséquent, ses vecteurs lignes sont liés. Il existe donc

𝕂^r ∋ y ≝ {}^t(y_1 ⋯ y_n) ≠ 0

tel que

{}^ty h = 0

D’où

{}^ty Ax = {}^ty h

avec $h ≝ c_0 + \sum_i c_i a_i + \sum_{i} c’_i x_i$

Pourquoi a-t-on ${}^ty A ∈ 𝕸_{1,p}(𝕂)$ ?

(et pas ${}^ty A ∈ 𝕸_{1,p}(𝕂[a_1, ⋯, a_n])$ )

⟶ ${}^ty A$ est de la forme

d_0 + \sum_i d_i a_i + \sum_i d'_i x_i

car $y$ est à coefficients dans $𝕂$.

Par l’absurde : Si il y avait un coefficient ${}^ty A[j]∈𝕂[a_1, ⋯ ,a_n] \backslash 𝕂$ :

alors le terme ${}^ty A[j] x_j$ de ${}^ty A x$ serait de degré supérieur à $2$, ce qui est impossible car il n’existe pas de tel terme dans ${}^ty h$ (qui est un polynôme de degré inférieur à $1$).

Donc

{}^ty A ∈ 𝕸_{1,p}(𝕂)

ce qui contredit l’indépendance modulo $𝕂$ des lignes de $A$, puisque $y≠0$.

OU :

M2 : en se plaçant dans l’anneau engendré par $𝕂$ et les $x_i$,

{}^ty Ax - {}^ty h = 0

est absurde car on a un polynôme de degré $1$ égal à $0$.

4.

A ≝ \begin{pmatrix} a & 0 \\ 0 & b \\ b & a \\ \end{pmatrix}
x ≝ \begin{pmatrix} c \\ d \\ \end{pmatrix}

Pour montrer qu’on a besoin d’au moins $3$ multiplications (se trouver dans le pire cas de l’exercice précédent), il suffit de montrer que le rang ligne de $A$ égal $3$.

Soient $c_1, c_2, c_3$ des scalaires tq :

c_1 \begin{pmatrix} a \\ 0 \\ \end{pmatrix}+ c_2 \begin{pmatrix} 0 \\ b \\ \end{pmatrix}+ c_3 \begin{pmatrix} b \\ a \\ \end{pmatrix} ∈ 𝕂

Comme $a, b∉𝕂$ :

  • la première égalité $c_1 a + c_3 b ∈ 𝕂$ équivaut à la nullité d’un polynôme de $𝕂[a, b]$, donc $c_1 = c_3 = 0$

  • De même, la deuxième égalité fournit : $c_2=0$

Donc les vecteurs lignes de $A$ sont indépendants modulo $𝕂$.

5.

Soient $v_1, ⋯, v_m$ des vecteurs de $𝕂[a_1, ⋯, a_n]^r$ dont $q$ sont linéairement indépendants modulo $𝕂$.

On pose pour $i≥2$

v'_i ≝ v_i + b_i v_1

On veut montrer que parmi $v’_1, ⋯, v’_m$, on a $q_1$ vecteurs linéairement indépendants modulo $𝕂$

  • Cas 1 :

    $\lbrace v_1, ⋯, v_q \rbrace$ sont linéairement indépendants modulo $𝕂$.

    Alors on montre aisément que $v’_2, ⋯, v’_q$ le restent.

  • Cas 2 :

    $\lbrace v_2, ⋯, v_{q+1} \rbrace$ sont linéairement indépendants modulo $𝕂$.

    Supposons que $v’_2, ⋯, v’_q$ ne sont pas linéairement indépendants.

    Alors il existe $(c_2, ⋯, c_q)≠0$ tq

    c_2 v'_2 + ⋯ + c_q v'_q ≝ w ∈𝕂^r \\ ⟺ \underbrace{\sum_i c_i b_i}_{≝ c_1} v_1 + c_2 v_2 + ⋯ + c_q v_q = w∈ 𝕂^r

    Avec $c_1 ≠0$ nécessairement, car sinon cela contredirait la linéaire indépendance modulo $𝕂$ des $v_2, ⋯, v_q$.

    Si on suppose en plus que $v’3, ⋯, v’{q+1}$ ne sont pas linéairement indépendants :

    alors il existe $(d_3, ⋯, d_{q+1})≠0$ tq

    d_1 v_1 d_3 v'_3 + ⋯ + d_{q+1} v'_{q+1} ≝ z ∈𝕂^r

    avec $d_1 ≠0$.

    Sans perte de généralité (quitte à réordonner) : disons que $c_2 ≠ 0$.

    \begin{align*} & d_1 w - c_1 z ∈ 𝕂^r \\ ⟺ & d_1 c_2 v_2 + (d_1 c_3 - c_1 d_3) v_3 + ⋯ + (d_1 c_q - c_1 d_q) v_q + c_1 d_{q+1} v_{q+1} ∈ 𝕂^r \\ ⟹ & d_1 c_2 = 0 \\ \end{align*}

    c’est absurde.

    Donc $v’2, ⋯, v’_q$ OU $v’_3, ⋯, v’{q+1}$ ne sont pas linéairement indépendants.

6.

\underbrace{A}_{𝕸_{r,p}(𝕂[a_1, ⋯, a_n])}x = \underbrace{(y_1 ⋯ y_r)}_{𝕸_{r,1}(𝕂[a_1, ⋯, a_n])}

Par récurrence sur $r$, le rang colonne modulo $𝕂$ de $A$.

  • Cas de base : rang colonne de $A$ modulo $𝕂$ égal à $1$.

    Supposons que le nombre de multiplications actives est égal à $0$.

    On en déduit que $Ax +y$ est de la forme

    \sum\limits_{i=1}^p c_i x_i + P(a_1, ⋯, a_n)

    Donc les coefficients de $A$ appartiennent à $𝕂$, donc le rang colonne de $A$ modulo $𝕂$ égal à $0$ : contradiction.

  • Héréditié : Si le rang colonne de $A$ modulo $𝕂$ égal à $q > 1$.

    Comme $q>1$, il y a forcément une multiplication active (sinon on a $q=0$ (cf. cas précédent)).

    Soit $f_i ⟵ g × h$ cette multiplication active.

    Comme c’est la première multiplication active, $g$ est de la forme

    g = \sum\limits_{i=1}^p c_i x_i + P(a_1, ⋯, a_n)

    (puisque qu’il n’y a pas eu de multiplication active dans $g$)

    Comme $f_i ⟵ g × h$ est une multiplication active, on sait (sans perte de généralité : si ce n’est pas le cas, considérer $h$ qui est aussi de la même forme) que l’un des $c_i≠0$, disons

    c_1 ≠ 0

    On pose

    x'_1 ≝ -c_1^{-1} (\sum\limits_{i=2}^p c_i x_i + P(a_1, ⋯, a_n)) et

    x' ≝ (x'_1, x_2, ⋯, x_p)

    Que se passe-t-il lorsqu’on calcule $Ax’ + y$ ?

    Je peux calculer $x’_1$ (pas de multiplication active), puis prendre le même calcul que pour $Ax +y$ en remplaçant $x_1$ par $x’_1$ (refaire les calculs avec $x’_1$) et $f_i ⟵ g × h$ par $f’_i ⟵ 0$.

    Ce nouveau calcul a (au moins) une multiplication active de moins que $Ax + y$.

    Il suffit que je montre que je dois faire $Ax’+y$ avec $q-1$ multiplications actives.

    Il suffit donc de montrer que

    Ax' + y = A'x''+y'

    avec $A’$ ayant un rang colonne égal à $q-1$

    Mq il existe $A’∈ 𝕸_{r,p-1}(𝕂[a_1, ⋯, a_n])$ et $y’$ tq :

    A' \begin{pmatrix} x_2 \\ \vdots \\ x_p \end{pmatrix} + y' = A x' + y

    On va prendre :

    A'[:, i] ≝ A[:, i] - c_1^{-1} c_i A[:, 1] \\ y' = y - c_1^{1} P(a_1, ⋯, a_n) A[:, 1]

    (pour se débarrasser de la première colonne de $A$)

    Comme dans $A$, il y a $q$ vecteurs colonnes indépendants, dans $A’$, il y en a $q-1$ (question 5), donc le rang colonne de $A’$ est au moins égal à $q-1$, et par hypothèse de récurrence, il faut au moins $q-1$ multiplications pour actives pour calculer $A’x’’ + y’ = Ax’+y$, donc au moins $q$ pour $Ax+y$.

7.

Il suffit de réécrire $Ax$ sous la forme $By$, avec $B$ ayant un rang colonne $np$.

Il suffit de poser :

B ≝ \underbrace{\begin{pmatrix} x_1 ⋯ x_p & 0 ⋯ 0 & ⋯ \\ 0 ⋯ 0 & x_1 ⋯ x_p & ⋯ \\ \end{pmatrix}}_{n×p \text{ colonnes}}
y ≝ \begin{pmatrix} a_{11} \\ a_{12} \\ \vdots \\ a_{21} \\ \vdots \end{pmatrix}

Leave a comment