The Probabilistic Method was primarily used in Combinatorics and pioneered by Erdös Pai, better known to Westerners as Paul Erdos in the 1950s. The probabilistic method is a powerful tool for solving many problems in discrete mathematics, combinatorics and also in graph .theory. It is also very useful to solve problems in number theory, combinatorial geometry, linear algebra and real analysis. More recently, it has been applied in the development of efficient algorithms and in the study of various computational problems.Broadly, the probabilistic method is somewhat opposite of the extremal graph theory. Instead of considering how a graph can behave in the extreme, we consider how a collection of graphs behave on 'average' where by we can formulate a probability space. The method allows one to prove the existence of a structure with particular properties by defining an appropriate probability space of structures and show that the desired properties hold in the space with positive probability.(please see PDF for complete abstract)

The dissertation uses a number of mathematical formula including de Rham cohomology with complex coefficients to state and prove extension of Brieskorn's Lemma theorem.

Dans cette thèse nous présentons la formalisation de trois résultats principaux que sont la forme normale de Jordan d’une matrice, le théorème de Bolzano-Weierstraß et le théorème de Perron-Frobenius. Pour la formalisation de la forme normale de Jordan nous introduisons différents concepts d’algèbre linéaire tel que les matrices diagonales par blocs, les matrices compagnes, les facteurs invariants, ... Ensuite nous définissons et développons une théorie sur les espaces topologiques et métriques pour la formalisation du théorème de Bolzano-Weierstraß. La formalisation du théorème de Perron-Frobenius n’est pas terminée. La preuve de ce théorème utilise des résultats d’algèbre linéaire, mais aussi de topologie. Nous montrerons comment les précédents résultats seront réutilisés. / In this thesis we present the formalization of three principal results that are the Jordan normal form of a matrix, the Bolzano-Weierstraß theorem, and the Perron-Frobenius theorem. To formalize the Jordan normal form, we introduce many concepts of linear algebra like block diagonal matrices, companion matrices, invariant factors, ... The formalization of Bolzano-Weierstraß theorem needs to develop some theory about topological space and metric space. The Perron-Frobenius theorem is not completly formalized. The proof of this theorem uses both algebraic and topological results. We will show how we reuse the previous results.

Álgebra Linear e particularmente a teoria das matrizes e dos sistemas lineares são tópicos da Matemática que têm aplicações, não só dentro da própria Matemática, mas também em várias outras áreas do conhecimento humano. Neste trabalho, além de estudar estas teorias, estudamos algumas de suas aplicações na área da Economia, como em modelos lineares de produção, modelos de Markov para emprego e modelos de benefícios obtidos no pagamento de impostos após realizarmos contribuições filantrópicas. / Linear Algebra and particularly matrices and linear systems theory are topics in Mathematics with many applications in several branches of science. In this work we study this theory and some of its applications in Economy as in linear models of production, Markov models of employment and tax benefits of charitable contributions.

