direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Leitung

Prof. Dr. Peter Bürgisser

Lupe [1]

Anschrift
Technische Universität Berlin
Institut für Mathematik
Sekretariat MA 3-2
Straße des 17. Juni 136
10623 Berlin

Büro
Raum MA 317 (3. OG)
Institut für Mathematik

Kontakt

Sekretariat
Beate Nießen [2]
Raum MA 318
Tel.: +49 (0)30 314 - 25771

eMail
peter.buergisser@offmath.tu-berlin.de
contact form [3]

Telefon
+49 (0)30 314 - 75902
Faxgerät
+49 (0)30 314 - 25839

Sprechstunde
Während der Vorlesungszeit: Do, 15-16 Uhr.
Während der vorlesungsfreien Zeit: nach Vereinbarung.

Publikationen

Some computational problems in linear algebra as hard as matrix multiplication
Zitatschlüssel BKL-Some-Computational-Problems-In-Linear-Algebra-As-Hard-As-Matrix-Multiplication
Autor Peter Bürgisser and Marek Karpinski and Thomas Lickteig
Seiten 131-155
Jahr 1991
DOI 10.1007/BF01272518
Journal Comp. Compl.
Jahrgang 1
Nummer 2
Zusammenfassung We define the complexity of a computational problem given by a relation using the model of computation trees together with the Ostrowski complexity measure. Natural examples from linear algebra are: $KER_n$: Compute a basis of the kernel for a given $n× n$ matrix, $OGB_n$: Find an invertible matrix that transforms a given symmetric $n× n$ matrix (quadratic form) into diagonal form, $SPR_n$: Find a sparse representation of a given $n× n$ matrix. To such a sequence of problems we assign an exponent similarly as for matrix multiplication. For the complexity of the above problems we prove relative lower bounds of the form $a M_n - b$ and absolute lower bounds $d n^2$, where $M_n$ denotes the complexity of matrix multiplication and $a$, $b$, $d$ are suitably chosen constants. We show that the exponents of the problem sequences KER, OGB, SPR are the same as the exponent of matrix multiplication.
Link zur Publikation [4] Link zur Originalpublikation [5] Download Bibtex Eintrag [6]
------ Links: ------

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe

Diese Seite verwendet Matomo für anonymisierte Webanalysen. Mehr Informationen und Opt-Out-Möglichkeiten unter Datenschutz.
Copyright TU Berlin 2008