High performance exact linear algebra
Date
2015
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
University of Delaware
Abstract
This is a study in exact computational linear algebra consisting of two parts. First the problem of computing the p -rank of an integer matrix with particular emphasis on the case when the matrix is large and dense, the rank is relatively small, and the prime is tiny (such as p =3). Second is a numeric-symbolic rational linear system solver using an iterative refinement approach. The rank problem arises from the study of difference sets of finite groups and their corresponding strongly regular graphs. The ranks of the adjacency matrices representing these graphs are sought. These matrices, defined in sequences, grow too large for previously known rank algorithms. Prior solutions either require too much memory or are too computationally costly for the scenario of a large matrix with much lower rank. The expected low rank invites us to find find a space- and time-efficient algorithm for this special case. The heuristic methods detailed here form a Monte Carlo algorithm which is essentially optimal when the rank is sufficiently small. Several tools are used in concert with the new algorithm which are vital in computing the rank of some of the larger matrices of the sequences, which contain on the order of peta-entries. A suite of finite-field data compression tools is discussed. Additionally, a framework for distributed- and shared-memory parallelism is detailed. The rational linear system solver produces, for each entry of the solution vector, a rational approximation with denominator a power of two. From this representation, the correct rational entry can be reconstructed. Our method is a numeric-symbolic hybrid in that it uses an approximate numeric solver at each iteration together with a symbolic (exact arithmetic) residual computation and symbolic rational reconstruction. It is able to be output sensitive (i.e. terminate early) with provably correct result. Alternatively, the algorithm may be used without the rational reconstruction to obtain an extended precision floating point approximation of any specified precision. The chief contributions of the method and implementation are confirmed continuation, highly tuned rational reconstruction, and fast, robust performance. All work contained herein contributes to the LinBox library for exact linear algebra.