Cette thèse est composée de deux axes principaux, le premier portant sur le chiffrement homomorphe et le second sur l’algèbre linéaire creuse sur corps finis. Avec l’essor des technologies de communication et en particulier d’internet, de nouveaux protocoles de chiffrement sont développés. En particulier, le besoin de systèmes de chiffrement permettant de manipuler les données chiffrées tout en assurant leur sécurité. C’est dans ce contexte que des systèmes de chiffrement homomorphe sont développés, ces protocoles permettent d’effectuer des calculs avec des données chiffrées. La sécurité de ce type système repose sur l’ajout de bruit aux messages à chiffrer. Ce bruit augmente avec chaque opération effectuée, mais il ne doit pas dépasser un certain seuil. Pour contourner ce problème, une technique nommée bootstrapping est utilisée permettant de réduire le bruit d’un chiffré. Les bootstrappings sont le goulot d’étranglement lors des calculs sur des données chiffrées, il est important d’en faire le moins possible. Or la quantité de bootstrappings à faire est déterminée par la nature des calculs à effectuer ainsi que du protocole de chiffrement utilisé.C’est dans ce contexte que notre travail intervient, nous proposons une méthode effective pour réduire le nombre bootstrappings basé sur la programmation linéaire en nombre entier. Cette méthode s’adapte à un grand nombre de protocoles de chiffrement. De plus, nous effectuons une analyse de la complexité de ce problème en montrant qu’il est APX-complet et nous fournissons un algorithme d’approximation.La résolution de système linéaire sur corps finis est une brique de calcul essentielle dans de nombreux problèmes de calcul formel. En particulier, beaucoup de problèmes produisent des matrices comprenant un grand nombre de zéros, on dit qu’elles sont creuses. Les meilleurs algorithmes permettant de résoudre ce type de système linéaire creux sont des algorithmes dits itératifs. L’opération fondamentale de ces algorithmes itératifs est la multiplication de la matrice par un vecteur ou une matrice dense. Afin d’obtenir les meilleures performances, il est important de tenir compte des propriétés (SIMD, multicoeurs, hiérarchie des caches ....) des processus modernes .C’est dans ce contexte que notre travail intervient, nous étudions la meilleure façon d’implanter efficacement cette opération sur les processeurs récents.Nous proposons un nouveau format permettant de tenir compte du grand nombre de +- 1 présents dans une matrice.Nous proposons une implantation parallèle basée sur le paradigme du vol de tâche offrant un meilleur passage à l’échelle que le parallélisme par threads.Nous montrons comment exploiter au mieux les instructions SIMD des processeurs dans les différentes opérations.Finalement, nous proposons une méthode efficace permettant d’effectuer cette opération lorsque le corps finis est multiprécision (les éléments sont stockés sur plusieurs mots machine) en ayant recours au système de représentation RNS. / This thesis is composed of two independent parts.The first one is related to homomorphic encryption and the second part deal with sparse linear algebra on finite fields.Homomorphic encryption extends traditional encryption in the sense that it becomes feasible to perform operations on ciphertexts, without the knowledge of the secret decryption key. As such, it enables someone to delegate heavy computations on his sensitive data to an untrusted third party, in a secure way. More precisely, with such a system, one user can encrypt his sensitive data such that the third party can evaluate a function on the encrypted data, without learning any information on the underlying plain data. Getting back the encrypted result, the user can use his secret key to decrypt it and obtain, in clear, the result of the evaluation of the function on his sensitive plain data. For a cloud user, the applications are numerous, and reconcile both a rich user experience and a strong privacy protection.The first fully homomorphic encryption (FHE) scheme, able to handle an arbitrary number of additions and multiplications on ciphertexts, has been proposed by Gentry in 2009.In homomorphic encryption schemes, the executed function is typically represented as an arithmetic circuit. In practice, any circuit can be described as a set of successive operation gates, each one being either a sum or a product performed over some ring.In Gentry’s construction, based on lattices, each ciphertext is associated with some noise, which grows at each operation (addition or multiplication) done throughout the evaluation of the function. When this noise reaches a certain limit, decryption is not possible anymore.To overcome this limitation, closely related to the number of operations that the HE.Eval procedure can handle, Gentry proposed in a technique of noise refreshment called“bootstrapping”.The main idea behind this bootstrapping procedure is to homomorphically run the decryptionprocedure of the scheme on the ciphertext, using an encrypted version of the secret key. In this context, our contribution is twofold. We first prove that the lmax-minimizing bootstrapping problem is APX-complete and NP-complete for lmax ≥ 3. We then propose a new method to determine the minimal number of bootstrappings needed for a given FHE scheme and a given circuit.We use linear programming to find the best outcome for our problem. The main advantage of our method over the previous one is that it is highly flexible and can be adapted for numerous types of homomorphic encryption schemes and circuits.Computing a kernel element of a matrix is a fundamental kernel in many computer algebra and cryptography algorithms. Especially, many applications produces matrices with many matrix elements equals to 0.Those matrices are named sparse matrices. Sparse linear algebra is fundamentally relying on iterative approaches such as Wiedemann or Lanczos. The main idea is to replace the direct manipulation of a sparse matrix with its Krylov subspace. In such approach, the cost is therefore dominated by the computation of the Krylov subspace, which is done by successive product of a matrix by a vector or a dense matrix.Modern processor unit characteristics (SIMD, multicores, caches hierarchy, ...) greatly influence algorithm design.In this context our work deal with the best approach to design efficient implementation of sparse matrix vector product for modern processors.We propose a new sparse matrix format dealing with the many +-1 matrix elements to improve performance.We propose a parallel implementation based on the work stealing paradigm that provide a good scaling on multicores architectures.We study the impact of SIMD instructions on sparse matrix operations.Finally, we provide a modular arithmetic implementation based on residue number system to deal with sparse matrix vector product over multiprecision finite fields.

