×

Probabilistic analysis of block Wiedemann for leading invariant factors. (English) Zbl 1478.15050

For a prime power \(q\), let \(\mathbf F\) denote a finite field of cardinality \(q\). Let \(A\) be a \(n\times n\) matrix over \(\mathbf F\). For a chosen block size \(b\), let \(U\), \(V\) be uniformly random in \(\mathbf{F}^{n\times b}\). Call the sequence \(S= \{U^T A^jV\}_i\), \(i\in Z_+\), the \((U, V)\)-projection of \(A\). A projection and its minimal generator, \(G\), are called \(r\)-faithful to \(A\) if the \(r\) largest invariant factors of \(G\) are the \(r\) largest invariant factor of \(xI - A\). The authors develop an exact formula for the probability \(P_{q, b, r}(A)\) that a random projection is \(r\)-faithful for a given eigenstructure of \(A\). In the worst case the probability bound is improved by incorporating the partial information on the invariant factors of the minimal generating matrix \(G\). The results in this paper extend those in [G. Harrison et al., J. Symb. Comput. 74, 55–69 (2016; Zbl 1375.15022)] and have been presented without proofs as a poster at ISSAC 2016 (see [G. Harrison et al., ACM Commun. Comput. Algebra 50, No. 4, 173–175 (2016; Zbl 1365.65112)]).

MSC:

15B52 Random matrices (algebraic aspects)
15B33 Matrices over special rings (quaternions, finite fields, etc.)
15A20 Diagonalization, Jordan forms
15A15 Determinants, permanents, traces, other special matrix functions
60D05 Geometric probability and stochastic geometry
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Brent, Richard P.; Gao, Shuhong; Lauder, Alan G. B., Random Krylov spaces over finite fields, SIAM J. Discrete Math., 16, 2, 276-287 (February 2003) · Zbl 1044.11104
[2] Chen, L.; Eberly, W.; Kaltofen, E.; Turner, W.; Saunders, B. D.; Villard, G., Efficient matrix preconditioners for black box linear algebra, Linear Algebra Appl., 343-344, 119-146 (2002) · Zbl 0997.65073
[3] Coppersmith, Don, Solving homogeneous linear equations over gf(2) via block Wiedemann algorithm, Math. Comput., 62, 205, 333-350 (January 1994) · Zbl 0805.65046
[4] Harrison, Gavin; Johnson, Jeremy; Saunders, B. David, Probabilistic analysis of Wiedemann’s algorithm for minimal polynomial computation, J. Symb. Comput., 74, 55-69 (2016) · Zbl 1375.15022
[5] Harrison, Gavin; Johnson, Jeremy; Saunders, B. David, Probabilistic analysis of block Wiedemann for leading invariant factors, ACM Commun. Comput. Algebra, 50, 4, 173-175 (February 2017) · Zbl 1365.65112
[6] Kaltofen, Erich; Villard, Gilles, On the complexity of computing determinants, (Proc. Fifth Asian Symposium on Computer Mathematics. Proc. Fifth Asian Symposium on Computer Mathematics, Lect. Notes Ser. Comput., vol. 9 (2001), World Sci.), 13-27 · Zbl 1012.65505
[7] Kaltofen, Erich; Villard, Gilles, On the complexity of computing determinants, Comput. Complex., 13, 91-130 (2004) · Zbl 1061.68185
[8] Kaltofen, Erich; Yuhasz, George, On the matrix Berlekamp-Massey algorithm, ACM Trans. Algorithms, 9, 4, 33:1-33:24 (October 2013) · Zbl 1301.65030
[9] Newman, M., Integral Matrices (1972), Academic Press · Zbl 0254.15009
[10] Novocin, A.; Saunders, B. D.; Stachnik, A.; Youse, B., 3-ranks for strongly regular graphs, (Dumas, J-G.; Kaltofen, E., Proceedings of the 2015 International Workshop on Parallel Symbolic Computation PASCO’15 (2015), ACM Press), 101-108
[11] Taussky, Olga; Zassenhaus, Hans, On the similarity transformation between a matrix and its transpose, Pac. J. Math., 9, 3, 893-896 (1959) · Zbl 0087.01501
[12] Villard, G., Further analysis of Coppersmith’s block Wiedemann algorithm for the solution of sparse linear systems (extended abstract), (Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation, ISSAC ’97. Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation, ISSAC ’97, New York, NY, USA (1997), ACM), 32-39 · Zbl 0917.65041
[13] Villard, Gilles, A study of Coppersmith’s block Wiedemann algorithm using matrix polynomials (1997), Technical report, LMC-IMAG, REPORT 975 IM
[14] Wiedemann, D., Solving sparse linear equations over finite fields, IEEE Trans. Inf. Theory, 32, 54-62 (1986) · Zbl 0607.65015
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.