A fundamental task of algebraists is to classify algebraic structures. For example, the classification of finite groups has been widely studied and has benefited from the use of computational tools. Advances in computer power have allowed researchers to attack problems never possible before. In this dissertation, algorithms for <I>noncommutative</I> algebra, when <I>ab</I> is not necessarily equal to <I>ba</I>, are examined with practical implementations in mind. Different encodings of <I>associative algebras</I> and <I>modules</I> are also considered. To effectively analyze these algorithms and encodings, the <I>encoding neutral</I> analysis framework is introduced. This framework builds on the ideas used in the arithmetic complexity framework defined by Winograd. Results in this dissertation fall into three categories: analysis of algorithms, experimental results, and novel algorithms. Known algorithms for calculating the Jacobson radical and Wedderburn decomposition of associative algebras are reviewed and analyzed. The algorithms are compared experimentally and a recommendation for algorithms to use in computer algebra systems is given based on the results. A new algorithm for constructing the Drinfel'd double of finite dimensional Hopf algebras is presented. The performance of the algorithm is analyzed and experiments are performed to demonstrate its practicality. The performance of the algorithm is elaborated upon for the special case of group algebras and shown to be very efficient. The <tt>MeatAxe</tt> algorithm for determining whether a module contains a proper submodule is reviewed. Implementation issues for the <tt>MeatAxe</tt> in an encoding neutral environment are discussed. A new algorithm for constructing endomorphism rings of modules defined over path algebras is presented. This algorithm is shown to have better performance than previously used algorithms. Finally, a linear time algorithm, to determine whether a quotient of a path algebra, with a known Gröbner basis, is finite or infinite dimensional is described. This algorithm is based on the Aho-Corasick pattern matching automata. The resulting automata is used to efficiently determine the dimension of the algebra, enumerate a basis for the algebra, and reduce elements to normal forms. / Ph. D.

There are discussed implementational aspects of the special-purpose computer algebra system FELIX designed for computations in constructive algebra. In particular, data types developed for the representation of and computation with commutative and non-commutative polynomials are described. Furthermore, comparisons of time and memory requirements of different polynomial representations are reported.

In this work, an interdisciplinary approach has been adopted for the study of: • teaching strategies of an Intelligent Tutoring System, in the paradigm of multiple teaching strategies, and • the use of Computer Algebra Systems (CAS) in teaching problem solving in university mathematics. As a result, the SIMTA (Styles Implemented by Methods Tactics Actions) theoretical framework has been developed to support and sustain teaching strategies in the paradigm of multiple teaching strategies. TeLoDe (TEaching Linear Ordinary Differential Equations), is a prototype Intelligent Tutoring System, teaching the solution of linear second order differential equations with constant coefficients in a novel way. This novel way, which has been empirically tested, has been achieved by augmenting Maple and represents an alternative use of CASs where the human lecturer and Maple are interlocked in a symbiotic and interdependent manner. In SIMTA, the contemporary concept of teaching strategy is rethought and proposed to be viewed at two fundamental levels: • the organisational level • and the operational level. The organisational level deals with the structure of the teaching strategy whereas the operational level deals with the manifestation of that structure. In SIMTA the organisational level is represented by a triple generic structure, method, tactic(s), action(s). A method is a mechanism for structuring the subject matter (e.g. analogy, examples, generalisation, specialisation). Likewise, a tactic is a mechanism for facilitating the interaction (e.g. explicit interaction, implicit interaction). An action is a low level activity such as display this message, ask this question. In SIMTA, the exact manifestation of the above generic structures (analogies, examples, implicit interaction, explicit interaction) depends on the concept of style: different styles result in different manifestations of the same generic structures. Thus, in SIMTA the concept of multiple teaching strategies is seen as merely a collection of teaching strategies manifested under the same style. These strategies operate with the aim of offering alternative representations of the same task at hand and ensuring that the lea~er is active by activating, directing and maintaining exploration. To help demonstrate the feasibility of SIMTA, two styles, the expository style and the , guided discovery style have been formed. The expository style draws on Ausubel's theory of meaningfulleaming, whereas, the guided discovery style draws on Bruner's work. These styles have been implemented in TeLoDe. TeLoDe, incorporates a teaching strategy module, based on a style, and declarative knowledge. Its purpose is threefold: (i) to serve as a research tool for the SIMTA framework, (ii) to serve as a prototype, demonstrating clearly how a 'second generation' CAS which undertakes the procedural aspect of mathematics allowing the human tutor to concentrate on its conceptual aspect, could be developed, (iii) to demonstrate how Maple and human lecturers are given clear roles which are, nevertheless, interdependent in carrying out the teaching of university mathematics. Two small-scale empirical studies were carried out in order to test SIMTA and TeLoDe respectively. The first study involved lecturers whereas the second study was carried out in a classroom environment. The results found from these studies demonstrate that TeLoDe has a potential as a teaching tool for problem solving in university mathematics in a novel way.