Covariance matrices are ubiquitous in computational sciences, typically describing the correlation of elements of large multivariate spatial data sets. For example, covari- ance matrices are employed in climate/weather modeling for the maximum likelihood estimation to improve prediction, as well as in computational ground-based astronomy to enhance the observed image quality by filtering out noise produced by the adap- tive optics instruments and atmospheric turbulence. The structure of these covariance matrices is dense, symmetric, positive-definite, and often data-sparse, therefore, hier- archically of low-rank. This thesis investigates the performance limit of dense matrix computations (e.g., Cholesky factorization) on covariance matrix problems as the number of unknowns grows, and in the context of the aforementioned applications. We employ recursive formulations of some of the basic linear algebra subroutines (BLAS) to accelerate the covariance matrix computation further, while reducing data traffic across the memory subsystems layers. However, dealing with large data sets (i.e., covariance matrices of billions in size) can rapidly become prohibitive in memory footprint and algorithmic complexity. Most importantly, this thesis investigates the tile low-rank data format (TLR), a new compressed data structure and layout, which is valuable in exploiting data sparsity by approximating the operator. The TLR com- pressed data structure allows approximating the original problem up to user-defined numerical accuracy. This comes at the expense of dealing with tasks with much lower arithmetic intensities than traditional dense computations. In fact, this thesis con- solidates the two trends of dense and data-sparse linear algebra for HPC. Not only does the thesis leverage recursive formulations for dense Cholesky-based matrix al- gorithms, but it also implements a novel TLR-Cholesky factorization using batched linear algebra operations to increase hardware occupancy and reduce the overhead of the API. Performance reported of the dense and TLR-Cholesky shows many-fold speedups against state-of-the-art implementations on various systems equipped with GPUs. Additionally, the TLR implementation gives the user flexibility to select the desired accuracy. This trade-off between performance and accuracy is, currently, a well-established leading trend in the convergence of the third and fourth paradigm, i.e., HPC and Big Data, when moving forward with exascale software roadmap.

