A Comparison of Algorithms for the Exact Solution of Linear Equations
Michael T. McClellan · ACM Transactions on Mathematical Software · 1977
A computing-time study is presented of several algorithms for the exact solution of dense systems of linear equations with integer or dense polynomial coefficients.The analytical computing times for rational Gauss elimination, exact division elimination (one step and two step), and the modular algorithm are summarized and supplemented.Extensive empirical studies illustrate the superiority of the modular algorithm for completely dense problems, in agreement with the analytical results.All algorithms were programmed in Fortran IV for the SAC-1 System, and all cases were run on a Univac 1108.