Mark Giesbrecht

Professor, David R. Cheriton School of Computer Science
Faculty of Mathematics
University of Waterloo, Canada

cs.uwaterloo.ca/~mwg | mwg@uwaterloo.ca

Research

My research interests are in all aspects of computer algebra and symbolic and numeric mathematical computation, including:

  • sparse polynomials and polynomial computation
  • algebraic complexity
  • algorithms for symbolic linear and multi-linear algebra
  • symbolic-numeric algorithms for polynomials
  • factoring polynomials and Ore operators
  • linear algebra over Ore domains
  • generic libraries and the LinBox projects
  • computer algebra systems (from top to bottom)

I am a member of the Symbolic Computation Group at the University of Waterloo and a principal investigator with the Ontario Research Centre for Computer Algebra.

Selected Publications and Preprints

Contributions with supervised students and postdocs are underlined.

Submitted and Preprints

  • M. Giesbrecht Computing Smith Forms Modulo p2 of Sparse Matrices Faster Than Matrix Multiplication . 20pp. 2026
  • M. Giesbrecht, Factoring Quantum-Plane Skew Polynomials over ℚ(ω)(t). 20pp. 2026.
  • J. Elliott, M. Giesbrecht, E. Gillot, M.S. El Din, and É. Schost. Refined bit complexity for the computation of at least one point per connected component of a smooth complete intersection real algebraic set. 2025. [DOI] [arXiv]

2026

  • M. Giesbrecht, P. Koiran, S. Lyu, D.S. Roche. Fast Decomposition of Sparse Polynomials. To appear: ACM International Symposium on Symbolic and Algebraic Computation, ISSAC 2026.

2023

  • J. Elliott, M. Giesbrecht and É. Schost. Bit complexity for computing one point in each connected component of a smooth real algebraic set. Journal of Symbolic Computation, v. 116, 2023, pp. 72–97. [DOI]

2022

  • M. Giesbrecht, H. Huang, G. Labahn and E. Zima. Efficient Rational Creative Telescoping. Journal of Symbolic Computation, v. 109, 2022, pp. 57–87. [DOI] [arXiv]

2021

  • M. Giesbrecht, Q.-L. Huang and É. Schost. Sparse multiplication of multivariate linear differential operators. Proc. International Symposium on Symbolic and Algebraic Computation (ISSAC'21), 2021, pp. 155–162. [DOI]
  • M. Giesbrecht, H. Huang, G. Labahn and E. Zima. Efficient q-Integer Linear Decomposition of Multivariate Polynomials. Journal of Symbolic Computation, v. 107, 2021, pp. 122–144. [DOI] [arXiv]
  • M. Giesbrecht, A. Jamshidpey, É. Schost. Subquadratic-Time Algorithms for Normal Bases. Computational Complexity, v. 30, no. 5, 2021. [DOI] [arXiv]
  • M. Giesbrecht, J. Haraldson and G. Labahn. Computing Nearby Non-trivial Smith Forms. Journal of Symbolic Computation, v. 102, 2021, pp. 304–327. [DOI] [arXiv]
  • J. von zur Gathen, M. Giesbrecht and K. Ziegler. Counting invariant subspaces and decompositions of additive polynomials. Journal of Symbolic Computation, v. 105, 2021, pp. 214–233. [DOI] [arXiv]

2020

  • R. Corless, M. Giesbrecht, L. Rafiee Sevyeri and B.D. Saunders. On Parametric Linear System Solving. Proceedings of Computer Algebra in Scientific Computation (CASC 2020), pp. 188–205. Lecture Notes in Computer Science, v. 12291. September 2020. [DOI] [arXiv]
  • M. Giesbrecht, Q.-L. Huang, É. Schost. Sparse Multiplication for Skew Polynomials. Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation (ISSAC'20). pp. 194–201. July 2020. [DOI]
  • J. Elliott, M. Giesbrecht and E. Schost. On the Bit Complexity of Finding Points in Connected Components of a Smooth Real Hypersurface. Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation (ISSAC'20), pp. 170–177. July 2020. [DOI]
  • M. Giesbrecht, J. Haraldson and E. Kaltofen. Computing Approximate Greatest Common Right Divisors of Differential Polynomials. Foundations of Computational Mathematics. v. 20(2), 2020, pp. 331–366. [DOI] [arXiv]
  • M. Giesbrecht, J. Haraldson and G. Labahn. Computing Lower Rank Approximations of Matrix Polynomials. Journal of Symbolic Computation, v. 98, 2020, pp. 225–245. [DOI] [arXiv]

2019

  • M. Giesbrecht, H. Huang, G. Labahn and E. Zima. Efficient Integer-Linear Decomposition of Multivariate Polynomials. Proc. 44th International Symposium on Symbolic and Algebraic Computation (ISSAC'19), 2019, pp. 171–178. [DOI]
  • M. Giesbrecht, A. Jamshidpey and É. Schost. Quadratic-time Algorithms for Normal Elements. Proc. 44th International Symposium on Symbolic and Algebraic Computation (ISSAC'19), 2019, pp. 179–186. [DOI] [arXiv]

2018

  • M. Giesbrecht, J. Haraldson and G. Labahn. Computing Nearby Non-trivial Smith Forms. Proc. International Symposium on Symbolic and Algebraic Computation (ISSAC 2018), pp. 159–166. Winner of ACM SIGSAM Distinguished Student Author Award. [DOI] [arXiv]

2017

  • M. Giesbrecht, J. Haraldson and G. Labahn. Computing the Nearest Rank-Deficient Matrix Polynomial. Proc. International Symposium on Symbolic and Algebraic Computation (ISSAC 2017), pp. 181–188. [DOI]

2016

  • M. Giesbrecht, A. Heinle, and V. Levandovskyy. Factoring linear partial differential operators in n variables. Journal of Symbolic Computation, v. 75, July–August 2016, pp. 127–148. [DOI] [arXiv]
  • A. Arnold, M. Giesbrecht and D. Roche. Faster sparse multivariate polynomial interpolation of straight-line programs. Journal of Symbolic Computation. v. 75, July–August 2016, pp. 4–24. [DOI] [arXiv]

2015

  • M. Elsheikh, M. Giesbrecht. Relating p-adic eigenvalues and the local Smith normal form. Linear Algebra and Its Applications, v. 481, September 2015, pp. 330–349. [DOI] [arXiv]
  • J. Bergen, M. Giesbrecht, P.N. Shivakumar and Y. Zhang. Factorizations for difference operators. Advances in Difference Equations. v. 2015:57, February 2015, pp. 1–6. [DOI]

2014

  • A. Arnold, M. Giesbrecht and D. Roche. Sparse interpolation over finite fields via low-order roots of unity. Proc. International Symposium on Symbolic and Algebraic Computation (ISSAC'14), July 2014, pp. 27–34. [DOI] [arXiv]
  • M. Giesbrecht, A. Heinle and V. Levandovskyy. Factoring Linear Differential Operators in n Variables. Proc. International Symposium on Symbolic and Algebraic Computation (ISSAC'14), July 2014, pp. 194–201. [DOI] [arXiv]
  • M. Giesbrecht and J. Haraldson. Computing GCRDs of Approximate Differential Polynomials. Proc. Workshop on Symbolic-Numeric Computing (SNC'14), July 2014, pp. 78–87. [DOI] [arXiv]

2013

  • M. Giesbrecht. Algorithms for irreducibility testing and constructing irreducible polynomials. Handbook of Finite Fields (invited article). pp. 374–380. CRC Press. 2013. [Book DOI]
  • A. Arnold, M. Giesbrecht and D. Roche. Faster sparse interpolation of straight-line programs. Proceedings of Computer Algebra in Scientific Computation (CASC 2013), Lecture Notes in Computer Science, v. 8136, pp. 61–74. [DOI]
  • M. Giesbrecht and M. Sub Kim. Computation of the Hermite form of a Matrix of Ore Polynomials. Journal of Algebra. Volume 376, 2013, pp. 341–362. [DOI] [arXiv]

2012

  • M. Giesbrecht and A. Heinle. A polynomial-time algorithm for the Jacobson form of a matrix of Ore polynomials. Proceedings of Computer Algebra in Scientific Computation (CASC 2012), pp. 117–128. Lecture Notes in Computer Science, v. 7442. [DOI]
  • M. Elsheikh, M. Giesbrecht, A. Novocin, B.D. Saunders. Fast Computation for Smith Forms of Sparse Matrices Over Local Rings. Proc. 37th International Symposium on Symbolic and Algebraic Computation (ISSAC 2012). pp. 146–153. [DOI] [arXiv]
  • M. Giesbrecht and N. Pham. A Symbolic Approach to Compute a Null-Space in the Projection Method, Proc. 10th Asian Symposium on Computer Mathematics (ASCM 2012), pp 245–259, 2014. [DOI]
  • M. Giesbrecht, D. Panario (Editors). Special issue of the Journal of Symbolic Computation. In honour of the research and influence of Joachim von zur Gathen at 60. Volume 47, Issue 4, April 2012. 147 pages. [DOI]
  • M. Giesbrecht, D. Roche, and H. Tilak. Computing sparse multiples of polynomials. Algorithmica. Volume 64, Number 3, pp. 454–480. [DOI] [arXiv]

2011

  • M. Giesbrecht and D. Roche. Detecting lacunary perfect powers and computing their roots. Journal of Symbolic Computation, v. 46, pp. 1242–1259, 2011. [DOI] [arXiv]
  • M. Giesbrecht and D. Roche. Diversification improves interpolation. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC 2011), pp. 123–130. [DOI] [arXiv]
  • M. Giesbrecht and S. Watt, In honour of Keith Geddes on his 60th birthday, v. 46, issue 7, pp. 735–740. [DOI]

2010

  • M. Giesbrecht, D. Roche, and H. Tilak. Computing sparse multiples of polynomials, International Symposium on Algorithms and Computation (ISAAC 2010). Lecture Notes in Computer Science v. 6506, pp. 266–278, 2010. [DOI] [arXiv]
  • M. Giesbrecht and D. Roche, Interpolation of shifted-lacunary polynomials. Computational Complexity. Volume 19, No 3, pp. 333–354, 2010. [DOI] [arXiv]
  • J. von zur Gathen, M. Giesbrecht and K. Ziegler, Composition collisions and projective polynomials. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC) 2010, pp. 123–130. [DOI] [arXiv]

2009

  • Mark Giesbrecht, George Labahn and Yang Zhang, Computing Popov Forms of Matrices over PBW Extensions. 9th Asian Symposium on Computer Mathematics (ASCM 2009). Fukuoka, Japan, December 14–17, 2009. [DOI]
  • Mark Giesbrecht and Myung Sub Kim, On computing the Hermite form of a matrix of differential polynomials. 11th International Workshop on Computer Algebra and Scientific Computation (CASC). September 2009, Kobe University, Japan. Lecture Notes in Computer Science 5743, pp. 118–129. [DOI] [arXiv]
  • M. Giesbrecht, G. Labahn and W.-s. Lee. Symbolic-numeric sparse interpolation of multivariate polynomials. Journal of Symbolic computation. Volume 44, Issue 8, pp. 943–959, 2009. [DOI]

2008

  • M. Giesbrecht and D. Roche. On Lacunary Polynomial Perfect Powers. ACM International Symposium on Symbolic and Algebraic Computation (ISSAC), 2008. RISC, Linz, Austria, July 20–23, 2008, pp. 103–110. [DOI]

2007

  • W. Eberly, M. Giesbrecht, P. Giorgi, A. Storjohann and G. Villard, Faster Inversion and Other Black Box Matrix Computations Using Efficient Block Projections. ACM International Symposium on Symbolic and Algebraic Computation (ISSAC), pp. 143–150, 2007. [DOI]
  • J. Selby, F. Ruffell, M. Giesbrecht and M. Godfrey. Examining the Effects of Global Data Usage on Software Maintainability. Proceedings of the 14th Working Conference on Reverse Engineering (WCRE), pp. 60–69, 2007. [DOI] [PDF]
  • M. Giesbrecht and D. Roche, Interpolation of Shifted-Lacunary Polynomials, Mathematical Aspects of Computer and Information Sciences (MACIS), Paris, France, 2007. [DOI] [arXiv]

2006

  • M. Giesbrecht, G. Labahn, W.-s. Lee, Symbolic-numeric sparse interpolation of multivariate polynomials. ACM International Symposium on Symbolic and Algebraic Computation (ISSAC), pp. 116–123, 2006. [DOI]
  • W. Eberly, M. Giesbrecht, P. Giorgi, A. Storjohann and G. Villard, Solving Sparse Rational Linear Systems. ACM International Symposium on Symbolic and Algebraic Computation (ISSAC), pp. 63–70, 2006. [DOI] [arXiv]
  • J. Selby and M. Giesbrecht, A Fine-Grained Analysis of the Performance and Power Benefits of Compiler Optimizations for Embedded Devices. International Conference on Programming Languages and Compilers, pp. 821–827, 2006.

2005

  • C. Oancea, J. Selby, M. Giesbrecht and S. Watt, Distributed Models of Thread-Level Speculation. International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA), pp. 920–927, 2005. DOI unavailable
  • M. Giesbrecht, G. Labahn and Y. Zhang, Computing Valuation Popov Forms. Workshop on Computer Algebra Systems and their Applications (CASA'05), Springer LNCS 3516, pp. 619–626, 2005. [DOI]
  • M. Giesbrecht and J.P. May, New algorithms for exact and approximate polynomial decomposition. International Workshop on Symbolic-Numeric Computation (SNC'05), pp. 297–307, 2005. [DOI]
  • B. Botting, M. Giesbrecht, and J.P. May, Using the Riemannian SVD for Problems in Approximate Algebra. International Workshop on Symbolic-Numeric Computation (SNC'05). July 2005, pp 209–219. DOI unavailable

2004

  • W. Eberly and M. Giesbrecht, Efficient decomposition of separable algebras. Journal of Symbolic Computation. Volume 37, Issue 1, pp. 35–81, 2004. [DOI]
  • M. Giesbrecht, G. Labahn, W.-s. Lee, Symbolic-numeric sparse interpolation of multivariate polynomials. Proc. 9th Rhine Workshop on Computer Algebra, 2004. DOI unavailable
  • M. Giesbrecht, G. Labahn and W.-s. Lee, Symbolic-Numeric Sparse Polynomial Interpolation in Chebyshev Basis and Trigonometric Interpolation. Proc. Workshop on Computer Algebra in Scientific Computation, pp. 195–205, 2004. DOI unavailable

2003

  • M. Giesbrecht, Y. Zhang, Factoring and Decomposing Ore Polynomials over 𝔽_q(t). ACM International Symposium on Symbolic and Algebraic Computation (ISSAC), pp. 127–134, 2003. [DOI]
  • J. Gerhard, M. Giesbrecht, A. Storjohann, E. Zima, Shiftless decomposition and polynomial-time rational summation. ACM International Symposium on Symbolic and Algebraic Computation (ISSAC), pp. 119–126, 2003. [DOI]
  • M. Giesbrecht, E. Kaltofen, W.-s. Lee, Algorithms for Computing Sparsest Shifts of Polynomials in Power, Chebyshev, and Pochhammer Bases. Journal of Symbolic Computation. Volume 36, Issues 3–4, 2003, pp. 401–424. [DOI]
  • M. Giesbrecht, A. Storjohann and G. Villard. Algorithms for matrix canonical forms. Invited Submission. Computer Algebra Handbook–Foundations, Applications, Systems. Springer Verlag, pp. 38–41, 2003. [Book DOI]

2002

  • M. Giesbrecht and A. Storjohann, Computing rational forms of integer matrices. Journal of Symbolic Computation. Volume 34, Issue 3, pp. 157–172, 2002. [DOI]
  • M. Giesbrecht, G. Reid and Y. Zhang, Non-commutative Gröbner Bases in Poincaré-Birkhoff-Witt Extensions, Conference on Computer Algebra and Scientific Computation (CASC'2002), pp. 97–106, 2002. DOI unavailable
  • M. Giesbrecht, E. Kaltofen and W.-s. Lee, Algorithms for Computing the Sparsest Shifts of Polynomials via the Berlekamp/Massey Algorithm. ACM International Symposium on Symbolic and Algebraic Computation (ISSAC), pp. 101–108, 2002. [DOI]
  • J.-G. Dumas, T. Gautier, M. Giesbrecht, P. Giorgi, B. Hovinen, E. Kaltofen, B.D. Saunders, W.J. Turner and G. Villard, LinBox: A Generic Library for Exact Linear Algebra. International Congress of Mathematical Software, Beijing, China, pp. 40–50, 2002. [DOI]

2001

  • M. Giesbrecht, Fast computation of the Smith form of a sparse integer matrix. Computational Complexity, v. 10, pp. 41–69, 2001. [DOI]
  • M. Giesbrecht, M. Jacobson, Jr. and A. Storjohann, Algorithms for large integer matrix problems. 14th Symposium on Applied Algebra, Algebraic Algorithms and Error Correcting Codes (AAECC), LNCS 2227, pp. 297–307, 2001. [DOI]
  • R. Corless, M. Giesbrecht, M. Van Hoeij, I. Kotsireas, S. Watt, Towards Factoring Bivariate Approximate Polynomials. ACM International Symposium on Symbolic and Algebraic Computation (ISSAC'01), pp. 85–92, 2001. [DOI]

2000

  • W. Eberly and M. Giesbrecht. Efficient decomposition of associative algebras over finite fields. Journal of Symbolic Computation, v. 29, pp. 441–458, 2000. [DOI]
  • W. Eberly, M. Giesbrecht, and G. Villard, On computing the determinant and Smith form of an integer matrix. Proceedings of the 41st IEEE Symposium on the Foundations of Computer Science (FOCS), pp. 675–685, 2000. [DOI]
  • D. Jeffrey, M. Giesbrecht, and R. Corless, Integer roots for integer-power-content calculations. Proceedings of the 4th Asian Symposium on Computer Mathematics (ASCM2000), Chiang Mai, Thailand, pp. 71–74, 2000. [DOI]
  • R. Corless, M. Giesbrecht, I. Kotsireas and S. Watt, Numerical implicitization of parametric hypersurfaces with linear algebra, Artificial Intelligence and Symbolic Computation (AISC'2000), pp. 174–183, 2000. [DOI]

1999

  • R. Corless, M. Giesbrecht, D. Jeffrey and S. Watt. Approximate polynomial decomposition. ACM International Symposium on Symbolic and Algebraic Computation (ISSAC'99), pp. 213–219, 1999. [DOI]

1998

  • M. Giesbrecht. Factoring skew polynomials over finite fields. Journal of Symbolic Computation, Vol. 26, No. 4, pp. 463–486, 1998. [DOI]
  • M. Giesbrecht, A. Lobo & B. D. Saunders. Certifying inconsistency of sparse linear systems. ACM International Symposium on Symbolic and Algebraic Computation (ISSAC'98), pp. 113–119, 1998. [DOI]

1997

  • M. Giesbrecht, Efficient parallel solution of sparse systems of linear diophantine equations. ACM International Symposium on Parallel Symbolic Computation (PASCO'97), pp. 1–10, 1997. [DOI]

1996

  • M. Giesbrecht, Probabilistic computation of the Smith normal form of a sparse integer matrix. Algorithms in Number Theory Symposium (ANTS'96), pp. 173–186. Lecture Notes in Computer Science 1122, 1996. [DOI]
  • W. Eberly and M. Giesbrecht, Efficient decomposition of associative algebras. ACM International Symposium on Symbolic and Algebraic Computation (ISSAC'96), pp. 170–178, 1996. [DOI]

1995

  • M. Giesbrecht, Nearly optimal algorithms for canonical matrix forms, SIAM Journal on Computing, Vol. 24, No. 5, pp. 948–969, 1995. [DOI]
  • M. Giesbrecht, Fast computation of the Smith form of an integer matrix, Proceedings of ACM International Symposium on Symbolic and Algebraic Computation (ISSAC'95), pp. 110–118, 1995. [DOI]
  • V.P. Krothapalli, J. Thulasiraman and M. Giesbrecht, Run-time parallelization of irregular DOACROSS loops, In Parallel Algorithms for Irregularly Structured Problems: Proceedings of Irregular'95, Springer LNCS 980, pp. 75–80, 1995. [DOI]

1994

  • M. Giesbrecht, Fast algorithms for rational forms of integer matrices, Proceedings of the ACM International Symposium on Symbolic and Algebraic Computation (ISSAC'94), Oxford, England, July, pp. 305–311, 1994. [DOI]

1992

  • M. Giesbrecht, Fast algorithms for matrix normal forms, Proceedings of the 33rd IEEE Symposium on the Foundations of Computer Science (FOCS), pp. 121–130, 1992. [DOI]
  • M. Giesbrecht, Factoring in skew polynomial rings. Proceedings of LATIN'92 conference, pp. 191–203, Springer Lecture Notes in Computer Science 583, 1992. [DOI]

1990

  • J. von zur Gathen & M. Giesbrecht. Constructing normal bases in finite fields. Journal of Symbolic Computation, volume 10, pp. 547–570, 1990. [DOI]

Technical Reports

  • E. Bach, M. Giesbrecht and J. McInnes. The complexity of number theoretic problems. University of Toronto Technical Report 247/91, 1991, 52 pp.

Books

  • J. von zur Gathen and M. Giesbrecht, Editors, Proceedings of the 1994 ACM International Symposium on Symbolic and Algebraic Computation (ISSAC'94), ACM Press, 1994. [Proceedings DOI]

Theses

  • M. Giesbrecht, Nearly optimal algorithms for canonical matrix forms, Ph.D. Thesis, 1993. DOI unavailable
  • M. Giesbrecht, Some Results on the Functional Decomposition of Polynomials, M.Sc. Thesis, 1988. [DOI] [arXiv]

Updated from the CV dated April 19, 2026. Web-page-only records retained and tagged.