Algorithms for Calculating Cyclotomic Polynomials
Andrew Arnold and Michael Monagan
We present two algorithms for calculating cyclotomic polynomials. The first algorithm calculates a cyclotomic polynomial as a quotient of sparse power series; the second algorithm retrieves the coefficients sequentially in a forgetful manner. We also show data we've gathered on the heights and lengths of cyclotomic polynomials.
A Dynamical System Model of the Social Influence in a Community of Drug Users
The compartmental model has been developed to reproduce the current epidemic of drug use. We have presented both qualitative and quantitative analysis by means of Bifurcation analysis, sensitivity parameters and simulation. In order to obtain a better approximation for the Bifurcation curves, we have compared the Bifurcation curve obtained by Cellular Automata version and compartmental model. Then we indicate for what values of the parameters, drug use problem goes extinct or becomes epidemic. This shows the potential value of the model for decisionmakers.
The long-term research goal is to make the model more realistic. In order to achieve our goal, the transition parameters should not be taken as constant but they should be represented as functions taking into account the history of individuals drug use.
Cellular Automata: Visualisation Beyond the Obvious
In his book "A New Kind of Science", Stephen Wolfram laid the foundations for an experimental approach to Cellular Automata (CA). Indeed, that is a strength of CA: they are visible, almost tangible, and they lend themselves very much for playing around with. To facilitate this, a generic CA class for MATLAB was implemented, which, of course, has the ability to visualise the iterations (up to 3D CA). Cute and amazing as these pictures and animations may be, the goal is to understand the properties of a CA.
A scientist showing images of CA iterations can be compared to a biologist showing pictures of his/her field work and organism of interest: although the individual pictures can be insightful, they do not convey understanding, whereas the diagram depicting the stages in the life history of this organism, does.
This poster is as much a question as it is a proposal: what could or should we show the world about CA? As one first step, the generic CA class is being extended with a visualisation of the relationship between CA and System Dynamics Modeling.
A Visualization Tool for a 3-Dimensional System of Differential Equations in Maple
Yuanxun Bill Bao and Michael Monagan
System of differential equations(DEs) plays an essential role in the study of dynamical systems and mathematical modeling. An important tool for studying system of DEs is using the direction field.
The direction field gives a graphical representation of the behavior of the system without solving it analytically. In this poster and demo, we present some new options to DEplot3d command in Maple, which solves a 3-dimensional system of DEs numerically and plot the solution curve(s). In an effort to enhance the visualization of the system, we create the direction field using a set of 3D arrows and provide animations for the direction field so that the dynamics of each point are well captured. We will also give some examples of interesting dynamical systems using this new visualization tool.
Nestings and crossings in four combinatorial families
The combinatorial families of matchings, set partitions, permutations and graphs can each be represented by a series of vertices along a horizontal line with arcs connecting them. Such a representation is referred to as an arc annotated sequence. A natural crossing and nesting structure arises in each of these representations, and remarkably enough, equidistribution between these two statistics has been shown for both matchings and partitions. To show this, tools such as RSK and several bijections are required. Furthermore, other useful bijections to lattice paths, and Ferrers diagrams give additional information, and aid the enumeration for each of the four families according to these two statistics.
Finding Possible Ancestral Genomes through Computational Optimization
Saehee Choi and Ryan Coghlan
Finding the genetic sequences of extinct animals is a longstanding problem in genetics, one compounded by the fact DNA decays over time until it is eventually no longer reliable. Due to this even if DNA samples of long extinct animals are found, one cannot reliably sequence their DNA. One possible way to get around this problem is to reconstruct these DNA sequences, or ancestral genomes, by comparing the DNA of the extinct animal's ancestors.
We describe a reconstruction technique that relies on a property of binary matrices called the Consecutive Ones' Property. A matrix has the Consecutive Ones' Property if there is an arrangement of its columns such that all the ones in each row are consecutive. By converting a set of candidate genomes to a binary matrix and using optimization techniques which rely on this property, we are then able to construct all possible ancestral genomes for the extinct species. In our work we extend these previous algorithms to the case where in a given row a single zero may appear between any two ones, allowing the algorithms to be run on new and higher resolution DNA sequences. Using these techniques we then applied our methods to various DNA sequences.
Polynomial Factorization over Algebraic Function Fields
We present an efficient algorithm for factoring a multivariate polynomial over an algebraic function field with several parameters and field extensions. Our algorithm uses Hensel lifting and extends the EEZ algorithm of Wang which was designed for factorization over Q. We also give a multivariate p-adic lifting algorithm which uses sparse interpolation. This enables us to avoid using poor bounds on the size of the integer coefficients in the factorization of f when using Hensel lifting. We have implemented our algorithm in Maple 13. We provide timings demonstrating the efficiency of our algorithm.
An investigation of a nonlocal hyperbolic model for self-organization of biological groups
Abstract to be announced
Parallel Sparse Polynomial Multiplication
Given two sparse polynomials f and g we want to compute their product. One of the fastest methods is Johnson's algorithm (1974), which uses a binary heap to simultaneously merge each fi*g for i=1..#f. In this poster we describe how Johnson's algorithm was parallelized for multicore processors with a shared cache. Our program is up to six times faster than the sequential algorithm on a Core i7 quad core processor.
Expanding HAART to Control the Spread of HIV among Injection Drug Users: A Mathematical Model
Natasha Richardson, Alexander R Rutherford, Bojan Ramadanovic, B Marshall, A Kaida, P Bastani, A van der Waall, Viviane D Lima, Robert Hogg, Julio SG Montaner, P Borwein, K Vasarhelyi
There is growing interest in Highly Active Antiretroviral Therapy (HAART) as a potential tool for controlling HIV transmission at the population level. Earlier, we described how HIV epidemics driven by risk behaviours among injection drug users (IDU) can become extinct in the presence of behavioural influences discouraging needle sharing (Dabbaghian, et al., IAS 2008, Mexico City). Here we use mathematical modelling to determine levels of HAART coverage required to eliminate risk-behaviour driven HIV epidemics among IDU.
We previously defined parameter subsets of behavioural influences, that generate sustained or extinct epidemics with rapid phase transition in a cellular-automaton/compartmental model of an IDU community in Vancouver. We incorporate HiAART into this model and test 10 coverage levels from 0 to 100%. Three scenarios considered are: I. HAART without behavioural intervention, II. HAART with recipients stopping needle-sharing upon initiating therapy, and III. same as scenario 2 but earlier initiation of HAART.
At 100% coverage HAART eliminates all epidemics. However, HIV prevalence increases between 40% and 90% coverage if no behavioural intervention is applied. If HAART-recipients stop needle sharing, more epidemics are eliminated. This is even more pronounced if HAART is initiated early.
Our results suggest that HAART could play a role in combating the HIV epidemic among injection drug users. In Vancouver's Downtown Eastside and other I DUcommunities, it is often difficult to recruit individuals to HAART and to ensure that they maintain the rigid therapy schedule. Therefore, future versions of the model will be used to evaluate effects of adherence, incomplete viral load suppression and changes in risk behaviour in the presence of HAART.
Using Cellular Automata to Model the Spread of HIV in a Population of Injection Drug Users
Vancouver's Downtown Eastside is home to a large community of injection drug users . An HIV epidemic, driven primarily by needle sharing, exists within this community. Highly Active Antiretroviral Therapy (HAART) suppresses the HIV virus within an individual and can prevent HIV transmission. The cellular automata model presented here considers a population of needle-sharing injection drug users. In the model, certain HIV+ individuals are put on HAART with a particular probability. Results of various simulations are presented and possible implications are discussed.
Visualizing Groups in Maple
Asif Zaman and Michael Monagan
A finite group has much structure, and effectively representing this information in a visual manner can be challenging. One can compute the entire multiplication table (Cayley table) of G, identify isomorphic forms of the same group, or determine all the subgroups of G and arrange them in a lattice of inclusion. Using Dimino’s Algorithm, we can efficiently generate all the elements of the group. To find all subgroups of a group, we use the Cyclic Extension Method. With these algorithms, we have implemented each of these new prospective additions and more for the group and upcoming FiniteGroups package for Maple.