Fachgebiet Algorithmische AlgebraProf. Dr. Peter Bürgisser

# Leitung

## Prof. Dr. Peter Bürgisser

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
pbuerg@math.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

Zitatschlüssel BKL-Some-Computational-Problems-In-Linear-Algebra-As-Hard-As-Matrix-Multiplication Peter Bürgisser and Marek Karpinski and Thomas Lickteig 131-155 1991 10.1007/BF01272518 Comp. Compl. 1 2 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.