This thesis investigates the solution of large, sparse, linear systems over finite fields by matrix-free algorithms. A matrix-free algorithm treats the coefficient matrix as a black box and requires a technique to apply the matrix to a vector. The components of the matrix are never directly addressed or changed. Hence structural properties such as sparseness become unimportant.; We studied the block Wiedemann algorithm due to Coppersmith and implemented it after parallelizing the output loop, in a distributed setting as an SPMD computation. We developed three complete differently-optimized solvers, for computing in GF(2), in GF(p) where p is a prime representable in less than 16 binary digits, and in GF(q) where q can be of arbitrary length. We conducted detailed investigations of their performance. Two of the largest systems solved are a system of 569,00 equations over GF(2), in 332 hours on 2 computers; and a system of 20,000 equations over GF(32749), in 28.5 hours using 8 computers.; We designed the Black Box Berlekamp algorithm for the factorization of high-degree polynomials over finite fields. A key component of our algorithm is a matrix-free linear system solver based upon the Block Wiedemann algorithm. We have written a complete software package in C++ using a library of classes for fast polynomial arithmetic. In our algorithm the coefficient matrix is never instantiated and the matrix times vector product is effected by the modular exponentiation of polynomials. These features make it possible for us to factor polynomials of higher degree than hitherto possible. Our algorithm works best for high degree polynomials with coefficients from fields of small cardinality. We have factored polynomials of degree as large as 15001 in the field GF(127).; Our experiments with the Block Wiedemann Algorithm supply strong evidence for its success over finite fields of small cardinality. The only existing probabilistic analysis, by Kaltofen, is valid for large fields only.; Seeking the probability of success in small fields, we considered an intermediate subproblem of the Block Wiedemann algorithm involving the solution of a system of equations having Toeplitz structure. We examined, in particular, the condition that the leading principal minors of the coefficient matrix up to dimension equal to the rank of the original matrix must be nonzero. Randomly generated matrices having Toeplitz structure themselves can be used to precondition the given Toeplitz system so as to give it such a generic rank profile.; We have proven that an n x n Toeplitz matrix whose first row and column are chosen uniformly at random from the elements of a field of q elements, has generic rank {dollar}r < n{dollar} with probability {dollar}(1/q)(1 - 1/q)sp2(1 - (q -1)/qsp2)sp{lcub}r-1{rcub}.{dollar} Using concepts from the theory of subresultants and Pade approximants we also proved that there are {dollar}(q - 1)qsp{lcub}n-2{rcub}{dollar} non-singular order-n Toeplitz matrices over GF(q). From this it follows that a random Toeplitz matrix is non-singular with probability {dollar}1-1/q{dollar}. (Abstract shortened by UMI.)
展开▼
