Please note: This seminar will take place in DC 1302.
Robert Dougherty-Bliss, Applied and Computational Mathematics
Dartmouth College
A popular approach to speed up computations is to reduce the input modulo several relatively prime numbers, do arithmetic on the residues, then reconstruct the result at the end. This improves the running time if the moduli (and their pairwise inverses) have “nice” binary shapes, but only a limited number of such moduli are known.
I will discuss a new system of moduli related to a family of trinomials. This system has shown promising real-world performance, can produce arbitrarily many moduli, and its elements can be computed quickly. I will mention some theoretical limitations of the system based on roots of unity and graph colorings, and point out what remains to be discovered.
Joint work with Mits Kobayashi, Natalya Ter-Saakov, and Eugene Zima.
Location Information
200 University Avenue West
DC 1302
Waterloo, ON, CA N2L 3G1
