This dissertation reviews the theory of fast matrix multiplication from a multilinear-algebraic point of view, as well as recent fast matrix multiplication algorithms based on discrete Fourier transforms over nite groups. To this end, the algebraic approach is described in terms of group algebras over groups satisfying the triple product Property, and the construction of such groups via uniquely solvable puzzles. The higher order singular value decomposition is an important decomposition of tensors that retains some of the properties of the singular value decomposition of matrices. However, we have proven a novel negative result which demonstrates that the higher order singular value decomposition yields a matrix multiplication algorithm that is no better than the standard algorithm. / Mathematical Sciences / M. Sc. (Applied Mathematics)

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Nesta dissertação é apresentada uma modelagem analítica para o processo evolucionário formulado pela Teoria da Evolução por Endossimbiose representado através de uma sucessão de estágios envolvendo diferentes interações ecológicas e metábolicas entre populações de bactérias considerando tanto a dinâmica populacional como os processos produtivos dessas populações. Para tal abordagem é feito uso do sistema de equações diferenciais conhecido como sistema de Volterra-Hamilton bem como de determinados conceitos geométricos envolvendo a Teoria KCC e a Geometria Projetiva. Os principais cálculos foram realizados pelo pacote de programação algébrica FINSLER, aplicado sobre o MAPLE. / This work presents an analytical approach for modeling the evolutionary process formulated by the Serial Endosymbiosis Theory represented by a succession of stages involving different metabolic and ecological interactions among populations of bacteria considering both the population dynamics and production processes of these populations. In such approach we make use of systems of differential equations known as Volterra-Hamilton systems as well as some geometric concepts involving the KCC Theory and the Projective Geometry. The main calculations were performed by the computer algebra software FINSLER based on MAPLE.

Dans cette thèse, nous nous sommes intéressés à l'analyse locale de systèmes différentiels linéaires singulièrement perturbés et de systèmes de Pfaff complètement intégrables et multivariés à croisements normaux. De tels systèmes ont une vaste littérature et se retrouvent dans de nombreuses applications. Cependant, leur résolution symbolique est toujours à l'étude. Nos approches reposent sur l'état de l'art de la réduction formelle des systèmes linéaires singuliers d'équations différentielles ordinaires univariées (ODS). Dans le cas des systèmes différentiels linéaires singulièrement perturbés, les complications surviennent essentiellement à cause du phénomène des points tournants. Nous généralisons les notions et les algorithmes introduits pour le traitement des ODS afin de construire des solutions formelles. Les algorithmes sous-jacents sont également autonomes (par exemple la réduction de rang, la classification de la singularité, le calcul de l'indice de restriction). Dans le cas des systèmes de Pfaff, les complications proviennent de l'interdépendance des multiples sous-systèmes et de leur nature multivariée. Néanmoins, nous montrons que les invariants formels de ces systèmes peuvent être récupérés à partir d'un ODS associé, ce qui limite donc le calcul à des corps univariés. De plus, nous donnons un algorithme de réduction de rang et nous discutons des obstacles rencontrés. Outre ces deux systèmes, nous parlons des singularités apparentes des systèmes différentiels univariés dont les coefficients sont des fonctions rationnelles et du problème des valeurs propres perturbées. Les techniques développées au sein de cette thèse facilitent les généralisations d'autres algorithmes disponibles pour les systèmes différentiels univariés aux cas des systèmes bivariés ou multivariés, et aussi aux systèmes d''equations fonctionnelles. / In this thesis, we are interested in the local analysis of singularly-perturbed linear differential systems and completely integrable Pfaffian systems in several variables. Such systems have a vast literature and arise profoundly in applications. However, their symbolic resolution is still open to investigation. Our approaches rely on the state of art of formal reduction of singular linear systems of ordinary differential equations (ODS) over univariate fields. In the case of singularly-perturbed linear differential systems, the complications arise mainly from the phenomenon of turning points. We extend notions introduced for the treatment of ODS to such systems and generalize corresponding algorithms to construct formal solutions in a neighborhood of a singularity. The underlying components of the formal reduction proposed are stand-alone algorithms as well and serve different purposes (e.g. rank reduction, classification of singularities, computing restraining index). In the case of Pfaffian systems, the complications arise from the interdependence of the multiple components which constitute the former and the multivariate nature of the field within which reduction occurs. However, we show that the formal invariants of such systems can be retrieved from an associated ODS, which limits computations to univariate fields. Furthermore, we complement our work with a rank reduction algorithm and discuss the obstacles encountered. The techniques developed herein paves the way for further generalizations of algorithms available for univariate differential systems to bivariate and multivariate ones, for different types of systems of functional equations.

