Algebraic Techniques in Coding Theory: Entropy Vectors, Frames, and Constrained Coding

The study of codes, classically motivated by the need to communicate information reliably in the presence of error, has found new life in fields as diverse as network communication, distributed storage of data, and even has connections to the design of linear measurements used in compressive sensing. But in all contexts, a code typically involves exploiting the algebraic or geometric structure underlying an application. In this thesis, we examine several problems in coding theory, and try to gain some insight into the algebraic structure behind them.

The first is the study of the entropy region - the space of all possible vectors of joint entropies which can arise from a set of discrete random variables. Understanding this region is essentially the key to optimizing network codes for a given network. To this end, we employ a group-theoretic method of constructing random variables producing so-called "group-characterizable" entropy vectors, which are capable of approximating any point in the entropy region. We show how small groups can be used to produce entropy vectors which violate the Ingleton inequality, a fundamental bound on entropy vectors arising from the random variables involved in linear network codes. We discuss the suitability of these groups to design codes for networks which could potentially outperform linear coding.

The second topic we discuss is the design of frames with low coherence, closely related to finding spherical codes in which the codewords are unit vectors spaced out around the unit sphere so as to minimize the magnitudes of their mutual inner products. We show how to build frames by selecting a cleverly chosen set of representations of a finite group to produce a "group code" as described by Slepian decades ago. We go on to reinterpret our method as selecting a subset of rows of a group Fourier matrix, allowing us to study and bound our frames' coherences using character theory. We discuss the usefulness of our frames in sparse signal recovery using linear measurements.

The final problem we investigate is that of coding with constraints, most recently motivated by the demand for ways to encode large amounts of data using error-correcting codes so that any small loss can be recovered from a small set of surviving data. Most often, this involves using a systematic linear error-correcting code in which each parity symbol is constrained to be a function of some subset of the message symbols. We derive bounds on the minimum distance of such a code based on its constraints, and characterize when these bounds can be achieved using subcodes of Reed-Solomon codes.

Optimum linear coding for additive noise systems using information feedback

The feedback coding problem for Gaussian systems in which the noise is neither white nor statistically independent between channels is formulated in terms of arbitrary linear codes at the transmitter and at the receiver. This new formulation is used to determine a number of feedback communication systems. In particular, the optimum linear code that satisfies an average power constraint on the transmitted signals is derived for a system with noiseless feedback and forward noise of arbitrary covariance. The noisy feedback problem is considered and signal sets for the forward and feedback channels are obtained with an average power constraint on each. The general formulation and results are valid for non-Gaussian systems in which the second order statistics are known, the results being applicable to the determination of error bounds via the Chebychev inequality.

Some properties of the coefficients of cyclotomic polynomials

An explicit formula is obtained for the coefficients of the cyclotomic polynomial F_n(x), where n is the product of two distinct odd primes. A recursion formula and a lower bound and an improvement of Bang’s upper bound for the coefficients of F_n(x) are also obtained, where n is the product of three distinct primes. The cyclotomic coefficients are also studied when n is the product of four distinct odd primes. A recursion formula and upper bounds for its coefficients are obtained. The last chapter includes a different approach to the cyclotomic coefficients. A connection is obtained between a certain partition function and the cyclotomic coefficients when n is the product of an arbitrary number of distinct odd primes. Finally, an upper bound for the coefficients is derived when n is the product of an arbitrary number of distinct and odd primes.

Resolução numérica de escoamentos compressíveis empregando um método de partículas livre de malhas e o processamento em paralelo (CUDA)

