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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Nakos G C, Turner P R, Williams R M. Fraction-free algorithms for linear and polynomial equations. SIGSAM Bull, ACM Press, 1997, 31(3): 11–19
Zhou W, Carette J, Jeffrey D J, et al. Hierarchical representations with signatures for large expression management. AISC, Springer-Verlag, LNAI 4120, 2006, 254–268
Sasaki T, Nurao H. Efficient Gaussian elimination method for symbolic determinants and linear systems. ACM Transactions on Mathematical Software, 1982, 8(3): 277–289
Kirsch B J, Turner P R. Modified Gaussian elimination for adaptive beamforming using complex RNS arithmetic. NAWC-AD Tech Rep, NAWCADWAR, 1994, 941112-50
Kirsch B J, Turner P R. Adaptive beamforming using RNS arithmetic. In: Proceedings of ARTH. Washington DC: IEEE Computer Society, 1993, 36–43
Turner P R. Gauss elimination: workhorse of linear algebra. NAWC-AD Tech Rep, NAWCAD-PAX 96-194-TR, 1996
Bareiss EH. Sylvester’s identity and multistep integer-preserving Gaussian elimination. Mathematics of Computation, 1968, 22(103): 565–578
Bareiss E H. Computational solutions of matrix problems over an integral domain. J. Inst. Maths Applics, 1972, 10: 68–104
Gentleman WM, Johnson S C. Analysis of algorithms, a case study: determinants of polynomials. In: Proceedings of 5th Annual ACM Symp on Theory of Computing. Austin: ACM Press, 1973, 135–142
Griss M L. An efficient sparse minor expansion algorithm. Houston: ACM, 1976, 429–434
McClellan M T. The exact solution of systems of linear equations with polynomial coefficients. J ACM, 1973, 20(4): 563–588
Smit J. The efficient calculation of symbolic determinants. In: Proceedings of SYMSAC. New York: ACM, 1976, 105–113
Smit J. A cancellation free algorithm, with factoring capabilities, for the efficient solution of large sparse sets of equations. In: Proceedings of ISSAC. New York: ACM, 1981, 146–154
Turing A M. Rounding-off errors in matrix processes. Quart. J. Mech. Appl. Math, 1948, 1: 287–308
Corless R M, Jeffrey D J. The Turing factorization of a rectangular matrix. SIGSAM Bull, ACM Press, 1997, 31(3): 20–30
Dixon J D. Exact solution of linear equations using p-adic expansion. Numer. Math, 1982, 137–141
Moenck R T, Carter J H. Approximate algorithms to derive exact solutions to systems of linear equations. In: Proceedings of the International Symposium on Symbolic and Algebraic Computation. Berlin: Springer-Verlag, 1979, 65–73
Storjohann A. High-order lifting and integrality certification. Journal of Symbolic Computation, 2003, 36(3–4): 613–648
Storjohann A. The shifted number system for fast linear algebra on integer matrices. Journal of Complexity, 2005, 21(4): 609–650
von zur Gathen J, Gerhard J. Modern computer algebra. London: Cambridge University Press, 1999
Krick T, Pardo L M, Sombra, M. Sharp estimates for the arithmetic Nullstellensatz. Duke Mathematical Journal, 2001, 109(3): 521–598
Pursell L, Trimble S Y. Gram-Schmidt orthogonalization by Gaussian elimination. American Math. Monthly, 1991, 98(6): 544–549
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Zhou, W., Jeffrey, D.J. Fraction-free matrix factors: new forms for LU and QR factors. Front. Comput. Sci. China 2, 67–80 (2008). https://doi.org/10.1007/s11704-008-0005-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11704-008-0005-z