| This dissertation is cognizant of the trend toward distributed computing, and the data management obstacles that must be overcome to achieve efficient, coherent solutions to large-scale finite-element problems. It forms the foundation for a highly structured, object-oriented, data management methodology, which offers portability, scalability of function, and access at multiple levels of abstraction. The methodology is based upon hierarchical multi-level substructuring (MLS) trees and methods. MLS data sets, or structures, are obtained by the decomposition or partitioning of a component. The following topics are presented: (1) Analysis and design of a polynomial time algorithm to approximate an optimal decomposition yielding a hierarchical MLS tree. (2) Design and analysis of a polynomial time algorithm to reorder the equations of a given coefficient matrix in an efficient manner subject to solution constraints. (3) A "tree compression" technique to reduce redundant computational effort and memory usage in MLS_Trees characterized by high-aspect ratio. (4) Methodologies for mapping the data and processes of each substructure within an MLS tree in a distributed computing environment. The investigation was limited to initially sparse matrix systems, static linear solution sequences and a realization that heuristic algorithms would be required.The integrated algorithms take a generic finite-element mesh as input, and output a hierarchical MLS_Tree structure, with suitable matrix reordering at each level in the structure. The overall complexity is O( n2lgn). Resultant MLS_Trees are mapped to processors by parsing the tree into a number of so-called branches. Branch size and number are dependent upon the available processors and the network latency. It is based upon the computational effort of each branch plus a weighted cost for transmission across the local area network. It is assumed that the latency is directly proportional to the size of the message.A large-scale FE problem, denoted Tcase, consisting of 921,669 system equations (DOF), was introduced. Tcase was subjected to the methodology, and the results are presented. The computational effort and memory requirements were decreased, as compared to the model without substructuring. A surface of all possible mappings in a distributed environment was created, from which optimal mappings can be ascertained. |
