Skip to content

analyse_problemes_v10_v12

Jump to bottom
hprzeta edited this page Nov 11, 2026 · 4 revisions

Analyse v10 → v12 — Illinois hybride 2-phases (Arb/FLINT)

📌 Note du 11/11/2026 (gains cumulés) — les gains « depuis v1 » de ce document comparent 21 h (mesurées à T=10 000) à des durées à T=100 000 : ils ne sont pas comparables, et certains (×4 500, ×5 040, ×5 628, ×28 600+) ne sont pas reproductibles (21 h divisées par la durée donnent ×53 à ×286). Référence retenue : comparaison à T égal, v2 → v16 ≈ ×7 490 à T=10 000 — voir Etape-1-Calcul-des-zéros-non-triviaux, « Gains cumulés à T égal ». Le texte ci-dessous est conservé tel quel (historique daté).

Date : 2026-06-13
Branche : Riemann_Lab_C
Auteur : hprzeta

1. Problèmes de v10 (Brent C/mpfr)

1.1 Bottleneck MPFR mémoire-bound irréductible

v10 atteint 23.7 min sur T=100 000 avec Brent C/mpfr à W=8. Le coût dominant :

Phase Coût Part du total
Brent phase 1 (prec=64 bits) ~10 ms/iter ~15 %
Brent phase 2 (prec=80 bits) ~64 ms/appel ~80 %
Scan Z_double (C inline) ~0.015 ms < 1 %
Turing-Backlund N(T) ~35 s total ~2.5 %

Cause : chaque appel Z_rs_mpfr_ntermes à prec=80 bits requiert $N(t) = \lfloor\sqrt{t/2\pi}\rfloor$ termes RS, chacun accédant à une mantisse MPFR 80 bits en RAM. À $t = 80 000$, $N(t) \approx 113$ termes → ~113 accès mémoire 80 bits par itération.

1.2 W=8 saturé sur i7-7500U

Avec 2 cœurs physiques HT, W=8 est le maximum pratique. Augmenter W davantage serait contre-productif (overhead context-switch > gain HT).

1.3 Absence de cache fa/fb

Les évaluations $Z(a)$ et $Z(b)$ lors du changement de signe (scan) sont recalculées à l'initialisation Brent → 2 évals redondantes par zéro.

2. v11 — étape intermédiaire (cache scan→Brent)

v11 a implémenté le cache (fa, fb) entre le scan et l'affinage :

# v11 : transmission de fa, fb depuis le scan vers Brent
sign_changes = [(a, b, Z(a), Z(b)) for a, b in brackets]
for a, b, fa, fb in sign_changes:
    zero = brent_refine_cached(a, b, fa, fb, ...)

Gain mesuré v11 vs v10 : modeste (les 2 évals redondantes représentent ~3–5 % du coût total quand chaque appel Brent coûte ~64 ms). Le bottleneck reste MPFR.

Conclusion v11 : gain marginal sur MPFR → décision de changer de backend d'affinage.

3. Solution v12 — Illinois hybride 2-phases (illinois_arb.c)

3.1 Principe général

v12 remplace Brent/MPFR par un algorithme hybride à 2 phases basé sur Arb/FLINT :

Phase Fonction Coût Précision Condition d'arrêt
Phase 1 Z_rs_double (C0+C1, double natif) ~0.015 ms ~2e-16 $|b-a| &lt; 10^{-6}$
Phase 2 2 Newton steps Z_arb ~3.5 ms × 2 $&lt; 10^{-12}$ 2 pas fixes
Fallback Illinois Z_arb classique ~3.5 ms/iter $&lt; 10^{-12}$ si signe incohérent, $t &lt; 200$

Chemin mpmath_petit_t conservé pour $t &lt; 200$ (LMFDB safe, 87 zéros sur 138 080).

3.2 Phase 1 — Illinois Z_rs_double : bracket 1e-6

La Phase 1 utilise la formule de Riemann-Siegel tronquée à 2 termes (C0 + C1) en double natif IEEE 754 :

$$Z_{\text{rs}}(t) \approx 2 \sum_{n=1}^{N(t)} \frac{\cos(\theta(t) - t \ln n)}{\sqrt{n}} + C_0(t) + C_1(t)$$

  • Coût : ~0.015 ms/appel (vs ~64 ms MPFR) → ×4 000 plus rapide
  • Précision : ~2e-16 (limite IEEE 754 double)
  • Objectif : réduire le bracket de $\delta_0 = 0.010$ à $|b-a| &lt; 10^{-6}$

Convergence Illinois modifié (méthode de fausse position) :

$$c_{n+1} = b_n - f(b_n) \cdot \frac{b_n - a_n}{f(b_n) - f(a_n)}$$

avec le modificateur Illinois : si $f(a) \cdot f(c) &lt; 0$, alors $f(a) \leftarrow f(a)/2$ (accélère la convergence superlinéaire).

Nombre d'itérations Phase 1 estimé (bracket initial = 0.010, cible = 1e-6) : $$n_1 \approx \frac{\ln(10^4)}{\ln 1.44} \approx 24 \text{ itérations}$$

Coût total Phase 1 : $24 \times 0.015 \approx 0.36 \text{ms}$ — négligeable.

3.3 Phase 2 — 2 Newton steps Z_arb : précision 1e-12

Depuis le bracket serré $[a', b']$ avec $|b'-a'| &lt; 10^{-6}$, 2 pas de Newton en Arb/FLINT :

