Parallele Lösung von grossen voll-besetzten Eigenwertproblemen mit ScaLAPACK

ScaLAPACK ist die Standard-Software für die parallele Lösung von grossen Eigenwertproblemen

A x = λ B x
mit vollen Matrizen A und B [1, 2]. Wir nehmen an, dass A und B symmetrisch sind und zusätzlich B positiv-definit ist.

In der Praxis wie zum Beispiel in der Quantenchemie (approximative Lösung der Schrödingergleichung) treten Matrizen der Ordung n=2000 - 3000 recht oft auf, siehe [3]. Es gibt eine optimale Zahl von Prozessoren für die Lösung dieser Probleme. Der Einsatz von weniger oder mehr Prozessoren erhöht die Lösungszeit.

In dieser Arbeit soll untersucht werden, wie vorzugehen ist, wenn die Matrizen noch grösser sind, n=5000 - 10000, und der Aufbau der Matrizen eine grössere Zahl von Prozessoren benötigt als für das Eigenwertproblem optimal ist. Diese Situation tritt dann auf, wenn die Berechnung der Matrizen A und B wesentlich teurer ist als die Lösung des Eigenwertproblems, eine suboptimale Lösung des Eigenwertproblems aber die Gesamtausführungszeit drastisch erhöhen kann. Das Hauptproblem wird sein, die Daten beim Matrixaufbau so zu verteilen, dass sie leicht auf eine Teilmenge der Prozessoren transferiert werden können und dort für den Eigenlöser von ScaLAPACK optimal verteilt sind.

Falls die Arbeit im Rahmen einer Semesterarbeit stattfindet, soll die Parallelisierung des Matrixaufbaus und der Diagonalisierung auf einem ausgewählten Rechner untersucht und (portabel) implementiert werden.

Im Fall einer Masterarbeit, sollen mehreren Rechner in die Untersuchung einbezogen werden. Die Algorithmen sollen analysiert werden anhand von charakteristischen Grössen von Parallelrechnern (Rechenleistung, Speichergrösse, Bandbreite der Interprozessorkommunikation). Es soll auch untersucht werden, ob es nicht von Vorteil wäre, ein heterogenes Netzwerk (Grid) für die Lösung des Gesamtproblems zu verwenden.

Diese Arbeit wird in Zusammenarbeit mit Dr. Hans P. Lüthi vom Laboratorium für Physikalische Chemie durchgeführt.

1. W. P. Petersen and P. Arbenz: Introduction to Parallel Computing. Oxford University Press, Oxford, 2004.
2. L. S. Blackford, J. Choi, A. Cleary, E. D'Azevedo, J. Demmel, I. Dhillon, J. Dongarra, S. Hammarling, G. Henry, A. Petitet, K. Stanley, D. Walker, and R. C. Whaley:  ScaLAPACK Users' Guide. SIAM, Philadelphia, PA, 1997. Siehe http://www.netlib.org/scalapack/.
3. L. Huber: Lösung von grossen voll besetzten Eigenwertproblemen mit ScaLAPACK. Semesterarbeit, Juli 2005.
4. H. P. Lüthi: Network computing: the Hartree-Fock calculation as a model. Theoretical Chemistry Accounts 97(1-4): 211-226, 1997
5. P. Arbenz, H. P. Lüthi, J. E. Mertz, and W. Scott: Applied Distributed Supercomputing in Homogeneous Networks. International Journal of High Speed Computing 4: 87-108, 1992.

Prof. Dr. Peter Arbenz

Institut für Computational Science
Universitätsstrasse 6, CAB G69.3

Tel.: 632 74 32

Email: arbenz@inf.ethz.ch

PD Dr. Hans Peter Lüthi

Laboratorium für Physikalische Chemie
ETH Hönggerberg HCI G 231

Tel.: 632 2105

Email: luethi@igc.phys.chem.ethz.ch