On Wiedemann's method of solving sparse linear systems (Q4038737)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 177858
Language Label Description Also known as
default for all languages
No label defined
    English
    On Wiedemann's method of solving sparse linear systems
    scientific article; zbMATH DE number 177858

      Statements

      0 references
      0 references
      18 May 1993
      0 references
      probabilistic method
      0 references
      finite field
      0 references
      complexity
      0 references
      singular systems
      0 references
      sparse matrix
      0 references
      coordinate recurrence method
      0 references
      randomization
      0 references
      rank
      0 references
      determinant
      0 references
      Toeplitz matrices
      0 references
      On Wiedemann's method of solving sparse linear systems (English)
      0 references
      [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.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references