Symbolic Computation Group

The determinant of an n x n matrix can be computed using Gaussian elimination. The cost of this in the "algebraic model" of computation is O(n^3) --- we assign a unit cost to each arithmetic operation. But if the matrix has entries, for exmaple, polynomials with coefficients from a finite field, our running time analysis should take into account the growth in degrees of entries --- this is called the "bit model" of computation.

In this talk I will present some new techniques which allow solving a number of linear algebra problems in the "bit model" in about the same time as the "algebraic model".