Entwicklung, Untersuchung und Beurteilung effizienter Verfahren zur Lastverteilung auf Graphen mit Anwendungen in Rechnernetzen und bei Gebietszerlegungen

• Antragsteller: Professor Dr. Andreas Frommer
• Fachliche Zuordnung: Mathematik
• Förderung: Förderung von 2000 bis 2005
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 5265120

Beim Loadbalancing auf Graphen ist eine von Knoten zu Knoten zunächst unterschiedliche Last ausschließlich durch Kommunikation zwischen benachbarten Knoten auszugleichen. Diese Aufgabe ist ein Modell für verschiedene praktische Situationen, etwa beim Lastausgleich in Rechnernetzen oder bei Gebietszerlegungsmethoden bei partiellen Differentialgleichungen. In der Theoretischen Informatik wird Loadbalancing seit langem untersucht. In jüngster Zeit, auch unter Beteiligung des Antragstellers verfolgte Ansätze greifen verstärkt auf Methoden der numerischen linearen Algebra (Stichwort: Krylov-Unterraum-Verfahren für singuläre Systeme) zurück. Das beantragte Vorhaben soll diese erfolgversprechende neue Entwicklung systematisch weiter anführen und voranbringen. In dem Vorhaben sollen schwerpunktmäßig Dimension-Exchange-Verfahren betrachtet und entwickelt, bezüglich Aufwand und Konvergenzeigenschaften untersucht und untereinander verglichen werden. Besondere Aufmerksamkeit soll der Qualität der entstehenden Flüsse über die Kanten des Graphen gewidmet werden, da für die Praxis möglichst kleine Flüsse wünschenswert sind. Die vorhandene Kooperation mit Professor Monien (Theoretische Informatik, Paderborn) soll im Vorhaben weiter vertieft werden.

• DFG-Verfahren: Sachbeihilfen