Imageamento acústico é um problema computacionalmente caro e mal-condicionado, que envolve estimar distribuições de fontes com grandes arranjos de microfones. O método clássico para imageamento acústico utiliza beamforming, e produz a distribuição de fontes de interesse convoluída com a função de espalhamento do arranjo. Esta convolução borra a imagem ideal, significativamente diminuindo sua resolução. Convoluções podem ser evitadas com técnicas de ajuste de covariância, que produzem estimativas de alta resolução. Porém, estas têm sido evitadas devido ao seu alto custo computacional. Nesta tese, admitimos um arranjo bidimensional com geometria separável, e desenvolvemos transformadas rápidas para acelerar imagens acústicas em várias ordens de grandeza. Estas transformadas são genéricas, e podem ser aplicadas para acelerar beamforming, algoritmos de deconvolução e métodos de mínimos quadrados regularizados. Assim, obtemos imagens de alta resolução com algoritmos estado-da-arte, mantendo baixo custo computacional. Mostramos que arranjos separáveis produzem estimativas competitivas com as de geometrias espirais logaritmicas, mas com enormes vantagens computacionais. Finalmente, mostramos como estender este método para incorporar calibração, um modelo para propagação em campo próximo e superfícies focais arbitrárias, abrindo novas possibilidades para imagens acústicas. / Acoustic imaging is a computationally intensive and ill-conditioned inverse problem, which involves estimating high resolution source distributions with large microphone arrays. The classical method for acoustic imaging consists of beamforming, and produces the source distribution of interest convolved with the array point spread function. This convolution smears the image of interest, significantly reducing its effective resolution. Convolutions can be avoided with covariance fitting methods, which have been known to produce robust high-resolution estimates. However, these have been avoided due to prohibitive computational costs. In this thesis, we assume a 2D separable array geometry, and develop fast transforms to accelerate acoustic imaging by several orders of magnitude with respect to previous methods. These transforms are very generic, and can be applied to accelerate beamforming, deconvolution algorithms and regularized least-squares solvers. Thus, one can obtain high-resolution images with state-of-the-art algorithms, while maintaining low computational cost. We show that separable arrays deliver accuracy competitive with multi-arm spiral geometries, while producing huge computational benefits. Finally, we show how to extend this approach with array calibration, a near-field propagation model and arbitrary focal surfaces, opening new and exciting possibilities for acoustic imaging.

Imageamento acústico é um problema computacionalmente caro e mal-condicionado, que envolve estimar distribuições de fontes com grandes arranjos de microfones. O método clássico para imageamento acústico utiliza beamforming, e produz a distribuição de fontes de interesse convoluída com a função de espalhamento do arranjo. Esta convolução borra a imagem ideal, significativamente diminuindo sua resolução. Convoluções podem ser evitadas com técnicas de ajuste de covariância, que produzem estimativas de alta resolução. Porém, estas têm sido evitadas devido ao seu alto custo computacional. Nesta tese, admitimos um arranjo bidimensional com geometria separável, e desenvolvemos transformadas rápidas para acelerar imagens acústicas em várias ordens de grandeza. Estas transformadas são genéricas, e podem ser aplicadas para acelerar beamforming, algoritmos de deconvolução e métodos de mínimos quadrados regularizados. Assim, obtemos imagens de alta resolução com algoritmos estado-da-arte, mantendo baixo custo computacional. Mostramos que arranjos separáveis produzem estimativas competitivas com as de geometrias espirais logaritmicas, mas com enormes vantagens computacionais. Finalmente, mostramos como estender este método para incorporar calibração, um modelo para propagação em campo próximo e superfícies focais arbitrárias, abrindo novas possibilidades para imagens acústicas. / Acoustic imaging is a computationally intensive and ill-conditioned inverse problem, which involves estimating high resolution source distributions with large microphone arrays. The classical method for acoustic imaging consists of beamforming, and produces the source distribution of interest convolved with the array point spread function. This convolution smears the image of interest, significantly reducing its effective resolution. Convolutions can be avoided with covariance fitting methods, which have been known to produce robust high-resolution estimates. However, these have been avoided due to prohibitive computational costs. In this thesis, we assume a 2D separable array geometry, and develop fast transforms to accelerate acoustic imaging by several orders of magnitude with respect to previous methods. These transforms are very generic, and can be applied to accelerate beamforming, deconvolution algorithms and regularized least-squares solvers. Thus, one can obtain high-resolution images with state-of-the-art algorithms, while maintaining low computational cost. We show that separable arrays deliver accuracy competitive with multi-arm spiral geometries, while producing huge computational benefits. Finally, we show how to extend this approach with array calibration, a near-field propagation model and arbitrary focal surfaces, opening new and exciting possibilities for acoustic imaging.

