TU Berlin

Fachgebiet Algorithmische AlgebraProf. Dr. Peter Bürgisser

Inhalt des Dokuments

zur Navigation

Leitung

Prof. Dr. Peter Bürgisser

Lupe

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
Raum MA 318
Tel.: +49 (0)30 314 - 25771

eMail
peter.buergisser@offmath.tu-berlin.de

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 Link zur Originalpublikation Download Bibtex Eintrag

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe