Introduction to MLML_DBASE Programs

The MLML DBASE family of programs described here provides many of the. algorithms used in oceanographic data reduction, general data manipulation and line graphs. These programs provide a consistent file structure for serial data typically encountered in oceanography. This introduction should provide enough general knowledge to explain the scope of the program and to run the basic MLML_DBASE programs. It is not intended as a programmer's guide. (PDF contains 50 pages)

Processing NOAA Spectroradiometric Data

This report outlines the NOAA spectroradiometer data processing system implemented by the MLML_DBASE programs. This is done by presenting the algorithms and graphs showing the effects of each step in the algorithms. [PDF contains 32 pages]

AUTOROTATION OF TWO TANDEM TRIANGULAR CYLINDERS

The autorotation of two tandem triangular cylinders at different gap distances is investigated by numerical simulations. At the Reynolds number of 200， three distinct regimes are observed with the increase of gap distance: namely, angular oscillation, quasi-periodic autorotation and ‘chaotic’ autorotation. For various gap distances, the characteristic of vortex shedding and vortex interaction are discussed. The phase graphs (angular acceleration vs. angular velocity) and the power spectra of moment are analyzed to characterize the motion of the cylinder. The Lyapunov exponent is also calculated to identify the existence of chaos.

Efficient learning of decomposable models with a bounded clique size

The learning of probability distributions from data is a ubiquitous problem in the fields of Statistics and Artificial Intelligence. During the last decades several learning algorithms have been proposed to learn probability distributions based on decomposable models due to their advantageous theoretical properties. Some of these algorithms can be used to search for a maximum likelihood decomposable model with a given maximum clique size, k, which controls the complexity of the model. Unfortunately, the problem of learning a maximum likelihood decomposable model given a maximum clique size is NP-hard for k > 2. In this work, we propose a family of algorithms which approximates this problem with a computational complexity of O(k · n^2 log n) in the worst case, where n is the number of implied random variables. The structures of the decomposable models that solve the maximum likelihood problem are called maximal k-order decomposable graphs. Our proposals, called fractal trees, construct a sequence of maximal i-order decomposable graphs, for i = 2, ..., k, in k − 1 steps. At each step, the algorithms follow a divide-and-conquer strategy based on the particular features of this type of structures. Additionally, we propose a prune-and-graft procedure which transforms a maximal k-order decomposable graph into another one, increasing its likelihood. We have implemented two particular fractal tree algorithms called parallel fractal tree and sequential fractal tree. These algorithms can be considered a natural extension of Chow and Liu’s algorithm, from k = 2 to arbitrary values of k. Both algorithms have been compared against other efficient approaches in artificial and real domains, and they have shown a competitive behavior to deal with the maximum likelihood problem. Due to their low computational complexity they are especially recommended to deal with high dimensional domains.

Extending Distance-based Ranking Models In Estimation of Distribution Algorithms

Recently, probability models on rankings have been proposed in the field of estimation of distribution algorithms in order to solve permutation-based combinatorial optimisation problems. Particularly, distance-based ranking models, such as Mallows and Generalized Mallows under the Kendall’s-t distance, have demonstrated their validity when solving this type of problems. Nevertheless, there are still many trends that deserve further study. In this paper, we extend the use of distance-based ranking models in the framework of EDAs by introducing new distance metrics such as Cayley and Ulam. In order to analyse the performance of the Mallows and Generalized Mallows EDAs under the Kendall, Cayley and Ulam distances, we run them on a benchmark of 120 instances from four well known permutation problems. The conducted experiments showed that there is not just one metric that performs the best in all the problems. However, the statistical test pointed out that Mallows-Ulam EDA is the most stable algorithm among the studied proposals.

Fisheries statistical bulletin, Kainji Lake, Nigeria, 1998

A tabulated summary is presented of the main fisheries data collected to date (1998) by the Nigerian-German Kainji Lake Fisheries Promotion Project, together with a current overview of the fishery. The data are given under the following sections: 1) Fishing localities and types; 2) Frame survey data; 3) Number of licensed fishermen by state; 4) Mesh size distribution; 5) Fishing net characteristics; 6) Fish yield; 7) Total annual fishing effort by gear type; 8) Total annual value of fish landed by gear type; 9) Graphs of effort and CPUE by gear type. (PDF contains 36 pages)

