This thesis consists of two parts, Papers A and B, in which some stochastic processes, originating from random matrix theory (RMT), are studied. In the first paper we study the fluctuations of the kth largest eigenvalue, xk, of the Gaussian unitary ensemble (GUE). That is, let N be the dimension of the matrix and k depend on N in such a way that k and N-k both tend to infinity as N - ∞. The main result is that xk, when appropriately rescaled, converges in distribution to a Gaussian random variable as N → ∞. Furthermore, if k1 < ...< km are such that k1, ki+1 - ki and N - km, i =1, ... ,m - 1, tend to infinity as N → ∞ it is shown that (xk1 , ... , xkm) is multivariate Gaussian in the rescaled N → ∞ limit. In the second paper we study the Airy process, A(t), and prove that it fluctuates like a Brownian motion on a local scale. We also prove that the Discrete polynuclear growth process (PNG) fluctuates like a Brownian motion in a scaling limit smaller than the one where one gets the Airy process. / QC 20100716

Cette thèse vise à approfondir les analogies entre les valeurs propres de matrices aléatoires sur les groupes compacts et les zéros de fonctions L, en particulier la fonction zêta.

Introducción El abuso de sustancias en los países occidentales ha acontecido un problema de salud pública. Estas sustancias también son consumidas por embarazadas, afectando al feto y recién nacido, especialmente vulnerables. Desde la década de los ochenta, la eventual presencia y disposición de una sustancia de abuso en el organismo y su correlación con efectos clínicos y/o subjetivos ha sido evaluada mediante el análisis de plasma u orina. Sin embargo, realizar estas determinaciones en fluidos y matrices biológicas diferentes a la sangre y la orina resultan mucho más atractivas. La no invasividad en la recolección de muestras y otorgar mayor información retrospectiva en el tiempo hacen de matrices biológicas como la placenta, el meconio y el pelo, buenas matrices para evaluar la exposición crónica a sustancias de abuso durante la gestación y diferentes etapas de la infancia. Metodología Revisión de la metodología empleada para la detección del consumo de sustancias de abuso durante el embarazo. Se ha realizado una revisión sobre los diferentes biomarcadores del consumo de alcohol durante la gestación. Centrándose en los biomarcadores que pueden ser utilizados en matrices alternativas, ya que presentan una ventana de detección más amplia y son más fáciles de obtener. Estudio microscópico y macroscópico de la morfología placentaria para valorar los cambios en mujeres consumidoras de sustancias de abuso durante el embarazo. Teniendo un marcador objetivo de exposición fetal durante el tercer trimestre (meconio). Determinación de la exposición a sustancias de abuso mediante una matriz alternativa del tercer trimestre (pelo materno). Resultados Se han publicado 3 artículos, relacionados con el tema. Una revisión sobre los biomarcadores de alcohol durante la gestación que pone de manifiesto la utilidad de los biomarcadores en matrices alternativas. Un estudio morfológico sobre los cambios en la placenta de madres consumidoras de sustancias de abuso, donde no se observan cambios macroscópicos pero sí algunas alteraciones de la vasculatura placentaria a nivel microscópico. Por último un estudio sobre la determinación de sustancias de abuso en pelo materno, el cual demuestra la utilidad de dicha matriz alternativa para la detección de sustancias de abuso durante el tercer trimestre de la gestación y reafirma la infradeclaración por parte de las madres. Discusión y conclusiones Esta tesis pone de manifiesto la utilidad de la detección del consumo de sustancias de abuso durante el tercer trimestre de la gestación mediante biomarcadores en matrices alternativas. De la misma manera indica cambios a nivel de la placenta, la cual puede ser utilizada también como matriz del tercer trimestre, los cuales nos podrían ayudar a entender los efectos nocivos que el consumo de sustancias provoca sobre el recién nacido, aunque son necesarios más estudios para llegar a conclusiones más objetivas. En conclusión, con el fin de detectar la exposición a sustancias de abuso durante el tercer trimestre de la gestación, se recomienda utilizar diferentes matrices no convencionales o alternativas (meconio, pelo, placenta) con el fin de minimizar la invasividad en la recogida de las muestras y tener una información de consumo crónico en comparación con las matrices utilizadas tradicionalmente (sangre y orina). / Introduction Substances of abuse consumption in Western countries has become a public health problem. These substances are also consumed by pregnant women, affecting the foetus and the newborn, especially vulnerables. Since the eighties, presence and eventual disposal of a substance of abuse and its correlation with clinical and/or subjective effects has been evaluated by analysis of plasma or urine. However, determinations in biological matrices other than blood and urine are very interesting. Non-invasiveness in sample collection and obtention of more information back in time make biological matrices such as placenta, meconium and hair, attractive to assess chronic exposure to drugs of abuse during pregnancy and chilhood. Methodology Review of the methodology used for the detection of drugs of abuse consumption during pregnancy, specifically of the different biomarkers of alcohol in alternative matrices, as they have a large exposure window and are easier to obtain. Microscopic and macroscopic study of changes in placental morphology in women using substances of abuse during pregnancy, detected through an objective marker of foetal exposure during the third trimester in an alternative matrix (meconium). Determination of exposure to substances of abuse by another alternative third trimester matrix (maternal hair). Results Three articles have been published related to the topic. A review on biomarkers of alcohol during pregnancy that demonstrates the utility of biomarkers in alternative matrices. A morphological study on the changes in the placenta of substances of abuse using mothers. No macroscopic changes were observed, but some alterations in placental vasculature at the microscopic level were found. Finally, a study on the determination of substances of abuse in maternal hair was made, demonstrating the usefulness of this alternative matrix for detecting drugs of abuse in the third trimester and confirming under-reporting by mothers. Discussion and conclusions In this thesis we demonstrated the usefulness of the detection of substances of abuse in the third trimester of pregnancy using biomarkers in alternative matrices. Similarly, we found changes in the placenta, which can also be used as a third trimester matrix, which could help us to understand the causes of harmful effects of substance use on the newborn, although further studies are needed. In conclusion, in order to detect exposure to substances of abuse during the third trimester of pregnancy, the use of different alternative matrices (meconium, hair, placenta) to minimize the invasiveness of collecting samples and to obtain information about chronic consumption compared to the matrices used traditionally (blood and urine) is recommended.

This thesis investigates lattice compression of polynomial matrices over finite fields. For an m x n matrix, the goal of lattice compression is to find an m x (m+k) matrix, for some relatively small k, such that the lattice span of two matrices are equivalent. For any m x n polynomial matrix with degree bound d, it can be compressed by multiplying by a random n x (m+k) matrix B with degree bound s. In this thesis, we prove that there is a positive probability that L(A)=L(AB) with k(s+1)=\Theta(\log(md)). This is shown to hold even when s=0 (i.e., where B is a matrix of constants). We also design a competitive probabilistic lattice compression algorithm of the Las Vegas type that has a positive probability of success on any input and requires O~(nm^{\theta-1}B(d)) field operations.

The analysis of similarity of matrices over fields, as well as integral domains which are not fields, is a classical problem in Linear Algebra and has received considerable attention. A related problem is that of simultaneous similarity of matrices. Many interesting algebraic questions that arise in such problems are discussed by Shmuel Friedland[1]. A special case of this problem is that of Simultaneous Unitary Similarity of hermitian matrices, which we describe as follows: Given a collection of m ordered pairs of similar n×n hermitian matrices denoted by {(Hl,Dl)}ml=1, 1. determine if there exists a unitary matrix U such that UHl U∗ = Dl for all l, 2. and in the case where a U exists, find such a U, (where U∗is the transpose conjugate of U ).The problem is easy for m =1. The problem is challenging for m > 1.The problem stated above is the algorithmic version of the problem of classifying hermitian matrices upto unitary similarity. Any problem involving classification of matrices up to similarity is considered to be “wild”[2]. The difficulty in solving the problem of classifying matrices up to unitary similarity is a indicator of, the toughness of problems involving matrices in unitary spaces [3](pg, 44-46 ).Suppose in the statement of the problem we replace the collection {(Hl,Dl)}ml=1, by a collection of m ordered pairs of complex square matrices denoted by {(Al,Bl) ml=1, then we get the Simultaneous Unitary Similarity problem for square matrices. Suppose we consider k ordered pairs of complex rectangular m ×n matrices denoted by {(Yl,Zl)}kl=1, then the Simultaneous Unitary Equivalence problem for rectangular matrices is the problem of finding whether there exists a m×m unitary matrix U and a n×n unitary matrix V such that UYlV ∗= Zl for all l and in the case they exist find them. In this thesis we describe algorithms to solve these problems. The Simultaneous Unitary Similarity problem for square matrices is challenging for even a single pair (m = 1) if the matrices involved i,e A1,B1 are not normal. In an expository article, Shapiro[4]describes the methods available to solve this problem by arriving at a canonical form. That is A1 or B1 is used to arrive at a canonical form and the matrices are unitarily similar if and only if the other matrix also leads to the same canonical form. In this thesis, in the second chapter we propose an iterative algorithm to solve the Simultaneous Unitary Similarity problem for hermitian matrices. In each iteration we either get a step closer to “the simple case” or end up solving the problem. The simple case which we describe in detail in the first chapter corresponds to finding whether there exists a diagonal unitary matrix U such that UHlU∗= Dl for all l. Solving this case involves defining “paths” made up of non-zero entries of Hl (or Dl). We use these paths to define an equivalence relation that partitions L = {1,…n}. Using these paths we associate scalars with each Hl(i,j) and Dl(i,j)denoted by pr(Hl(i,j)) and pr(Dl(i,j)) (pr is used to indicate that these scalars are obtained by considering products of non-zero elements along the paths from i,j to their class representative). Suppose i (I Є L)belongs to the class[d(i)](d(i) Є L) we denote by uisol a modulus one scalar expressed in terms of ud(i) using the path from i to d( i). The free variable ud(i) can be chosen to be any modulus one scalar. Let U sol be a diagonal unitary matrix given by U sol = diag(u1 sol , u2 sol , unsol ). We show that a diagonal U such that U HlU∗ = Dl exists if and only if pr(Hl(i, j)) = pr(Dl(i, j))for all l, i, j and UsolHlUsol∗= Dl. Solving the simple case sets the trend for solving the general case. In the general case in an iteration we are looking for a unitary U such that U = blk −diag(U1,…, Ur) where each Ui is a pi ×p (i, j Є L = {1,… , r}) unitary matrix such that U HlU ∗= Dl. Our aim in each iteration is to get at least a step closer to the simple case. Based on pi we partition the rows and columns of Hl and Dl to obtain pi ×pj sub-matrices denoted by Flij in Hl and Glij in D1. The aim is to diagonalize either Flij∗Flij Flij∗ and a get a step closer to the simple case. If square sub-matrices are multiples of unitary and rectangular sub-matrices are zeros we say that the collection is in Non-reductive-form and in this case we cannot get a step closer to the simple case. In Non- reductive-form just as in the simple case we define a relation on L using paths made up of these non-zero (multiples of unitary) sub-matrices. We have a partition of L. Using these paths we associate with Flij and (G1ij ) matrices denoted by pr(F1ij) and pr(G1ij) respectively where pr(F1ij) and pr(G1ij) are multiples of unitary. If there exist pr(Flij) which are not multiples of identity then we diagonalize these matrices and move a step closer to the simple case and the given collection is said to be in Reduction-form. If not, the collection is in Solution-form. In Solution-form we identify a unitary matrix U sol = blk −diag(U1sol , U2 sol , …, Ur sol )where U isol is a pi ×pi unitary matrix that is expressed in terms of Ud(i) by using the path from i to[d(i)]( i Є [d(i)], d(i) Є L, Ud(i) is free). We show that there exists U such that U HlU∗ = Dl if and only if pr((Flij) = pr(G1ij) and U solHlU sol∗ = Dl. Thus in a maximum of n steps the algorithm solves the Simultaneous Unitary Similarity problem for hermitian matrices. In the second chapter we also relate the Simultaneous Unitary Similarity problem for hermitian matrices to the simultaneous closed system evolution problem for quantum states. In the third chapter we describe algorithms to solve the Unitary Similarity problem for square matrices (single ordered pair) and the Simultaneous Unitary Equivalence problem for rectangular matrices. These problems are related to the Simultaneous Unitary Similarity problem for hermitian matrices. The algorithms described in this chapter are similar in flow to the algorithm described in the second chapter. This shows that it is the fact that we are looking for unitary similarity that makes these forms possible. The hermitian (or normal)nature of the matrices is of secondary importance. Non-reductive-form is the same as in the hermitian case. The definition of the paths changes a little. But once the paths are defined and the set L is partitioned the definitions of Reduction-form and Solution-form are similar to their counterparts in the hermitian case. In the fourth chapter we analyze the worst case complexity of the proposed algorithms. The main computation in all these algorithms is that of diagonalizing normal matrices, partitioning L and calculating the products pr((Flij) = pr(G1ij). Finding the partition of L is like partitioning an undirected graph in the square case and partitioning a bi-graph in the rectangular case. Also, in this chapter we demonstrate the working of the proposed algorithms by running through the steps of the algorithms for three examples. In the fifth and the final chapter we show that finding if a given collection of ordered pairs of normal matrices is Simultaneously Similar is same as finding if the collection is Simultaneously Unitarily Similar. We also discuss why an algorithm to solve the Simultaneous Similarity problem, along the lines of the algorithms we have discussed in this thesis, may not exist. (For equations pl refer the pdf file)

Reproduction de : Thèse de doctorat : informatique : Grenoble, INPG : 1989. / Titre provenant de l'écran-titre. Bibliogr. p. 163-168.

Reproduction de : Thèse de doctorat : informatique et mathématiques appliquées : Grenoble 1 : 1987. / Titre provenant de l'écran-titre. Bibliogr. p. 149-151.

We present a fast direct algorithm for the solution of linear systems arising from elliptic equations. We extend the work of Xia et al. (2009) on combining the multifrontal method with hierarchical matrices. We offer a more geometric interpretation of that approach, extend it in two dimensions to the unstructured mesh case, and detail an adaptive decomposition procedure for selectively refined meshes. Linear time complexity is shown for a quasi-uniform grid and demonstrated via numerical results for the adaptive algorithm. We also provide an extension to three dimensions with proven linear complexity but a more practical variant with slightly worse scaling is also described. / text

published_or_final_version / Mathematics / Master / Master of Philosophy

published_or_final_version / Computer Science and Information Systems / Master / Master of Philosophy