Sistemas complexos que apresentam interações competitivas são ubíquos na natureza. Obter descrições adequadas das propriedades termodinâmicas desses sistemas é um desafio para o entendimento de uma série de processos químicos e físicos. Soluções analíticas em termos da Mecânica Estatística são extremamente difíceis de serem obtidas para esses sistemas. Isso faz com que o uso de simulações numéricas seja, na maioria dos casos, a única abordagem possível. Nesta Tese avaliamos o desempenho de duas classes de algoritmos de Monte Carlo generalizados empregados na determinação da natureza das transições de fase em dois sistemas complexos: o modelo de Ising dipolar bidimensional (2D) e um modelo mínimo para descrever proteínas. Na primeira classe, a qual representa os algoritmos seriais, incluimos os algoritmos multicanônico (MUCA) e de amostragem entrópica (ES), também conhecidos como algoritmos de amostragem uniforme. Na segunda classe, que diz respeito aos algoritmos paralelizáveis, incluimos o algoritmo canônico de Metropolis associado ao método de troca entre réplicas (REM). Para ambas as classes introduzimos contribuições metodológicas visando o aumento da eficiência na obtenção das propriedades canônicas e microcanônicas dos modelos. No caso dos algoritmos de amostragem uniforme, caracterizamos protocolos baseados na contagem de viagens de ida e volta que otimizam a determinação dos pesos de amostragem, e dessa maneira, aumentam a eficiência na obtenção da densidades de estados. Com relação ao uso de simulações canônicas implementadas com o REM, introduzimos o método ST-WHAM-MUCA como uma nova maneira de calcular a entropia microcanônica, associando o inverso da temperatura estatística obtida via ST-WHAM às equações de recorrência do algoritmo MUCA. A partir de simulações canônicas para os dois modelos estudados, mostramos que a termoestatística microcanônica obtida via ST-WHAM é equivalente àquela obtida pelo algoritmo MUCA, mesmo para a região onde ocorrem transições de fase de primeira ordem e uma não concavidade é observada na entropia microcanônica. Além dos estudos sobre a metodologia empregada na implementação dos algoritmos, realizamos contribuições para o entendimento da criticalidade nos modelos. Em particular, determinamos os aspectos críticos no modelo de Ising dipolar 2D para dois cenários distintos. Para o Cenário I, onde apenas uma transição entre as fases de faixas e tetragonal é observada, empregamos o algoritmo MUCA aliado à metodologia de obtenção dos zeros complexos da função de partição canônica. Nesse caso, foi possível determinar a natureza contínua da transição de fase faixas tetragonal, excluindo um possível ponto trícritico, como sugerido na literatura para a região h=1 do diagrama de fases. Para o Cenário II, o qual descreve uma região que apresenta duas transições de fase em decorrência do aparecimento de uma fase nemática entre as fases de faixas e tetragonal, mostramos que o algoritmo MUCA apresenta problemas mesmo para redes pequenas. Utilizando o algoritmo de Metropolis associado ao REM, realizamos simulações para uma rede de tamanho L=72. A partir da análise via ST-WHAM dessas simulações, obtivemos estimativas para o inverso da temperatura microcanônica, as quais sugerem que ambas transições de fase, faixas-nemática e nemática-tetragonal, sejam de primeira ordem, excluindo a possibilidade de uma transição de Kosterlitz-Thouless (KT). Também realizamos simulações utilizando o algoritmo de Metropolis associado ao REM para estudar a criticalidade em proteínas descritas por um modelo mínimo. Nesse estudo caracterizamos a termoestatística microcanônica das transições de enovelamento de quatro cadeias polipeptídicas com conhecida propensidade à formação de agregados. Nossos resultados sugerem que a ausência de barreiras na energia livre favorece a presença de conformações parcialmente desenoveladas, o que facilitaria a agregação das proteínas. Por fim, introduzimos o raio de giração hidrofóbico como parâmetro de ordem para a transição de enovelamento. Além de fornecer resultados condizentes com a descrição microcanônica, essa quantidade pode ser utilizada mesmo que não existam informações sobre o estado nativo. / Complex systems which present competitive interactions are ubiquitous in nature. Obtaining adequate descriptions of the thermodynamic properties of these systems is a major challenge to understand many chemical and physical processes. Analytical solutions in terms of Statistiscal Mechanics are extremely hard to obtain for these systems. Thus, in most cases numerical simulations become the only possible approach. In this Thesis we evaluate the performance of two categories of generalized Monte Carlo algorithms employed to determine the nature of phase transitions in two complex systems: the two-dimensional (2D) dipolar Ising model and a minimal model to describe proteins. In the first category, which represents serial algorithms, we include the multicanonical (MUCA) and entropic sampling (ES) algorithms, which are known as flat histogram algorithms. In the second category, which concerns parallelizable algorithms, we include the Metropolis algorithm associated with replica exchange method (REM). For both categories we introduce methodological contributions aiming the increase of efficiency in obtaining the canonical and microcanonical properties of the models. In case of flat histogram algorithms, we characterized protocols based on round trip counting to optimize the determination of the sampling weights, and therefore increasing the efficiency in obtaining the density of states. Regarding the use of canonical simulations implemented with REM, we introduce ST-WHAM-MUCA as a new method to evaluate the microcanonical entropy, associating the inverse of the statistical temperature obtained from ST-WHAM with the recursions equations of MUCA algorithm. From canonical simulations for both models, we show that the microcanonical thermostatistics obtained via ST-WHAM is equivalent to that obtained by MUCA algorithm, even for a region where a first order phase transition takes place and a non concavity is observed in the microcanonical entropy. In addition to the studies about the methodology employed in implementation of the algorithms, we present the contributions we make to understand the criticality in the models. In particular, we determined the critical aspects of the 2D dipolar Ising model for two different scenarios. For Scenario I, where only one transition is between the stripe and tetragonal phases is observed, we use MUCA algorithm associated with the analysis of the complex zeros from the canonical partition function. In this case, it was possible to determine the continuous character of the stripe-tetragonal phase transition, excluding the existente of a tricritical point, as suggested in the literature for the h=1 region in the phase diagram. For Scenario II, which describe a region that presents two phase transitions due to the appearance of a nematic phase between the stripe and tetragonal phases, we show that the MUCA algorithm present problems even for small lattices. Using the canonical Metropolis algorithm with REM, we run simulations for a lattice with size L=72. From ST-WHAM analysis of these simulations, we obtained estimates for the microcanonical inverse temperature, which suggests that both phase transitions, stripe-nematic and nematic tetragonal, are first order, excluding the possibility of a Kosterlitz-Thouless (KT) transition. We also performed simulations using the canonical Metropolis algorithm associated with the REM to study the criticality in proteins described by a minimal model. In this study we characterized the microcanonical thermostatistics of the folding transitions of four polypeptide chains with known propensity to form aggregates. Our results suggest that the absence of a free-energy barrier favors the presence of partial unfolded conformations, which could facilitate the aggregation of the proteins. Finally, we introduce the hydrophobic radius of gyration as an order parameter for the folding transition. In addition to provide consistent results with the microcanonical description, this quantity can be used even if there is no information about the native state.

