NeuroCOLT: Neural Networks and Computational Learning Theory

NeuroCOLT

Neural Networks and Computational Learning Theory

1994	1995
1996	1997
1998	1999
2000	2001

Books

info@neurocolt.org

NeuroCOLT Technical Report NC-TR-97-008

Semi-algebraic Complexity -- Additive Complexity of Matrix Computational Tasks

T. Lickteig
Universit\"at Bonn
Germany

K. Meer
RWTH, Aachen
Germany

Abstract
This paper is devoted to the study of lower bounds on the inherent number of additions and subtractions necessary to solve some natural matrix computational tasks such as for instance computing the nullspace, a band transformation or a triangulation of a given $m \times m$ matrix. The additive complexities of such tasks are shown to grow asymptotically lik that of $m \times m$ matrix multiplication. We also propose a formalization of semi-algebraic computational tasks.

Download Compressed Postscript
Title Page