Mathematical study of complex networks : brain, internet, and power grid

The dissertation is concerned with the mathematical study of various network problems. First, three real-world networks are considered: (i) the human brain network (ii) communication networks, (iii) electric power networks. Although these networks perform very different tasks, they share similar mathematical foundations. The high-level goal is to analyze and/or synthesis each of these systems from a “control and optimization” point of view. After studying these three real-world networks, two abstract network problems are also explored, which are motivated by power systems. The first one is “flow optimization over a flow network” and the second one is “nonlinear optimization over a generalized weighted graph”. The results derived in this dissertation are summarized below.

Brain Networks: Neuroimaging data reveals the coordinated activity of spatially distinct brain regions, which may be represented mathematically as a network of nodes (brain regions) and links (interdependencies). To obtain the brain connectivity network, the graphs associated with the correlation matrix and the inverse covariance matrix—describing marginal and conditional dependencies between brain regions—have been proposed in the literature. A question arises as to whether any of these graphs provides useful information about the brain connectivity. Due to the electrical properties of the brain, this problem will be investigated in the context of electrical circuits. First, we consider an electric circuit model and show that the inverse covariance matrix of the node voltages reveals the topology of the circuit. Second, we study the problem of finding the topology of the circuit based on only measurement. In this case, by assuming that the circuit is hidden inside a black box and only the nodal signals are available for measurement, the aim is to find the topology of the circuit when a limited number of samples are available. For this purpose, we deploy the graphical lasso technique to estimate a sparse inverse covariance matrix. It is shown that the graphical lasso may find most of the circuit topology if the exact covariance matrix is well-conditioned. However, it may fail to work well when this matrix is ill-conditioned. To deal with ill-conditioned matrices, we propose a small modification to the graphical lasso algorithm and demonstrate its performance. Finally, the technique developed in this work will be applied to the resting-state fMRI data of a number of healthy subjects.

Communication Networks: Congestion control techniques aim to adjust the transmission rates of competing users in the Internet in such a way that the network resources are shared efficiently. Despite the progress in the analysis and synthesis of the Internet congestion control, almost all existing fluid models of congestion control assume that every link in the path of a flow observes the original source rate. To address this issue, a more accurate model is derived in this work for the behavior of the network under an arbitrary congestion controller, which takes into account of the effect of buffering (queueing) on data flows. Using this model, it is proved that the well-known Internet congestion control algorithms may no longer be stable for the common pricing schemes, unless a sufficient condition is satisfied. It is also shown that these algorithms are guaranteed to be stable if a new pricing mechanism is used.

Electrical Power Networks: Optimal power flow (OPF) has been one of the most studied problems for power systems since its introduction by Carpentier in 1962. This problem is concerned with finding an optimal operating point of a power network minimizing the total power generation cost subject to network and physical constraints. It is well known that OPF is computationally hard to solve due to the nonlinear interrelation among the optimization variables. The objective is to identify a large class of networks over which every OPF problem can be solved in polynomial time. To this end, a convex relaxation is proposed, which solves the OPF problem exactly for every radial network and every meshed network with a sufficient number of phase shifters, provided power over-delivery is allowed. The concept of “power over-delivery” is equivalent to relaxing the power balance equations to inequality constraints.

Flow Networks: In this part of the dissertation, the minimum-cost flow problem over an arbitrary flow network is considered. In this problem, each node is associated with some possibly unknown injection, each line has two unknown flows at its ends related to each other via a nonlinear function, and all injections and flows need to satisfy certain box constraints. This problem, named generalized network flow (GNF), is highly non-convex due to its nonlinear equality constraints. Under the assumption of monotonicity and convexity of the flow and cost functions, a convex relaxation is proposed, which always finds the optimal injections. A primary application of this work is in the OPF problem. The results of this work on GNF prove that the relaxation on power balance equations (i.e., load over-delivery) is not needed in practice under a very mild angle assumption.

