I work on developing efficient algorithms for mathematical problems. I am especially focused on computations with polynomials, both from a complexity-theoretic and a 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,
doi:10.1007/s00453-012-9652-4).
Algorithmica,
Special Issue on Algorithms and Computation, in press, 2012.
—.
Chunky and Equal-Spaced Polynomial Multiplication
(arXiv,
doi:10.1016/j.jsc.2010.08.013).
Journal of Symbolic Computation,
Special Issue in Honour of Keith Geddes on his 60th Birthday, July 2011.
Mark Giesbrecht
and —.
Detecting lacunary perfect powers and computing
their roots (arXiv,
doi:10.1016/j.jsc.2011.08.006).
Journal of Symbolic Computation,
November 2011.
Mark Giesbrecht and —.
Interpolation of Shifted-Lacunary Polynomials
(arXiv,
doi:10.1007/s00037-010-0294-0).
Computational Complexity,
2010.
—. Efficient Computation with
Sparse and Dense Polynomials
(UW Space).
Ph.D. thesis, April 2011.
Abstract and individual chapters.
Mark Giesbrecht
and —.
Diversification improves interpolation
(arXiv,
doi:10.1145/1993886.1993909).
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,
doi:10.1145/1837934.1837996).
International Symposium on Symbolic and Algebraic Computaion (ISSAC) 2010.
Munich, Germany, July 25-28, 2010.
—.
Space- and Time-Efficient Polynomial Multiplication
(PDF,
doi:10.1145/1576702.1576743).
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,
doi:10.1145/1390768.1390785).
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 Sparse and Dense Arithmetic.
Symbolic Computation Seminar,
NC State University, December 6, 2012.
Between Sparse and Dense Arithmetic
(PDF).
NARC Seminar, USNA, November 28, 2012.
Finding a polynomial multiple that is sparse
.
AMS Special Session on Mathematics of Computation:
Algebra and Number Theory,
JMM Boston, January 6, 2012.
Stable Sparse Interpolation with Fewer Samples
(PDF).
Fields Institute Workshop on Hybrid Methodologies for
Symbolic-Numeric Computation,
Waterloo, Ontario, Canada,
November 18, 2011.
Between Dense and Sparse Polynomial Multiplication
(PDF).
Computer Science Colloquium, Drexel University, May 9, 2011.
Sparse interpolation and small primes in
arithmetic progressions
(PDF).
Number Theory Session,
CMS Winter Meeting,
Windsor, Ontario, Canada, December 5, 2009.
Fast and Small:
Multiplying Polynomials without Extra Space
(PDF).
CECM Summer Meeting,
Vancouver, British Columbia, Canada,
July 24, 2009.
Memory Efficiency in Polynomial Multiplicaion.
Session on High-Performance Computer Algebra,
Applications of Computer Algebra (ACA),
Montreal, Quebec, Canada,
June 29, 2009.
Interpolation of Shifted-Lacunary Polynomials
(PDF).
SIG Theory and Algorithms Seminar, University of Delaware,
January 9, 2009.
Fast Multiplication with Low Space Complexity
(PDF).
AMS Special Session on SAGE and Mathematical Research Using Open Source
Software,
JMM Washington, D.C.,
January 8, 2009.
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.
Faster Sparse Interpolation over Finite Fields
and Complex Numbers
(PDF).
with Mark Giesbrecht.
East Coast Computer Algebra
Day (ECCAD 2011), University of Waterloo, April 9, 2011.
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.