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

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.

• 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.

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.