Semi-algebraic complexity - Additive complexity of matrix computational tasks
- 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 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 of 4where multiplicative complexity has been considered. We also propose a formalization of semialgebraic computational tasks.
Author: | Klaus MeerGND, Thomas Lickteig |
---|---|
URL: | http://www.sciencedirect.com/science/article/pii/S0885064X97904301 |
DOI: | https://doi.org/10.1006/jcom.1997.0430 |
ISSN: | 0885-064X |
Title of the source (English): | Journal of Complexity |
Document Type: | Scientific journal article peer-reviewed |
Language: | English |
Year of publication: | 1997 |
Volume/Year: | 13 |
Issue number: | 1 |
First Page: | 83 |
Last Page: | 107 |
Faculty/Chair: | Fakultät 1 MINT - Mathematik, Informatik, Physik, Elektro- und Informationstechnik / FG Theoretische Informatik |