Dans cette thèse, nous étudions des algorithmes pour un problème de recherche de relations à une ou plusieurs variables. Il généralise celui de calculer une solution à un système d’équations linéaires modulaires sur un anneau de polynômes, et inclut par exemple le calcul d’approximants de Hermite-Padé ou d’interpolants bivariés. Plutôt qu’une seule solution, nous nous attacherons à calculer un ensemble de générateurs possédant de bonnes propriétés. Précisément, l’entrée de notre problème consiste en un module de dimension finie spécifié par l’action des variables sur ses éléments, et en un certain nombre d’éléments de ce module ; il s’agit de calculer une base de Gröbner du modules des relations entre ces éléments. En termes d’algèbre linéaire, l’entrée décrit une matrice avec une structure de type Krylov, et il s’agit de calculer sous forme compacte une base du noyau de cette matrice. Nous proposons plusieurs algorithmes en fonction de la forme des matrices de multiplication qui représentent l’action des variables. Dans le cas d’une matrice de Jordan,nous accélérons le calcul d’interpolants multivariés sous certaines contraintes de degré ; nos résultats pour une forme de Frobenius permettent d’accélérer le calcul de formes normales de matrices polynomiales univariées. Enfin, dans le cas de plusieurs matrices denses, nous accélérons le changement d’ordre pour des bases de Gröbner d’idéaux multivariés zéro-dimensionnels. / In this thesis, we study algorithms for a problem of finding relations in one or several variables. It generalizes that of computing a solution to a system of linear modular equations over a polynomial ring, including in particular the computation of Hermite- Padéapproximants and bivariate interpolants. Rather than a single solution, we aim at computing generators of the solution set which have good properties. Precisely, the input of our problem consists of a finite-dimensional module given by the action of the variables on its elements, and of some elements of this module; the goal is to compute a Gröbner basis of the module of syzygies between these elements. In terms of linear algebra, the input describes a matrix with a type of Krylov structure, and the goal is to compute a compact representation of a basis of the nullspace of this matrix. We propose several algorithms in accordance with the structure of the multiplication matrices which specify the action of the variables. In the case of a Jordan matrix, we accelerate the computation of multivariate interpolants under degree constraints; our result for a Frobenius matrix leads to a faster algorithm for computing normal forms of univariate polynomial matrices. In the case of several dense matrices, we accelerate the change of monomial order for Gröbner bases of multivariate zero-dimensional ideals.