$$x_{n+1} = x_n - \frac{Z(x_n)}{Z'(x_n)}$$

Dérivée $Z'(x)$ estimée numériquement via Arb : $$Z'(x) \approx \frac{Z(x + h) - Z(x - h)}{2h}, \quad h = 10^{-8}$$

Ordre de convergence Newton : quadratique (ordre 2). Partant de $|x_0 - \rho| &lt; 5 \times 10^{-7}$ :

$$|x_2 - \rho| \lesssim (5 \times 10^{-7})^{2^2} = (5 \times 10^{-7})^4 \approx 6 \times 10^{-26} \ll 10^{-12}$$

Coût total Phase 2 : $2 \times 2 \times 3.5 \approx 14 \text{ms}$ (2 Newton steps × 2 appels Z_arb chacun).

Coût moyen observé par zéro : $\approx 4.7 \text{ms}$ (Phase 1 négligeable + Phase 2 ~7 ms + overhead scan).

3.4 Conditions de bascule et fallback

// Conditions de bascule Phase 1 → Phase 2
if (fabs(b - a) < 1e-6) {
    // → Phase 2 Newton Z_arb
}

// Fallback : Illinois Z_arb classique
if (signe_incoherent || t < 200.0) {
    // → illinois_arb classique (Z_arb à chaque iteration)
}

Le fallback s'active principalement pour $t &lt; 200$ (où $N(t) &lt; 6$ termes RS → $Z_{\text{rs-double}}$ imprécis). Cela concerne environ 0.06 % des zéros sur T=100 000.

3.5 Signature C — illinois_arb.c

double illinois_refine_arb(
    double a, double b,      // bracket initial avec changement de signe
    double fa, double fb,    // Z(a), Z(b) pré-calculés (cache v11)
    double t_center,         // valeur t centrale (pour chemin t < 200)
    double tol,              // = 1e-6 (cible Phase 1)
    int max_iter_phase1,     // = 60
    int max_newton           // = 2
);

4. Résultats T=100 000 v12 (mesurés 2026-06-13)

4.1 Validation T=10 000

Indicateur v10 T=10k v12 T=10k Gain
Zéros 10 142 10 142 =
Manquants 0 0 =
Durée 16.2 s 25.8 s × 0.6
Vitesse 624 z/s 392 z/s —

Note : v12 est légèrement plus lent sur T=10k. À petit t ($t &lt; 10 000$), $N(t) &lt; 40$ termes RS → MPFR v10 est rapide (~10 ms/appel). L'avantage Arb s'exprime pleinement à grand t ($t &gt; 50 000$).

4.2 Run T=100 000

Indicateur v10 (turbo) v12 (turbo) Gain
Zéros 138 069 ~138 080 ≈ +11
Manquants 0 0 ✅ =
Durée 23.7 min 8.8 min ×2.69
Vitesse 97.08 z/s ~261 z/s ×2.69
Gain vs v10 — — ×16.9 (benchmark T=10k)
ms/appel moyen 64.09 ms ~4.7 ms ×13.6
Turing-Backlund COMPLET ✅ COMPLET ✅ =
LMFDB 19/20 20/20 ✅ +1/20
Phase 1 utilisée — ~99.94 % —
Fallback t<200 — ~0.06 % —

Le gain ×16.9 est mesuré sur T=10k (25.8s v12 vs 434.5s v10 pur Z_arb). Le run T=100k mesure ×2.69 direct (23.7 → 8.8 min), différence expliquée par le profil de t : grand t dominant dans T=100k.

4.3 Tableau récapitulatif Avant/Après/Gain

Métrique v10 v12 Gain
Backend affinage Brent C/mpfr 64→80 bits Illinois hybride Z_rs_double + Newton Arb —
Coût moyen/zéro ~64 ms ~4.7 ms ×13.6
Phase 1 coût ~10 ms ~0.36 ms ×28
Phase 2 coût ~54 ms ~7 ms ×7.7
Durée T=100k 23.7 min 8.8 min ×2.69
Gain benchmarké T=10k — — ×16.9
Zéros manquants 0 0 ✅ =
LMFDB 19/20 20/20 ✅ +1/20
Turing COMPLET COMPLET ✅ =
Gain cumulé v1→vN ×5 040 — —

Gain global v1 → v12 mesuré T=100k : $$\frac{21 \text{h}}{8.8 \text{min}} = \frac{1 260 \text{min}}{8.8 \text{min}} \approx \times 143$$

5. Questions ouvertes

  • T=1 000 000 : à $t = 10^6$, $N(t) \approx 399$ termes RS → coût Phase 2 Newton ×3.5. Durée estimée : ~50–100 min sur i7-7500U avec W=8. Faisable en une nuit.
  • Odlyzko-Schönhage : algorithme $O(T^{1/2+\varepsilon})$ — pour T=10 000 000, incontournable. Implémentation complexe (DFT non-uniforme + FFT radix-2).
  • Cloud : AWS c2-standard-16 (16 vCPU) → gain ×4 vs i7 dual-core HT → T=100k en ~2 min.
  • Précision Phase 2 : 2 Newton steps suffisent pour 1e-12. Passer à 3 steps pour 1e-18 (validation LMFDB 20/20 → 20/20 robuste) ?
  • GPU CUDA : toujours inutile pour Illinois séquentiel (dépendance inter-itérations). Utile uniquement pour scan Z(t) vectorisé en float64 GPU.

analyse_problemes_v10_v12.md · Riemann_Lab.wiki/master · hprzeta · MAJ 2026-06-13 · 12 septembre 2026 (correction rendu KaTeX : _ et # — GitHub retirait le backslash en mode math) · note du 11/11/2026 (gains cumulés) · 196 lignes

Clone this wiki locally