Generalized Weighted Graphs: Motivated by power optimizations, this part aims to find a global optimization technique for a nonlinear optimization defined over a generalized weighted graph. Every edge of this type of graph is associated with a weight set corresponding to the known parameters of the optimization (e.g., the coefficients). The motivation behind this problem is to investigate how the (hidden) structure of a given real/complex valued optimization makes the problem easy to solve, and indeed the generalized weighted graph is introduced to capture the structure of an optimization. Various sufficient conditions are derived, which relate the polynomial-time solvability of different classes of optimization problems to weak properties of the generalized weighted graph such as its topology and the sign definiteness of its weight sets. As an application, it is proved that a broad class of real and complex optimizations over power networks are polynomial-time solvable due to the passivity of transmission lines and transformers.

Diagonal forms, linear algebraic methods and Ramsey-type problems

This thesis focuses mainly on linear algebraic aspects of combinatorics. Let N_t(H) be an incidence matrix with edges versus all subhypergraphs of a complete hypergraph that are isomorphic to H. Richard M. Wilson and the author find the general formula for the Smith normal form or diagonal form of N_t(H) for all simple graphs H and for a very general class of t-uniform hypergraphs H.

As a continuation, the author determines the formula for diagonal forms of integer matrices obtained from other combinatorial structures, including incidence matrices for subgraphs of a complete bipartite graph and inclusion matrices for multisets.

One major application of diagonal forms is in zero-sum Ramsey theory. For instance, Caro's results in zero-sum Ramsey numbers for graphs and Caro and Yuster's results in zero-sum bipartite Ramsey numbers can be reproduced. These results are further generalized to t-uniform hypergraphs. Other applications include signed bipartite graph designs.

Research results on some other problems are also included in this thesis, such as a Ramsey-type problem on equipartitions, Hartman's conjecture on large sets of designs and a matroid theory problem proposed by Welsh.

Completions of epsilon-dense partial Latin squares

A classical question in combinatorics is the following: given a partial Latin square $P$, when can we complete $P$ to a Latin square $L$? In this paper, we investigate the class of textbf{$epsilon$-dense partial Latin squares}: partial Latin squares in which each symbol, row, and column contains no more than $epsilon n$-many nonblank cells. Based on a conjecture of Nash-Williams, Daykin and H"aggkvist conjectured that all $frac{1}{4}$-dense partial Latin squares are completable. In this paper, we will discuss the proof methods and results used in previous attempts to resolve this conjecture, introduce a novel technique derived from a paper by Jacobson and Matthews on generating random Latin squares, and use this novel technique to study $ epsilon$-dense partial Latin squares that contain no more than $delta n^2$ filled cells in total.

In Chapter 2, we construct completions for all $ epsilon$-dense partial Latin squares containing no more than $delta n^2$ filled cells in total, given that $epsilon < frac{1}{12}, delta < frac{ left(1-12epsilonright)^{2}}{10409}$. In particular, we show that all $9.8 cdot 10^{-5}$-dense partial Latin squares are completable. In Chapter 4, we augment these results by roughly a factor of two using some probabilistic techniques. These results improve prior work by Gustavsson, which required $epsilon = delta leq 10^{-7}$, as well as Chetwynd and H"aggkvist, which required $epsilon = delta = 10^{-5}$, $n$ even and greater than $10^7$.

If we omit the probabilistic techniques noted above, we further show that such completions can always be found in polynomial time. This contrasts a result of Colbourn, which states that completing arbitrary partial Latin squares is an NP-complete task. In Chapter 3, we strengthen Colbourn's result to the claim that completing an arbitrary $left(frac{1}{2} + epsilonright)$-dense partial Latin square is NP-complete, for any $epsilon > 0$.

Colbourn's result hinges heavily on a connection between triangulations of tripartite graphs and Latin squares. Motivated by this, we use our results on Latin squares to prove that any tripartite graph $G = (V_1, V_2, V_3)$ such that begin{itemize} item $|V_1| = |V_2| = |V_3| = n$, item For every vertex $v in V_i$, $deg_+(v) = deg_-(v) geq (1- epsilon)n,$ and item $|E(G)| > (1 - delta)cdot 3n^2$ end{itemize} admits a triangulation, if $epsilon < frac{1}{132}$, $delta < frac{(1 -132epsilon)^2 }{83272}$. In particular, this holds when $epsilon = delta=1.197 cdot 10^{-5}$.

This strengthens results of Gustavsson, which requires $epsilon = delta = 10^{-7}$.

