I work on developing efficient algorithms for mathematical problems. I am especially focused on computations with polynomials, both from a complexity-theoretic and practical standpoint. A recurring theme has been the role that sparsity plays in computational efficiency. I am also involved in the LinBox project for exact linear algebra.
Mark Giesbrecht,
—, and Hrushikesh Tilak.
Computing Sparse Multiples of Polynomials
(arXiv).
Journal submission, December 2010.
.
—. Efficient Computation with
Sparse and Dense Polynomials
(UW Space).
Ph.D. thesis, April 2011.
Abstract and individual chapters.
—.
Chunky and Equal-Spaced Polynomial Multiplication
(arXiv,
doi:10.1016/j.jsc.2010.08.013).
Journal of Symbolic Computation, in press (accepted July 2010).
Mark Giesbrecht
and —.
Detecting lacunary perfect powers and computing
their roots (arXiv).
Journal of Symbolic Computation,
to appear (accepted January 2010).
Mark Giesbrecht and —.
Interpolation of Shifted-Lacunary Polynomials
(arXiv,
doi:10.1007/s00037-010-0294-0).
Computational Complexity,
2010.
Mark Giesbrecht
and —.
Diversification improves interpolation
(arXiv).
International
Symposium on Symbolic and Algebraic Computation (ISSAC) 2011.
San Jose, California, USA, June 8-11, 2011.
Implementation and abstract.
Mark Giesbrecht,
—, and Hrushikesh Tilak.
Computing Sparse Multiples of Polynomials,
extended abstract
(PDF,
doi:10.1007/978-3-642-17517-6 25).
International Symposium on Algorithms and Computation (ISAAC) 2010.
Jeju Island, Korea, December 15-17, 2010.
Presentation (PDF).
David Harvey
and —.
An in-place truncated Fourier transform and
applications to polynomial multiplication
(arXiv).
International Symposium on Symbolic and Algebraic Computaion (ISSAC) 2010.
Munich, Germany, July 25-28, 2010.
—.
Space- and Time-Efficient Polynomial Multiplication
(PDF).
International Symposium on Symbolic and Algebraic Computaion (ISSAC) 2009.
Seoul, Korea, July 28-31, 2009.
Implementation (gzipped tar).
Presentation
(longer) (PDF).
Mark Giesbrecht and —.
On Lacunary Polynomial Perfect Powers
(PDF).
International Symposium on Symbolic and Algebraic Computaion (ISSAC) 2008.
Hagenberg, Austria, July 20-23, 2008.
Implementation (gzipped tar) -
requires GMP and
NTL.
Presentation (PDF).
—.
Adaptive Polynomial Multiplication
(PDF).
Milestones in Computer Algebra (MICA 2008).
Stonehaven Bay, Trinidad and Tobago, May 1-3, 2008.
Mark Giesbrecht and —.
Interpolation of Shifted-Lacunary Polynomials
[Extended Abstract]
(PDF).
Mathematical Aspects of Computer and Information Sciences (MACIS) 2007.
Paris, France, December 5-7, 2007.
Presentation (PDF).
Between Dense and Sparse Polynomial Multiplication
(PDF).
Computer Science Colloquium, Drexel University, May 9, 2011.
The LinBox Project for Linear Algebra
Computation: A Practical Tutorial
(PDF).
MOCAA M3
workshop in computational algebra, University of Western Ontario,
May 8, 2008.
Adaptive Polynomial Multiplication
(PDF).
ORCCA Joint Lab Meeting,
University of Western Ontario, March 14, 2008.
Complexity of Shifted-Lacunary Polynomial Interpolation
(PDF).
SCG Seminar, School of Computer Science, University of Waterloo, December 13, 2007.
Matrix Input and Toeplitz Determinant:
Undergraduate Research Projects with LinBox
(PDF).
Symbolic Computation Group
Lab Meeting, University of Waterloo, December 8, 2006.
Detecting Polynomial Perfect Powers
(PDF).
with Mark Giesbrecht.
ORCCA Joint Lab Meeting.
Maplesoft,
Waterloo, ON, Canada, February 8, 2008.
New Algorithms for Lacunary Polynomials
(PDF).
with Mark Giesbrecht.
International Symposium on Symbolic and Algebraic Computation (ISSAC 2007).
Waterloo, ON, Canada, July 29-August 1, 2007.
New Algorithms for Lacunary Polynomials
(PDF).
with Mark Giesbrecht.
CMS-MITACS Joint Conference 2007. Winnipeg, MB, Canada,
May 31-June 1, 2007.