Paper Info
Title
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 computa- tions. 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.
Year
DOI
Venue
2008
10.1007/s11704-008-0005-z
Frontiers of Computer Science in China
Keywords
DocType
Volume
fraction free LU factoring,fraction free Gaussian elimination,fraction free QR factoring,complexity analysis
Journal
2
Issue
ISSN
Citations 
1
2095-2228
5
PageRank 
References 
Authors
0.65
13
2
Name
Order
Citations
PageRank
Wenqin Zhou1102.17
David J. Jeffrey21172132.12