Algebraic Complexity Theory (Grundlehren der mathematischen Wissenschaften)
Peter Bürgisser,Michael Clausen,Mohammad A. Shokrollahi | 1997-02-14 00:00:00 | Springer | 618 | Theory of Computing
This is the first book to present an up-to-date and self-contained account of Algebraic Complexity Theory that is both comprehensive and unified. Requiring of the reader only some basic algebra and offering over 350 exercises, it is well-suited as a textbook for beginners at graduate level. With its extensive bibliography covering about 500 research papers, this text is also an ideal reference book for the professional researcher. The subdivision of the contents into 21 more or less independent chapters enables readers to familiarize themselves quickly with a specific topic, and facilitates the use of this book as a basis for complementary courses in other areas such as computer algebra.
Reviews
This book presents an excellent and thorough introduction and overview of the field. It contains results of 573 papers in the field, but requires few prerequisites beyond basic abstract and linear algebra. It's perfect for independent study.
The key parts of the book for those interested in the matrix multiplication problem, like myself, and related problems are chapters 14-18. Chapter 14 describes the theory of the multiplicative complexity of bilinear maps, of which matrix multiplication is one, in terms of the concept of rank (also tensor rank), especially in the context of matrix algebras. The rank of a bilinear map is essentially a measure of the minimum number of multiplications in a bilinear algorithm for computing the map. Chapter 15 introduces the exponent of matrix multiplication in relation to the asymptotic complexity of the latter, and describes the fundamental relations between these asymptotic and bilinear measures, including the proof of Schonhage's important asymptotic direct sum inequality. Chapter 16 shows the fundamental importance of the exponent because it is found to determine the complexities of other important matrix operations such as inversion, taking of determinants, computing of characteristic polynomials etc. Chapters 17 and 18 describe further extensions, applications and links, including an interesting link between the ranks of finite fields and the minimal distances of linear error-correcting codes.
Download this book!
Free Ebooks Download