Computational solutions of matrix problems over an integral domain

Recent methods for handling matrix problems over an integral domain are investigated from a unifying point of view. Emphasized are symbolic matrix inversion and numeri-cally exact methods for solving Ax = b. New proofs are given for the theory of the multistep method. A proof for the existence and an algorithm for the exact solution of Tx = b, where T is a finite Toeplitz matrix, is given. This algorithm reduces the number of required single precision multiplications by a factor of order n over the corresponding Gaussian elimination method. The use of residue arithmetic is enhanced by a new termination process. The matrix inversion problem with elements in the ring of poly-nomials is reduced to operations over a Galois field. It is shown that interpolation methods are equivalent to congruence methods with linear modulus and that the Chinese remainder theorem over GF(x—pJ is the Lagrange interpolation formula. With regard to the numerical problem of exact matrix inversion, the One- and Two-step Elimination methods are critically compared with the methods using modular or residue arithmetic. Formulas for estimating maximum requirements for storage and timing of the salient parts of the algorithms are developed. The results of a series o