Sparse integer-preserving Gram–Schmidt orthogonalization for REF QR factorization

Abstract QR factorization is foundational for mathematics, computer science, and operations research. Typically, QR factorizations are computed in floating-point precision, which, though appropriate for the majority of applications, have been shown to lead to incorrect rank computation, loss of orthogonality, or incorrect solutions for highly ill-conditioned input matrices. The REF QR factorization and integer-preserving Gram–Schmidt (IPGS) orthogonalization provide a framework to compute exact QR factorizations of any dense rational input matrix. This paper expands that framework to sparse matrices by deriving a sparse IPGS–QR algorithm. Notably, we show that the complexity of the entire sparse IPGS–QR algorithm is proportional to the cost of its arithmetic work plus a small overhead. Importantly, we show how the sparse IPGS–QR algorithm can be used to factorize matrices with full column rank and determine the exact rank of rank-deficient matrices. To the best of our knowledge, this paper represents the first method to calculate the exact rank of matrices, as it does not rely on numeric or probabilistic approximations. Altogether, the sparse IPGS–QR algorithm is an efficient method for solving problems with exact QR (least squares, quadratic programming, etc.), exactly computing a matrix rank, and finding exact orthogonal bases.