Mathematics of
Computer Algbebra
and Analsysis


Project Highlights
Sample Papers
Team Members
Partner Organizations
Seminar Series
Mprime Home

Project Highlights

Last updated December 17, 2012.

This page is being redesigned so that it contains highlights of our industrial contributions.
Research highlights can be found under Sample Papers.

Descriptions of Industrial Contributions

POLY : A new polynomial data structure for Maple

Michael Monagan and Roman Pearce, Simon Fraser University

We demonstrate how a new data structure for sparse distributed polynomials in the Maple kernel significantly accelerates several key Maple library routines. The POLY data structure and its associated kernel operations (degree, coeff, subs, has, diff, eval, ...) are programmed for high scalability with very low overhead. This enables polynomial to have tens of millions of terms, increases parallel speedup in existing routines and dramatically improves the performance of high level Maple library routines.

Sparse Polynomial Multiplication and Divison in Maple 14.

Michael Monagan and Roman Pearce, Simon Fraser University

We report on new codes for sparse multivariate polynomial multiplication and division over the integers that we have integrated into Maple 14's expand and divide commands. We describe our the polynomial data structure and compare it with the one used by Maple. We then presents some benchmarks comparing our software with that in the Magma, Maple, Singular, Trip and Pari computer algebra systems and also illustrating how multivariate polynomial factorization benefits from our improvements to polynomial multiplication and division.

The Impact of Social Interactions on the Spread of HIV Infection among Injection Drug Users: A Cellular Automaton Model

Vahid Dabbaghian, Kristina Vasarhelyi, Natasha Richardson, Viviane Dias Lima, Peter Borwein, and Alexander Rutherford

Injection drug users (IDU) who share needles are at high risk for contracting human immunodeficiency virus (HIV) infection. Social and behavioral influences that promote needle sharing can, therefore, impact HIV transmission. HIV spreads rapidly in IDU communities and interventions that target needle sharing have had variable results. We constructed a cellular automaton model to study the dynamics of the HIV epidemic in an IDU community in the presence of influences that promote or discourage sharing of used needles. Peer influences are tracked by a counter associated with each individual who begins to stop sharing needles once a threshold level of influences from neighbours is reached. The simulated epidemic exhibited a strong non-linear response to social influence on needle-sharing behaviour. An epidemic phase diagram for the parameter space of social influences revealed two states for HIV prevalence. The endemic state above the phase transition curve is characterised by stable HIV prevalence of approximately 35%. Parameter values below the phase transition curve lead to the extinct state. This is simalar to a herd immunity effect; the epidemic in this region of the parameter space is eventually driven to extinction. The behaviour of the system implies that public health interventions aimed at reducing needle sharing may have little effect if coverage is limited. If coverage exceeds phase transition threshold, interventions are expected to be highly effective in stemming HIV epidemics in IDU communities.

Computing Polynomial Greatest Common Divisors over Algebraic Function Fields.

Michael Monagan and Mahdi Javadi, Simon Fraser University

We report on a new GCD code that our Computer Algebra group at Simon Fraser University has integrated into the development version of Maple. We present some benchmarks illustrating the improvements and make some comments on the implications of this work.

Toward high-performance computer algebra with Maple.

Xin Li, Marc Moreno Maza, Raqueeb Rasheed and Eric Schost, University of Western Ontario

In this report, we present Modpn, a Maple library dedicated to fast arithmetic for multivariate polynomials. The main objective of Modpn is to provide highly efficient routines for supporting the implementation of modular methods in Maple. We demonstrate in this work that Modpn allows us to re-implement core operations in Maple bringing huge performance increases and offering to Maple the ability of solving problems which were previously out of reach. The core operation that we benchmark in this report is solving systems of two non-linear polynomial equations.

The ConstructibleSets and ParametricSystems modules of the Regular Chains library in Maple.

Changbo Chen, Marc Moreno Maza, Francois Lemaire, Wei Pan, Liyun Li and Yuzhen Xie, University of Western Ontario

Solving systems of parametric polynomial equations symbolically is in demand for an increasing number of applications such as program verification, optimization and the study of dynamical systems. Groebner bases and triangular decompositions are classical techniques for processing parametric systems. Recent research in our MITACS project has focused on enhancing theories and algorithms to meet the practical requirement of these systems. The ParametricSystemTools is a new module of the RegularChainslibrary in Maple which implements "comprehensive triangular decompositions" (CTD), our new algorithmic approach for studying polynomial systems with parameters. Constructible sets are the geometrical objects naturally attached to triangular decompositions, as polynomial ideals are the algebraic concept underlying the computation of Groebner bases. The ConstructibleSetTools of the RegularChains library is, up to our knowledge, the first computer algebra package providing constructible set as a type and exporting a rich collection of operations for manipulating constructible sets. Meanwhile, this module provides routines in support of solving parametric polynomial systems.