Os métodos numéricos convencionais, baseados em malhas, têm sido amplamente aplicados na resolução de problemas da Dinâmica dos Fluidos Computacional. Entretanto, em problemas de escoamento de fluidos que envolvem superfícies livres, grandes explosões, grandes deformações, descontinuidades, ondas de choque etc., estes métodos podem apresentar algumas dificuldades práticas quando da resolução destes problemas. Como uma alternativa viável, existem os métodos de partículas livre de malhas. Neste trabalho é feita uma introdução ao método Lagrangeano de partículas, livre de malhas, Smoothed Particle Hydrodynamics (SPH) voltado para a simulação numérica de escoamentos de fluidos newtonianos compressíveis e quase-incompressíveis. Dois códigos numéricos foram desenvolvidos, uma versão serial e outra em paralelo, empregando a linguagem de programação C/C++ e a Compute Unified Device Architecture (CUDA), que possibilita o processamento em paralelo empregando os núcleos das Graphics Processing Units (GPUs) das placas de vídeo da NVIDIA Corporation. Os resultados numéricos foram validados e a eficiência computacional avaliada considerandose a resolução dos problemas unidimensionais Shock Tube e Blast Wave e bidimensional da Cavidade (Shear Driven Cavity Problem).

Relativistic velocity - potential hydrodynamics and stellar stability

The equations of relativistic, perfect-fluid hydrodynamics are cast in Eulerian form using six scalar "velocity-potential" fields, each of which has an equation of evolution. These equations determine the motion of the fluid through the equation

U_ʋ=µ^-1 (ø,_ʋ + αβ,_ʋ + ƟS,_ʋ).

Einstein's equations and the velocity-potential hydrodynamical equations follow from a variational principle whose action is

I = (R + 16π p) (-g)^1/2 d⁴x,

where R is the scalar curvature of spacetime and p is the pressure of the fluid. These equations are also cast into Hamiltonian form, with Hamiltonian density –T₀⁰ (-g^oo)^-1/2.

The second variation of the action is used as the Lagrangian governing the evolution of small perturbations of differentially rotating stellar models. In Newtonian gravity this leads to linear dynamical stability criteria already known. In general relativity it leads to a new sufficient condition for the stability of such models against arbitrary perturbations.

By introducing three scalar fields defined by

ρ ᵴ = ∇λ + ∇x(xi + ∇xɣi)

(where ᵴ is the vector displacement of the perturbed fluid element, ρ is the mass-density, and i, is an arbitrary vector), the Newtonian stability criteria are greatly simplified for the purpose of practical applications. The relativistic stability criterion is not yet in a form that permits practical calculations, but ways to place it in such a form are discussed.

On the Lyapunov transformation for stable matrices

The matrices studied here are positive stable (or briefly stable). These are matrices, real or complex, whose eigenvalues have positive real parts. A theorem of Lyapunov states that A is stable if and only if there exists H ˃ 0 such that AH + HA* = I. Let A be a stable matrix. Three aspects of the Lyapunov transformation L_A :H → AH + HA* are discussed.

1. Let C₁ (A) = {AH + HA* :H ≥ 0} and C₂ (A) = {H: AH+HA* ≥ 0}. The problems of determining the cones C₁(A) and C₂(A) are still unsolved. Using solvability theory for linear equations over cones it is proved that C₁(A) is the polar of C₂(A*), and it is also shown that C₁ (A) = C₁(A^-1). The inertia assumed by matrices in C₁(A) is characterized.

2. The index of dissipation of A was defined to be the maximum number of equal eigenvalues of H, where H runs through all matrices in the interior of C₂(A). Upper and lower bounds, as well as some properties of this index, are given.

3. We consider the minimal eigenvalue of the Lyapunov transform AH+HA*, where H varies over the set of all positive semi-definite matrices whose largest eigenvalue is less than or equal to one. Denote it by ψ(A). It is proved that if A is Hermitian and has eigenvalues μ₁ ≥ μ₂…≥ μ_n ˃ 0, then ψ(A) = -(μ₁-μ_n)²/(4(μ₁ + μ_n)). The value of ψ(A) is also determined in case A is a normal, stable matrix. Then ψ(A) can be expressed in terms of at most three of the eigenvalues of A. If A is an arbitrary stable matrix, then upper and lower bounds for ψ(A) are obtained.

Desenvolvimento de um simulador numérico empregando o método Smoothed Particle Hydrodynamics para a resolução de escoamentos incompressíveis. Implementação computacional em paralelo (CUDA)

