Algebraic complexity theory / Peter Bürgisser, Michael Clausen, M. Amin Shokrollahi

Auteur: Bürgisser, Peter (1962-) - AuteurCo-auteur: Clausen, Michael - Auteur ; Shokrollahi, Amin (1964-) - AuteurAuteur secondaire : Lickteig, Thomas (1955-) - CollaborateurType de document: MonographieCollection: Grundlehren der mathematischen wissenschaften ; 315Langue: anglaisÉditeur: Berlin : Springer, 1997 ISBN: 9783662033388 Note: Within the general theory of computational complexity, algebraic complexity theory can be distinguished by the source of its problems (algebra) and by its stress on symbolic (as opposed to numerical) aspects in computational models. Among others, the book discusses the following fundamental problems: multiplication of polynomials; multiplication, inversion and composition of power series; computing the greatest common divisor of polynomials; polynomial interpolation and evaluation of polynomials; matrix multiplication; inversion and other problems of (bi)linear algebra. The main computational models are the straight-line program and the computation tree. The authors stress that there is a difference between algebraic complexity and computer algebra. The book emphasizes proving lower bounds on complexity, that is, proving that a given problem cannot be solved faster than in a particular time. On the other hand, computer algebra deals with upper bounds on complexity for algorithmic problems in algebra. Naturally, proving a good upper bound reduces to constructing an efficient algorithm. Proving a nontrivial lower bound may turn out to be quite difficult and often requires an advanced technique even if the problem is "elementary'' and the bound looks "obvious''. ... (MathSciNet) Sujets MSC: 68Q25 Computer science -- Theory of computing -- Analysis of algorithms and problem complexity
68W30 Computer science -- Algorithms -- Symbolic computation and algebraic computation
68Q05 Computer science -- Theory of computing -- Models of computation (Turing machines, etc.)
68Q15 Computer science -- Theory of computing -- Complexity classes (hierarchies, relations among complexity classes, etc.)
12Y05 Field theory and polynomials -- Computational aspects of field theory and polynomials -- Computational aspects of field theory and polynomials
En-ligne: Springerlink | Zentralblatt | MathSciNet

No physical items for this record


Within the general theory of computational complexity, algebraic complexity theory can be distinguished by the source of its problems (algebra) and by its stress on symbolic (as opposed to numerical) aspects in computational models. Among others, the book discusses the following fundamental problems: multiplication of polynomials; multiplication, inversion and composition of power series; computing the greatest common divisor of polynomials; polynomial interpolation and evaluation of polynomials; matrix multiplication; inversion and other problems of (bi)linear algebra. The main computational models are the straight-line program and the computation tree.
The authors stress that there is a difference between algebraic complexity and computer algebra. The book emphasizes proving lower bounds on complexity, that is, proving that a given problem cannot be solved faster than in a particular time. On the other hand, computer algebra deals with upper bounds on complexity for algorithmic problems in algebra. Naturally, proving a good upper bound reduces to constructing an efficient algorithm. Proving a nontrivial lower bound may turn out to be quite difficult and often requires an advanced technique even if the problem is "elementary'' and the bound looks "obvious''. ... (MathSciNet)

There are no comments for this item.

Log in to your account to post a comment.
Languages: English | Français | |