[retour]
Méthodes Matricielles.
Introduction à
la Complexité Algébrique
Reviews
-
MathSciNet
The main purpose of this well-written book is to propose an introduction to
the modern tools of algebraic complexity. To remain as simple as possible
while providing meaningful examples, Jounaïdi and Lombardi chose to focus
on effective linear algebra; this is certainly one of the best possible
choices to give an idea of the main problems in algebraic complexity.
The
contents of the book are the following:
-
classical results of linear algebra
and basic algorithms in linear algebra, straight-line programs as a model
of computation, with an emphasis on Strassen's method known as "elimination
of divisions",
-
a discussion on various notions of complexity,
-
a
presentation of the general algorithmic strategy "divide and conquer",
-
a
first important example: the fast multiplication of polynomials,
-
the very
heart of the book: the fast multiplication of matrices, with a discussion
of derived fast algorithms for various problems of linear algebra.
-
The
particular case of the computation of the determinant is then discussed,
and the last chapter deals with the difficult computation of the permanent
(Valiant's conjecture).
This book is certainly well-suited for an
introduction to a fascinating subject at a reasonable level ... for
French-speaking people.
Reviewed by Jean Moulin Ollagnier
-