Mark Giesbrecht

Professor

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

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

Research

My research interests are in all aspects of symbolic 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.

Publications and Preprints

Submitted for Publication

  • M. Giesbrecht and M. Sub Kim. Computation of the Hermite form of a Matrix of Ore Polynomials. Submitted for publication. Preprint in arXiv.

2012

  • M. Giesbrecht and A. Heinle. A polynomial-time algorithm for the Jacobson form of a matrix of Ore polynomials. To appear, CASC 2012.
  • M. Elsheikh, M. Giesbrecht, A. Novocin, B.D. Saunders. Fast Computation for Smith Forms of Sparse Matrices Over Local Rings. To appear, ISSAC 2012. arXiv.
  • M. Giesbrecht, D. Roche, and H. Tilak. Computing sparse multiples of polynomials. Algorithmica. In Press. DOI, arXiv.
  • M. Giesbrecht, D. Panario. In honour of the research and influence of Joachim von zur Gathen at 60. To appear. DOI.
  • M. Giesbrecht. Algorithms for irreducibility testing and constructing irreducible polynomials. Handbook of Finite Fields. To appear.

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

2007

  • M. Giesbrecht and D. Roche, Interpolation of Shifted-Lacunary Polynomials, Mathematical Aspects of Computer and Information Sciences (MACIS), 2007.  To appear. 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 Fq(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

1994

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

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

 

Last modified on Wednesday, 23 May 2012, at 05:22 hours.