<p> Partial Evaluation (PE) is a program transformation technique that generates a specialized version of a program with respect to a subset of its inputs. PE is an automatic approach to program generation and meta-programming. This thesis presents a method of partially evaluating Maple programs using a fully online methodology.</p> <p> We present an implementation called MapleMIX, and use it towards two goals. Firstly we show how MapleMIX can be used to generate optimized versions of generic programs written in Maple. Secondly we use MapleMIX to mine symbolic computation code for residual theorems, which we present as precise solutions to parametric problems encountered in Computer Algebra Systems.</p> <p> The implementation of MapleMIX has been modularized using a high-level intermediate language called M-form. Several syntax transformations from Maple to M-form make it an ideal representation for performing program specialization. Many specialization techniques have been explored including a novel online approach to handle partially-static data structures and an on-the-fly syntax transformation technique that propagates loop context into the body of dynamic conditionals.</p> / Thesis / Master of Science (MSc)

In this thesis we study algorithms for computing normal forms for matrices of Ore polynomials while controlling coefficient growth. By formulating row reduction as a linear algebra problem, we obtain a fraction-free algorithm for row reduction for matrices of Ore polynomials. The algorithm allows us to compute the rank and a basis of the left nullspace of the input matrix. When the input is restricted to matrices of shift polynomials and ordinary polynomials, we obtain fraction-free algorithms for computing row-reduced forms and weak Popov forms. These algorithms can be used to compute a greatest common right divisor and a least common left multiple of such matrices. Our fraction-free row reduction algorithm can be viewed as a generalization of subresultant algorithms. The linear algebra formulation allows us to obtain bounds on the size of the intermediate results and to analyze the complexity of our algorithms. We then make use of the fraction-free algorithm as a basis to formulate modular algorithms for computing a row-reduced form, a weak Popov form, and the Popov form of a polynomial matrix. By examining the linear algebra formulation, we develop criteria for detecting unlucky homomorphisms and determining the number of homomorphic images required.

Since their conception by Collins in 1975, Cylindrical Algebraic Decompositions (CADs) have been used to analyse the real algebraic geometry of systems of polynomials. Applications for CAD technology range from quantifier elimination to robot motion planning. Although of great use in practice, the CAD algorithm was shown to have doubly exponential complexity with respect to the number of variables for the problem, which limits its use for large examples. Due to the high complexity of CAD, much work has been done to improve its performance. In this thesis new advances will be discussed that improve the practical efficiency of CAD for a variety of problems, with a new complexity result for one set of algorithms. A new invariance condition, truth table invariance (TTICAD), and two algorithms to construct TTICADs are given and shown to be highly efficient. The idea of restricting the output of CADs, allowing for greater efficiency, is formalised as sub-decompositions and two particular ideas are investigated in depth. Efficient selection of various formulation choices for a CAD problem are discussed, with a collection of heuristics investigated and machine learning applied to assist in choosing an optimal heuristic. The mathematical expression of a problem is shown to be of great importance, with preconditioning and reformulation investigated. Finally, these advances are collected together in a general framework for applying CAD in an efficient manner to a given problem. It is shown that their combination is not cumulative and care must be taken. To this end, a prototype software CADassistant is described to help users take advantage of the advances without knowledge of the underlying theory. The effects of the various advances are demonstrated through a guiding example originally considered by Solotareff, which describes the approximation of a cubic polynomial by a linear function. Naïvely applying CAD to the problem takes 916.1 seconds of construction (from which a solution can easily be derived), which is reduced to 20.1 seconds by combining various advances from this thesis.

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.

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.

In this thesis we study algorithms for computing normal forms for matrices of Ore polynomials while controlling coefficient growth. By formulating row reduction as a linear algebra problem, we obtain a fraction-free algorithm for row reduction for matrices of Ore polynomials. The algorithm allows us to compute the rank and a basis of the left nullspace of the input matrix. When the input is restricted to matrices of shift polynomials and ordinary polynomials, we obtain fraction-free algorithms for computing row-reduced forms and weak Popov forms. These algorithms can be used to compute a greatest common right divisor and a least common left multiple of such matrices. Our fraction-free row reduction algorithm can be viewed as a generalization of subresultant algorithms. The linear algebra formulation allows us to obtain bounds on the size of the intermediate results and to analyze the complexity of our algorithms. We then make use of the fraction-free algorithm as a basis to formulate modular algorithms for computing a row-reduced form, a weak Popov form, and the Popov form of a polynomial matrix. By examining the linear algebra formulation, we develop criteria for detecting unlucky homomorphisms and determining the number of homomorphic images required.

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.