Cette thèse est consacrée aux méthodes symboliques de résolution locale des systèmes différentiels linéaires à coefficients dans K = C((x)), le corps des séries de Laurent, sur un corps effectif C. Plus précisément, nous nous intéressons aux algorithmes effectifs de réduction formelle. Au cours de la réduction, nous sommes amenés à introduire des extensions algébriques du corps de coefficients K (extensions algébriques de C, ramifications de la variable x) afin d’obtenir une structure plus fine. Du point de vue algorithmique, il est préférable de retarder autant que possible l’introduction de ces extensions. Dans ce but, nous développons un nouvel algorithme de réduction formelle qui utilise l’anneau des endomorphismes du système, appelé « eigenring », afin de se ramener au cas d’un système indécomposable sur K. En utilisant la classification formelle donnée par Balser-Jurkat-Lutz, nous déduisons la structure de l’eigenring d’un système indécomposable. Ces résultats théoriques nous permettent de construire une décomposition sur le corps de base K qui sépare les différentes parties exponentielles du système et permet ainsi d’isoler dans des sous-systèmes, indécomposables sur K, les différentes extensions de corps qui peuvent apparaître afin de les traiter séparément. Dans une deuxième partie, nous nous intéressons à l’algorithme de Miyake pour la réduction formelle. Celle-ci est basée sur le calcul du poids et d’une suite de Volevic de la matrice de valuation du système. Nous donnons des interprétations en théorie de graphe et en algèbre tropicale du poids et suites de Volevic, et obtenons ainsi des méthodes de calculs efficaces sur le plan pratique, à l’aide de la programmation linéaire. Ceci complète une étape fondamentale dans l’algorithme de réduction de Miyake. Ces différents algorithmes sont implémentés sous forme de librairies pour le logiciel de calcul formel Maple. Enfin, nous présentons une discussion sur la performance de l’algorithme de réduction avec l’eigenring ainsi qu’une comparaison en terme de temps de calcul entre notre implémentation de l’algorithme de réduction de Miyake par la programmation linéaire et ceux de Barkatou et Pflügel. / This thesis is devoted to symbolic methods for local resolution of linear differential systems with coefficients in K = C((x)), the field of Laurent series, on an effective field C. More specifically, we are interested in effective algorithms for formal reduction. During the reduction, we are led to introduce algebraic extensions of the field of coefficients K (algebraic extensions of C, ramification of the variable x) in order to obtain a finer structure. From an algorithmic point of view, it is preferable to delay as much as possible the introduction of these extensions. To this end, we developed a new algorithm for formal reduction that uses the ring of endomorphisms of the system, called "eigenring". Using the formal classification given by Balser-Jurkat-Lutz, we deduce the structure of the eigenring of an indecomposable system. These theoretical results allow us to construct a decomposition on the base field K that separates the different exponential parts of the system and thus allows us to isolate, in indecomposable subsystems in K, the different algebraic extensions that can appear in order to treat them separately. In a second part, we are interested in Miyake’s algorithm for formal reduction. This algorithm is based on the computation of the Volevic weight and numbers of the valuation matrix of the system. We provide interpretations in graph theory and tropical algebra of the Volevic weight and numbers, and thus obtain practically efficient methods using linear programming. This completes a fundamental step in the Miyake reduction algorithm. These different algorithms are implemented as libraries for the computer algebra software Maple. Finally, we present a discussion on the performance of the reduction algorithm using the eigenring as well as a comparison in terms of timing between our implementation of Miyake’s reduction algorithm by linear programming and the algorithms of Barkatou and Pflügel.

Computer Algebra Systems (CAS) have been changing the mathematics instruction requirements for many years. Since the tendency of using CAS in mathematics instruction has been rising for decades and reports have often been positive, the implementation of notebook classes seems to be the consequent next step of mathematics instruction supported by computers. Experiences that have been made with the use of CAS in PC-rooms can be transformed directly into the classroom. Hence the use of CAS is no longer limited to certain rooms. The permanent availability of the notebook with installed CAS offers the chance to realize these concepts that have already been approved with the use of CAS so far. The following speech shall show what these concepts could look like and that the use of notebooks is not only the further development of teaching in PC-classes. Examples from personal experience in teaching will especially show meanders and thought-provoking impulses in order to support teachers finding their way into teaching mathematics instruction in notebook classes successfully. Please allow me to point out two things in the beginning: (1) Yes, I am a vehement supporter of the use of notebooks (and the use of CAS in particular) in mathematics instruction. (2) No, I do not believe that teachers who have chosen another path (or at least partly) are teaching badly.

