The size of numbers in the analysis of certain algorithms
Ravindran Kannan · 1980
The aim of this thesis is to emphasize the importance of reckoning the size of the numbers produced and handled by certain algorithms. In the main, algorithms in the literature are analyzed in terms of the number of arithmetic operations executed by them--the tacit assumption being that the operands would not be too large and hence each operation may be considered to take a constant amount of time. The alternative, perhaps more realistic, measure would be to reckon the total time spent by the algorithm which would have to include the time spent on each operation--which is a function of the size of the operands. The justifications for the use of the first measure are that it is easier to compute and in general, the operands do remain small. However we point out some examples of well-known algorithms where these assumptions do not apply. In the case of the LUP decomposition algorithm for solving simultaneous equations and the Euclidean algorithm to find the greatest common divisor of two polynomials, we present prima facie cases for the size of the numbers (number of binary digits required to represent the numbers) produced by these algorithms not to be polynomially bounded in the length of the input. However neither a proof that these algorithms are polynomial-time bounded under the second measure nor an exponential lower bound is known for them. There are known good algorithms (i.e., polynomial-time bounded under the second measure) for both these problems. For the first, a good algorithm also follows as a corollary of the triangularization algorithm of this thesis as is pointed out later. A different situation obtains in the case of unimodular triangularization and diagonalization, i.e., computation of the Hermite and Smith normal forms of an integer matrix. Known algorithms for these problems could be proved to be polynomially-time bounded only under the assumption that all intermediate numbers produced by these algorithms were polynomial-size bounded. This results from the fact that the number of arithmetic operations performed by these algorithms depends upon the size of the numbers computed. Thus the algorithms were not known to be polynomial-time bounded even under the first measure. Here again no exponential lower bound is known, even under the second measure. However, as pointed out in the literature, there is a possibility of the magnitude of numbers squaring at each iteration, and since there are n such iterations for an n X n matrix, there is a case for numbers as large as 2('2('n)) being produced, thus rendering the algorithms exponential under the second measure. The thesis gives a good algorithm for the Hermite normal form and using this we present a good algorithm for the Smith normal form. Since these normal forms find numerous applications, accurate and fast computability of the forms is important. Several extensions of the Hermite normal form algorithm and further applications thereof are presented. In the case of aggregation--a technique used to produce one linear Diophantine equation in nonnegative variables that has the same set of solutions as a given system of simultaneous linear Diophantine equations in nonnegative variables--known methods were usually discussed with a note of caution about the large size of the coefficients in the aggregated equation. The last chapter supplies a proof that, in fact, aggregation can be done by a good algorithm. Aggregation is also usually qualified by the remark that the set of solutions of the original system must be assumed bounded. We show that such a hypothesis can be circumvented. For the case of bounded integer programming, aggregation is shown to yield an exact analog of the well-known Farkas' lemma of linear programming.