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.

In 1883 Leopold Kronecker published a paper containing “a few explanatory remarks” to an earlier paper of his from 1866. His work loosely connected the theory of integral binary bilinear forms to the theory of integral binary quadratic forms. In this dissertation we discover the statements within Kronecker's paper and offer detailed arithmetic proofs. We begin by developing the theory of binary bilinear forms and their automorphs, providing a classification of integral binary bilinear forms up to equivalence, proper equivalence and complete equivalence. In the second chapter we introduce the class number, proper class number and complete class number as well as two refinements, which facilitate the development of a connection with binary quadratic forms. Our third chapter is devoted to deriving several class number formulas in terms of divisors of the determinant. This chapter also contains lower bounds on the class number for bilinear forms and classifies when these bounds are attained. Lastly, we use the class number formulas to rigorously develop Kronecker's connection between binary bilinear forms and binary quadratic forms. We supply purely arithmetic proofs of five results stated but not proven in the original paper. We conclude by giving an application of this material to the number of representations of an integer as a sum of three squares and show the resulting formula is equivalent to the well-known result due to Gauss.

在這一篇論文中，我們討論 Ck/Cm/1 的等候系統。 我們利用矩陣多項式的奇異點及向量造 C_k/C_m/1 的機率分配的解空間。而矩陣多項式的非零奇異點和一個由抵達間隔時間與服務時間所形成的方程式有密切的關係。我們證明了在 E_k/E_m/1 的等候系統中，方程式的所有根都是相異的。但是當方程式有重根時，我們必須解一組相當複雜的方程式才能得到構成解空間的向量。此外，我們建立了一個描述飽和機率為 Kronecker products 線性組合的演算方法。 / In this thesis, we analyze the single server queueing system Ck/Cm/1. We construct a general solution space of the vector for stationary probability and describe the solution space in terms of singularities and vectors of the fundamental matrix polynomial Q(w). There is a relation between the singularities of Q(w) and the roots of the characteristic polynomial involving the Laplace transforms of the interarrival and service times distributions. In the Ek/Em/1 queueing system, it is proved that the roots of the characteristic polynomial are distinct if the arrival and service rates are real. When multiple roots occur, one needs to solve a set of equations of matrix polynomials. As a result, we establish a procedure for describing those vectors used in the expression of saturated probability as linear combination of Kronecker products.

Representation of sentences that captures semantics is an essential part of natural language processing systems, such as information retrieval or machine translation. The representation of a sentence is commonly built by combining the representations of the words that the sentence consists of. Similarity between words is widely used as a proxy to evaluate semantic representations. Word similarity models are well-studied and are shown to positively correlate with human similarity judgements. Current evaluation of models of sentential similarity builds on the results obtained in lexical experiments. The main focus is how the lexical representations are used, rather than what they should be. It is often assumed that the optimal representations for word similarity are also optimal for sentence similarity. This work discards this assumption and systematically looks for lexical representations that are optimal for similarity measurement between sentences. We find that the best representation for word similarity is not always the best for sentence similarity and vice versa. The best models in word similarity tasks perform best with additive composition. However, the best result on compositional tasks is achieved with Kroneckerbased composition. There are representations that are equally good in both tasks when used with multiplicative composition. The systematic study of the parameters of similarity models reveals that the more information lexical representations contain, the more attention should be paid to noise. In particular, the word vectors in models with the feature size at the magnitude of the vocabulary size should be sparse, but if a small number of context features is used then the vectors should be dense. Given the right lexical representations, compositional operators achieve state-of-the-art performance, improving over models that use neural-word embeddings. To avoid overfitting, either several test datasets should be used or parameter selection should be based on parameters' average behaviours.

