Recent methods for handling matrix problems over an integral domain are investigated from a unifying point of view. Emphasized are symbolic matrix inversion and numerically 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 ordernover 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 polynomials 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 overGF(x-pk)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 of recent tests, using existing codes, standard matrices and matrices with random elements are reported and summarized in tabular form. The paper concludes that the two-step elimination method be used for the inversion problem of numeric matrices, and in particular when a black-box approach to the matrix inversion problem is attempted such as in commercial time sharing systems. It is recommended that the inversion problem of matrices with elements over the polynomial ring be reduced to the numeric inversion problem with subsequent interpolation. An extensive Reference list is added.
展开▼
