Algorithm for the exact reduction of a matrix to Frobenius form using modular arithmetic. II

Part I contained a description of the single-modulus algorithm for reducing a matrix to Frobenius form, obtaining exact integral factors of the characteristic polynomial.Part II contains a description of the multiple-modulus algorithm.Since different moduli may yield different factorizations, an algorithm is given for determining which factorizations are not correct factorizations over the integers of the characteristic polynomial.Part II also contains a discussion of the selection of the moduli and numerical examples.C. The Multiple-Modulus Algorithm 7. Introduction.The algorithm described in Chapter B uses single-modulus residue arithmetic to reduce a matrix A to Frobenius form (1.1).We recall that the size of the modulus p depends on the bound (4.4).If 2 is too large to be representable in a computer as a single-precision integer, then /? will have to be stored as a multiple-precision integer, making computations modulo p too difficult to be practical.In order to avoid this problem, we select a set of prime moduli, pu p2, , p" with (7.1) p = Pip2 p,, because this enables us to obtain results modulo p by doing most of the arithmetic modulo pi, for i = 1,2, , s. Choosing the moduli as primes also guarantees that** (/?,, Pi) = 1, for ; ; j.Furthermore, we choose the moduli so thatwhere the bn are defined in (4.2).We perform similarity transformations modulo /? on \A\Pi, for i = 1,2, , s, by using the single-modulus procedure described in Chapter B in order to obtain the residue representations (see Szabo and Tanaka [1967, p. 12]) for the factors of the characteristic polynomial modulo /? of A, (7.3) /,(\) ~ !|/,(X)L, |/,(X)L, , \ii(X)\p,}.