Black Box Linear Algebra with the LinBox Library

black box linear algebra;Wiedemann method;block Wiedemann method;linear algebra;randomized algorithm;LinBox library

Turner, William J. ; Erich Kaltofen, Committee Chair,Carl D. Meyer, Committee Member,Ralph C. Smith, Committee Member,B. David Saunders, Committee Member,Hoon Hong, Committee Member,Turner, William J. ; Erich Kaltofen ; Committee Chair ; Carl D. Meyer ; Committee Member ; Ralph C. Smith ; Committee Member ; B. David Saunders ; Committee Member ; Hoon Hong ; Committee Member

University:North Carolina State University

关键词: black box linear algebra;    Wiedemann method;    block Wiedemann method;    linear algebra;    randomized algorithm;    LinBox library;   

Others  :  https://repository.lib.ncsu.edu/bitstream/handle/1840.16/3025/etd.pdf?sequence=1&isAllowed=y

美国|英语

来源: null

【 摘 要 】

Black box algorithms for exact linear algebra view a matrix as a linear operator on a vector space, gathering information about the matrix only though matrix-vector products and not by directly accessing the matrix elements. Wiedemann's approach to black box linear algebra uses the fact that the minimal polynomial of a matrix generates the Krylov sequences of the matrix and their projections.By preconditioning the matrix, this approach can be used to solve a linear system, find the determinant of the matrix, or to find the matrix's rank.This dissertation discusses preconditioners based on Benes networks to localize the linear independence of a black box matrix and introduces a technique to use determinantal divisors to find preconditioners that ensure the cyclicity of nonzero eigenvalues.This technique, in turn, introduces a new determinant-preserving preconditioner for a dense integer matrix determinant algorithm based on the Wiedemann approach to black box linear algebra and relaxes a condition on the preconditioner for the Kaltofen-Saunders black box rank algorithm.The dissertation also investigates the minimal generating matrix polynomial of Coppersmith's block Wiedemann algorithm, how to compute it using Beckermann and Labahn's Fast Power Hermite-Pade Solver, and a block algorithm for computing the rank of a black box matrix.Finally, it discusses the design of the LinBox library for symbolic linear algebra.