In an unrelated vein, Chapter 6 explores the class of textbf{quasirandom graphs}, a notion first introduced by Chung, Graham and Wilson cite{chung1989quasi} in 1989. Roughly speaking, a sequence of graphs is called "quasirandom"' if it has a number of properties possessed by the random graph, all of which turn out to be equivalent. In this chapter, we study possible extensions of these results to random $k$-edge colorings, and create an analogue of Chung, Graham and Wilson's result for such colorings.

Convex Relaxation for Low-Dimensional Representation: Phase Transitions and Limitations

There is a growing interest in taking advantage of possible patterns and structures in data so as to extract the desired information and overcome the curse of dimensionality. In a wide range of applications, including computer vision, machine learning, medical imaging, and social networks, the signal that gives rise to the observations can be modeled to be approximately sparse and exploiting this fact can be very beneficial. This has led to an immense interest in the problem of efficiently reconstructing a sparse signal from limited linear observations. More recently, low-rank approximation techniques have become prominent tools to approach problems arising in machine learning, system identification and quantum tomography.

In sparse and low-rank estimation problems, the challenge is the inherent intractability of the objective function, and one needs efficient methods to capture the low-dimensionality of these models. Convex optimization is often a promising tool to attack such problems. An intractable problem with a combinatorial objective can often be "relaxed" to obtain a tractable but almost as powerful convex optimization problem. This dissertation studies convex optimization techniques that can take advantage of low-dimensional representations of the underlying high-dimensional data. We provide provable guarantees that ensure that the proposed algorithms will succeed under reasonable conditions, and answer questions of the following flavor:

More specifically, i) Focusing on linear inverse problems, we generalize the classical error bounds known for the least-squares technique to the lasso formulation, which incorporates the signal model. ii) We show that intuitive convex approaches do not perform as well as expected when it comes to signals that have multiple low-dimensional structures simultaneously. iii) Finally, we propose convex relaxations for the graph clustering problem and give sharp performance guarantees for a family of graphs arising from the so-called stochastic block model. We pay particular attention to the following aspects. For i) and ii), we aim to provide a general geometric framework, in which the results on sparse and low-rank estimation can be obtained as special cases. For i) and iii), we investigate the precise performance characterization, which yields the right constants in our bounds and the true dependence between the problem parameters.

Herramienta software para el análisis de rendimiento de redes 4G

[ES]El objetivo de este proyecto ha sido desarrollar una herramienta software que permita medir el rendimiento de redes con tecnología móvil 4G, también conocida como LTE. Para ello se ha creado un sistema software que está compuesto por una aplicación móvil y un servidor de aplicaciones. El sistema en conjunto realiza la función de recoger indicadores de calidad de la red móvil de diversa índole, que posteriormente son procesados utilizando herramientas software matemáticas, para así obtener gráficas y mapas que permiten analizar la situación y el rendimiento de una red 4G concreta. El desarrollo del software ha llegado a nivel de prototipo y se han realizado pruebas reales con él obteniendo resultados positivos de funcionamiento.

Atlas digital: uma contribuição para o sistema de informação do município de São João de Meriti-RJ

Um Atlas Digital é um atlas que foi concebido através de técnicas computacionais e que, consequentemente, pode ser acessado através de um computador. Estruturado em um ambiente gráfico, além dos mapas, pode-se contar também com textos, fotografias, dados estatísticos, gráficos e tabelas. Por estar em meio digital existe a possibilidade de utilização de uma expressiva gama de temas, formatos e escalas. Nesta dissertação apresenta-se um protótipo de Atlas Digital como uma colaboração ao Sistema de Informação Municipal SIM, para o município de São João de Meriti, RJ. O referido SIM, que tem como meta os serviços municipais, visa atender ao próprio município, ao cidadão e a outros interessados na cidade, sendo as suas informações fundamentais para a melhoria da gestão das prefeituras. A pesquisa foi direcionada para o tema da habitabilidade, que consiste num conjunto de condições voltadas para a construção de habitat saudável, abrangendo temas físicos, psicológicos, sociais, culturais e ambientais. Dentro do tema habitabilidade, foram trabalhados os subtemas relativos a infraestrutura de abastecimento de água, esgoto, coleta de lixo, saúde e educação, esses subtemas foram confrontados entre si para uma comparação entre os bairros do município. O SIM e a habitabilidade são contemplados no plano diretor da cidade e representa uma grande parte da sustentação teórica da dissertação. A modelagem e implementação do protótipo do Atlas Digital foram feitas com auxílio de softwares gratuitos, sendo possível acessar mapas temáticos e outras informações sobre São João de Meriti

