The present work aims at an efficient, portable, and robust design of a data-distributed massively parallel DIRECT, the deterministic global optimization algorithm widely used in multidisciplinary engineering design, biological science, and physical science applications. The original algorithm is modified to adapt to different problem scales and optimization (exploration vs.\ exploitation) goals. Enhanced with a memory reduction technique, dynamic data structures are used to organize local data, handle unpredictable memory requirements, reduce the memory usage, and share the data across multiple processors. The parallel scheme employs a multilevel functional and data parallelism to boost concurrency and mitigate the data dependency, thus improving the load balancing and scalability. In addition, checkpointing features are integrated to provide fault tolerance and hot restarts. Important algorithm modifications and design considerations are discussed regarding data structures, parallel schemes, error handling, and portability. Using several benchmark functions and real-world applications, the present work is evaluated in terms of optimization effectiveness, data structure efficiency, memory usage, parallel performance, and checkpointing overhead. Modeling and analysis techniques are used to investigate the design effectiveness and performance sensitivity under various problem structures, parallel schemes, and system settings. Theoretical and experimental results are compared for two parallel clusters with different system scale and network connectivity. An analytical bounding model is constructed to measure the load balancing performance under different schemes. Additionally, linear regression models are used to characterize two major overhead sources---interprocessor communication and processor idleness, and also applied to the isoefficiency functions in scalability analysis. For a variety of high-dimensional problems and large scale systems, the data-distributed massively parallel design has achieved reasonable performance. The results of the performance study provide guidance for efficient problem and scheme configuration. More importantly, the generalized design considerations and analysis techniques are beneficial for transforming many global search algorithms to become effective large scale parallel optimization tools. / Ph. D.

In this thesis we study sparse classes of graphs and their properties usable for design of algorithms and data structures. Our specific focus is on the con- cepts of bounded expansion and tree-depth, developed in recent years mainly by J. Nešetřil and P. Ossona de Mendez. We first give a brief introduction to the theory as whole and survey tools and results from related areas of parametrised complexity and algorithmic model theory. The main part of the thesis, application of the theory, presents two new dynamic data structures. The first is for keeping a tree-depth decomposition of a graph, the second counts appearances of fixed subgraphs in a given graph. The time and space complexity of operations of both structures is guaranteed to be low when used for sparse graphs. 1

Estudam-se, nesta Tese, procedimentos e aplicações práticas de técnicas de otimização no projeto de estruturas civis submetidas a carregamento dinâmico. Ênfase especial é colocada em soluções integradas para sistemas estruturais compostos por fundações, pórticos e placas, destinados ao suporte de máquinas vibratórias. Problemas de minimizar o custo de estruturas e fundações são definidos como problemas de otimização. As dimensões dos elementos estruturais, bem como as armadura utilizadas, no caso do concreto armado, são as variáveis de projeto. Para se calcular a função custo, são considerados os custos de construção, incluindo os custos do concreto, do aço, da forma e do escoramento, quando aplicáveis. São consideradas, entre outras, restrições devidas à ruptura dos materiais e do solo, deslocamentos excessivos, bem como as relacionadas com a percepção pelo ser humano de níveis de vibração inconfortáveis. Um critério de ruína para barras de concreto armado submetidas à flexão obliqua composta é desenvolvido, com o objetivo de minimizar o tempo computacional Um programa de computador foi implementado, com base no Método dos Elementos Finitos e no algoritmo do Lagrangiano Aumentado, e utilizado para resolver diversos problemas práticos de otimização. Também a sensibilidade das soluções é abordada. / In this Thesis, procedures and practical applications of optimization techniques to the project of Civil Engineering structures subjected to dynamic loading are studied. Special emphasis is placed on integrated solutions for structural systems composed by beams, columns, plates and footings designed to support vibrating machines. Problems of minimizing structures and foundations cost are defined as optimization problems. The dimensions of the structural parts and their reinforcements, when reinforced concrete is used, are the design variables. In order to evaluate the cost function, the cost of the concrete, the steel, the form and the propping form, whenever proper, are considered. Constraints are considered, among others, due to material and soil failure, excessive displacements, as well as those related to the perception of uncomfortable vibration levels by human beings. A failure criterion for reinforced concrete members subjected to asymmetric bending and axial loading is presented in order to minimize computer time. A computer code was implemented, based on the Finite Element Method and the Augmented Lagrangian algorithm, and used to solve several practical optimization problems. The sensitivity of the solutions is also assessed.

