Symbolic Computation Group

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

High-Order Lifting
Arne Storjohann, University of Waterloo
Friday, February 8, 2002, at U. of Western Ontario.

Abstract:

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

 

Last modified on Sunday, 04 November 2012, at 20:42 hours.