Symbolic Computation Group

Recent Papers

This is a short list of some recent publications by researchers associated with SCG. For more details see individual researchers' home pages.

2010

J. von zur Gathen, Mark Giesbrecht and K. Ziegler. Composition collisions at degree p². To appear: International Symposium on Symbolic and Algebraic Computation (ISSAC) 2010, 2010.
Mark Giesbrecht and D. Roche. Detecting lacunary perfect powers and computing their roots. To appear: Journal of Symbolic Computation, 2010.

2009

Mark Giesbrecht, George Labahn and W.-s. Lee. Symbolic-numeric sparse interpolation of multivariate polynomials. Journal of Symbolic Computation, Volume 44, pp. 943-959, 2009.
Mark Giesbrecht and 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, 2009.
B. Beckermann and George Labahn. Fraction-Free Computation of Simultaneous Pade Approximants. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC) 2009, ACM Press, pp. 15-22, Seoul, Korea, 2009.
Wei Zhou and George Labahn. Efficient Computation of Order Bases. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC) 2009, ACM Press, pp. 375-382, Seoul, Korea, 2009.
S. Maclean, D. Tausky, George Labahn, E. Lank and M. Marzouk. Tools for the efficient generation of hand-drawn corpora based on context-free grammars. Proceedings of the Eurographics Symposium on Sketch-Based Interfaces and Modeling (SBIM 2009), pp. 125-132, 2009.
D. Roche. Space- and Time-Efficient Polynomial Multiplication. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC) 2009, Seoul, Korea, July 28-31, 2009. Implementation (gzipped tar). Presentation (PDF). Longer Version (PDF).
Arne Storjohann. Integer matrix rank certification. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC) 2009, ACM Press, pp. 8, 2009.
Brice Boyer, Jean-Guillaume Dumas, C. Pernet and Wei Zhou. Memory efficient scheduling of Strassen-Winograd's matrix multiplication algorithm. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC) 2009, July 28, 2009. Slides.
Mark Giesbrecht and D. Roche. Interpolation of shifted-lacunary polynomials. To appear: Computational Complexity, 2009.
Mark Giesbrecht, George Labahn and Yang Zhang. Computing Popov Forms of Matrices over PBW Extensions. Ninth Asian Symposium on Computer Mathematics (ASCM) 2009, Fukuoka, Japan, December 14-17, 2009.

2008

Mark Giesbrecht and D. Roche. On Lacunary Polynomial Perfect Powers. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC) 2008, RISC, Linz, Austria, July 20-23, 2008. Implementation (gzipped tar) (requires GMP and NTL) . GMP. NTL.
George Labahn, E. Lank, M. Marzouk, A. Bunt, S. Maclean and D. Tausky. MathBrush: A Case Study for Pen-based Interactive Mathematics. Proceedings of the 5th Eurographics Workshop on Sketch-Based Interfaces and Modelling (SBIM 2008), 2008.
Arne Storjohann. On the complexity of inverting integer and polynomial matrices. Updated draft pp. 26 (December 31 2008), Submitted for publication, 2008.
D. Roche. Adaptive Polynomial Multiplication. Milestones in Computer Algebra (MICA 2008), Stonehaven Bay, Trinidad and Tobago, May 1-3, 2008.
George Labahn, E. Lank, S. Maclean, M. Marzouk and D. Tausky. MathBrush: A system for doing math on pen-based devices. Eighth IAPR Workshop on Document Analysis Systems, pp. 599-606, 2008.

2007

C. Pernet and Arne Storjohann. Faster algorithms for the characteristic polynomial. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC) 2007, ACM Press, pp. 307-314, 2007.
B. Beckermann, G. Golub and George Labahn. On the Numerical Condition of a Generalized Hankel Eigenvalue Problem. Numerische Mathematik, 106(1),pp. 41-68, 2007.
H. Cheng and George Labahn. Output-sensitive Modular Algorithms for Polynomial Matrix Normal Forms. Journal of Symbolic Computation, 42(7) pp. 733-750, 2007.
D. Tausky, George Labahn, E. Lank and M. Marzouk. Managing Ambiguity in Mathematical Matrices. Proceedings of the Eurographics Workshop on Sketch-Base Interfaces and Modelling (SBIM), 2007.
W. Eberly, Mark Giesbrecht, P. Giorgi, Arne Storjohann and G. Villard. Faster inversion and other black box matrix computations using efficient block projections. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC) 2007, ACM Press, pp. 143-150, 2007.
Mark Giesbrecht and D. Roche. Interpolation of Shifted-Lacunary Polynomials. Mathematical Aspects of Computer and Information Sciences (MACIS), 2007.
Z. Olesh and Arne Storjohann. The vector rational function reconstruction problems. Proceedings of the Waterloo Workshop on Computer Algebra: devoted to the 60th birthday of Sergei Abramov (WWCA), World Scientific, pp. 137-149, 2007.
J. Selby, F. Ruffell, Mark Giesbrecht and M. Godfrey. Recovering Maintainability Effort in the Presence of Global Data Usage. Proceedings of the 14th Working Conference on Reverse Engineering (WCRE), pp. 60-69, 2007.

