CECM Home > Events > CECM Annual Summer Meeting 2009 > Program > Talk Abstracts
Talk Abstracts
Pseudospectra for Exponential Polynomial Matrices
Rob Corless · University of Western Ontario
Abstract to be announced
The future of parallel computing on the desktop
Roman Pearce · Simon Fraser University
A desktop computer today is comparable to a supercomputer of only a decade ago, and the trend towards ever greater performance shows no sign of slowing down. In this talk we discuss the new computing architectures that are coming to commodity hardware and applications in computational mathematics that they will enable. In particular, we will cover multicore CPUs, GPUs, and Intel's Larrabee processor, and present some benchmarks comparing our polynomial multiplication software on Intel quad-core CPUs with other computer algebra systems.
Fast and Small: Multiplying Polynomials without Extra Space
Daniel S. Roche · University of Waterloo
The multiplication of univariate polynomials and multi-precision integers is one of the most basic, well-studied, and widely-used operations in mathematical computing. While asymptotic time complexity correlates with performance, it is well-known that memory usage and cache misses also contribute significantly to the running time of computer programs. Furthermore, in some applications such as embedded systems, physical restrictions on memory can limit the size of possible computations. All algorithms which achieve sub-quadratic time complexity for multiplication currently require at least O(n) auxiliary storage space for their implementation, producing an apparent time/space trade-off.
Two new algorithms are presented which achieve the same time complexity as Karatsuba's and FFT-based algorithms (respectively) without requiring the use of an auxiliary array for temporary storage. While the FFT-based approach only applies under certain conditions, the Karatsuba-like method is general and is the first algorithm to break the O(n^2) time-space barrier, under a practical space complexity model which allows both reads and writes to the output array. A low-level C language implementation is also presented which demonstrates the practical effectiveness of these new approaches.
Two pairs of boolean functions in biology
Tamon Stephen · Simon Fraser University
We introduce monotone boolean functions through two quite different examples from biology, in which they help to understand complex systems. Representing these functions is an interesting computational challenge.
Dynamic Medical Imaging
Manfred Trummer · Simon Fraser University
Abstract to be announced
Periods of Feynman graphs
Karen Yeats · Simon Fraser University
I will discuss some graph theoretic and computational aspects of calculating the residues of Feynman integrals in simple cases, and consider the interesting transcendental numbers which result.