East Coast Computer Algebra Day 2013

Invited Talks

What's the best data structure for multivariate polynomials in a world with 64 bit multicore computers?

Michael Monagan
Centre for Experimental and Constructive Mathematics
Simon Fraser University

Abstract

We have designed and implemented a new polynomial data structure to speed up polynomial multiplication and division and we have implemented parallel algorithms for both operations. When we integrated our software into Maple we found that often most of the time is spent converting to and from our polynomial data structure and Maple's polynomial data structure.

It's rather pointless to have a great parallel algorithm if 60% of the time is spent converting between polynomial representations!

How do we reduce overhead so that we get decent parallel speedup? In the talk I'll show our solution to this problem which is now available in Maple 17. I'll compare our new data structure with the data structures used in other computer algebra systems. I'll present an old forgotten algorithm for polynomial multiplication and our parallelization of it. I'll present some timings run on an Intel Core i7 that show that our improvements to polynomial multiplication and division improve polynomial factorization as well. I'll compare Maple 17 with Mathematica 9, Magma 2.19-1 and Singular 3-1-4 on a variety of polynomial benchmarks.

This is joint work with Roman Pearce.

Finding closed form solutions of differential equations

Manuel Kauers, RISC-Linz

Abstract

We consider ordinary linear differential equations with polynomial coefficients. Each such equation has a finite dimensional vector space of solutions, but usually none of these solutions can be expressed in closed form. We discuss the problem of finding out for a given specific differential equation whether one (or some, or all) of its solutions admit a closed form representation. After recalling the classical algorithms for finding polynomial and rational solutions, we turn to hyperexponential solutions. These are solutions that can be written in the form \(\exp(u(x))v_1(x)^{e_1}\cdots v_k(x)^{e_k}\) for certain rational functions \(u,v_1,\dots,v_k\) and constants \(e_1,\dots,e_k\). The first algorithm for finding such solutions was proposed by Beke at the end of the 19th century. His algorithm is very costly. A more efficient algorithm was given at the end of the 20th century by Mark van Hoeij. We will sketch the basic ideas of these two algorithms and then present a new algorithm based on effective analytic continuation, which was recently found by the speaker in joint work with F. Johansson and M. Mezzarobba [arXiv:1301.2486].

New Cryptographic Challenges: Computing on Remote Data

Shafi Goldwasser, MIT

Abstract

Modern technologies such as cloud computing raise fundamentally new cryptographic challenges: how to extract useful information from encrypted data and still preserve privacy?

In this talk, I will present recent work on functional encryption schemes and its applications to reusable garbled circuits and delegating computations.