O Método do Lagrangeano aumentado em problemas de otimização estrutural com restrições dinâmicas, bem como os conceitos matemáticos e numéricos necessários à sua compreensão são descritos. Este método resolve uma seqüência de problemas de minimização sem restrições definidos utilizando a função objetivo e as funções restrições. Um programa de computador é desenvolvido e aplicado em diversos exemplos. Alem disto, foi efetuada uma análise de sensibilidade com relação aos parâmetros utilizados no método. O método mostrou-se eficiente nas aplicações em problemas com restrições dinâmicas. / We present the method of the augmented Lagrangian in problems of scructural optimization with dynamic restrictions, as well as its mathemathical and numerical concepts. This method solves a series of unconstrained minimization problems using the objective function and the restriction functions. A computational program is implemented and applied in several examples. The augmented Lagrangian parameters senbility is analysed. The method is quite efficient in applications in optimization problems with dynamic restrictions.

O Método do Lagrangeano aumentado em problemas de otimização estrutural com restrições dinâmicas, bem como os conceitos matemáticos e numéricos necessários à sua compreensão são descritos. Este método resolve uma seqüência de problemas de minimização sem restrições definidos utilizando a função objetivo e as funções restrições. Um programa de computador é desenvolvido e aplicado em diversos exemplos. Alem disto, foi efetuada uma análise de sensibilidade com relação aos parâmetros utilizados no método. O método mostrou-se eficiente nas aplicações em problemas com restrições dinâmicas. / We present the method of the augmented Lagrangian in problems of scructural optimization with dynamic restrictions, as well as its mathemathical and numerical concepts. This method solves a series of unconstrained minimization problems using the objective function and the restriction functions. A computational program is implemented and applied in several examples. The augmented Lagrangian parameters senbility is analysed. The method is quite efficient in applications in optimization problems with dynamic restrictions.

A Cartesian method for solution of the steady two-dimensional Euler equations is produced. Dynamic data structures are used and both geometric and solution-based adaptations are applied. Solution adaptation is achieved through solution-based gradient information. The finite volume method is used with cell-centered approach. The solution is converged to a steady state by means of an approximate Riemann solver. Local time step is used for convergence acceleration. A multistage time stepping scheme is used to advance the solution in time. A number of internal and external flow problems are solved in order to demonstrate the efficiency and accuracy of the method.

