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
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
0.8502228260040283
0 references
0.8502228260040283
0 references
0.8327182531356812
0 references
0.8298794031143188
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