Journal article
Probabilistic analysis of Wiedemann's algorithm for minimal polynomial computation
Journal of symbolic computation, v 74, pp 55-69
May 2016
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.
Metrics
Details
- Title
- Probabilistic analysis of Wiedemann's algorithm for minimal polynomial computation
- Creators
- Gavin Harrison - Drexel UniversityJeremy Johnson - Drexel UniversityB. David Saunders - University of Delaware
- Publication Details
- Journal of symbolic computation, v 74, pp 55-69
- Publisher
- Elsevier
- Grant note
- CCF-1018063; CCF-1016728 / National Science Foundation (http://dx.doi.org/10.13039/100000001)
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- Computer Science
- Web of Science ID
- WOS:000366794100003
- Scopus ID
- 2-s2.0-84948719307
- Other Identifier
- 991019168049104721
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Collaboration types
- Domestic collaboration
- Web of Science research areas
- Computer Science, Theory & Methods
- Mathematics, Applied