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.

Export metadata

Additional Services

Search Google Scholar
Metadaten
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
Einverstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.