The main part of the thesis is applications of the Strong Artin conjecture to number theory. We have two applications. One is generating number fields with extreme class numbers. The other is generating extreme positive and negative values of Euler-Kronecker constants. For a given number field $K$ of degree $n$, let $\widehat{K}$ be the normal closure of $K$ with $Gal(\widehat{K}/\Bbb Q)=G.$ Let $Gal(\widehat{K}/K)=H$ for some subgroup $H$ of $G$. Then, $$ L(s,\rho,\widehat{K}/\Bbb Q)=\frac{\zeta_K(s)}{\zeta(s)} $$ where $Ind_H^G1_H = 1_G + \rho$. When $L(s,\rho)$ is an entire function and has a zero-free region $[\alpha,1] \times [-(\log N)^2, (\log N)^2]$ where $N$ is the conductor of $L(s,\rho)$, we can estimate $\log L(1,\rho)$ and $\frac{L'}{L}(1,\rho)$ as a sum over small primes: $$ \log L(1,\rho) = \sum_{p\leq(\log N)^{k}}\lambda(p)p^{-1} + O_{l,k,\alpha}(1)$$ $$ \frac{L'}{L}(1,\rho)=-\sum_{p\leq x} \frac{\lambda(p) \log{p}}{p} +O_{l,x,\alpha}(1). $$ where $0 < k < \frac{16}{1-\alpha}$ and $(\log N)^{\frac{16}{1-\alpha}} \leq x \leq N^{\frac{1}{4}}$. With these approximations, we can study extreme values of class numbers and Euler-Kronecker constants. Let $\frak{K}$ $(n,G,r_1,r_2)$ be the set of number fields of degree $n$ with signature $(r_1,r_2)$ whose normal closures are Galois $G$ extension over $\Bbb Q$. Let $f(x,t) \in \Bbb Z[t][x]$ be a parametric polynomial whose splitting field over $\Bbb Q (t)$ is a regular $G$ extension. By Cohen's theorem, most specialization $t\in \Bbb Z$ corresponds to a number field $K_t$ in $\frak{K}$ $(n,G,r_1,r_2)$ with signature $(r_1,r_2)$ and hence we have a family of Artin L-functions $L(s,\rho,t)$. By counting zeros of L-functions over this family, we can obtain L-functions with the zero-free region above. In Chapter 1, we collect the known cases for the Strong Artin conjecture and prove it for the cases of $G=A_4$ and $S_4$. We explain how to obtain the approximations of $\log (1,\rho)$ and $\frac{L'}{L}(1,\rho)$ as a sum over small primes in detail. We review the theorem of Kowalski-Michel on counting zeros of automorphic L-functions in a family. In Chapter 2, we exhibit many parametric polynomials giving rise to regular extensions. They contain the cases when $G=C_n,$ $3\leq n \leq 6$, $D_n$, $3\leq n \leq 5$, $A_4, A_5, S_4, S_5$ and $S_n$, $n \geq 2$. In Chapter 3, we construct number fields with extreme class numbers using the parametric polynomials in Chapter 2. In Chapter 4, We construct number fields with extreme Euler-Kronecker constants also using the parametric polynomials in Chapter 2. In Chapter 5, we state the refinement of Weil's theorem on rational points of algebraic curves and prove it. The second topic in the thesis is about simple zeros of Maass L-functions. We consider a Hecke Maass form $f$ for $SL(2,\Bbb Z)$. In Chapter 6, we show that if the L-function $L(s,f)$ has a non-trivial simple zero, it has infinitely many simple zeros. This result is an extension of the result of Conrey and Ghosh.