2006

B. Beckermann, George Labahn and G. Villard. Normal Forms for General Polynomial Matrices. Journal of Symbolic Computation, 41(6), pp. 708-737, 2006.
B. Beckermann, H. Cheng and George Labahn. Fraction-free Row Reduction of Matrices of Ore Polynomials. Journal of Symbolic Computation, 41(5), pp. 513-543, 2006.
H. Cheng and George Labahn. On Computing Polynomial GCD in Alternate Bases. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC) 2006, ACM Press, pp. 47-54, Genoa, Italy, 2006.
Mark Giesbrecht, George Labahn and W.-s. Lee. Symbolic-numeric Sparse Interpolation of Multivariate Polynomials. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC) 2006, ACM Press, pp. 116-123, Genoa, Italy, 2006.
George Labahn, S. Maclean, M. Marzouk, I. Rutherford and D. Tausky. A preliminary report on the MathBrush pen-math system. Proceedings of the Maple Conference 2006, pp. 162-178, 2006.
W. Eberly, Mark Giesbrecht, P. Giorgi, Arne Storjohann and G. Villard. Solving sparse rational linear systems. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC) 2006, ACM Press, pp. 63-70, 2006.
F.W. Chapman and K.O. Geddes. An improved algorithm for the automatic derivation and proof of tensor product identities via computer algebra. Proceedings of Calculemus 2006, (Genoa, Italy, Jul 2006), Anna Bigatti and Silvio Ranise (ed.), pp. 67. To appear in Electronic Notes in Theoretical Computer Science, Elsevier B.V., Amsterdam, 2006.
J. Selby and Mark 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.

2005

Mark Giesbrecht, George Labahn and Yang Zhang. Computing Valuation Popov Forms. Proceedings of Computer Algebra Systems and their Applications (CASA) 2005, Lecture Notes on Computer Science 3516, Springer-Verlag, pp. 619-626, 2005.
Arne Storjohann. The shifted number system for fast linear algebra on integer matrices. Journal of Complexity, v. 21(4), pp. 609-650, 2005.
Z. Chen and Arne Storjohann. A BLAS based C library for exact linear algebra on integer matrices. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC) 2005, ACM Press, pp. 92-99, 2005.
Arne Storjohann and G. Villard. Computing the rank and a small nullspace basis of a polynomial matrix. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC) 2005, ACM Press, pp. 309-316, 2005. Extended Version in RR LIP 2005-3, ENS Lyon, France.
George Labahn and T. Humphries. Symbolic Integration of Jacobian Elliptic Functions in Maple. Proceedings of the Maple Conference 2005, pp. 331-339, 2005.
O.A. Carvajal, F.W. Chapman and K.O. Geddes. Hybrid symbolic-numeric integration in multiple dimensions via tensor-product series. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC) 2005, Manuel Kauers (ed.), ACM Press, pp. 91, New York, 2005.
Tom Robinson and K.O. Geddes. Automated generation of numerical evaluation routines. Proceedings of the Maple Conference 2005, Ilias S. Kotsireas (ed.), Maplesoft, Waterloo, Ontario, Canada, pp. 398, 2005.
Yu.A. Brychkov and K.O. Geddes. On the derivatives of the Bessel and Struve functions with respect to the order. Integral Transforms and Special Functions, 16 (3), pp. 198, April, 2005.
C. Oancea, J. Selby and Mark Giesbrecht. Distributed Models of Thread-Level Speculation. International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA), 2005.
Mark 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.
B. Botting, Mark Giesbrecht and J.P. May. Using the Riemannian SVD for Problems in Approximate Algebra. International Workshop on Symbolic-Numeric Computation (SNC), pp. 209-219, July, 2005.

2004