Neste trabalho, foi desenvolvido um simulador numérico baseado no método livre de malhas Smoothed Particle Hydrodynamics (SPH) para a resolução de escoamentos de fluidos newtonianos incompressíveis. Diferentemente da maioria das versões existentes deste método, o código numérico faz uso de uma técnica iterativa na determinação do campo de pressões. Este procedimento emprega a forma diferencial de uma equação de estado para um fluido compressível e a equação da continuidade a fim de que a correção da pressão seja determinada. Uma versão paralelizada do simulador numérico foi implementada usando a linguagem de programação C/C++ e a Compute Unified Device Architecture (CUDA) da NVIDIA Corporation. Foram simulados três problemas, o problema unidimensional do escoamento de Couette e os problemas bidimensionais do escoamento no interior de uma Cavidade (Shear Driven Cavity Problem) e da Quebra de Barragem (Dambreak).

Mafalda na aula de História: a crítica aos elementos característicos da sociedade burguesa e a construção coletiva de sentidos contra-hegemônicos

A partir da leitura crítica de Mafalda, obra do cartunista argentino Quino, e alicerçados no conceito de hegemonia de Gramsci, sobretudo na noção de contra-hegemonia, buscamos analisar as possibilidades de se construir coletivamente sentidos contra-hegemônicos no ensino de História a partir do que chamamos de crítica aos elementos característicos da sociedade burguesa (a democracia, o individualismo, o estímulo ao consumo, a propriedade privada, a naturalização das diferenças, a competição, dentre outros). As contribuições de Gramsci ao campo da Educação, como o vínculo dialético entre as relações hegemônicas e pedagógicas, sua concepção da escola como um destacado aparelho privado de hegemonia, além das reflexões sobre os intelectuais e sua ação pedagógica na construção/difusão/legitimação de consensos, constituem pilares fundamentais das análises. É esforço fundamental da pesquisa identificar em que medida os professores, conscientes de seus vínculos de classe e compromissados com as classes dominadas, podem atuar como educadores-intelectuais orgânicos à estas classes, no âmbito da escola, tornando-a uma trincheira sob o conceito gramsciano de guerra de posição contra a hegemonia burguesa. Em termos metodológicos, foram selecionadas quinze tiras de Mafalda (divididas em onze temas os elementos que caracterizam a sociedade burguesa), presentes na obra Toda Mafalda (2002), no intuito de subsidiar as reflexões aqui esboçadas. Obviamente, todo recorte é ideológico e nenhuma escolha é neutra. As tiras escolhidas, longe de sintetizarem o olhar do artista argentino a respeito da burguesia, atendem aos objetivos deste trabalho.

Simulação de escoamentos incompressíveis empregando o método Smoothed Particle Hydrodynamics utilizando algoritmos iterativos na determinação do campo de pressões

Nesse trabalho, foi desenvolvido um simulador numérico (C/C++) para a resolução de escoamentos de fluidos newtonianos incompressíveis, baseado no método de partículas Lagrangiano, livre de malhas, Smoothed Particle Hydrodynamics (SPH). Tradicionalmente, duas estratégias são utilizadas na determinação do campo de pressões de forma a garantir-se a condição de incompressibilidade do fluido. A primeira delas é a formulação chamada Weak Compressible Smoothed Particle Hydrodynamics (WCSPH), onde uma equação de estado para um fluido quase-incompressível é utilizada na determinação do campo de pressões. A segunda, emprega o Método da Projeção e o campo de pressões é obtido mediante a resolução de uma equação de Poisson. No estudo aqui desenvolvido, propõe-se três métodos iterativos, baseados noMétodo da Projeção, para o cálculo do campo de pressões, Incompressible Smoothed Particle Hydrodynamics (ISPH). A fim de validar os métodos iterativos e o código computacional, foram simulados dois problemas unidimensionais: os escoamentos de Couette entre duas placas planas paralelas infinitas e de Poiseuille em um duto infinito e foram usadas condições de contorno do tipo periódicas e partículas fantasmas. Um problema bidimensional, o escoamento no interior de uma cavidade com a parede superior posta em movimento, também foi considerado. Na resolução deste problema foi utilizado o reposicionamento periódico de partículas e partículas fantasmas.

