Matrix methods. An introduction to algebraic complexity

MaRDI QIDQ1414899zbMATH OpenFDO

Authors Jounaïdi Abdeljaoued, Henri Lombardi

Publication date 8 December 2003

Published in Mathématiques \& Applications (Berlin) (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1604.00795

zbMATH Keywords

algebraic complexityalgorithmsfast matrix multiplicationfast polynomial multiplicationmatrix methodsparallel computationtextbook

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to linear algebra (15-02) Research exposition (monographs, survey articles) pertaining to numerical analysis (65-02) Parallel numerical computation (65Y05) Complexity and performance of numerical algorithms (65Y20) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Abstract: The main purpose of this book is to propose an introduction to the modern tools of algebraic complexity. To remain as simple as possible while providing meaningful examples, we 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 gives an introduction to a fascinating subject at a reasonable level. . . for French-speaking people.

Recommendations

• scientific article; zbMATH DE number 976329
• scientific article; zbMATH DE number 691245
• scientific article; zbMATH DE number 1453452
• Geometry and complexity theory
• scientific article; zbMATH DE number 727424

Cited in

(4)

• Formal reduction of singular linear differential systems using eigenrings: a refined approach
• Computing greatest common divisors and squarefree decompositions through matrix methods: the parametric and approximate cases
• Inversion modulo zero-dimensional regular chains
• Polynomials whose roots are the differences of the roots of a given polynomial

This page was built for publication: Matrix methods. An introduction to algebraic complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1414899)