George Labahn and Ziming Li. Hyperexponential Solutions of Finite-rank Ideals in Orthogonal Ore Algebras. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC) 2004, Santander, Spain, ACM Press, pp. 213-220, 2004.
R. Burger, George Labahn and M. van Hoeij. Closed form solutions of linear odes having elliptic functions as coefficients. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC) 2004, Santander, Spain, ACM Press, pp. 58-64, 2004.
Mark Giesbrecht, George Labahn and W.-s. Lee. Symbolic-Numeric Sparse Polynomial Interpolation in Chebyshev Basis and Trigonometric Interpolation. Proceedings of Computer Algebra in Scientific Computing (CASC) 2004, St. Petersburg, Russia, 2004.
T. Mulders and Arne Storjohann. Certified dense linear system solving. Journal of Symbolic Computation, 37(4), pp. 485-510, 2004.
D. Saunders, Arne Storjohann and G. Villard. Matrix rank certification . Electronic Journal of Linear Algebra, 11, pp. 16-23, 2004.
S.A. Abramov, J.J. Carette, K.O. Geddes and H.Q. Le. Telescoping in the context of symbolic summation in Maple. Journal of Symbolic Computation, 38 (4), pp. 1326, October, 2004.
K.O. Geddes, H.Q. Le and Ziming Li. Differential rational normal forms and a reduction algorithm for hyperexponential functions. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC) 2004, J. Gutierrez (ed.), ACM Press, pp. 190, New York, 2004.
Yu.A. Brychkov and K.O. Geddes. Differentiation of hypergeometric functions with respect to parameters. Appears in Abstract and Applied Analysis, (Proceedings of the International Conference, Hanoi, Vietnam), N.M. Chuong, L. Nirenberg and W. Tutschke (ed.), World Scientific, pp. 28, 2004.
W. Eberly and Mark Giesbrecht. Efficient decomposition of separable algebras. Journal of Symbolic Computation, Volume 37, Issue 1, pp. 35-81, 2004.
Mark Giesbrecht, George Labahn and W.-s. Lee. Symbolic-numeric sparse interpolation of multivariate polynomials. Proceedings of the Ninth Rhine Workshop on Computer Algebra, 2004.

2003

T. Mulders and Arne Storjohann. On lattice reduction for polynomial matrices. Journal of Symbolic Computation, 35(4), pp. 377-401, 2003.
Arne Storjohann. High-order lifting and integrality certification. Journal of Symbolic Computation, 36(3-4), pp. 613-648, 2003.
K.O. Geddes and W.W. Zheng. Exploiting fast hardware floating point in high precision computation. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC) 2003, J.R. Sendra (ed.), ACM Press, pp. 118, New York, 2003.
Mark Giesbrecht and Yang Zhang. Factoring and Decomposing Ore Polynomials over F_q(t). Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC) 2003, pp. 127-134, 2003.
J. Gerhard, Mark Giesbrecht, Arne Storjohann and E. Zima. Shiftless decomposition and polynomial-time rational summation. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC) 2003, pp. 119-126, 2003.
Mark Giesbrecht, E. Kaltofen and W.-s. Lee. Algorithms for Computing Sparsest Shifts of Polynomials in Standard, Chebyshev, and Pochhammer Bases. Journal of Symbolic Computation, 36(3-4), pp. 287-683, 2003.
Mark Giesbrecht, Arne Storjohann and G. Villard. Algorithms for matrix canonical forms. Invited Submission: Computer Algebra Handbook · Foundations, Applications, Systems, Springer Verlag, pp. 38-41, 2003.

2002

B. Beckermann, H. Cheng and George Labahn. Fraction-free row reduction of matrices of skew polynomials. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC) 2002, ACM Press, pp. 8-15, Lille, France, 2002.
Jean-Guillaume Dumas, T. Gautier, Mark Giesbrecht, P. Giorgi, B. Hovinen, E. Kaltofen, 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.
Mark Giesbrecht, E. Kaltofen and W.-s. Lee. Algorithms for computing the sparsest shifts for polynomials via the Berlekamp/Massey algorithm. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC) 2002, ACM Press, Lille, France, 2002.
Mark Giesbrecht and Arne Storjohann. Computing Rational Forms of Integer Matrices. Journal of Symbolic Computation, 34(3), pp. 157-172, September 1, 2002.
Mark Giesbrecht, G. Reid and Yang Zhang. Non-commutative Gröobner Bases in Poincaré-Burkhoff-Witt Extensions. Conference on Computer Algebra and Scientific Computation, pp. 97-106, 2002.
C.P. Jeannerod and George Labahn. The SNAP package for arithmetic with numeric polynomials. International Congress of Mathematical Software, World Scientific, pp. 61-71, 2002.
S.A. Abramov, K.O. Geddes and H.Q. Le. Computer algebra library for the construction of the minimal telescopers. International Congress of Mathematical Software, A.M. Cohen, X. Gao, N. Takayama (ed.), World Scientific, pp. 329, 2002.
K.O. Geddes and H.Q. Le. An algorithm to compute the minimal telescopers for rational functions (Differential-integral case). International Congress of Mathematical Software, A.M. Cohen, X. Gao, N. Takayama (ed.), World Scientific, pp. 463, 2002.