Hierarchical Markovian Models (HMMs) are composed of multiple low level models (LLMs) and high level model (HLM) that defines the interaction among LLMs. The essence of the HMM approach is to model the system at hand in the form of interacting components so that its (larger) underlying continous-time Markov chain (CTMC) is not generated but implicitly represented as a sum of Kronecker products of (smaller) component matrices. The Kronecker structure of an HMM induces nested block partitionings in its underlying CTMC. These partitionings may be used in block versions of classical iterative methods based on splittings, such as block SOR (BSOR), to solve the underlying CTMC for its stationary vector. Therein the problem becomes that of solving multiple nonsingular linear systems whose coefficient matrices are the diagonal blocks of a particular partitioning. This paper shows that in each HLM state there may be diagonal blocks with identical off-diagonal parts and diagonals differing from each other by a multiple of the identity matrix. Such diagonal blocks are named candidate blocks. The paper explains how candidate blocks can be detected and how the can mutually benefit from a single real Schur factorization. It gives sufficient conditions for the existence of diagonal blocks with real eigenvalues and shows how these conditions can be checked using component matrices. It describes how the sparse real Schur factors of candidate blocks satisfying these conditions can be constructed from component matrices and their real Schur factors. It also demonstrates how fill in- of LU factorized (non-candidate) diagonal blocks can be reduced by using the column approximate minimum degree algorithm (COLAMD). Then it presents a three-level BSOR solver in which the diagonal blocks at the first level are solved using block Gauss-Seidel (BGS) at the second and the methods of real Schur and LU factorizations at the third level. Finally, on a set of numerical experiments it shows how these ideas can be used to reduce the storage required by the factors of the diagonal blocks at the third level and to improve the solution time compared to an all LU factorization implementation of the three-level BSOR solver.

Soit k un corps algébriquement clos de caractéristique 0 et F une suite de n polynômes en intersection complète sur k[X1,...,Xn]. Le Bezoutien de F fournit une forme dualisante sur k[X]/<F> appelée symbole de Kronecker, qui est un analogue algébrique du résidu. L'objet de ce travail est de construire et calculer le symbole de Kronecker dans le tore (C*)n relativement à une famille f de n polynômes de Laurent en n variables. La famille f possède un nombre fini de zéros et est régulière pour ses polytopes de Newton. La représentation du résidu global dans le tore à l'aide d'un résidu torique, donnée par Cattani et Dickenstein, suggère d'interpréter le symbole de Kronecker dans le tore dans la variété torique projective définie par le polytope P, somme de Minkowski des polytopes de Newton de f.Lorsque P est premier, Roy et Szpirglas ont défini le symbole de Kronecker dans le tore à partir des symboles de Kronecker définis sur les ouverts affines de la variété torique Xp relativement à une famille de n + 1 polynômes homogènes sans zéros communs dans la variété Xp. Nous montrons ici que le cas « P non premier » est réductible au cas précédent en explicitant les morphismes d'éclatement qui traduisent le raffinement de l’éventail de Xp en un éventail simplicial. / Let k be an algebraically closed field with char(k) = 0 and let be polynomials F1,..., Fn such that k[X1,...,Xn]/<F1,..., Fn> is a complete intersection k-algebra. The Bezoutian of F1,..., Fn gives a dualizing form acting on k[X1,...,Xn]/<F1,..., Fn> called Kronecker symbol. It is an algebraic analogue of residue. The aim of this work is to build and calculate the Kronecker symbol in the torus (C*)n for a system f of Laurent polynomials with a a finite set of zeroes and regular for its Newton polytopes. In the same way as Cattani and Dickenstein have done for the global residue in the torus, we consider the projective variety given by the Minkowski sum P of the Newton polytopes of f in order to build the Kronecker symbol in the torus.When P is prime, Roy and Szpirglas have defined the Kronecker symbol in the torus from Kronecker symbols on affine subsets of Xp for a system of n+1 homogeneous polynomials with no common zeroes in XP . We prove that the case "P no prime" can be reduced to the previous case by using simplicial refinements of the fan of Xp and making explicit the associated toric morphisms on the total coordinate spaces.