The main part of the thesis is applications of the Strong Artin conjecture to number theory. We have two applications. One is generating number fields with extreme class numbers. The other is generating extreme positive and negative values of Euler-Kronecker constants. For a given number field $K$ of degree $n$, let $\widehat{K}$ be the normal closure of $K$ with $Gal(\widehat{K}/\Bbb Q)=G.$ Let $Gal(\widehat{K}/K)=H$ for some subgroup $H$ of $G$. Then, $$ L(s,\rho,\widehat{K}/\Bbb Q)=\frac{\zeta_K(s)}{\zeta(s)} $$ where $Ind_H^G1_H = 1_G + \rho$. When $L(s,\rho)$ is an entire function and has a zero-free region $[\alpha,1] \times [-(\log N)^2, (\log N)^2]$ where $N$ is the conductor of $L(s,\rho)$, we can estimate $\log L(1,\rho)$ and $\frac{L'}{L}(1,\rho)$ as a sum over small primes: $$ \log L(1,\rho) = \sum_{p\leq(\log N)^{k}}\lambda(p)p^{-1} + O_{l,k,\alpha}(1)$$ $$ \frac{L'}{L}(1,\rho)=-\sum_{p\leq x} \frac{\lambda(p) \log{p}}{p} +O_{l,x,\alpha}(1). $$ where $0 < k < \frac{16}{1-\alpha}$ and $(\log N)^{\frac{16}{1-\alpha}} \leq x \leq N^{\frac{1}{4}}$. With these approximations, we can study extreme values of class numbers and Euler-Kronecker constants. Let $\frak{K}$ $(n,G,r_1,r_2)$ be the set of number fields of degree $n$ with signature $(r_1,r_2)$ whose normal closures are Galois $G$ extension over $\Bbb Q$. Let $f(x,t) \in \Bbb Z[t][x]$ be a parametric polynomial whose splitting field over $\Bbb Q (t)$ is a regular $G$ extension. By Cohen's theorem, most specialization $t\in \Bbb Z$ corresponds to a number field $K_t$ in $\frak{K}$ $(n,G,r_1,r_2)$ with signature $(r_1,r_2)$ and hence we have a family of Artin L-functions $L(s,\rho,t)$. By counting zeros of L-functions over this family, we can obtain L-functions with the zero-free region above. In Chapter 1, we collect the known cases for the Strong Artin conjecture and prove it for the cases of $G=A_4$ and $S_4$. We explain how to obtain the approximations of $\log (1,\rho)$ and $\frac{L'}{L}(1,\rho)$ as a sum over small primes in detail. We review the theorem of Kowalski-Michel on counting zeros of automorphic L-functions in a family. In Chapter 2, we exhibit many parametric polynomials giving rise to regular extensions. They contain the cases when $G=C_n,$ $3\leq n \leq 6$, $D_n$, $3\leq n \leq 5$, $A_4, A_5, S_4, S_5$ and $S_n$, $n \geq 2$. In Chapter 3, we construct number fields with extreme class numbers using the parametric polynomials in Chapter 2. In Chapter 4, We construct number fields with extreme Euler-Kronecker constants also using the parametric polynomials in Chapter 2. In Chapter 5, we state the refinement of Weil's theorem on rational points of algebraic curves and prove it. The second topic in the thesis is about simple zeros of Maass L-functions. We consider a Hecke Maass form $f$ for $SL(2,\Bbb Z)$. In Chapter 6, we show that if the L-function $L(s,f)$ has a non-trivial simple zero, it has infinitely many simple zeros. This result is an extension of the result of Conrey and Ghosh.

Submitted by Johnny Rodrigues (johnnyrodrigues@ufcg.edu.br) on 2018-08-05T13:30:11Z No. of bitstreams: 1 ISRAEL BURITÍ GALVÃO - DISSERTAÇÃO PPGMAT 2012..pdf: 650302 bytes, checksum: a18f67c466fa85d401a769d86e98be3a (MD5) / Made available in DSpace on 2018-08-05T13:30:11Z (GMT). No. of bitstreams: 1 ISRAEL BURITÍ GALVÃO - DISSERTAÇÃO PPGMAT 2012..pdf: 650302 bytes, checksum: a18f67c466fa85d401a769d86e98be3a (MD5) Previous issue date: 2012-03 / CNPq / Nesta dissertação foi feita uma abordagem sobre identidades polinomiais para o produto tensorial de duas álgebras. Com base no crescimento da sequência de codimensões de uma PI-álgebra, estudado inicialmente por Regev em 1972, apresentamos uma prova de que o produto tensorial de duas PI-álgebras é ainda uma PI-álgebra. Depois, através do produto de Kronecker de caracteres e do clássico Teorema do Gancho de Amitsur e Regev, obtemos relações entre as codimensões e os cocaracteres de duas PI-álgebras e as codimensões e cocaracteres do seu produto tensorial. Também através do estudo de codimensões e cocaracteres, conseguimos exibir identidades polinomiais para o produto tensorial. / In this dissertation we study polynomial identities for the tensor product of two algebras. Based on the growth of the PI-algebra’s codimensions sequence, originally studied by Regev in 1972, we present a proof that the tensor product of two PI-algebras is still a PI-algebra. After this, using the Kronecker product of characters and the classic Amitsur and Regev Hook Theorem, we obtained relations between the codimensions and cocharacters of two PI-algebras and the codimensions and cocharacters of their tensor product. With the study of codimensions and cocharacters, we also exhibit polynomial identities for the tensor product.

