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

DOI10.2307/2153451zbMATH Open0828.65035OpenAlexW2059454546MaRDI QIDQ4846019FDOQ4846019

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

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

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)

Cited In (25)

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

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)