Sistemas complexos que apresentam interações competitivas são ubíquos na natureza. Obter descrições adequadas das propriedades termodinâmicas desses sistemas é um desafio para o entendimento de uma série de processos químicos e físicos. Soluções analíticas em termos da Mecânica Estatística são extremamente difíceis de serem obtidas para esses sistemas. Isso faz com que o uso de simulações numéricas seja, na maioria dos casos, a única abordagem possível. Nesta Tese avaliamos o desempenho de duas classes de algoritmos de Monte Carlo generalizados empregados na determinação da natureza das transições de fase em dois sistemas complexos: o modelo de Ising dipolar bidimensional (2D) e um modelo mínimo para descrever proteínas. Na primeira classe, a qual representa os algoritmos seriais, incluimos os algoritmos multicanônico (MUCA) e de amostragem entrópica (ES), também conhecidos como algoritmos de amostragem uniforme. Na segunda classe, que diz respeito aos algoritmos paralelizáveis, incluimos o algoritmo canônico de Metropolis associado ao método de troca entre réplicas (REM). Para ambas as classes introduzimos contribuições metodológicas visando o aumento da eficiência na obtenção das propriedades canônicas e microcanônicas dos modelos. No caso dos algoritmos de amostragem uniforme, caracterizamos protocolos baseados na contagem de viagens de ida e volta que otimizam a determinação dos pesos de amostragem, e dessa maneira, aumentam a eficiência na obtenção da densidades de estados. Com relação ao uso de simulações canônicas implementadas com o REM, introduzimos o método ST-WHAM-MUCA como uma nova maneira de calcular a entropia microcanônica, associando o inverso da temperatura estatística obtida via ST-WHAM às equações de recorrência do algoritmo MUCA. A partir de simulações canônicas para os dois modelos estudados, mostramos que a termoestatística microcanônica obtida via ST-WHAM é equivalente àquela obtida pelo algoritmo MUCA, mesmo para a região onde ocorrem transições de fase de primeira ordem e uma não concavidade é observada na entropia microcanônica. Além dos estudos sobre a metodologia empregada na implementação dos algoritmos, realizamos contribuições para o entendimento da criticalidade nos modelos. Em particular, determinamos os aspectos críticos no modelo de Ising dipolar 2D para dois cenários distintos. Para o Cenário I, onde apenas uma transição entre as fases de faixas e tetragonal é observada, empregamos o algoritmo MUCA aliado à metodologia de obtenção dos zeros complexos da função de partição canônica. Nesse caso, foi possível determinar a natureza contínua da transição de fase faixas tetragonal, excluindo um possível ponto trícritico, como sugerido na literatura para a região h=1 do diagrama de fases. Para o Cenário II, o qual descreve uma região que apresenta duas transições de fase em decorrência do aparecimento de uma fase nemática entre as fases de faixas e tetragonal, mostramos que o algoritmo MUCA apresenta problemas mesmo para redes pequenas. Utilizando o algoritmo de Metropolis associado ao REM, realizamos simulações para uma rede de tamanho L=72. A partir da análise via ST-WHAM dessas simulações, obtivemos estimativas para o inverso da temperatura microcanônica, as quais sugerem que ambas transições de fase, faixas-nemática e nemática-tetragonal, sejam de primeira ordem, excluindo a possibilidade de uma transição de Kosterlitz-Thouless (KT). Também realizamos simulações utilizando o algoritmo de Metropolis associado ao REM para estudar a criticalidade em proteínas descritas por um modelo mínimo. Nesse estudo caracterizamos a termoestatística microcanônica das transições de enovelamento de quatro cadeias polipeptídicas com conhecida propensidade à formação de agregados. Nossos resultados sugerem que a ausência de barreiras na energia livre favorece a presença de conformações parcialmente desenoveladas, o que facilitaria a agregação das proteínas. Por fim, introduzimos o raio de giração hidrofóbico como parâmetro de ordem para a transição de enovelamento. Além de fornecer resultados condizentes com a descrição microcanônica, essa quantidade pode ser utilizada mesmo que não existam informações sobre o estado nativo. / Complex systems which present competitive interactions are ubiquitous in nature. Obtaining adequate descriptions of the thermodynamic properties of these systems is a major challenge to understand many chemical and physical processes. Analytical solutions in terms of Statistiscal Mechanics are extremely hard to obtain for these systems. Thus, in most cases numerical simulations become the only possible approach. In this Thesis we evaluate the performance of two categories of generalized Monte Carlo algorithms employed to determine the nature of phase transitions in two complex systems: the two-dimensional (2D) dipolar Ising model and a minimal model to describe proteins. In the first category, which represents serial algorithms, we include the multicanonical (MUCA) and entropic sampling (ES) algorithms, which are known as flat histogram algorithms. In the second category, which concerns parallelizable algorithms, we include the Metropolis algorithm associated with replica exchange method (REM). For both categories we introduce methodological contributions aiming the increase of efficiency in obtaining the canonical and microcanonical properties of the models. In case of flat histogram algorithms, we characterized protocols based on round trip counting to optimize the determination of the sampling weights, and therefore increasing the efficiency in obtaining the density of states. Regarding the use of canonical simulations implemented with REM, we introduce ST-WHAM-MUCA as a new method to evaluate the microcanonical entropy, associating the inverse of the statistical temperature obtained from ST-WHAM with the recursions equations of MUCA algorithm. From canonical simulations for both models, we show that the microcanonical thermostatistics obtained via ST-WHAM is equivalent to that obtained by MUCA algorithm, even for a region where a first order phase transition takes place and a non concavity is observed in the microcanonical entropy. In addition to the studies about the methodology employed in implementation of the algorithms, we present the contributions we make to understand the criticality in the models. In particular, we determined the critical aspects of the 2D dipolar Ising model for two different scenarios. For Scenario I, where only one transition is between the stripe and tetragonal phases is observed, we use MUCA algorithm associated with the analysis of the complex zeros from the canonical partition function. In this case, it was possible to determine the continuous character of the stripe-tetragonal phase transition, excluding the existente of a tricritical point, as suggested in the literature for the h=1 region in the phase diagram. For Scenario II, which describe a region that presents two phase transitions due to the appearance of a nematic phase between the stripe and tetragonal phases, we show that the MUCA algorithm present problems even for small lattices. Using the canonical Metropolis algorithm with REM, we run simulations for a lattice with size L=72. From ST-WHAM analysis of these simulations, we obtained estimates for the microcanonical inverse temperature, which suggests that both phase transitions, stripe-nematic and nematic tetragonal, are first order, excluding the possibility of a Kosterlitz-Thouless (KT) transition. We also performed simulations using the canonical Metropolis algorithm associated with the REM to study the criticality in proteins described by a minimal model. In this study we characterized the microcanonical thermostatistics of the folding transitions of four polypeptide chains with known propensity to form aggregates. Our results suggest that the absence of a free-energy barrier favors the presence of partial unfolded conformations, which could facilitate the aggregation of the proteins. Finally, we introduce the hydrophobic radius of gyration as an order parameter for the folding transition. In addition to provide consistent results with the microcanonical description, this quantity can be used even if there is no information about the native state.

