COPLAS Talk by Prof. Mark Giesbrecht

Sparsity, Complexity and Practicality in Symbolic Computation

Coplas Talk by Prof. Mark Giesbrecht, Cheriton School of Computer Science, Faculty of Mathematics, University of Waterloo


Modern symbolic computation systems provide an expressive language for describing mathematical objects. For example, we can easily enter equations such as
f=x^{2^{100}}y^2 + 2x^{2^{99}+1}y^{2^{99}+1}+2x^{2^{99}}y+y^{2^{100}}x^{2}+2y^{2^{99}}x+1
into a computer algebra system. However, to determine the factorization
f -> (x^{2^{99}}y+y^{2^{99}}x+1)^2
with traditional methods would incur huge expression swell and high complexity. Indeed, many problems related to this one are provably intractable under various reasonable assumptions, or are suspected to be so. Nonetheless, recent work has yielded exciting new algorithms for computing with sparse mathematical expressions. In this talk, we will attempt to navigate this hazardous computational terrain of sparse algebraic computation. We will discuss new algorithms for sparse polynomial root finding and functional decomposition. We will also look at the "inverse" problem of interpolating or reconstructing sparse mathematical functions from a small number of sample points. Computations over both "traditional" exact and symbolic domains, such as the integers and finite fields, as well as approximate (floating point) data, will be considered.


Dr. Mark Giesbrecht is a Professor and Director of the David R. Cheriton School of Computer Science at the University of Waterloo. He received a B.Sc. from the University of British Columbia in 1986, and a Ph.D from the University of Toronto in 1993. He is an ACM Distinguished Scientist, and former Chair of ACM SIGSAM (Special Interest Group on Symbolic and Algebraic Manipulation) and the International Symposium on Symbolic and Algebraic Computation (ISSAC) Steering Committees, as well as serving as ISSAC Program Committee Chair. His research interests are in symbolic computation and computer algebra, as well as computational linear algebra.

Host: Cosmin Oancea (DIKU, tel. +45 23828086, e-mail:

All are welcome. No registration required.