CECM Home > Events > CECM Annual Summer Meeting 2006 > Program > Poster Abstracts

### Poster Abstracts

###### Digital Inpainting Using the Ginzburg-Landau Equation

*Wilson Au*

The Ginzburg-Landau equation was originally introduced in 1950 to model the phase transitions in superconductors. In this poster, we present a digital inpainting approach based on the Ginzburg-Landau equation. This approach was based on the remarkable relationship between the steady state solutions to the Ginzburg-Landau equation and the image intensity in image processing, which was first discovered by Grossauer and Scherzer in 2003.

###### The Snow Equation

*Pouya Bastani*

The 'Snow Equation' is a mathematical model recently proposed by T. Tiedje et al. to describe the ablation hollows or suncups that form on the surface of snowfields in summer. This poster outlines the main ingredients of the model partial differential equation (PDE) and shows how different factors contribute to the formation of suncup patterns. The numerical schemes used to study the dynamics of the PDE is described along with our present numerical results and observations.

###### Solving Linear Systems of Equations Over Cyclotomic Fields

*Liang Chen*

Solving linear systems of equations over cyclotomic fields by directly applying Gauss Elimilation is inefficient. We consider two approaches, namely, Chinese remaindering and p-adic lifting. Both of the approaches use rational reconstruction to recover the rational coefficients in solution vectors.

###### A Finite Groups Package

*Vahid Dabbaghian-Abdoly and Greg Fee*

As part of our MITACS research project at SFU, with MapleSoft, we are building a library of finite groups for Maple. This library contains:

- A finite presentation of all non isomorphic small groups of order up to 200.
- A permutation representation of classical matrix groups of moderate size.
- Finite simple groups including classical and exceptional groups of Lie type, and sporadic groups.
- Functions for creating groups of some particular classes such as: cyclic, symmetric, alternating, dihedral, etc.

###### New features of the GraphTheory package

*Al Erickson, Simon Lo and Michael Monagan*

We are building a graph theory package which is expected to be distributed with Maple 11. In addition to features presented at the Maple conference in 2005 and others being presented this year, we have developed a package for generating random graphs, including random trees and random networks, a package of various special graphs with hardcoded drawings, and an implementation of a graph isomorphism algorithm which uses the all pairs distance matrix to reduce the search space.

In this poster (and demonstration) we will show

- an animation for visualizing Kruskal's mimimal spanning tree algorithm,
- an algorithm for generating random regular graphs with almost uniform distribution,
- a hamiltonian cycle for the soccer ball graph and how we drew it,
- pictures of various special graphs in the package, and
- give a description of our graph isomorphism test.

###### Two New Radial Basis Functions

*Greg Fee*

The 3 most common radial basis functions for two dimensional interpolation are:

- the Gaussian exp(-r^2)
- the Multiquadric (1+r^2)^(1/2)
- the Thin Plate Spline r^2*ln(r)

We have discovered 2 others, which are:

- the tanh-rule weight function sech(r)^2
- the tanh-sinh-rule weight function sech(Pi/2*sinh(t))^2*cosh(t)

###### Demo of the Maple GraphTheory package

*Mohammad Ghebleh and Michael Monagan*

*Computer Algebra Group, Simon Fraser University*

Our mitacs project at SFU was asked by MapleSoft to develope a new graph theory package for Maple to replace the old "networks" package. This we began in the Fall of 2004. Our package presently supports directed and undirected graphs, weighted or unweighted but not multigraphs. We have implemented many graph algorithms, e.g., for planarity testing, graph vertex/edge coloring, the TSP, max-flow, Tutte polynomials. Many of these commands are available from a menu from inside Maple which helps to make the package quick and easy to use. We are presently implementing a graph isomorphism test which uses the all pairs distance matrix to prune the search, and animations for visualizing graph algorithms for application in teaching.

In this demo we will show the following facilties.

- Different ways to input and output graphs, including support
for other graph packages and LaTeX.

