Une introduction à la théorie de la complexité algébrique basée sur un panorama des méthodes algorithmiques en algèbre linéaire. Aborde aussi la complexité binaire. ©Electre 2025

La Société de Mathématiques Appliquées et Industrielles (SMAI), fondée en 1983, s'est fixé comme objectif la promotion des mathématiques appliquées. Dans cet esprit, la SMAI a créé une collection d'ouvrages Mathématiques & Applications, don't voici un nouveau numéro

Le but de cette collection est d'éditer des textes de niveau 3ème cycle universitaire ou de dernière année d'école d'ingénieurs. Les lecteurs concernés sont donc des étudiants, mais également des chercheurs et ingénieurs qui veulent s'intier aux méthodes et aux résultats des mathématiques appliquées. Certains ouvrages auront ainsi une vocation purement pédagogique alors que d'autres pourront constituer des textes de référence.

La principale source des manuscrits réside dans les très nombreux cours qui sont enseignés en France, compte tenu de la variété des Diplômes d'Etudes Approfondies (D.E.A.), des Diplômes d'Études Supérieures Spécialisées (D.E.S.S.) ou des options de mathématiques appliquées dans les écoles d'ingénieurs. Mais ce n'est pas l'unique source : certains textes pourront avoir une autre originc.

Parmi les suiets que la collection souhaite aborder, figurent les suivants : Analyse numérique - Analyse stochastique - Probabilités appliquées - Équations aux dérivées partielles - Automatique - Optimisation - Recherche opérationnelle - Statistique et analyse des données - Modélisation (en mécanique, en économie...) - Infographie et Traitement d'images - Codage et cryptographie - Calcul formel - Calcul parallèle...

Jounaïdi Abdeliaoued
Henri Lombardi

Méthodes matricielles -
Introduction à la complexité algébrique

Ce liver est une introduction à théorie de la complexité algébrique basée sur un panorama des méthodes algorithmiques en algèbre linéaire exacte. Il donne en particulier les principaux algorithmes pour le calcul du polynôme caractéristique. Il donne aussi une discussion détaillée des methodes de multiplication rapide des polynômes et des matrices, sans pour autant réclamer de prérequis théoriques de haut niveau. Tout en étant centré sur les problèmes de complexité algéebrique, il aborde aussi la complexité binaire. Une place importante est accordée au parallélisme. Le livre se termine par une introduction raisonnée à l'importante théorie de Valiant concerant un analogue algébrique de la coniecture P#NP. Ce livre se remarque par l'étendue des suiets traités tout en restnat très lisible.