Seminar Numerische lineare Algebra - SS 2013

Allgemeine Informationen

Veranstalungsform

• Blockseminar

Verantwortlich

• Prof. Dr. Stefan Funken

Studiengänge

• Bachelor- & Master-Studenten im Studiengang Mathematik und Wirtschaftsmathematik

Bei Interesse, Email senden an (Stefan Funken)

Inhalt

Sei Α eine invertierbare n×n Matrix. Das Gauß- Verfahren benötigt O(n³) Operationen zur Berechnung der LR-Zerlegung von Α. Kann man den Aufwand reduzieren, wenn die Matrix  Α eine spezielle Struktur hat? Spezielle Matrizen sind z.B. Toeplitz-, Cauchy-, Vandermonde- und Hankel-Matrizen.

Im Seminar beschäftigen wir uns mit

• schnellen Algorithmen für Matrizen mit Struktur, d.h. wie kann man Α^-1x, LR- oder QR-Zerlegungen mit quadratischem Aufwand
• oder näherungsweise sogar mit O( n log²(n) ) Operationen bestimmen,
• den Anwendungsfällen solcher Matrizen,
• weiteren Algorithmen, welche zu den TOP 10 des 20. Jahrhunderts gezählt werden (siehe SIAM News, Volume 33, Number 4). Dies wären u.a.
  • der QR-Algorithmus zur Berechnung von Eigenwerten
  • die schnelle Fourier-Transformation
  • und Krylov-Unterraummethoden.

Literatur

• T. Boros, T. Kailath und V. Olshevsky, Pivoting and Backward Stability of Fast Algorithms for Solving Cauchy Linear Equations (pdf download)
• SIAM News, Volume 33, Number 4, B.A. Cipra,The Best of the 20th Century: Editors Name Top 10 Algorithms (pdf download)
• I. Gohberg, V. Olshevsky, Fast Algorithms with Preprocessing for Matrix-Vector Multiplication Problems (pdf download)