Quantum Simulation of Dissipative Processes without Reservoir Engineering

We present a quantum algorithm to simulate general finite dimensional Lindblad master equations without the requirement of engineering the system-environment interactions. The proposed method is able to simulate both Markovian and non-Markovian quantum dynamics. It consists in the quantum computation of the dissipative corrections to the unitary evolution of the system of interest, via the reconstruction of the response functions associated with the Lindblad operators. Our approach is equally applicable to dynamics generated by effectively non-Hermitian Hamiltonians. We confirm the quality of our method providing specific error bounds that quantify its accuracy.

Estratégias terapêuticas no tratamento da dor crônica: uma genealogia da Clínica da Dor

O objetivo desse trabalho é analisar a singularidade das estratégias terapêuticas introduzidas pelo modelo das Clínicas da Dor, através de um estudo genealógico desse projeto terapêutico e sua contextualização no âmbito da racionalidade científica moderna. Mais especificamente, pretende-se analisar as transformações na racionalidade médica que permitiram, sucessivamente, a apreensão da dor pelo discurso médico, a concepção da dor como uma doença e a construção e a consolidação do modelo terapêutico das Clínicas da Dor. Para tal, inicialmente, analisamos o modelo terapêutico desenvolvido pelo médico anestesista John Bonica, idealizador do modelo das Clínicas da Dor, destacando as ferramentas conceituais que possibilitaram a compreensão da dor crônica como doença e como fenômeno biopsicossocial. Num segundo momento, realizamos uma descrição e análise dos principais eventos que permitiram a consolidação da medicina da dor como uma prática específica e multidisciplinar, dando destaque à inserção deste modelo no contexto do Sistema Único de Saúde Brasileiro. Finalmente, a partir de uma experiência clínico-institucional buscamos refletir sobre os limites e possibilidades da aplicação prática deste modelo, lançando luz sobre os impasses da clínica e tensões oriundas da problematização, do dualismo mente e corpo e das práticas terapêuticas interdisciplinares.

Estudo da quantificação de incertezas para o problema de contaminação de meios porosos heterogêneos

As técnicas de injeção de traçadores têm sido amplamente utilizadas na investigação de escoamentos em meios porosos, principalmente em problemas envolvendo a simulação numérica de escoamentos miscíveis em reservatórios de petróleo e o transporte de contaminantes em aquíferos. Reservatórios subterrâneos são em geral heterogêneos e podem apresentar variações significativas das suas propriedades em várias escalas de comprimento. Estas variações espaciais são incorporadas às equações que governam o escoamento no interior do meio poroso por meio de campos aleatórios. Estes campos podem prover uma descrição das heterogeneidades da formação subterrânea nos casos onde o conhecimento geológico não fornece o detalhamento necessário para a predição determinística do escoamento através do meio poroso. Nesta tese é empregado um modelo lognormal para o campo de permeabilidades a fim de reproduzir-se a distribuição de permeabilidades do meio real, e a geração numérica destes campos aleatórios é feita pelo método da Soma Sucessiva de Campos Gaussianos Independentes (SSCGI). O objetivo principal deste trabalho é o estudo da quantificação de incertezas para o problema inverso do transporte de um traçador em um meio poroso heterogêneo empregando uma abordagem Bayesiana para a atualização dos campos de permeabilidades, baseada na medição dos valores da concentração espacial do traçador em tempos específicos. Um método do tipo Markov Chain Monte Carlo a dois estágios é utilizado na amostragem da distribuição de probabilidade a posteriori e a cadeia de Markov é construída a partir da reconstrução aleatória dos campos de permeabilidades. Na resolução do problema de pressão-velocidade que governa o escoamento empregase um método do tipo Elementos Finitos Mistos adequado para o cálculo acurado dos fluxos em campos de permeabilidades heterogêneos e uma abordagem Lagrangiana, o método Forward Integral Tracking (FIT), é utilizada na simulação numérica do problema do transporte do traçador. Resultados numéricos são obtidos e apresentados para um conjunto de realizações amostrais dos campos de permeabilidades.