Este trabalho consiste de três partes: Teoremas de coordenatização de Wedderburn e de Zorn, O problema de Nathan Jacobson e Teoremas de Fatorização de Kronecker para as superálgebras alternativas. Na primeira parte apresentamos os teoremas de coordenatização de Wedderburn e de Zorn e suas aplicações na teoria de representações das álgebras associativas e alternativas. Na segunda parte resolvemos um problema de longa data que foi anunciado por Nathan Jacobson sobre a descrição das álgebras alternativas que contém M&#8322(F ) (álgebra associativa de matrizes 2 × 2) com o mesmo elemento identidade. Na terceira parte damos uma prova independente que é válida em qualquer característica do clássico Teorema de Fatorização de Kronecker de Nathan Jacobson. Generalizamos esse resultado e provamos um teorema de Fatorização de Kronecker para as superálgebras alternativas cuja parte par contém O com o mesmo elemento identidade. Além disso, provamos um Teorema de Fatorização de Kronecker para as superálgebras alternativas que contêm a superálgebra associativa M(1|1)(F ) com o mesmo elemento identidade. Como Corolário desse resultado, respondemos a um análogo do problema de Jacobson para as superálgebras alternativas, isto é, descrevemos as superálgebras alternativas que contêm à superálgebra associativa M(1|1)(F ) com o mesmo elemento identidade. Finalmente, estudamos as representações das superálgebras alternativa simples O(4,4) e O[u]. Classificamos os bimodules sobre essas superálgebras e provamos alguns análogos do Teorema de Fatorização de Kronecker para as superálgebras alternativas que contenham O(4|4) ou O[u] com o mesmo elemento identidade / This work consists of three parts: Wedderburn and Zorn coordinatizations theorems, Nathan Jacobsons problem and Kroneckers Factorization theorems for alternative superalgebras. In the first part we present Wedderburn and Zorn coordinatizations theorems and their applications in the theory of representations of associative and alternative algebras. In the second part we solve a long standing problem that was announced by Nathan Jacobson on the description of alternative algebras containing M&#8322(F ) (associative matrix algebra 2 × 2) with the same identity element. In the third part we give an independent proof that is valid in any characteristic of Nathan Jacobsons classic Kronecker Factorization Theorem. We generalize this result and prove a Kronecker Factorization Theorem for alternative superalgebras whose even part contains O with the same identity element. In addition, we prove a Kronecker Factorization Theorem for alternative superalgebras containing the associative superalgebra M(1|1)(F ) with the same identity element. As a corollary of this result, we respond to an analogue of Jacobsons problem for alternative superalgebras, that is, we describe the alternative superalgebras containing the associative superalgebra M(1|1)(F ) with the same identity element. Finally, we study the representations of the simple alternative superalgebras O(4|4) e O[u]. We classify the bimodules on these superalgebras and prove some analogues of the Kronecker Factorization Theorem for alternative superalgebras containing O(4|4) or O[u] with the same identity element

