Vorlesungen Diskrete Strukturen Effiziente Algorithmen und Datenstrukturen I Fortgeschrittene Netzwerk- und Graph-Algorithmen Proseminar Datenkompression Hauptseminar Algorithmen für NP-schwere Probleme Praktikum Algorithmen-Entwurf Lehrveranstaltungen für Doktoranden Oberseminar

Oberseminar Lehrstuhl Mayr

• Sparse Matrix Multiplications in the I/O-Model

  Raum: 03.11.018
  Zeit: Mittwoch, 22.3.2011, 13.45 Uhr
  Vortragender: Gero Greiner
  The talk overviews the multiplication of a sparse matrix with both vectors and matrices in the semiring I/O-model. Multiplying a sparse N x N matrix A, having kN non-zero entries, with a dense vector was considered by Bender, Brodal, Fagerberg, Jacob and Vicari in 2007. They determined its complexity for different layouts for storing A up to a certain density. In this talk, we present results extending their work towards
  - creating the matrix-vector product of A with multiple vectors simultaneously,
  - multiplying A with a dense matrix B,
  - transposing A, which also yields a lower bound for creating the product of two sparse matrices A and B.
  Furthermore, we show that in our model for most parameter settings, creating the matrix-vector product has the same complexity as evaluating the bilinear form. For all the considered tasks, upper and lower bounds that match up to constant factors are obtained for a wide range of parameters. Only the task of creating the product of two sparse matrices eludes matching bounds so far. Finally, we regard the task of permuting N elements, aiming to examine what makes a certain instance difficult.

• Ansätze für schwierige Permutationen im I/O-Modell

  Raum: 03.11.018
  Zeit: Mittwoch, 9.3.2011, 13.45 Uhr
  Vortragender: Gero Greiner
  Permutieren im externen Speicher ist durch die in Blöcken organisierte Struktur der Speichermedien komplizierter zu handhaben als im klassischen RAM-Modell. Die Komplexität des Permutierens im I/O-Modell wurde bereits weitgehend untersucht. So existieren asymptotisch passende obere und untere Schranken. Eine untere Schranke wurde jedoch bislang nur auf Basis der Anzahl an verschiedenen Permutationen gewonnen. Die Struktur hingegen, welche das Problem schwierig machen kann, ist noch unverstanden. Der Vortrag stellt verschiedene Perspektiven auf die Suche nach schwierigen Permutationen vor und kann einige vielversprechende Kandidaten ausschließen. Der Fokus liegt dabei auf Expandern, die eine hohe Konnektivität versprechen. Dennoch können Beispiele konstruiert werden, bei denen der Vorgang der damit verbundenen Permutation einfach ist.

• Speichereffiziente Algorithmen für dünne Gitter

  Raum: 03.11.018
  Zeit: Mittwoch, 2.3.2011, 13.45 Uhr
  Vortragender: Philipp Hupp
  Der Einführungsvortrag zu meinem Dissertationsthema "Speichereffiziente Algorithmen für dünne Gittern" stellt die wichtigsten theoretischen Grundlagen und die Forschungsziele der Arbeit vor. Im Vortrag werde ich zunächst das I/O-Modell und seine Bedeutung für das Verarbeiten von großen Datensätzen erläutern. Danach gehe ich auf dünne Gitter ein und erörtere deren Relevanz für hochdimensionale Probleme. Anschließend werden die Forschungsziele der Arbeit vorgestellt: Die Herleitung von Laufzeitschranken für verschiedene Probleme auf dünnen Gittern, die Entwicklung von Algorithmen, die diese Probleme optimal lösen und die Weiterentwicklung des theoretischen Modells zur Bewertung der I/O-Komplexität dieser Algorithmen.
  

• Cache-optimierte Permutations-Algorithmen

  Raum: 01.10.011 (Seminarraum Lehrstuhl Bichler)
  Zeit: Mittwoch, 23.2.2011, 13.45 Uhr
  Vortragender: Yang Guo
  
  Zusammenfassung:
  Das Permutieren von Daten im Speicher erscheint auf dem ersten Blick als triviale Aufgabe. Unter Berücksichtigung der Speicherhierarchien in modernen Rechner können jedoch komplexere Algorithmen unter Umständen effizienter sein. In diesem Vortrag werden einige Ansätze und damit verbundenen Problematiken vorgestellt. Insbesondere werden verschiedene sortier-basierte Algorithmen und Implementationen in ihrer Laufzeit verglichen.