Analysis of Coppersmith's Block Wiedemann Algorithm for the Parallel Solution of Sparse Linear Systems
From MaRDI portal
Publication:4846019
DOI10.2307/2153451zbMath0828.65035OpenAlexW2059454546MaRDI QIDQ4846019
Publication date: 7 September 1995
Published in: Mathematics of Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.2307/2153451
randomizationfinite fieldconjugate gradient methoditerative methodsparallel implementationlarge sparse linear systemsBerlekamp-Massey algorithmKrylov subspacesexact arithmetic
Computational methods for sparse matrices (65F50) Matrices over special rings (quaternions, finite fields, etc.) (15B33) Iterative numerical methods for linear systems (65F10)
Related Items
Efficient matrix preconditioners for black box linear algebra, On efficient sparse integer matrix Smith normal form computations, A connection of series approximations and the basis of the Krylov space in block algorithms of Coppersmith and Montgomery, Accelerating Iterative SpMV for the Discrete Logarithm Problem Using GPUs, On Matrices With Displacement Structure: Generalized Operators and Faster Algorithms, Improving support-minors rank attacks: applications to G\textit{e}MSS and Rainbow, Probabilistic analysis of Wiedemann's algorithm for minimal polynomial computation, Computing the sign or the value of the determinant of an integer matrix, a complexity survey., New techniques for the computation of linear recurrence coefficients, Superfast algorithms for Cauchy-like matrix computations and extensions, Solving structured linear systems with large displacement rank, Factoring polynomials over finite fields: A survey, Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm, Computation of a 768-Bit Prime Field Discrete Logarithm, A Kilobit Hidden SNFS Discrete Logarithm Computation, Essentially optimal computation of the inverse of generic polynomial matrices, Block-Krylov techniques in the context of sparse-FGLM algorithms, Euclid’s algorithm and the Lanczos method over finite fields, Comparing the difficulty of factorization and discrete logarithm: a 240-digit experiment