Hourya Sinaceur présente dans son ouvrage Corps et Modèles la théorie des caractéristiques de Kronecker comme la fin d’« un cycle d’idées sturmiennes », la situant ainsi dans une histoire de l’algébrisation du théorème de Sturm. Pourtant, cette théorie est souvent aussi présentée comme le point de départ de certains des premiers travaux de topologie de la toute fin du dix-neuvième siècle. Nous souhaitons dans cette thèse rendre compte de la façon dont ces deux histoires se rencontrent au sein de la théorie de Kronecker. Pour cela, nous disposons d’un matériel particulièrement éclairant et jusqu’alors très peu exploité : les manuscrits des cours que Kronecker a donnés à l’Université de Berlin entre 1872 et 1891 sur la Théorie des équations algébriques. Nous commencerons par présenter ces manuscrits, leur contenu et leur contexte de rédaction. Nous nous intéresserons ensuite plus précisément à la reprise du théorème de Sturm par Kronecker, et nous montrerons que la théorie des caractéristiques n’est pas seulement un prolongement algébrique de ce théorème, mais qu’elle se transforme pour fournir certains des outils analytiques que Poincaré utilisera lors de la construction de son Analysis Situs. L’exposition de la théorie des caractéristiques dans ses cours est l’occasion pour Kronecker de reprendre trois des quatre démonstrations que Gauss a données du théorème fondamental de l’algèbre, et nous montrerons comment, dans la pratique de Kronecker, la notion même de racine est interrogée / In her book Corps et Modèles, Hourya Sinaceur presented Kronecker’s theory of characteristics as the end of a “cycle of Sturmian ideas”, making it a step in history of the algebraization of Sturm’s theorem. However, this theory is often also introduced as the starting point of some of the early works of topology of the very end of the nineteenth century. In this PhD thesis, I will describe how these two stories are connected in Kronecker’s theory. To achieve this, I used material which has seldom been discussed before : the manuscripts of the courses that Kronecker gave at the University of Berlin between 1872 and 1891 on the Theory of algebraic equations. I begin with the presentation of these manuscripts, their contents and their writing contexts. I then look more closely at Kronecker’s rework of the theorem of Sturm and show that the theory of characteristics is not only an algebraic extension of this theorem but also that it is transformed in order to provide some of the analytic tools that Poincaré will use for the construction of his Analysis Situs. The exposition of the theory of characteristics in his courses is an opportunity for Kronecker to take up three of the four demonstrations from Gauss of the fundamental theorem of algebra, and I will show how, in Kronecker’s practice, the very notion of root is questioned

A long term record of the earth's vegetation is important in studies of global climate change. Over the last three decades, multiple data sets on vegetation have been collected using different satellite-based sensors. There is a need for methods that combine these data into a long term earth system data record. The Advanced Very High Resolution Radiometer (AVHRR) has provided reflectance measures of the entire earth since 1978. Physical and statistical models have been used to improve the consistency and reliability of this record. The Moderated Resolution Imaging Spectroradiometer (MODIS) has provided measurements with superior radiometric properties and geolocation accuracy. However, this record is available only since 2000. In this thesis, we perform statistical calibration of AVHRR to MODIS. We aim to: (1) fill in gaps in the ongoing MODIS record; (2) extend MODIS values back to 1982. We propose Bayesian mixed models to predict MODIS values using snow cover and AVHRR values as covariates. Random effects are used to account for spatiotemporal correlation in the data. We estimate the parameters based on the data after 2000, using Markov chain Monte Carlo methods. We then back-predict MODIS data between 1978 and 1999, using the posterior samples of the parameter estimates. We develop new Conditional Autoregressive (CAR) models for seasonal data. We also develop new sampling methods for CAR models. Our approach enables filling in gaps in the MODIS record and back-predicting these values to construct a consistent historical record. The Bayesian framework incorporates multiple sources of variation in estimating the accuracy of the obtained data. The approach is illustrated using vegetation data over a region in Minnesota.

