Probabilistic analysis of block wiedemann for leading invariant factors
| Autor: | Gavin Harrison, B. David Saunders, Jeremy Johnson |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
FOS: Computer and information sciences
Computer Science - Symbolic Computation Algebra and Number Theory Block Wiedemann algorithm 010102 general mathematics Structure (category theory) F.2.1 I.1.2 Field (mathematics) 010103 numerical & computational mathematics General Medicine Symbolic Computation (cs.SC) 01 natural sciences Upper and lower bounds Combinatorics Computational Mathematics Probabilistic analysis of algorithms 0101 mathematics Invariant (mathematics) Block size Block (data storage) Mathematics Exact probability |
| Zdroj: | ACM Communications in Computer Algebra. 50:173-175 |
| ISSN: | 1932-2240 |
| DOI: | 10.1145/3055282.3055294 |
| Popis: | 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. 17 pages |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|