Symbolic Linear Algebra: Design, analysis and implementation, Mark Giesbrecht and Arne Storjohann

Computations with matrices over symbolic and exact domains lie at the heart of many computations in Computer Algebra. Solving and computing normal forms (and other invariants) of linear systems whose coefficients are integers, polynomials, or members of a generic ring or field, are often bottlenecks for big algebraic computations. Very large and often structured symbolic linear systems must be solved in fundamental algorithms in computational number theory, computational group theory, symbolic integration and polynomial and differential systems.

Over the past decade there has been significant progress in the design and implementation of algorithms for these problems. These methods are adapted to the very large and often sparse and/or structured systems which now arise.

  1. Matrix operations over a generic field. Algorithms are presented for matrix computations over a generic field. Fundamental in this is the row-echelon form --- to recover invariants such as the rank, determinant, nullspace and to solve linear systems. Computation of canonical matrix forms such as the Frobenius and Jordan form are also discussed. The efficient solution of these problems in the case of dense input matrices is now very well understood; for sparse input some questions remain. An additional issue is to bound the intermediate storage requirements.
  2. Matrices over more general rings. The ring of integers and the ring of polynomials with coefficients from a field are ubiquitous in practice. Here we need to consider the effect of intermediate expression swell in terms of coefficient size and (in the case of polynomials) degree. For sparse matrices we must also manage fill-in. A careful cost analysis of both time (in machine word operations) and space (in words) will yield effective and practical algorithms. Fundamental problems include solving linear diophantine systems and computing canonical matrix forms such as the Hermite and Smith form.
  3. Implementation. We will look at some of the available tools and packages for doing symbolic linear algebra, and discuss the development of algorithms for linear systems with special structure or properties.

Target Audience
  • Researchers and students designing and implementing algorithms in Computer Algebra which demand the solution of large symbolic or exact linear systems.
  • Computer scientists interested in a survey of the main algorithmic techniques used in the design of fast algorithms for symbolic linear algebra.

The Presenters
Mark Giesbrecht is an Associate Professor of Computer Science at the University of Western Ontario and a Principal Investigator at the Ontario Research Centre for Computer Algebra. His research interests include symbolic linear and multi-linear algebra, symbolic-numeric algorithms, and compilers.

Arne Storjohann obtained his PhD in 2000 (ETH Zurich) and currently holds a position at the Ontario Research Center for Computer Algebra. His research interests include symbolic linear algebra and computational number theory.

Christopher W Brown
Last modified: Tue Apr 3 16:26:27 EDT 2001