abstract: Tracking a time-varying number of targets is a challenging dynamic state estimation problem whose complexity is intensified under low signal-to-noise ratio (SNR) or high clutter conditions. This is important, for example, when tracking multiple, closely spaced targets moving in the same direction such as a convoy of low observable vehicles moving through a forest or multiple targets moving in a crisscross pattern. The SNR in these applications is usually low as the reflected signals from the targets are weak or the noise level is very high. An effective approach for detecting and tracking a single target under low SNR conditions is the track-before-detect filter (TBDF) that uses unthresholded measurements. However, the TBDF has only been used to track a small fixed number of targets at low SNR. This work proposes a new multiple target TBDF approach to track a dynamically varying number of targets under the recursive Bayesian framework. For a given maximum number of targets, the state estimates are obtained by estimating the joint multiple target posterior probability density function under all possible target existence combinations. The estimation of the corresponding target existence combination probabilities and the target existence probabilities are also derived. A feasible sequential Monte Carlo (SMC) based implementation algorithm is proposed. The approximation accuracy of the SMC method with a reduced number of particles is improved by an efficient proposal density function that partitions the multiple target space into a single target space. The proposed multiple target TBDF method is extended to track targets in sea clutter using highly time-varying radar measurements. A generalized likelihood function for closely spaced multiple targets in compound Gaussian sea clutter is derived together with the maximum likelihood estimate of the model parameters using an iterative fixed point algorithm. The TBDF performance is improved by proposing a computationally feasible method to estimate the space-time covariance matrix of rapidly-varying sea clutter. The method applies the Kronecker product approximation to the covariance matrix and uses particle filtering to solve the resulting dynamic state space model formulation. / Dissertation/Thesis / Doctoral Dissertation Electrical Engineering 2015

The first half of the thesis focuses on the computation of high-dimensional multivariate normal (MVN) and multivariate Student-t (MVT) probabilities. Chapter 2 generalizes the bivariate conditioning method to a d-dimensional conditioning method and combines it with a hierarchical representation of the n × n covariance matrix. The resulting two-level hierarchical-block conditioning method requires Monte Carlo simulations to be performed only in d dimensions, with d ≪ n, and allows the dominant complexity term of the algorithm to be O(n log n). Chapter 3 improves the block reordering scheme from Chapter 2 and integrates it into the Quasi-Monte Carlo simulation under the tile-low-rank representation of the covariance matrix. Simulations up to dimension 65,536 suggest that this method can improve the run time by one order of magnitude compared with the hierarchical Monte Carlo method. The second half of the thesis discusses a novel matrix compression scheme with Kronecker products, an R package that implements the methods described in Chapter 3, and an application study with the probit Gaussian random field. Chapter 4 studies the potential of using the sum of Kronecker products (SKP) as a compressed covariance matrix representation. Experiments show that this new SKP representation can save the memory footprint by one order of magnitude compared with the hierarchical representation for covariance matrices from large grids and the Cholesky factorization in one million dimensions can be achieved within 600 seconds. In Chapter 5, an R package is introduced that implements the methods in Chapter 3 and show how the package improves the accuracy of the computed excursion sets. Chapter 6 derives the posterior properties of the probit Gaussian random field, based on which model selection and posterior prediction are performed. With the tlrmvnmvt package, the computation becomes feasible in tens of thousands of dimensions, where the prediction errors are significantly reduced.

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal.