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

To appear

• J. Elliott, M. Giesbrecht and E. Schost. Bit complexity for computing one point in each connected component of a smooth real algebraic set. Accepted for publication, Journal of Symbolic Computation, .

2022

• M. Giesbrecht, H. Huang, G. Labahn and E. Zima. Efficient Rational Creative Telescoping. Journal of Symbolic Computation, v. 109, pp. 57-87. 10.1016/j.jsc.2021.07.005.

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).
• 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. 10.1016/j.jsc.2021.02.001 . arXiv:2002.00124.
• M. Giesbrecht, A. Jamshidpey, E. Schost. Subquadratic-Time Algorithms for Normal Bases. Computational Complexity, v. 30, no. 5, 2021. DOI:10.1007/s00037-020-00204-9, arXiv:2005.03497.
• M. Giesbrecht, J. Haraldson and G. Labahn. Computing Nearby Non-trivial Smith Forms. Journal of Symbolic Computation, v. 102, 2021. DOI:10.1016/j.jsc.2019.10.019 , arXiv:1812.04590.
• J. von zur Gathen, M. Giesbrecht and K. Ziegler. Counting decompositions of additive polynomials via invariant subspaces. Journal of Symbolic Computation. v.105, July-August, 2021, pp. 214-233 10.1016/j.jsc.2020.06.008
arXiv:1912.00212

2020