Estudam-se, nesta Tese, procedimentos e aplicações práticas de técnicas de otimização no projeto de estruturas civis submetidas a carregamento dinâmico. Ênfase especial é colocada em soluções integradas para sistemas estruturais compostos por fundações, pórticos e placas, destinados ao suporte de máquinas vibratórias. Problemas de minimizar o custo de estruturas e fundações são definidos como problemas de otimização. As dimensões dos elementos estruturais, bem como as armadura utilizadas, no caso do concreto armado, são as variáveis de projeto. Para se calcular a função custo, são considerados os custos de construção, incluindo os custos do concreto, do aço, da forma e do escoramento, quando aplicáveis. São consideradas, entre outras, restrições devidas à ruptura dos materiais e do solo, deslocamentos excessivos, bem como as relacionadas com a percepção pelo ser humano de níveis de vibração inconfortáveis. Um critério de ruína para barras de concreto armado submetidas à flexão obliqua composta é desenvolvido, com o objetivo de minimizar o tempo computacional Um programa de computador foi implementado, com base no Método dos Elementos Finitos e no algoritmo do Lagrangiano Aumentado, e utilizado para resolver diversos problemas práticos de otimização. Também a sensibilidade das soluções é abordada. / In this Thesis, procedures and practical applications of optimization techniques to the project of Civil Engineering structures subjected to dynamic loading are studied. Special emphasis is placed on integrated solutions for structural systems composed by beams, columns, plates and footings designed to support vibrating machines. Problems of minimizing structures and foundations cost are defined as optimization problems. The dimensions of the structural parts and their reinforcements, when reinforced concrete is used, are the design variables. In order to evaluate the cost function, the cost of the concrete, the steel, the form and the propping form, whenever proper, are considered. Constraints are considered, among others, due to material and soil failure, excessive displacements, as well as those related to the perception of uncomfortable vibration levels by human beings. A failure criterion for reinforced concrete members subjected to asymmetric bending and axial loading is presented in order to minimize computer time. A computer code was implemented, based on the Finite Element Method and the Augmented Lagrangian algorithm, and used to solve several practical optimization problems. The sensitivity of the solutions is also assessed.

The DIRECT (DIviding RECTangles) algorithm JONESJOTi, a variant of Lipschitzian methods for bound constrained global optimization, has been applied to the optimal transmitter placement for indoor wireless systems. Power coverage and BER (bit error rate) are considered as two criteria for optimizing locations of a specified number of transmitters across the feasible region of the design space. The performance of a DIRECT implementation in such applications depends on the characteristics of the objective function, the problem dimension, and the desired solution accuracy. Implementations with static data structures often fail in practice because of unpredictable memory requirements. This is especially critical in S⁴W (Site-Specific System Simulator for Wireless communication systems), where the DIRECT optimization is just one small component connected to a parallel 3D propagation ray tracing modeler running on a 200-node Beowulf cluster of Linux workstations, and surrogate functions for a WCDMA (wideband code division multiple access) simulator are also used to estimate the channel performance. Any component failure of this large computation would abort the entire design process. To make the DIRECT global optimization algorithm efficient and robust, a set of dynamic data structures is proposed here to balance the memory requirements with execution time, while simultaneously adapting to arbitrary problem size. The focus is on design issues of the dynamic data structures, related memory management strategies, and application issues of the DIRECT algorithm to the transmitter placement optimization for wireless communication systems. Results for two indoor systems are presented to demonstrate the effectiveness of the present work. / Master of Science

Nesta pesquisa, estuda-se o fenômeno de localização de modos de vibração em estruturas moduladas quase periódicas de comportamento linear e não-linear. Em particular, contempla-se uma aplicação na Engenharia Civil, os painéis de placas periódicos com pequenas imperfeições fracamente acoplados entre si através de viga de grande rigidez, e principalmente submetidos à variação de forças de membrana introduzidas por meio da protensão, o que só pode ser levado em conta introduzindo a rigidez geométrica no modelo matemático. No caso de sistemas lineares, a presença de pequenas desordens nas características de rigidez ou massa de subsistemas fracamente acoplados pode causar confinamento espacial nas vibrações livres, conhecido como Localização de Modos, e pode inibir a propagação da resposta forçada. È o que tem sido mostrado na literatura técnica, em especial nas áreas de Engenharia Mecânica e Aeroespacial. Os efeitos de localização serão obtidos numa perspectiva modal. O programa de elementos finitos DYMPLATE implementado pelo autor para análise dinâmica não-linear de estruturas de placas, será utilizado para modelar estruturas periódicas (ordenadas) e quase periódicas (desordenadas). Os modelos são linearizados em torno de configurações deformadas de referência. O problema algébrico de autovalores é resolvido para obter as freqüências naturais e correspondentes modos de vibração. Estruturas planas constituídas por placas protendidas com módulos repetidos, pequenas imperfeições e diferentes condições de apoio e de carregamento, serão utilizadas na investigação numérica da influência de diversos fatores na Localização de Modos, em especial as forças de membrana. / In this research, the phenomenon of vibration modes localization in nearly periodic modular structures of linear and nonlinear behavior is studied. Of special interest is an application in Civil Engineering, lightly coupled periodic plate panels with small imperfections, mainly submitted to the variation of membrane forces introduced by prestress forces, which can be only considered by introducing geometric stiffness in the mathematical model. In the linear case, the presence of small disorders in the stiffness or mass characteristics of lightly coupled sub-systems can cause spatial confinement of free vibrations, known as Mode Localization, and can inhibit the propagation of the forced response. That is what has been shown in the literature, especially in the areas of Mechanical and Aerospace Engineering. The effects of localization are viewed from a modal perspective. DYMPLATE, a finite element software implemented by the author for nonlinear dynamic analysis of plates, will be utilized to model ordered and disordered plate periodic structures. The models are linearized about a deformed reference configuration. The algebraic eigenvalue problem is solved to obtain the natural frequencies and corresponding modes shapes. Plane structures constituted by prestressed plates with repetitive dynamic characteristics, small imperfections and different boundary conditions and loads, will be utilized in the numerical investigation of the influence of numerous factors in the Mode Localization.

