Fraction-free matrix factors: new forms for LU and QR factors

Abstract

Gaussian elimination and LU factoring have been greatly studied from the algorithmic point of view, but much less from the point view of the best output format. In this paper, we give new output formats for fraction free LU factoring and for QR factoring. The formats and the algorithms used to obtain them are valid for any matrix system in which the entries are taken from an integral domain, not just for integer matrix systems. After discussing the new output format of LU factoring, the complexity analysis for the fraction free algorithm and fraction free output is given. Our new output format contains smaller entries than previously suggested forms, and it avoids the gcd computations required by some other partially fraction free computations. As applications of our fraction free algorithm and format, we demonstrate how to construct a fraction free QR factorization and how to solve linear systems within a given domain.

References

1. Nakos G C Turner P R Williams R M Fraction-free algorithms for linear and polynomial equationsSIGSAM Bull, ACM Press 1997 31(3)1119
2. Zhou W Carette J Jeffrey D J et al.Hierarchical representations with signatures forlarge expression managementAISC, Springer-Verlag,LNAI 4120 2006 254268
3. Sasaki T Nurao H Efficient Gaussian eliminationmethod for symbolic determinants and linear systemsACM Transactions on Mathematical Software 1982 8(3)277289
4. Kirsch B J Turner P R Modified Gaussian eliminationfor adaptive beamforming using complex RNS arithmeticNAWC-AD Tech Rep, NAWCADWAR 1994 941112-50
5. Kirsch B J Turner P R Adaptive beamforming usingRNS arithmeticProceedings of ARTHWashington DCIEEE Computer Society 1993 3643
6. Turner P R Gausselimination: workhorse of linear algebraNAWC-AD Tech Rep, NAWCAD-PAX 96-194-TR 1996
7. Bareiss E H Sylvester'sidentity and multistep integer-preserving Gaussian eliminationMathematics of Computation 1968 22(103)565578
8. Bareiss E H Computationalsolutions of matrix problems over an integral domainJ. Inst. Maths Applics 1972 1068104
9. Gentleman W M Johnson S C Analysis of algorithms, a casestudy: determinants of polynomialsProceedingsof 5th Annual ACM Symp on Theory of ComputingAustinACM Press 1973 135142
10. Griss M L Anefficient sparse minor expansion algorithmHoustonACM 1976 429434
11. McClellan M T Theexact solution of systems of linear equations with polynomial coefficientsJ ACM 1973 20(4)563588
12. Smit J Theefficient calculation of symbolic determinantsProceedings of SYMSACNew YorkACM 1976 105113
13. Smit J A cancellationfree algorithm, with factoring capabilities, for the efficient solutionof large sparse sets of equationsProceedingsof ISSACNew YorkACM 1981 146154
14. Turing A M Rounding-offerrors in matrix processesQuart. J. Mech.Appl. Math 1948 1287308
15. Corless R M Jeffrey D J The Turing factorization ofa rectangular matrixSIGSAM Bull, ACM Press 1997 31(3)2030
16. Dixon J D Exactsolution of linear equations using p–adic expansionNumer. Math 1982 137141
17. Moenck R T Carter J H Approximate algorithms to deriveexact solutions to systems of linear equationsProceedings of the International Symposium on Symbolic and AlgebraicComputationBerlinSpringer-Verlag 1979 6573
18. Storjohann A High-orderlifting and integrality certificationJournalof Symbolic Computation 2003 36(3–4)613648
19. Storjohann A Theshifted number system for fast linear algebra on integer matricesJournal of Complexity 2005 21(4)609650
20. von zur Gathen J Gerhard J Modern computer algebraLondonCambridgeUniversity Press 1999
21. Krick T Pardo L M Sombra M Sharp estimates for the arithmetic NullstellensatzDuke Mathematical Journal 2001 109(3)521598
22. Pursell L Trimble S Y Gram-Schmidt orthogonalizationby Gaussian eliminationAmerican Math. Monthly 1991 98(6)544549