Extended gcds and exact linear algebra

George Havas
University of Queensland

Reduction methods are the basis of algorithms for determining canonical forms of matrices over many computational domains. Experimental results have shown that various methods based on Gaussian elimination (which is a specialized kind of reduction algorithm) in Euclidean rings may lead to rapid growth of intermediate entries. On the other hand various polynomial time algorithms do exist for such computations, but these algorithms are relatively complicated to describe and understand.

Straightforward reduction methods provide the simplest descriptions of algorithms for this purpose. Such algorithms have a nice polynomial number of steps, but the steps deal with long operands. Here we show that there is a doubly exponential lower bound on the operands for a well-defined reduction algorithm when applied to Smith and Hermite normal form calculation for certain Euclidean rings. We present explicit matrices for which this variant produces doubly exponential entries.

Thus, reduction algorithms have worst-case exponential space and time complexity for such applications. The analysis provides guidance as to how matrix algorithms for Euclidean rings which use reduction algorithms may be further developed for better performance. This is important since many practical algorithms for computing canonical forms are so based. Reduction algorithms are composed of repeated applications of the extended gcd algorithm, and the analysis is explained in terms of this.