The Exact Solution of Linear Equations with Rational Function Coefficients

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.