Les applications des mesures dynamiques sur les bâtiments existants sont nombreuses : vérification de la vulnérabilité sismique des structures qui ont été construites avant l’apparition des règles parasismiques ; auscultation de la capacité des structures en situation post-sismique ou après des modifications au voisinage (creusement d’un tunnel à côté ou démolition des immeubles voisins par exemple). A l’heure actuelle, ce type de mesure permet le diagnostic d’une structure à l’échelle globale (toute la structure) alors que l’identification et la localisation des endommagements à l’échelle locale (chaque élément de la structure) restent encore à approfondir. Dans le cadre de cette thèse, le diagnostic à l’échelle locale des structures sera étudié. Cette thèse s’insère dans un contexte national de réévaluation des structures existantes du fait du nombre important de bâtiments à réhabiliter. Au sein du LOCIE, nous pensons que le comportement global des bâtiments est certes influencé par l’interaction sol-structure mais au moins autant par la qualité des connexions des éléments de structures entre eux. Il existe un besoin de qualification de ces connexions dont la variabilité du comportement peut provenir aussi bien de défauts de mise en œuvre (positionnement des armatures,…) que du vieillissement des structures. L’objectif principal de cette thèse est de proposer une méthode pouvant caractériser les liaisons entre les éléments de structure afin de pouvoir caler un modèle numérique. Ces caractérisations devaient être possibles à partir de mesures de sollicitations dynamiques. Une première étape de ce travail consistera à caractériser sur une partie de structure une liaison. Cela sera fait sur un portique en béton armé. Par la suite, cette méthode sera adaptée à une caractérisation au sein d’une structure de bâtiment. Pour cela nous ferons appel à la notion de sous-modèle. Un modèle numérique sera associé à cette méthode aussi bien sur la connexion simple que sur l’ensemble du bâtiment. Le travail de thèse s’appuiera sur l’utilisation et le développement de techniques concernant le traitement des données dynamiques ; la réduction de modèles ; l’expérimentation en laboratoire (échelle locale et échelle d’un élément de structure) et la modélisation numérique par éléments finis à plusieurs échelles / There are many of the examples of dynamics measurements applications in the existing building: verification of structural seismic vulnerability, which was constructed before the earthquake building code; auscultation of structural capacity in post-earthquake situation or after modification in surround environment (Excavation of tunnel or demolition the neighbour buildings for example). Currently, this measurement type enables the diagnosis a structure in global scale (a whole structure) while identification and localization of damage in local scale (each elements of the structure) remains to be explored. In this dissertation, diagnosis in locale scale will be studied. This study is significant for its contribution to the national reassessment of existing structures where there is the large number of buildings to be rehabilitated