Probabilistic analysis of Wiedemann's algorithm for minimal polynomial computation. (May 2016)

• Record Type: Journal Article
• Authors: Harrison, Gavin; Johnson, Jeremy; Saunders, B. David
• Is Part Of: Journal of symbolic computation. Volume 74(2016)
• Page Start: 55
• Page End: 69
• Publication Date: 2016-05
• Subjects: Matrix -- Minimal polynomial -- Finite field -- Block blackbox algorithm -- Probability; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2015.06.005
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: Blackbox algorithms for linear algebra problems start with projection of the sequence of powers of a matrix to a sequence of vectors (Lanczos), a sequence of scalars (Wiedemann) or a sequence of smaller matrices (block methods). Such algorithms usually depend on the minimal polynomial of the resulting sequence being that of the given matrix. Here exact formulas are given for the probability that this occurs. They are based on the generalized Jordan normal form (direct sum of companion matrices of the elementary divisors) of the matrix. Sharp bounds follow from this for matrices of unknown elementary divisors. The bounds are valid for all finite field sizes and show that a small blocking factor can give high probability of success for all cardinalities and matrix dimensions.