Analysis of Coppersmith's Block Wiedemann Algorithm for the Parallel Solution of Sparse Linear Systems

DOI10.2307/2153451MaRDI QIDQ4846019zbMATH OpenOpenAlexFDO

Authors Erich L. Kaltofen

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

zbMATH Keywords

randomizationKrylov subspacesiterative methodsconjugate gradient methodfinite fieldlarge sparse linear systemsparallel implementationBerlekamp-Massey algorithmexact arithmetic

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Iterative numerical methods for linear systems (65F10) Matrices over special rings (quaternions, finite fields, etc.) (15B33)

Recommendations

• scientific article; zbMATH DE number 503245
• scientific article; zbMATH DE number 1253961
• The universal block Lanczos-Padé method for linear systems over large prime fields
• Solving sparse linear equations over finite fields
• Reliable Krylov-based algorithms for matrix null space and rank
• scientific article; zbMATH DE number 503196
• Fast computation of linear generators for matrix sequences and application to the block Wiedemann algorithm
• Nearly sparse linear algebra and application to discrete logarithms computations
• Parallel hybrid iteration methods for block bordered linear systems
• Solving linear equations over GF(2): Block Lanczos algorithm

Cited in

(25)

• Comparing the difficulty of factorization and discrete logarithm: a 240-digit experiment
• scientific article; zbMATH DE number 2151185 (Why is no real title available?)
• Superfast algorithms for Cauchy-like matrix computations and extensions
• Computation of a 768-bit prime field discrete logarithm
• Improving support-minors rank attacks: applications to G\textit{e}MSS and Rainbow
• Interpolation by decomposable univariate polynomials
• scientific article; zbMATH DE number 177858 (Why is no real title available?)
• A connection of series approximations and the basis of the Krylov space in block algorithms of Coppersmith and Montgomery
• Efficient matrix preconditioners for black box linear algebra
• A Kilobit Hidden SNFS Discrete Logarithm Computation
• Fast computation of linear generators for matrix sequences and application to the block Wiedemann algorithm
• Probabilistic analysis of Wiedemann's algorithm for minimal polynomial computation
• A block algorithm of Lanczos type for solving sparse systems of linear equations
• New techniques for the computation of linear recurrence coefficients
• Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm
• On efficient sparse integer matrix Smith normal form computations
• Solving structured linear systems with large displacement rank
• Euclid’s algorithm and the Lanczos method over finite fields
• Essentially optimal computation of the inverse of generic polynomial matrices
• The universal block Lanczos-Padé method for linear systems over large prime fields
• On matrices with displacement structure: generalized operators and faster algorithms
• Accelerating Iterative SpMV for the Discrete Logarithm Problem Using GPUs
• Computing the sign or the value of the determinant of an integer matrix, a complexity survey.
• Block-Krylov techniques in the context of sparse-FGLM algorithms
• Factoring polynomials over finite fields: A survey

This page was built for publication: Analysis of Coppersmith's Block Wiedemann Algorithm for the Parallel Solution of Sparse Linear Systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4846019)