The Exact Solution of Linear Equations with Rational Function Coefficients
Michael T. McClellan · ACM Transactions on Mathematical Software · 1977
Algorithms for computing exact general solutions for systems of linear equations with rational function (or rational number) coefficients are described, and analytical time and space bounds are obtained.The algorithms chosen are those most effective for systems with dense coefficient matrices and dense polynomial numerators and denominators.The first algorithm (semimodular algorithm LCM) converts the system to integral form and applies the modular algorithm for systems with polynomial coefficients.This is compared to a complete modular algorithm (RLES) which applies directly to systems with rational coefficients.The third algorithm compared is rational Gauss elimination (RGE).The analytical bounds show that LCM is orders of magnitude faster than RGE and always requires less space, while RLES is the worst case of LCM spacewise and timewise.Tables of actual computing times are given for the algorithms, which were programmed in Fortran IV for the SAC-1 system for symbolic and algebraic calculation and run on a Univac 1108.These confirm the analytical results and are used to obtain actual computing time growth rates as functions of system size m.Also given is a sample application to inverting ill-conditioned matrices which reexamines the effect of initial roundoff.