1997/01/01 by Xin Fang, George Havas · 2 citations
Computer Science · Engineering · #Complexity and Algorithms in Graphs #graph theory and CDMA systems #Algorithms and Data Compression
paper · pdf · doi:10.1145/258726.258740
openalex publication_date 1997/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
Gaussian elimination is the baais for classical algorithms for computing canonical forms of integer matrices. Experimental results have shown that integer Gaussian elimination 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. Gaussian elimination provides the simplest descriptions of algorithms for this purpose. These algorithms have a nice polynomial number of steps, but the steps deaf with long operands. Here we show that there is an exponential length lower bound onthe operands for swell-defined variant of Gaussian elimination when applied to Smith and Hermite normal form calculation, We present explicit matrices for which this variant produces exponential length entries. Thus, Gaussian elimination has worst-case exponential space and time complexity for such applications. The analysis provides guidance as to how integer matrix algorithms based on Gaussian elimination may be further developed for better performance, which is important since many practical algorithms for computing canonical forms are so based.