Estimativa do erro de discretização analítico na solução de equações diferenciais utilizando o Método de Volumes Finitos

As análises de erros são conduzidas antes de qualquer projeto a ser desenvolvido. A necessidade do conhecimento do comportamento do erro numérico em malhas estruturadas e não-estruturadas surge com o aumento do uso destas malhas nos métodos de discretização. Desta forma, o objetivo deste trabalho foi criar uma metodologia para analisar os erros de discretização gerados através do truncamento na Série de Taylor, aplicados às equações de Poisson e de Advecção-Difusão estacionárias uni e bidimensionais, utilizando-se o Método de Volumes Finitos em malhas do tipo Voronoi. A escolha dessas equações se dá devido a sua grande utilização em testes de novos modelos matemáticos e função de interpolação. Foram usados os esquemas Central Difference Scheme (CDS) e Upwind Difference Scheme(UDS) nos termos advectivos. Verificou-se a influência do tipo de condição de contorno e a posição do ponto gerador do volume na solução numérica. Os resultados analíticos foram confrontados com resultados experimentais para dois tipos de malhas de Voronoi, uma malha cartesiana e outra triangular comprovando a influência da forma do volume finito na solução numérica obtida. Foi percebido no estudo que a discretização usando o esquema CDS tem erros menores do que a discretização usando o esquema UDS conforme literatura. Também se percebe a diferença nos erros em volumes vizinhos nas malhas triangulares o que faz com que não se tenha uma uniformidade nos gráficos dos erros estudados. Percebeu-se que as malhas cartesianas com nó no centróide do volume tem menor erro de discretização do que malhas triangulares. Mas o uso deste tipo de malha depende da geometria do problema estudado

Análise comparativa dos modelos de cálculo dos retornos anormais utilizando o evento recompra de ações na Bovespa

Este trabalho tem por objetivo verificar se há diferença quanto ao nível de significância estatística no cálculo do retorno anormal realizado através de quatro modelos estatísticos utilizados em estudos de eventos, tendo como objeto de estudo empresas no mercado de ações no Brasil durante o período de março de 2003 até julho de 2010 na Bovespa. Considerando a importância do cálculo do retorno anormal nos estudos de eventos, bem como possíveis variações de resultados decorrentes da escolha do modelo de cálculo, este estudo utiliza um tema bastante conhecido, qual seja, o anúncio de recompra de ações feito pela própria companhia emissora dos títulos. A metodologia utilizada nesta pesquisa foi quantitativa, utilizando o estudo de corte transversal. Os resultados apontam que há diferença entre os níveis de significância encontrados. Ao analisar o gráfico dos modelos calculados no período da janela do evento, verificou-se que as empresas que recompraram ações a fizeram quando os papéis estavam com retorno anormal acumulado negativo e, após a recompra, os papéis tiveram retornos anormais acumulados positivos. Recalculou-se os dois modelos que utilizam o Ibovespa em sua fórmula de cálculo, através de um Ibovespa sem ponderação e conclui-se que os resultados apontam na direção de se evitar o uso de índices ponderados de mercado, preferindo a utilização de carteiras compostas apenas com uma ação para cada empresa componente da carteira de controle. Após este recálculo, verificou-se que o modelo que era menos próximo dos demais graficamente era o modelo de retorno ajustado ao mercado ponderado. Por fim, as evidências empíricas indicam que o mercado de capitais brasileiro ajusta tempestivamente os papéis das empresas que realizaram recompra de ações, em linha com o que prescreve a hipótese do mercado eficiente na sua forma semiforte.

Treewidth: theory and applications to computer science

This report is an introduction to the concept of treewidth, a property of graphs that has important implications in algorithms. Some basic concepts of graph theory are presented in the first chapter for those readers that are not familiar with the notation. In Chapter 2, the definition of treewidth and some different ways of characterizing it are explained. The last two chapters focus on the algorithmic implications of treewidth, which are very relevant in Computer Science. An algorithm to compute the treewidth of a graph is presented and its result can be later applied to many other problems in graph theory, like those introduced in the last chapter.