Development analysis and assessment of efficient load balancing methods on graphs with applications in computer networks and domain decomposition

• Applicant: Professor Dr. Andreas Frommer
• Subject Area: Mathematics
• Term: from 2000 to 2005
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 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 Programme: Research Grants