- Facilities for drawing graphs and highlighting features of graphs
such as vertex colorings and hamiltonian cycles.

- A library of special graphs and tools for creating random graphs.

Our graph drawing algorithm models the graph as a set of repelling "electrons" with edges modeled by "springs". This leads to a dense system of ordinary differential equations for which we have developed an special purpose solver for Maple that can treat graphs with up to 1000 vertices. This approach results in good drawings for many graphs in 2D and 3D.

This is joint work with Mohammad Ali Ebrahimi, Al Erickson, Jeff Farr, Mahdi Javadi, Simon Lo, Mahdad Khatarine-jard Fard, Sara Khodadad, and Allan Wittkopf.

###### Computing GCDs over Algebraic Function Fields

*Mahdi Javadi and Michael Monagan*

Let f1, f2 be non-zero polynomials in L[x], where L is an algebraic function field in k parameters t1, …, tk and r field extensions (RootOf's) a1, …, ar. Our problem is to compute g = gcd(f1, f2). We have designed and implemented a sparse modular algorithm for computing g which uses Zippel's sparse interpolation. As a result our algorithm has a better performance then the dense interpolation algorithm of Monagan and van Hoeij when g is sparse.

In this poster we illustrate our algorithm with a carefully chosen example and provide some timings comparing our new algorithm with that of Monagan and van Hoeij.

###### Equiangular Lines in Real and Complex Spaces

*Mahdad Khatirinejad*

One of the most interesting problems in Algebraic Combinatorics is finding the maximum number of equiangular lines in the Euclidean spaces. Equiangular lines are collections of lines through the origin with only one angle between them. An introduction to this problem along with its connection to different areas of discrete math is provided. We also consider the same problem in the complex spaces and describe the recent progress that we have made in that direction. One of the primary motivations for studying these objects in complex spaces comes from the quantum information theory.

###### Planar Lattice Walks in Restricted Regions

*David Laferriere*

We generalise Kreweras' Walks in three different regions of the planar lattice: the first quadrant, the 1/8 plane i ≥ 0, i ≥ j, and the 3/4 plane bounded by the negative x- and y-axes. All combinations of three step types are chosen from {N,S,E,W,NE,NW,SE,SW}.

With the help of Maple, the length generating functions of walks in the 1/4 plane have been classified rigorously (Mishna 2005, preprint), but there remain many unclassified in the 1/8 and 3/4 plane.

###### Generic Linear Algebra, Groebner Bases and Quotient Rings in Maple

*Simon Lo, Michael Monagan and Roman Pearce*

We demonstrate a new Maple package which allows the user to define a field, Euclidean domain, integral domain, or ring and then perform linear algebra computations over that ring. For example, to solve a linear system over a Galois field.

The package is a collection of generic algorithms, e.g., Gaussian elimination over a field, the Berkowitz algorithm over a ring, together with user level routines which, depending on what operations are available in the ring, decide which algorithm to us.

We have also implemented a compatible package for computing in polynomial quotient rings, allowing the user to do "linear algebra modulo side-relations" and compute in the fraction field of a quotient ring. The algorithms utilize Groebner bases.

Both packages are being integrated into Maple 11 which will be using the `FGB' Groebner basis package of Faugere, which we will demo.

###### An Iterative Method for Dual-Isotope SPECT Imaging

*Sergey Shcherbinin, Anna Celler, Manfred Trummer, Thomas Humphries and Joe Qranfal*

*PIMS Medical Imaging Group, Simon Fraser University
Medical Imaging Research Group, The University of British Columbia*

The goal of this study is to develop a quantitatively accurate method for reconstruction of the two separate 3D images representing the spatial distribution of radiopharmaceuticals labeled with two different isotopes. Our algorithm applies a series of alternating reconstructions of 3D images for both isotopes from cross-contaminated projections corresponding to the lower or upper energy windows. Our approach is validated using several Monte-Carlo simulations of the mathematical thorax phantom. Numerical experiments with different clinical parameters demonstrate high accuracy of the reconstructed images.