Matrix calculations underlie countless problems in science, mathematics, and engineering. When the involved matrices are highly structured, displacement operators can be used to accelerate fundamental operations such as matrix-vector multiplication. In this thesis, we provide an introduction to the theory of displacement operators and study the interplay between displacement and natural matrix constructions involving direct sums, Kronecker products, and blocking. We also investigate the algebraic behavior of displacement operators, developing results about invertibility and kernels.

In 1981 the author submitted that "many of the (then) more recent school syllabuses remain disjointed and give expression still to a school mathematics course as step-by-step progression through a list of disparate topics". The position has not changed. It is not yet generally accepted that there can no longer be an accepted body of mathematical knowledge that needs to be taught. The rapid development of new technology and the introduction of the microcomputer should enable the 'modern' mathematics of the early 1960's to enhance the mathematical experiences of pupils in a practical and comprehensible way and prompt a new style of teaching and learning mathematics. There is, however, a fundamental core of mathematics which must inevitably find a place in the school mathematics curriculum. In Part I of the thesis the emphasis is on a method of presentation of certain key topics which illustrate the basic pattern of a group structure. Former complications at school level of putting plane geometry on a logical footing have to be avoided. The use of complex numbers highlights significant and sometimes rather difficult geometrical ideas. In Part 11 the author attempts to show how some of these ideas may be presented to extend the basic pattern to that of linear algebra. The work culminates in Part III with the use of linear complex algebra to present more vividly the symmetries of the Platonic solids. The author anticipates the realistic presentation of the aesthetic side of 3-dimensional geometry and takes a look at its possible presentation through the medium of the microcomputer. At this early stage of the development of the ideas to be discussed, there can be no formal testing of the results by quantitative analysis. Evaluation of the viability of the proposals will be qualitative and the comments of 'critical academic friends' will be included. The originality demanded of a piece of research goes beyond the exposition. Here it will consist of new insights into ideas appropriate to senior pupils in schools and a rewriting of existing material often thought to be beyond their scope. The work is supported by suggested lesson sequences, transcripts of recorded presentations, and examples of students' work. Subsequent development must face the question of assessment and evaluation at sixth-form level of the proposed new style of teaching mathematics. The author makes some suggestions in the concluding chapter.

For many matrix algebras, every associative automorphism is inner. We discuss results by Đoković that a non-associative Lie automorphism φ of a triangular matrix algebra Tₙ over a connected unital commutative ring, is of the form φ(A)=SAS⁻¹ + τ(A)I or φ(A)=−SJ Aᵀ JS⁻¹ + τ(A)I, where S ∈ Tₙ is invertible, J is an antidiagonal permutation matrix, and τ is a generalized trace. We incorporate additional arguments by Cao that extended Đoković’s result to unital commutative rings containing nontrivial idempotents. Following this we develop new results for Lie isomorphisms of block upper-triangular matrix algebras over unique factorization domains. We build on an approach used by Marcoux and Sourour to characterize Lie isomorphisms of nest algebras over separable Hilbert spaces. We find that these Lie isomorphisms generally follow the form φ = σ + τ where σ is either an associative isomorphism or the negative of an associative anti-isomorphism, and τ is an additive mapping into the center, which maps commutators to zero. This echoes established results by Martindale for simple and prime rings. / Graduate

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.