A number of recent developments has increased the desirability of using exclusive OR (XOR) gates in the synthesis of switching functions. This has, in turn, led naturally to an increased interest in algorithms for the minimization of Exclusive-Or Sum of Products (ESOP) forms. Although this is an active area of research, it is not nearly as developed as the traditional Sum of Products forms. Computer programs to find minimum ESOPs are not readily available and those that do exist are impractical to use as investigative tools because they are too slow and/or require too much memory. A practical tool would be easy enough to use (faster/smaller) so that it could be run many times to explore the solution space of the minimization problem as well as to provide a baseline of comparison. This thesis develops and investigates such a tool.

Several classes of AND-EXOR circuit expressions have been defined and their relationship have been shown. A new class of AND-EXOR circuit, the Partially Mixed Polarity Reed-Muller Expression(PMPRM), which is a subclass of the Generalized Reed-Muller expression, is created, along with an efficient minimization algorithm. This new AND/EXOR circuit form has the following features: • Since this sub-family of ESOP (with a total of n2n-I22n-i - (n-1)2n forms which includes the 2n Fixed-Polarity Reed-Muller forms) is much larger than the Kronecker Reed-Muller(KRM) expansion(with 3n forms), generally the minimal form of this expansion will be much closer to the minimal ESOP than the minimal form of KRM expansion. • It is a sub-class of the Generalized Reed-Muller Expansion, thus has better testibility than other AND/EXOR circuits. Those design methods of easily testable GRM circuit networks[ 6] [35] can also be used for this new circuit form. • The exact solution to the minimization of this new expansion provides a upperbound for the minimization of ORM expansion. In this thesis, we prove that to calculate a PMPRM expansion from one of its adjacent polarity expansion , only one EXOR operation is needed. By calculating the adjacent polarity expansions one-by-one and searching all the PMPRM forms the minimum one can be found. A speedup approach allows us to find the exact minimum PMPRM without calculating all forms. The algorithm is explained by minimizing the 3-variable functions and is demonstrated by flow graphs. With the introduction of termwise complementary expansion diagram, a computerized algorithm for the calculation of any ORM expansion is presented. The exact minimum ORM form can be obtained by an exhaustive search through all ORM forms. A heuristic minimization algorithm, which is designed to decrease the time complexity of the exact one, is also presented in this thesis. Instead of depending on the number of input variables, the computation time of this quasi-minimum algorithm depends mainly on the complexity of the input functions, thus can solve much larger problems. The exact minimization algorithm for PMPRM and the quasi-minimum ORM minimization algorithm have been implemented in C programs and a set of benchmark functions has been tested. The results are compared to those from [16], [36], and Espresso's. In most cases our program gives the same or better solutions.

Several advancements related to the solution of 3D time-harmonic wave equations are presented, especially in the context of a parallel moving-PML sweeping preconditioner for problems without large-scale resonances. The main contribution of this dissertation is the introduction of an efficient parallel sweeping preconditioner and its subsequent application to several challenging velocity models. For instance, 3D seismic problems approaching a billion degrees of freedom have been solved in just a few minutes using several thousand processors. The setup and application costs of the sequential algorithm were also respectively refined to O(γ^2 N^(4/3)) and O(γ N log N), where N denotes the total number of degrees of freedom in the 3D volume and γ(ω) denotes the modestly frequency-dependent number of grid points per Perfectly Matched Layer discretization. Furthermore, high-performance parallel algorithms are proposed for performing multifrontal triangular solves with many right-hand sides, and a custom compression scheme is introduced which builds upon the translation invariance of free-space Green’s functions in order to justify the replacement of each dense matrix within a certain modified multifrontal method with the sum of a small number of Kronecker products. For the sake of reproducibility, every algorithm exercised within this dissertation is made available as part of the open source packages Clique and Parallel Sweeping Preconditioner (PSP). / text