Der Vortrag zeigt, wie aus einem mathematisch-technischen Sachverhalt ein didaktisch begründetes Unterrichtsbeispiel abgeleitet werden kann und stellt die unterrichtlichen Nutzungsmöglichkeiten vor. Für die digitale Bildbearbeitung spielt die Interpolation eine wichtige Rolle und dient hierbei als Berechnungsverfahren für die Bildgrößenänderung. Interpolation ist ein Approximationsverfahren, bei dem z.B. zu Punkten mit bekannten Koordinaten eine Funktion berechnet wird, die alle diese Punkte erfüllt. Mit dieser Funktion können dann beliebige Zwischenwerte berechnet werden. Dabei bestimmt die Zahl der Datenpunkte die Zahl der notwendigen Polynomterme. Wegen ihrer mathematischen Eigenschaften werden häufig Polynome benutzt. Die Lösung der Aufgabe führt über ein lineares Gleichungssystem zur Bestimmung der Koeffizienten des Polynoms. Der erste Teil des Vortrages befasst sich mit der beispielhaften Darstellung der bikubischen Interpolation und deren Realisierung mittels MathCAD. Es wird gezeigt, wie aus den konkreten Schwärzungswerten eines Digitalbildes für eine Bildvergrößerung ein zu interpolierender Zwischenwert für einen neuen Bildpunkt berechnet wird. Der MathCAD-Wortschatz wird angegeben und notwendige didaktische Vereinfachungen werden beschrieben. Im zweiten Teil werden die Nutzung des Themas als Unterrichtsgegenstand in der Sekundarstufe II in seiner Wechselwirkung zwischen digitaler Bildbearbeitung, Mathematik und Informatik (Nutzung von MathCAD) erläutert, die thematischen Verflechtungsmöglichkeiten aufgezeigt und das didaktische Potential beleuchtet.

Recently, there has been an increasing interest in high school mathematics education, especially in the teaching and learning of calculus. For example, studies conducted by Bressoud (2010); Judson and Nishimori (2005); Koh and Divaharan (2011); and St. Jarre (2008) all looked at how to improve the understanding of calculus students and what roles the educator must take to ensure that their students are successful. The purpose of this study was to determine if there was a significant difference between instruction using computer algebra system (CAS) compared to instruction using the graphing calculator in high school calculus on students’ conceptual and procedural understanding. This study explored and compared two different types of instruction based on the use of two different types of technology, CAS and graphing calculator. The total population for this study consisted of 333 students. There were 187 students classified as using the graphing calculator and 146 students classified as using CAS. The data for this study were collected from four Advanced Placement (AP) calculus AB courses from high schools in Florida. The study used observations and two sets of calculus tasks in order to gather data. The research questions for this study looked at comparing the grades of students categorized based on the type of instruction received during the learning of calculus. The statistical procedure that was used was a simple oneway analysis of variance (ANOVA). The results indicated that there was no significant difference between the two types of instruction on the students’ procedural knowledge, iii however, there was statistical significance on the students’ conceptual understanding in favor of the CAS students. The study introduces a framework on how to obtain information about the effects of different types of instruction on students’ understanding of calculus. The results of this study contribute in assisting teachers and future researchers on how to analyze student work in order to obtain information about the students’ conceptual and procedural understanding of first semester calculus.

Cette thèse porte sur trois problèmes en combinatoire algébrique effective et algorithmique.Les premières parties proposent une approche alternative aux bases de Gröbner pour le calcul des invariants secondaires des groupes de permutations, par évaluation en des points choisis de manière appropriée. Cette méthode permet de tirer parti des symétries du problème pour confiner les calculs dans un quotient de petite dimension, et ainsi d'obtenir un meilleur contrôle de la complexité algorithmique, en particulier pour les groupes de grande taille. L'étude théorique est illustrée par de nombreux bancs d'essais utilisant une implantation fine des algorithmes. Un prérequis important est la génération efficace de vecteurs d'entiers modulo l'action d'un groupe de permutation, dont l'algorithmique fait l'objet d'une partie préliminaire.La quatrième partie cherche à déterminer, pour un certain quotient naturel d'une algèbre de Hecke affine, quelles spécialisations des paramètres aux racines de l'unité donne un comportement non générique.Finalement, la dernière partie présente une conjecture sur la structure d'une certaine $q$-déformation des polynômes harmoniques diagonaux en plusieurs paquets de variables pour la famille infinie de groupes de réflexions complexes.Tous ces chapitres s'appuient fortement sur l'exploration informatique, et font l'objet de multiples contributions au logiciel Sage. / This thesis concerns algorithmic approaches to three challenging problems in computational algebraic combinatorics.The firsts parts propose a Gröbner basis free approach for calculating the secondary invariants of a finite permutation group, proceeding by using evaluation at appropriately chosen points. This approach allows for exploiting the symmetries to confine the calculations into a smaller quotient space, which gives a tighter control on the algorithmic complexity, especially for large groups. The theoretical study is illustrated by extensive benchmarks using a fine implementation of algorithms. An important prerequisite is the generation of integer vectors modulo the action of a permutation group, whose algorithmic constitute a preliminary part of the thesis.The fourth part of this thesis is determining for a certain interesting quotient of an affine Hecke algebra exactly which root-of-unity specialization of its parameter lead to non-generic behavior.Finally, the last part presents a conjecture on the structure of certain q-deformed diagonal harmonics in many sets of variables for the infinite family of complex reflection groups.All chapters proceed widely by computer exploration, and most of established algorithms constitute contributions of the software Sage.

