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

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

eMail
pbuerg@math.tu-berlin.de
contact form

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.

The computational complexity to evaluate representations of general linear groups
Zitatschlüssel	B-The-Computational-Complexity-To-Evaluate-Representations-Of-General-Linear-Groups
Autor	Peter Bürgisser
Seiten	1010-1022
Jahr	2000
Journal	SIAM J. Comp.
Jahrgang	30
Nummer	3
Zusammenfassung	We describe a fast algorithm to evaluate irreducible matrix representations of general linear groups $\mathrm G\mathrm L(m,\mathbb C)$ with respect to a symmetry adapted basis (Gelfand-Tsetlin basis). This is complemented by a lower bound, which shows that our algorithm is optimal up to a factor $m^2$ with regard to nonscalar complexity. Our algorithm can be used for the fast evaluation of special functions: for instance, we obtain an $O(l\cdotłog(l))$ algorithm to evaluate all associated Legendre functions of degree $l$. As a further application we obtain an algorithm to evaluate immanants, which is faster than previous algorithms due to Hartmann and Barvinok.