In the wake of the Big Data phenomenon, the computing world has seen a number of computational paradigms developed in response to the sudden need to process ever-increasing volumes of data. Most notably, MapReduce has proven quite successful in scaling out an extensible class of simple algorithms to even hundreds of thousands of nodes. However, there are some tasks---even embarrassingly parallelizable ones---that neither MapReduce nor any existing automated parallelization framework is well-equipped to perform. For instance, any computation that (naively) requires consideration of all pairs of inputs becomes prohibitively expensive even when parallelized over a large number of worker nodes. Many of the most desirable methods in machine learning and statistics exhibit these kinds of all-pairs or, more generally, all-tuples computations; accordingly, their application in the Big Data setting may seem beyond hope. However, a new algorithmic strategy inspired by breakthroughs in computational physics has shown great promise for a wide class of computations dubbed generalized N-body problems (GNBPs). This strategy, which involves the simultaneous traversal of multiple space-partitioning trees, has been applied to a succession of well-known learning methods, accelerating each asymptotically and by orders of magnitude. Examples of these include all-k-nearest-neighbors search, k-nearest-neighbors classification, k-means clustering, EM for mixtures of Gaussians, kernel density estimation, kernel discriminant analysis, kernel machines, particle filters, the n-point correlation, and many others. For each of these problems, no overall faster algorithms are known. Further, these dual- and multi-tree algorithms compute either exact results or approximations to within specified error bounds, a rarity amongst fast methods. This dissertation aims to unify a family of GNBPs under a common framework in order to ease implementation and future study. We start by formalizing the problem class and then describe a general algorithm, the generalized fast multipole method (GFMM), capable of solving all problems that fit the class, though with varying degrees of speedup. We then show O(N) and O(log N) theoretical run-time bounds that may be obtained under certain conditions. As a corollary, we derive the tightest known general-dimensional run-time bounds for exact all-nearest-neighbors and several approximated kernel summations. Next, we implement a number of these algorithms in a commercial database, empirically demonstrating dramatic asymptotic speedup over their conventional SQL implementations. Lastly, we implement a fast, parallelized algorithm for kernel discriminant analysis and apply it to a large dataset (40 million points in 4D) from the Sloan Digital Sky Survey, identifying approximately one million quasars with high accuracy. This exceeds the previous largest catalog of quasars in size by a factor of ten and has since been used in a follow-up study to confirm the existence of dark energy.