The Exact Solution of Systems of Linear Equations with Polynomial Coefficients

Publisher Website
Google Scholar
Abstract
An algorithm is presented for computing exactly general solutions for systems of linear equations with integer or polynomial coefficients. The algorithm applies modular homomorphisms-- reductions modulo a prime and evaluations eventually applying a Gaussian elimination algorithm to systenis with coefficients in GF(p). Then, by applying interpolation and the Chinese Remainder Algorithm, a general solution is obtained if the system is found to be consistent. Also included is a modular algorithm for matrix multiplication, as required for substitution tests. The computing times of these modular algorithms are analyzed. The computing time bounds, which dominate these times, are obtained as functions of the size of the system and the numeric coefficient and degree sizes of the system coefficients. A comparison with similar bounds for the exact division algorithm reveals the clear superiority of the modular algorithm.