2001

H. Cheng and George Labahn. Computing all factorizations in Zn[x]. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC) 2001, ACM Press, pp. 64-71, London, Ontario, 2001.
R.M. Corless, Mark Giesbrecht, M. van Hoeij, Ilias S. Kotsireas and S.M. Watt. Towards Factoring Bivariate Approximate Polynomials. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC) 2001, ACM Press, pp. 85-92, 2001.
Ziming Li and F. Schwarz. Rational Solutions of Riccati-like Partial Differential Equations. Journal of Symbolic Computation, 31, pp. 619-716, 2001.
E. Zima. On computational properties of chains of recurrences. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC) 2001, ACM Press, 2001.
K.O. Geddes. Algorithms for indefinite and definite integration in Maple. Appears in Applications of Computer Algebra, (Proceedings of the International Symposium on Applications of Computer Algebra, Kolhapur, India, Oct 2000), R. Akerkar (ed.), Allied Publishers Ltd, Mumbai, pp. 84, 2001.
K.O. Geddes. Hybrid symbolic-numeric methods applied to definite integrals and ODEs. Appears in Applications of Computer Algebra, (Proceedings of the International Symposium on Applications of Computer Algebra, Kolhapur, India, Oct 2000), R. Akerkar (ed.), Allied Publishers Ltd, Mumbai, pp. 108, 2001.
Mark Giesbrecht, M. Jacobson Jr. and Arne Storjohann. Algorithms for Large Integer Matrix Problems. Proceedings of the Fourteenth Symposium on Applied Algebra, Algebraic Algorithms and Error Correcting Codes (AAECC), LNCS 2227, pp. 297-307, 2001.
Mark Giesbrecht. Fast computation of the Smith form of a sparse integer matrix. Computational Complexity, 10(1), pp.41-69, 2001.

2000

S.A. Abramov and H.Q. Le. Applicability of Zeilberger's algorithm to rational functions. Proceedings of the International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC) 2000, Springer-Verlag, pp. 91-102, 2000.
H. Cheng and E. Zima. On Accelerated Methods to Evaluate Sums of Products of Rational Numbers. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC) 2000, ACM Press, pp. 54-61, 2000.
K.O. Geddes. Generating numerical ODE formulas via a symbolic calculus of divided differences. SIGSAM Bulletin, 33 (128), pp. 29-42, 2000.
C.P. Jeannerod. An algorithm for the eigenvalue perturbation problem: reduction of a kappa-matrix to a Lidskii matrix. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC) 2000, ACM Press, pp. 184-191, 2000.
E. Kaltofen, W.-s. Lee and A. Lobo. Early termination in Ben-Or/Tiwari sparse interpolation and a hybrid of Zippel's algorithm. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC) 2000, ACM Press, pp. 192-201, 2000.
B. Beckermann and George Labahn. Fraction-free Computation of Matrix Rational Interpolants and Matrix GCD's. SIAM Journal on Matrix Analysis and Applications, 22(1), pp. 114-144, 2000.
B. Beckermann and George Labahn. Effective Computation of Rational Approximants and Interpolants. Reliable Computing, 6, pp. 365-390, 2000.
T. Mulders and Arne Storjohann. Rational Solutions of Singular Linear Systems. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC) 2000, ACM Press, pp. 242-249, 2000.
W. Eberly and Mark Giesbrecht. Efficient decomposition of associative algebras over finite fields. Journal of Symbolic Computation, 29(1), 2000.
W. Eberly, Mark Giesbrecht and G. Villard. On Computing the Determinant and Smith Form of an Integer Matrix. Proceedings of the Fourty-first Annual IEEE Symposium on Foundations of Computer Science (FOCS) 2000, pp. 675-687, 2000.
R.M. Corless, Mark Giesbrecht, Ilias S. Kotsireas and S.M. Watt. Numerical Implicitization of Parametric Hypersurfaces with Linear Algebra. Proceedings of the Artificial Intelligence and Symbolic Computation (AISC) International Conference 2000, Madrid, Spain, July 17-19, 2000.

Symbolic Computation Group
Cheriton School of Computer Science
University of Waterloo
200 University Avenue West
Waterloo, Ontario, Canada N2L 3G1
519 888 4567

| http://www.scg.uwaterloo.ca