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.