Zugl. überarb. Fassung von: Berlin, Univ., Diss., 2009

Zugl.: Regensburg, Univ., Diss., 2006

Universiẗat, Diss., 2004--Tübingen.

Universiẗat, Diss., 1997--Saarbrücken.

Techn. Universiẗat, Diss., 2000--Berlin.

Chemnitz, Techn. Univ., Studienarb., 2007.

Techn. Universiẗat, Diss., 2000--Darmstadt.

University, Diss., 2002--Marburg.

Partitionierung von Graphen ist im Allgemeinen sehr schwierig. Es stehen derzeit keine Algorithmen zur Verfügung, die ein allgemeines Partitionierungsproblem effizient lösen. Aus diesem Grund werden heuristische Ansätze verfolgt. Zur Analyse dieser Heuristiken ist man derzeit gezwungen zufällige Graphen zu Verwenden. Daten realer Graphen sind derzeit entweder nur sehr schwer zu erheben (z.B. Internetgraph), oder aus rechtlichen bzw. wirtschaftlichen Gründen nicht zugänglich (z.B. soziale Netzwerke). Die untersuchten Heuristiken liefern teilweise nur unter bestimmten Voraussetzungen Ergebnisse. Einige arbeiten lediglich auf einer eingeschränkten Menge von Graphen, andere benötigen zum Erkennen einer Partition einen mit der Knotenzahl steigenden Durchschnittsgrad der Knoten, z.B. [DHM04]. Der im Zuge dieser Arbeit erstmals implementierte Algorithmus aus [CGL07a] benötigt lediglich einen konstanten Durchschnittsgrad der Knoten um eine Partition des Graphen, wenn diese existiert, zu erkennen. Insbesondere muss dieser Durchschnittsgrad nicht mit der Knotenzahl steigen. Nach der Implementierung erfolgten Tests des Algorithmus an zufälligen Graphen. Diese Graphen entsprachen dem Gnp-Modell mit eingepflanzter Partition. Die untersuchten Clusterprobleme waren dabei große Schnitte, kleine Schnitte und unabhängige Mengen. Der von der Art des Clusterproblems abhängige Durchschnittsgrad wurde während der Tests bestimmt.

Die vorliegende Arbeit ist ein Beitrag auf dem Gebiet der theoretischen Chemie und beschäftigt sich mit der Entwicklung effizienter Berechnungsmethoden für die Elektronendichte und die Energie des Grundzustands molekularer und periodischer Systeme im Rahmen der Kohn-Sham-Dichtefunktionaltheorie (Kohn-Sham-DFT) und unter Verwendung von lokalen Basisfunktionen. Im Vordergrund steht dabei die einheitliche Beschreibung von Molekülen und ausgedehnten Systemen beliebiger Periodizität (zum Beispiel Volumenkristalle, dünne Filme und Polymere) mit einfachen Algorithmen bei einem hohen Maß an numerischer Genauigkeit und Recheneffizienz. Dafür hat der Verfasser bewährte molekulare Simulationsmethoden in neuartiger Form auf periodische Randbedingungen erweitert und zu einer vollständigen DFT-Methode vereint. Von diesen Methoden ist das völlig neue Konzept für die RI-Methode (resolution of identity, Zerlegung der Einheit), die auf den Coulomb-Term angewendet wird, die Schlüsseltechnologie in dieser Arbeit. Ein Merkmal der Methode ist, dass sie ausschließlich im direkten Raum arbeitet. Neben der RI-Methode wurden weitere methodische Ansätze entwickelt werden, um eine gute Speicher- und Zeiteffizienz der gesamten DFT-Methode zu gewährleisten. Dazu gehören die Komprimierung der speicherintensiven Dichte- und Kohn-Sham-Matrizes und die numerische Integration des Austausch-Korrelationsterms durch die Anwendung eines adaptiven, numerischen Integrationsschemas. Die vorgestellten Methoden werden zum Prototypen eines RI-DFT-Programms zusammengefügt. Dieses Programm ermöglicht die Berechnung von single point-Energien am Gamma-Punkt für Systeme mit abgeschlossenen Schalen. Anhand von Berechnungen werden die numerische Genauigkeit und Effizienz bewertet. Das Programm bildet die Basis für ein effizientes und leistungsfähiges DFT-Programm, das Moleküle und periodische Systeme methodisch einheitlich und numerisch genau behandelt. / This work contributes to the field of theoretical chemistry and is aimed at the development of efficient methods for computation of the electron density and the energy belonging to the ground state of molecular and periodic systems. It is based on the use of Kohn Sham density functional theory (Kohn Sham DFT) and local basis functions. In this scope, the molecular and the periodic systems of any dimensionality (e.g., bulk crystals, thin films, and polymers) are treated on an equal footing using methods which are easy to implement, numerically accurate, and highly efficient. For this, the author has augmented established methods of molecular simulations for their use with periodic boundary conditions applying novel techniques. These methods have been combined to a complete DFT method. Among these methods, the innovative approach for the RI (resolution of identity) method applied to the Coulomb term represents the key technology of this work. As a striking feature, this approach operates exclusively in real space. Although the RI method is the chief ingredient, the development of further methods is required to achieve overall efficiency for the consumption of storage and time. One of these methods is used to compress the density and Kohn Sham matrices. Moreover, numerical integration of the exchange-correlation term has been improved applying an adaptive numerical integration scheme. The methods presented in this thesis are combined to the prototype of an RI-DFT program. Using this program single point energies on the gamma point can be calculated for systems with closed shells. Calculations have been performed and the results are used to assess the accuracy and efficiency achieved. This program forms the foundation of an efficient and competitive DFT code. It works numerically accurate and treats molecules and periodic systems on an equal footing.