Common Factors in Fraction-Free Matrix Decompositions
- PDF / 412,487 Bytes
- 20 Pages / 547.087 x 737.008 pts Page_size
- 20 Downloads / 198 Views
Mathematics in Computer Science
Common Factors in Fraction-Free Matrix Decompositions Johannes Middeke · David J. Jeffrey · Christoph Koutschan
Received: 22 May 2020 / Revised: 12 August 2020 / Accepted: 21 August 2020 © The Author(s) 2020
Abstract We consider LU and Q R matrix decompositions using exact computations. We show that fractionfree Gauß–Bareiss reduction leads to triangular matrices having a non-trivial number of common row factors. We identify two types of common factors: systematic and statistical. Systematic factors depend on the reduction process, independent of the data, while statistical factors depend on the specific data. We relate the existence of row factors in the LU decomposition to factors appearing in the Smith–Jacobson normal form of the matrix. For statistical factors, we identify some of the mechanisms that create them and give estimates of the frequency of their occurrence. Similar observations apply to the common factors in a fraction-free Q R decomposition. Our conclusions are tested experimentally. Keywords Fraction-free algorithms · Gaussian elimination · Exact linear system solving · LU decomposition · Smith–Jacobson normal form Mathematics Subject Classification 15A23 · 11C20 · 68W30
J.M. was supported in part by the Austrian Science Fund (FWF): SFB50 (F5009-N15). C.K. was supported by the Austrian Science Fund (FWF): P29467-N32 and F5011-N15. J. Middeke (B) Research Institute for Symbolic Computation, Johannes Kepler University, Altenberger Straße 69, 4040 Linz, Austria e-mail: [email protected] D. J. Jeffrey Department of Applied Mathematics, University of Western Ontario, Middlesex College, Room 255, 1151 Richmond Street North, London, ON N6A 5B7, Canada e-mail: [email protected] C. Koutschan Johann Radon Institute for Computational and Applied Mathematics, Austrian Academy of Sciences, Altenberger Straße 69, 4040 Linz, Austria e-mail: [email protected]
J. Middeke et al.
1 Introduction Although known earlier to Dodgson [8] and Jordan1 (see Durand [9]), the fraction-free method for exact matrix computations became well known because of its application by Bareiss [1] to the solution of a linear system over Z, and later over an integral domain [2]. He implemented fraction-free Gaussian elimination of the augmented matrix [A B], and kept all computations in Z until a final division step. Since, in linear algebra, equation solving is related to the matrix factorizations LU and Q R, it is natural that fraction-free methods would be extended later to those factorizations. The forms of the factorizations, however, had to be modified from their floating-point counterparts in order to retain purely integral data. The first proposed modifications were based on inflating the initial data until all divisions were guaranteed to be exact, see for example Lee and Saunders [17], Nakos et al. [21] and Corless and Jeffrey [7]. This strategy, however, led to the entries in the L and U matrices becoming very large, and an alternative form was presented in Zhou and Jeffre
Data Loading...
