Probabilistic analysis of block Wiedemann for leading invariant factors. (January 2022)

• Record Type: Journal Article
• Authors: Harrison, Gavin; Johnson, Jeremy; Saunders, B. David
• Is Part Of: Journal of symbolic computation. Volume 108(2022)
• Page Start: 98
• Page End: 116
• Publication Date: 2022-01
• Subjects: Invariant factors -- Minimum polynomial -- Wiedemann's algorithm -- Block blackbox algorithm -- Probability analysis -- Post hoc analysis; 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.2021.06.005
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: We determine the probability, structure dependent, that the block Wiedemann algorithm correctly computes leading invariant factors. This leads to a tight lower bound for the probability, structure independent. We show, using block size slightly larger than r, that the leading r invariant factors are computed correctly with high probability over any field. Moreover, an algorithm is provided to compute the probability bound for a given matrix size and thus to select the block size needed to obtain the desired probability. The worst case probability bound is improved, post hoc, by incorporating the partial information about the invariant factors.