arXiv Open Access 2018

Probabilistic Analysis of Block Wiedemann for Leading Invariant Factors

Gavin Harrison Jeremy Johnson B. David Saunders

Lihat Sumber

Abstrak

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.

Topik & Kata Kunci

cs.SC

Penulis (3)

Gavin Harrison

Jeremy Johnson

B. David Saunders

Format Sitasi

APA MLA BibTeX

Harrison, G., Johnson, J., Saunders, B.D. (2018). Probabilistic Analysis of Block Wiedemann for Leading Invariant Factors. https://arxiv.org/abs/1803.03864

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2018
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