Comparison of habitat-based indices of abundance with fishery-independent biomass estimates from bottom trawl surveys

Rockfish species are notoriously difficult to sample with multispecies bottom trawl survey methods. Typically, biomass estimates have high coefficients of variation and can fluctuate outside the bounds of biological reality from year to year. This variation may be due in part to their patchy distribution related to very specific habitat preferences. We successfully modeled the distribution of five commercially important and abundant rockf ish species. A two-stage modeling method (modeling both presence-absence and abundance) and a collection of important habitat variables were used to predict bottom trawl survey catch per unit of effort. The resulting models explained between 22% and 66% of the variation in rockfish distribution. The models were largely driven by depth, local slope, bottom temperature, abundance of coral and sponge, and measures of water column productivity (i.e., phytoplankton and zooplankton). A year-effect in the models was back-transformed and used as an index of the time series of abundance. The abundance index trajectories of three of five species were similar to the existing estimates of their biomass. In the majority of cases the habitat-based indices exhibited less interannual variability and similar precision when compared with stratified survey-based biomass estimates. These indices may provide for stock assessment models a more stable alternative to current biomass estimates produced by the multispecies bottom trawl survey in the Gulf of Alaska.

Propagação de ondas em teorias alternativas da gravitação

Uma forma de generalizar a teoria de Einstein da gravitação é incorporar na lagrangiana termos que dependem de escalares formados com os tensores de Ricci e Riemann, tais como (Ricci)2, ou (Riemann)2. Estas teorias tem sido estudadas intensamente nos últimos anos, já que elas podem ser usadas para descrever a expansão acelerada do universo no modelo cosmológico standard. Entre os desfios de modificar a teoria de Einstein, se encontra o de limitar a ambiguidade na escolha da dependência da lagrangiana com os escalares antes mencionados. A proposta desta dissertação é a de colocar limites sobre as possíveis lagrangianas impondo que as ondas (isto é, perturbações lineares) se propaguem no vácuo sem que apareça, shocks.

Variability in supply and cross-shelf transport of pink shrimp (Farfantepenaeus duorarum) postlarvae into western Florida Bay

The variability in the supply of pink shrimp (Farfantepenaeus duorarum) postlarvae and the transport mechanisms of planktonic stages were investigated with field data and simulations of transport. Postlarvae entering the nursery grounds of Florida Bay were collected for three consecutive years at channels that connect the Bay with the Gulf of Mexico, and in channels of the Middle Florida Keys that connect the southeastern margin of the Bay with the Atlantic Ocean. The influx of postlarvae in the Middle Florida Keys was low in magnitude and varied seasonally and among years. In contrast, the greater postlarval influx occurred at the northwestern border of the Bay, where there was a strong seasonal pattern with peaks in influx from July through September each year. Planktonic stages need to travel up to 150 km eastward between spawning grounds (northeast of Dry Tortugas) and nursery grounds (western Florida Bay) in about 30 days, the estimated time of planktonic development for this species. A Lagrangian trajectory model was developed to estimate the drift of planktonic stages across the SW Florida shelf. The model simulated the maximal distance traveled by planktonic stages under various assumptions of behavior. Simulation results indicated that larvae traveling with the instantaneous current and exhibiting a diel behavior travel up to 65 km and 75% of the larvae travel only 30 km. However, the eastward distance traveled increased substantially when a larval response to tides was added to the behavioral variable (distance increased to 200 km and 85% of larvae traveled 150 km). The question is, when during larval development, and where on the shallow SW Florida shelf, does the tidal response become incorporated into the behavior of pink shrimp.