• R. Corless, M. Giesbrecht and 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. DOI: 10.1007/978-3-030-60026-6_11. September 2020.
• M. Giesbrecht, Q.-L. Huang, E. Schost. Sparse Multiplication for Skew Polynomials. Proceedings of the 45^th International Symposium on Symbolic and Algebraic Computation (ISSAC'20). pp. 194-201. July 2020. doi:10.1145/3373207.3404023.
• 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 45^th International Symposium on Symbolic and Algebraic Computation (ISSAC'20). July 2020. doi:10.1145/3373207.3404058.
• M. Giesbrecht, J. Haraldson and E. Kaltofen. Computing Approximate Greatest Common Right Divisors of Differential Polynomials. Journal of the Foundations of Computational Mathematics. v. 20(2), 2020, pp. 331-366. doi:10.1007/s10208-019-09422-2; arXiv:1712.04007.

2019

• M. Giesbrecht, H. Huang, G. Labahn and E. Zima. Efficient Integer-Linear Decomposition of Multivariate Polynomials. Proc. 44^th International Symposium on Symbolic and Algebraic Computation (ISSAC'19), 2019, pp. 171-189. doi:10.1145/3326229.3326261.
• M. Giesbrecht, A. Jamshidpey and E. Schost. Quadratic-time Algorithms for Normal Elements. Proc. 44^th International Symposium on Symbolic and Algebraic Computation (ISSAC'19), 2019, pp. 179-186. doi:10.1145/3326229.3326260; arXiv:1903.03278.
• M. Giesbrecht, J. Haraldson and G. Labahn. Computing Lower Rank Approximations of Matrix Polynomials. Journal of Symbolic Computation, v. 98, pp. 225-245, 2019. DOI:10.1016/j.jsc.2019.07.012 arXiv:1712.04007.

2018

• M. Giesbrecht, J. Haraldson and G. Labahn. Computing Nearby Non-trivial Smith Forms. Proc. International Symposium on Symbolic and Algebra Computation (ISSAC 2018), pp. 159-166. DOI:10.1145/3208976.3209024. Winner of the ACM SIGSAM Distinguished Student Author Award.

2017

• M. Giesbrecht, J. Haraldson and G. Labahn. Computing the Nearest Rank-Deficient Matrix Polynomial. Proc. International Symposium on Symbolic and Algebra Computation (ISSAC 2017), pp. 181-188. DOI:10.1145/3087604.3087648.

2016

• M. Giesbrecht, A. Heinle and V. Levandovskyy. Factoring Differential Operators in n Variables. Journal of Symbolic Computation. v. 75 July-August 2016, pp. 126-148. DOI:10.1016/j.jsc.2015.11.011, arXiv:1404.0002.
• A. Arnold, M. Giesbrecht and D. Roche. Multivariate Polynomial Interpolation of Straight-Line Program. Journal of Symbolic Computation v.75 July-August 2016. pp. 4-24. DOI:10.1016/j.jsc.2015.11.005, arxiv:1412.4088.

2015

• M. Elsheikh, M. Giesbrecht. Relating p-adic eigenvalues and the local Smith normal form. Linear Algebra and It's Applications, v. 481, September 2015, pp. 330-349 DOI:10.1016/j.laa.2015.05.001, arXiv:1401.1773.
• M. Giesbrecht, A. Heinle and V. Levandovskyy. Factoring Differential Operators in n Variables. Journal of Symbolic Computation. pp. 127-148. DOI:10.1016/j.jsc.2015.11.011, arXiv:1404.0002.
• A. Arnold, M. Giesbrecht and D. Roche. Multivariate Polynomial Interpolation of Straight-Line Program. Journal of Symbolic Computation. pp. 4-24. DOI:10.1016/j.jsc.2015.11.005, arxiv:1412.4088.
• 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:10.1186/s13662-015-0402-1.

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:10.1145/2608628.2608671, arXiv:1401.4744.
• M. Giesbrecht, A. Heinle and V. Levandovskyy. Factoring Differential Operators in n Variables. Proc. International Symposium on Symbolic and Algebraic Computation (ISSAC'14), July 2014, pp. 194-201. DOI:10.1145/2608628.2608667, arXiv:1404.0002.
• 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:10.1145/2631948.2631964.

2013

• M. Giesbrecht and M. Sub Kim. Computation of the Hermite form of a Matrix of Ore Polynomials. Journal of Algebra, v. 376, pp. 341-362, 2013. DOI: 10.1016/j.jalgebra.2012.11.033.
• M. Giesbrecht. Algorithms for irreducibility testing and constructing irreducible polynomials. Handbook of Finite Fields (invited article). pp. 374-380. CRC Press. 2013.
• A. Arnold, M. Giesbrecht, and D. Roche. Faster Sparse Interpolation of Straight-Line Programs. Proceedings of Computer Algebra in Scientific Computation (CASC 2013), pp. 61-74. Lecture Notes in Computer Science, v.8136. DOI: 10.1007/978-3-319-02297-0_5.

2012

• M. Giesbrecht and N. Pham. A Symbolic Computation Approach to the Projection Method, Proc. 10th Asian Symposium on Computer Mathematics (ASCM 2012), 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 Volume, v.7442. DOI.
• M. Elsheikh, M. Giesbrecht, A. Novocin, B.D. Saunders. Fast Computation for Smith Forms of Sparse Matrices Over Local Rings. International Symposium on Symbolic and Algebra Computation (ISSAC 2012), pp. 146-153. DOI, arXiv.
• M. Giesbrecht, D. Roche, and H. Tilak. Computing sparse multiples of polynomials. Algorithmica. Volume 64, Number 3, pp.454-480. DOI, arXiv.
• M. Giesbrecht, D. Panario. In honour of the research and influence of Joachim von zur Gathen at 60. Volume 47, Issue 4, April 2012. DOI.

2011

• M. Giesbrecht and D. Roche. Detecting lacunary perfect powers and computing their roots, Journal of Symbolic Computation, v. 46, pp. 1242-1259, 2011. arXiv. DOI.
• M. Giesbrecht and D Roche. Diversification improves interpolation. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC) 2011, pp. 123-130. Extended abstract: DOI. Preprint in 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.
• 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 Composition Collisions and Projective Polynomials. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC) 2010, pp. 123-130. Extended abstract: DOI. Full version: arXiv.

2009

• M. Giesbrecht, G. Labahn and W-s. Lee, Symbolic-numeric sparse interpolation of multivariate polynomials. Journal of Symbolic Computation. Volume 44, 2009, pp. 943-959, 2009. PDF.

• Mark Giesbrecht, Myung Sub Kim, On computing the Hermite form of a matrix of differential polynomials. Computer Algebra and Scientific Computation (CASC) Workshop. Lecture Notes in Computer Science 5743. PDF. arXiv.
• 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.
  

2008

• M. Giesbrecht and D. Roche, On Lacunary Polynomial Perfect Powers. The International Symposium on Symbolic and Algebraic Computation (ISSAC), 2008. RISC, Linz, Austria, July 20-23, 2008. PDF. Implementation (gzipped tar) - requires GMP and NTL.

2007

• M. Giesbrecht and D. Roche, Interpolation of Shifted-Lacunary Polynomials, Mathematical Aspects of Computer and Information Sciences (MACIS), 2007. PDF.
• 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. PDF.
• J. Selby, F. Ruffell, M. Giesbrecht and M. Godfrey, Recovering Maintainability Effort in the Presence of Global Data Usage. Proc. 14th Working Conference on Reverse Engineering (WCRE), pp. 60-69, 2007.  PDF.

2006

• 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. PDF.
• M. Giesbrecht, G. Labahn and W-s. Lee, Symbolic-numeric Sparse Interpolation of Multivariate Polynomials. ACM International Symposium on Symbolic and Algebraic Computation (ISSAC), pp. 116-123, 2006. PDF.
• 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 & Compilers. pp. 920-927, 2006. PDF.

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), 2005. PDF.
• M. Giesbrecht, G. Labahn and Y. Zhang, Computing Valuation Popov Forms, Workshop on Computer Algebra Systems and their Applications (CASA), pp. 619-626, 2005.
• M. Giesbrecht and J.P. May, New algorithms for exact and approximate polynomial decomposition. International Workshop on Symbolic-Numeric Computation (SNC). pp. 297-307. July 2005. Extended version submitted to edited volume available as PDF.
• 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), pp. 209-219. July 2005.

2004

• W. Eberly and M. Giesbrecht,  Efficient decomposition of separable algebras. Journal of Symbolic Computation.  Volume 37, Issue 1, pp. 35-81, 2004. Distributed as PDF, Postscript.
• M. Giesbrecht, G. Labahn, W.-s. Lee, Symbolic-numeric sparse interpolation of multivariate polynomials. Proc. 9th Rhine Workshop on Computer Algebra, 2004.
  
• 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 (CASC), pp. 195-205, 2004. Distributed as PDF.
  

2003

• M. Giesbrecht, Y. Zhang, Factoring and Decomposing Ore Polynomials over F_q(t). ACM International Symposium on Symbolic and Algebraic Computation (ISSAC), pp. 127-134, 2003.
• 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.
• M. Giesbrecht, E. Kaltofen, W.-s. Lee, Algorithms for Computing Sparsest Shifts of Polynomials in Standard, Chebyshev, and Pochhammer Bases. Journal of Symbolic Computation. Volume 36, Issues 3-4, 2003, pp. 287-683.
• 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.
  

2002

• 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.
  
• 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, pp. 40-50, Beijing, China, 2002.
• M. Giesbrecht and A. Storjohann, Computing Rational Forms of Integer Matrices.  Journal of Symbolic Computation. Vol. 34, No. 3, September 1, 2002. Distributed as PDF.
• M. Giesbrecht, G. Reid and Y. Zhang, Non-commutative Gröbner Bases in Poincaré-Burkhoff-Witt Extensions, Conference on Computer Algebra and Scientific Computation (CASC'2002), pp. 97-106, 2002. Distributed as PDF, Postscript.

2001

• 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), 2001. pp. 85--92.
• M. Giesbrecht, M. Jacobson, Jr. and A. Storjohann, Algorithms for large integer lattice problems. 14th Symposium on Applied Algebra, Algebraic Algorithms and Error Correcting Codes (AAECC), LNCS 2227, 2001. pp. 297--307.
• M. Giesbrecht, Fast computation of the Smith form of a sparse integer matrix. Computational Complexity, v. 10, number 1, 2001, pp. 41--69. DOI.

2000

• W. Eberly and M. Giesbrecht, Efficient decomposition of associative algebras over finite fields.  Journal of Symbolic Computation, v. 29, 2000, pp. 441-458. Distributed as PDF, Postscript.
• W. Eberly, M. Giesbrecht and G. Villard, On Computing the Determinant and Smith Form of an Integer Matrix.  Proc. 41st Annual IEEE Symposium on Foundations of Computer Science (FOCS'2000), pp. 675-687, 2000. Distributed as PDF, Postscript
• 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. Distributed as PDF, Postscript

1999

• R. Corless, M. Giesbrecht,  D. Jeffrey, and S. Watt,  Approximate Polynomial Decomposition, ACM International Symposium on Symbolic and Algebraic Computation (ISSAC'99), 1999.  Distributed as PDF, Postscript

1998

• M. Giesbrecht, Factoring in skew polynomial rings over finite finite fields.  Journal of Symbolic Computation, v. 26, 1998, pp. 463-486. Distributed as PDF, Postscript.
• M. Giesbrecht, A. Lobo, and B. D. Saunders, Certifying Inconsistency of Sparse Linear Systems, ACM International Symposium on Symbolic and Algebraic Computation (ISSAC'98), 1998, pp. 113-119.  Distributed as PDF, Postscript

1997

• M. Giesbrecht.  Efficient Parallel Solution of Sparse Systems of Linear Diophantine Equations, Proceedings of the ACM International Symposium on Parallel Symbolic Computation (PASCO'97), ACM Press, 1997, pp. 1-10. Distributed as PDF, Postscript.

1996

• W. Eberly & M. Giesbrecht. Efficient Decomposition of Associative Algebras.Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC), 1996, ACM press, pp. 170-178. U. of Manitoba Technical Report 96/03, 1996, 42pp.  Distributed as PDF,PostScript.
• M. Giesbrecht, Probabilistic computation of the Smith normal form of a sparse integer matrix. Proceedings of Algorithms in Number Theory Symposium (ANTS), 1996, Springer Lecture Notes in Computer Science 1122, pp. 173-186.

1995

• M. Giesbrecht, Nearly optimal algorithms for canonical matrix forms. SIAM Journal on Computing, October 1995, v. 24, pp. 948-969.
• M. Giesbrecht, Fast Computation of the Smith form of an integer matrix. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC), 1995, ACM Press, pp. 110-118.
• V.P. Krothapalli, J. Thulasiraman & M. Giesbrecht. Run-time parallelization of irregular DOACROSS loops. In Parallel algorithms for irregularly structured problems: Proceedings of Irregular'95, LNCS 980, pp. 75-80, 1995.

1994

• M. Giesbrecht, Fast algorithms for rational forms of integer matrices. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC), 1994, ACM Press, pp. 305-311.

1992

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

1990

• J. von zur Gathen & M. Giesbrecht, Constructing normal bases in finite fields.  Journal of Symbolic Computation, v. 10, 1990, pp. 547-570.

Technical Reports

• J. Thulasiraman, V.P. Krothapalli & M. Giesbrecht. Run-time parallelization of irregular DOACROSS loops. U. of Manitoba Technical Report 95/03, 1995, 35 pp.
• E. Bach, M. Giesbrecht and J. McInnes. The complexity of number theoretic problems. U. of Toronto Technical Report 247/91, 1991, 52 pp.

Edited Volumes

• J. von zur Gathen and M. Giesbrecht, editors Proceedings of ACM International Symposium on Symbolic and Algebraic Computation. (ISSAC'94), 1994. 359pp.

Dissertations

• M. Giesbrecht, Nearly optimal algorithms for canonical matrix forms. Ph.D. Thesis and U. of Toronto Technical Report 268/93, 1993, 189pp.
• M. Giesbrecht, Some Results on the Functional Decomposition of Polynomials. M.Sc. Thesis and U. of Toronto Technical Report 209/88, 1988, 117 pp.