Semi-algebraic Complexity—Additive Complexity of Matrix Computational Tasks

AbstractThis 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 computing the nullspace, some band transformation, and some triangulation of a givenm×mmatrix. The additive complexities of such tasks are shown to grow asymptotically like that of them×mmatrix multiplication. The paper is a continuation of an earlier paper by the authors, and also of4where multiplicative complexity has been considered. We also propose a formalization of semialgebraic computational tasks