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

doi:10.1007/s11704-008-0005-z

Front. Comput. Sci.

2008, Vol. 2

Issue (1) : 67-80 https://doi.org/10.1007/s11704-008-0005-z

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

ZHOU Wenqin, J. JEFFREY David

Applied Mathematics Department, University of Western Ontario

Download: PDF(273 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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.

Issue Date: 05 March 2008

Cite this article:

J. JEFFREY David,ZHOU Wenqin. Fraction-free matrix factors: new forms for LU and QR factors[J]. Front. Comput. Sci., 2008, 2(1): 67-80.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-008-0005-z
https://academic.hep.com.cn/fcs/EN/Y2008/V2/I1/67

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

Viewed

Full text

Abstract

Cited

Shared

Discussed