Notre recherche porte sur la question de l'enseignement de l'algèbre linéaire au niveau universitaire, plus précisément sur les applications linéaires en Classes Préparatoires aux Grandes Écoles. La théorie des situations didactiques avec la sémiotique de Peirce fournissent le cadre principal de nos travaux et nous permettent d'analyser les raisonnements produits par les étudiants en situation d'interrogation orale. Nous proposons dans un premier temps des éléments d'analyse épistémologique concernant le rôle des applications linéaires dans l'émergence de l'algèbre linéaire. Puis nous présentons dans une optique d'analyse didactique les principaux éléments de la sémiotique de Peirce et son algébrisation par le treillis des classes de signes. Nous complétons alors le modèle d'analyse des raisonnements de Bloch et Gibel et proposons un outil d'analyse sémiotique, le diagramme sémantique. Nous utilisons cet outil pour une analyse sémiotique locale a priori d'une situation mathématique. Cette analyse met en évidence le lien entre les premiers signes et premières actions de la situation et la sémiose qui en découle. Nous procédons ensuite à une analyse des raisonnements produits par des étudiants en situation d'interrogation orale, dite « classique ». Cette analyse confirme le lien entre l'absence de niveaux de milieu adidactiques et la difficulté sémantique d'organiser les objets en situation de preuve. Puis, nous expérimentons une situation d'interrogation orale de telle sorte que les niveaux de milieu adidactiques soient riches et stabilisés. L'analyse des raisonnements produits dans cette situation nous permet de montrer que les étudiants sollicitent un point de vue sémantique sur les objets utile lors de leurs validations et contrôles. Ces trois moments de notre travail confirment l'importance du discours et des pratiques heuristiques dans le cadre de l'algèbre linéaire. / Our research is concerned with the teaching of linear algebra at the university level. More precisely, it focuses on the teaching of linear transformations in Classes Préparatoires aux Grandes Écoles. The theory of didactical situations, jointly with Peirce’s semiotics, constitute the main theoretical framework of our works and allow us to analyse student’s reasoning in situations of oral evaluation. Firstly, we put forward some epistemological aspects highlighting the links between linear transformations and the emergence of linear algebra. Then, with a didactical objective, we outline the main features of Perice’s semiotics and its algebraization with the treillis of sign’s categories. Hence, we can enhance the model of analysis for reasoning processes of Bloch and Gibel and build a tool for semiotic analysis called semantic diagram. We illustrate the use of this tool by conducting a local semiotic a priori analysis of a mathematical situation. This analysis highlight the link between the first signs and actions of the situation and the resulting semiosis. Next, we analyse some students’ reasonings produced during oral evaluations said « classical ». This analysis confirms the link between the lack of an adidactical milieu and the semantic difficulty to organize and articulate the objects and signs in a proof situation. Then we experiment a situation of oral evaluation in which the adidactical milieus are rich enough and stabilized. The analysis of the reasoning process conducted in this experimental situation allows us to show that, in this case, the students rely on a semantic point of view on the objects to produce their validations and controls their productions. These three different moments of our research attest the importance of the heuristic practices and discourse in the field of linear algebra.

Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2014-09-22T13:24:09Z No. of bitstreams: 2 Nogueira, Leonardo Bernardes.pdf: 4758026 bytes, checksum: 81be665ec243b277cb285cc686730f04 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2014-09-23T11:17:17Z (GMT) No. of bitstreams: 2 Nogueira, Leonardo Bernardes.pdf: 4758026 bytes, checksum: 81be665ec243b277cb285cc686730f04 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2014-09-23T11:17:17Z (GMT). No. of bitstreams: 2 Nogueira, Leonardo Bernardes.pdf: 4758026 bytes, checksum: 81be665ec243b277cb285cc686730f04 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2013-03-15 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This paper begins with a brief history about the development of vector spaces and linear transformations, then presents fundamental concepts for the study of Linear Algebra, with greater focus on linear operators in the R2 space. Through examples it explores a wide range of operators in R2 in order to show other applications of matrices in high school and prepares the ground for the presentation a version of Spectral Theorem for selfadjoint operators in R2, which says that for every operator self-adjoint T : E!E in finite dimensional vector space with inner product, exists an orthonormal basis fu1; : : : ;ung E formed by eigenvectors of T, and culminates with their applications on the study of conic sections, quadratic forms and equations of second degree in x and y; on the study of operators associated to quadratic forms, a version of Spectral Theorem could be called as The Main Axis Theorem albeit this nomenclature is not used in this paper. Thereby summarizing a study made by Lagrange in "Recherche d’arithmétique ", between 1773 and 1775, which he studied the property of numbers that are the sum of two squares. Thus he was led to study the effects of linear transformation with integer coefficients in a quadratic form in two variables. / Este trabalho inicia-se com um breve embasamento histórico sobre o desenvolvimento de espaços vetoriais e transformações lineares. Em seguida, apresenta conceitos fundamentais básicos, que formam uma linguagem mínima necessária para falar sobre Álgebra Linear, com enfoque maior nos operadores lineares do plano R2. Através de exemplos, explora-se um vasto conjunto de transformações no plano a fim de mostrar outras aplicações de matrizes no ensino médio e prepara o terreno para a apresentação do Teorema Espectral para operadores auto-adjuntos de R2. Este Teorema diz que para todo operador auto-adjunto T : E!E, num espaço vetorial de dimensão finita, munido de produto interno, existe uma base ortonormal fu1; : : : ;ung E formada por autovetores de T. O trabalho culmina com aplicações sobre o estudo das secções cônicas, formas quadráticas e equações do segundo grau em x e y, no qual o Teorema Espectral se traduz como Teorema dos Eixos Principais, embora essa nomenclatura não seja usada nesse trabalho (para um estudo mais aprofundado neste tema ver [3], [4], [5], [7]). Retomando assim um estudo feito por Joseph Louis Lagrange em "Recherche d’Arithmétique", entre 1773 e 1775, no qual estudou a propriedade de números que são a soma de dois quadrados. Assim, foi levado a estudar os efeitos das transformações lineares com coeficientes inteiros numa forma quadrática de duas variáveis.

We begin by introducing matroids in the context of finite collections of vectors from a vector space over a specified field, where the notion of independence is linear independence. Then we will introduce the concept of a matroid invariant. Specifically, we will look at the Tutte polynomial, which is a well-defined two-variable invariant that can be used to determine differences and similarities between a collection of given matroids. The Tutte polynomial can tell us certain properties of a given matroid (such as the number of bases, independent sets, etc.) without the need to manually solve for them. Although the Tutte polynomial gives us significant information about a matroid, it does not uniquely determine a matroid. This thesis will focus on non-isomorphic matroids that have the same Tutte polynomial. We call such matroids Tutte-equivalent, and we will study the characteristics needed for two matroids to be Tutte-equivalent. Finally, we will demonstrate methods to construct families of Tutte-equivalent matroids.

This bachelor thesis shows a way to classify second order symmetric tensors in the Lorentz metric. Some basic prerequisite about indefinite and definite algebra is introduced, such as the Jordan form, indefinite inner products, the Segre type, and the Minkowski space. There are also some results concerning the invariant 2-spaces of a symmetric tensor and a different approach on how to classify second order symmetric tensor.