Le calcul rigoureux vise à produire des représentations certifiées pour les solutions de nombreux problèmes, notamment en analyse fonctionnelle, comme des équations différentielles ou des problèmes de contrôle optimal. En effet, certains domaines particuliers comme l’ingénierie des systèmes critiques ou les preuves mathématiques assistées par ordinateur ont des exigences de fiabilité supérieures à ce qui peut résulter de l’utilisation d’algorithmes relevant de l’analyse numérique classique.Notre objectif consiste à développer des algorithmes à la fois efficaces et validés / certifiés, dans le sens où toutes les erreurs numériques (d’arrondi ou de méthode) sont prises en compte. En particulier, nous recourons aux approximations polynomiales rigoureuses combinées avec des méthodes de validation a posteriori à base de points fixes. Ces techniques sont implémentées au sein d’une bibliothèque écrite en C, ainsi que dans un développement de preuve formelle en Coq, offrant ainsi le plus haut niveau de confiance, c’est-à-dire une implémentation certifiée.Après avoir présenté les opérations élémentaires sur les approximations polynomiales rigoureuses, nous détaillons un nouvel algorithme de validation pour des approximations sous forme de séries de Tchebychev tronquées de fonctions D-finies, qui sont les solutions d’équations différentielles ordinaires linéaires à coefficients polynomiaux. Nous fournissons une analyse fine de sa complexité, ainsi qu’une extension aux équations différentielles ordinaires linéaires générales et aux systèmes couplés de telles équations. Ces méthodes dites symboliques-numériques sont ensuite utilisées dans plusieurs problèmes reliés : une nouvelle borne sur le nombre de Hilbert pour les systèmes quartiques, la validation de trajectoires de satellites lors du problème du rendez-vous linéarisé, le calcul de polynômes d’approximation optimisés pour l’erreur d’évaluation, et enfin la reconstruction du support et de la densité pour certaines mesures, grâce à des techniques algébriques. / Rigorous numerics aims at providing certified representations for solutions of various problems, notably in functional analysis, e.g., differential equations or optimal control. Indeed, specific domains like safety-critical engineering or computer-assisted proofs in mathematics have stronger reliability requirements than what can be achieved by resorting to standard numerical analysis algorithms. Our goal consists in developing efficient algorithms, which are also validated / certified in the sense that all numerical errors (method or rounding) are taken into account. Specifically, a central contribution is to combine polynomial approximations with a posteriori fixed-point validation techniques. A C code library for rigorous polynomial approximations (RPAs) is provided, together with a Coq formal proof development, offering the highest confidence at the implementation level.After providing basic operations on RPAs, we focus on a new validation algorithm for Chebyshev basis solutions of D-finite functions, i.e., solutions of linear ordinary differential equations (LODEs) with polynomial coefficients. We give an in-depth complexity analysis, as well as an extension to general LODEs, and even coupled systems of them. These symbolic-numeric methods are finally used in several related problems: a new lower bound on the Hilbert number for quartic systems; a validation of trajectories arising in the linearized spacecraft rendezvous problem; the design of evaluation error efficient polynomial approximations; and the support and density reconstruction of particular measures using algebraic techniques.