Groebner bases have many applications in mathematics, science, and engineering. This dissertation deals with the algorithmic aspects of computing these bases. The dissertation begins with a brief introduction of fundamental concepts about Groebner bases. Following this a discussion of various implementation issues are discussed. Much of the practical difficulties of using Groebner basis algorithms and techniques stems from the high computational complexity. It is shown that the algorithmic complexity of computing a Groebner basis primarily stems from the calculation of normal forms. This is established by studying run profiles of various computations. This leads to two options of making Groebner basis techniques more practical. They are to reduce the complexity by developing new algorithms (heuristics) or reduce running time of normal form calculations by introducing concurrency. The later approach is taken in the remainder of the dissertation where a multithreaded normal form algorithm is presented and discussed. It is shown with a simple example that the new algorithm demonstrates a speedup and scalability. The algorithm also has the advantage of being completion strategy independent. We conclude with an outline of future research involving the new algorithm.

The Fourier transform is one of the most useful tools in science and engineering and can be expanded to multi-dimensions and curvilinear coordinates. Multidimensional Fourier transforms are widely used in image processing, tomographic reconstructions and in fact any application that requires a multidimensional convolution. By examining a function in the frequency domain, additional information and insights may be obtained. In this thesis, the development of a symbolic computer algebra toolbox to compute two dimensional Fourier transforms in polar coordinates is discussed. Among the many operations implemented in this toolbox are different types of convolutions and procedures that allow for managing the toolbox effectively. The implementation of the two dimensional Fourier transform in polar coordinates within the toolbox is shown to be a combination of two significantly simpler transforms. The toolbox is also tested throughout the thesis to verify its capabilities.

This thesis presents a new algorithm for computing the Hermite form of a polynomial matrix. Given a nonsingular n by n matrix A filled with degree d polynomials with coefficients from a field, the algorithm computes the Hermite form of A in expected number of field operations similar to that of matrix multiplication. The algorithm is randomized of the Las Vegas type.

At a time of transition, when the increasing availability and affordability of Computer Algebra Systems (CAS) presents mathematics educators with new challenges, this thesis explores two facets of students’ abilities and understanding that impact on the use of CAS in teaching and learning mathematics. In this thesis, these are called ‘Algebraic Insight’ and ‘Effective Use of CAS’. A framework is presented and described for each construct and then the frameworks are explored within the context of a course in introductory calculus, taught by the researcher to a class of 21 undergraduate tertiary students. Algebraic Insight is the subset of Symbol Sense required when using CAS for the mathematical solution phase of problem solving. The framework breaks Algebraic Insight into two aspects: ability to Link Representations (symbolic, numeric, graphical); and Algebraic Expectation, the cognitive skill required to monitor symbolic work (comparable to arithmetic estimation for monitoring numeric work). The framework of Effective Use of CAS is also divided into two aspects: Technical, using syntax and program features; and Personal, the willingness to use CAS in a judicious manner.

The Fourier transform is one of the most useful tools in science and engineering and can be expanded to multi-dimensions and curvilinear coordinates. Multidimensional Fourier transforms are widely used in image processing, tomographic reconstructions and in fact any application that requires a multidimensional convolution. By examining a function in the frequency domain, additional information and insights may be obtained. In this thesis, the development of a symbolic computer algebra toolbox to compute two dimensional Fourier transforms in polar coordinates is discussed. Among the many operations implemented in this toolbox are different types of convolutions and procedures that allow for managing the toolbox effectively. The implementation of the two dimensional Fourier transform in polar coordinates within the toolbox is shown to be a combination of two significantly simpler transforms. The toolbox is also tested throughout the thesis to verify its capabilities.

Systems of polynomial equations often have symmetries. In solving such a system using Buchberger's algorithm, the symmetries are neglected. Incorporating symmetries into the solution process enables us to solve larger problems than with Buchberger's algorithm alone. This paper presents a method that shows how this can be achieved and also gives an algorithm that brings together continuously parameterized symmetries with Buchberger's algorithm.

No description available.

This contribution describes an experiment carried out by a team within the ReMath (Representing Mathematics with Digital Media) European Project (http://remath.cti.gr). Within this project six digital dynamic artefacts (DDAs) have been developed, thirteen experiments have been planned (Artigue & al., 2007) and carried out, analysis of the collected data are still in progress. In this contribution, we focus on the case of the Aplusix DDA (http://aplusix.imag.fr), from the point in which the designers deliver their product to the team in charge of planning the experiment, up to the point in which the artefact is experimented within the ReMath project.

This contribution describes an experiment carried out by a team within the ReMath (Representing Mathematics with Digital Media) European Project (http://remath.cti.gr). Within this project six digital dynamic artefacts (DDAs) have been developed, thirteen experiments have been planned (Artigue & al., 2007) and carried out, analysis of the collected data are still in progress. In this contribution, we focus on the case of the Aplusix DDA (http://aplusix.imag.fr), from the point in which the designers deliver their product to the team in charge of planning the experiment, up to the point in which the artefact is experimented within the ReMath project.

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.