Please wait a minute...
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

Postal Subscription Code 80-970

2018 Impact Factor: 1.129

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