On Wiedemann's method of solving sparse linear systems
[For the entire collection see Zbl 0758.00016.] Given a `black box model' of a sparse matrix \(A\) which evaluates \(Ay\) for any \(y\), and a vector \(b\), this paper attempts to find a random precise solution vector \(x\) with \(Ax=b\) by using a refinement of \textit{D. H. Wiedemann}'s method [IEEE Trans. Inf. Theory IT-32, 54-62 (1986; Zbl 0607.65015)]. Here the coordinate recurrence method from coding theory and randomization are used in the finite field case. Singular systems are randomly perturbed to obtain non-singular ones; for finding rank and determinant, algebraic methods such as premultiplying by Toeplitz matrices are used that require less multiplies than Wiedemann's original method.
- Analysis of Coppersmith's Block Wiedemann Algorithm for the Parallel Solution of Sparse Linear Systems
- Black box linear algebra: extending Wiedemann's analysis of a sparse matrix preconditioner for computations over small fields
- Solving sparse linear equations over finite fields
- scientific article; zbMATH DE number 503196
- Solving very sparse rational systems of equations
- Techniques for exploiting structure in matrix formulae of the sparse resultant
- A new efficient algorithm for computing Gröbner bases (F₄)
- Efficient matrix preconditioners for black box linear algebra
- Parallel computation of polynomial GCD and some related parallel computations over abstract fields
- Algebraic and numerical techniques for the computation of matrix determinants
- Symbolic and numeric methods for exploiting structure in constructing resultant matrices
- Improved algorithms for computing determinants and resultants
- A note on the factorization method of Niederreiter
- Superfast algorithms for Cauchy-like matrix computations and extensions
- Multiparty cardinality testing for threshold private intersection
- A practical approach to the secure computation of the Moore-Penrose pseudoinverse over the rationals
- Degeneracy loci and polynomial equation solving
- Relating \(p\)-adic eigenvalues and the local Smith normal form
- Numerically safe Gaussian elimination with no pivoting
- Lifting and recombination techniques for absolute factorization
- Improved dense multivariate polynomial factorization algorithms
- Efficient parallel factorization and solution of structured and unstructured linear systems
- Fast computation of the rank profile matrix and the generalized Bruhat decomposition
- Certified sparse linear system solving
- Black box methods for least squares problems
- Solving very sparse rational systems of equations
- On fast and provably secure message authentication based on universal hashing
- Solving sparse linear equations over finite fields
- scientific article; zbMATH DE number 1262436 (Why is no real title available?)
- Exact solution of sparse linear systems via left-looking roundoff-error-free Lu factorization in time proportional to arithmetic work
- Black box linear algebra: extending Wiedemann's analysis of a sparse matrix preconditioner for computations over small fields
- On matrices with displacement structure: generalized operators and faster algorithms
- Kaltofen's division-free determinant algorithm differentiated for matrix adjoint computation
- On efficient sparse integer matrix Smith normal form computations
- Elimination ideal and bivariate resultant over finite fields
- Nearly optimal solution of rational linear systems of equations with symbolic lifting and numerical initialization
- Bivariate polynomial reduction and elimination ideal over finite fields
- Computing the characteristic polynomial of generic Toeplitz-like and Hankel-like matrices
- Solving sparse linear systems faster than matrix multiplication
- Faster modular composition
- Optimal fine-grained hardness of approximation of linear equations
- Explicit Riemann-Roch spaces in the Hilbert class field
- Attacks on Goldreich's pseudorandom generators by grouping and solving
- Probabilistic analysis of Wiedemann's algorithm for minimal polynomial computation
- Solving structured linear systems with large displacement rank
- New recombination algorithms for bivariate polynomial factorization based on Hensel lifting
This page was built for publication: On Wiedemann's method of solving sparse linear systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4038737)
