Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm (Q697496)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm |
scientific article |
Statements
Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm (English)
0 references
17 September 2002
0 references
Coppersmith's block Wiedemann algorithm is modified to a new algorithm for computing linear generators for matrix sequences. The complexity reduction (from quadratic to subquadratic) is obtained by using the fast Fourier transformation. Experiments show that the method has an important speedup for realistic matrix sizes.
0 references
linear generator for matrix sequences
0 references
Wiedemann algorithm
0 references
complexity reduction
0 references
fast Fourier transformation
0 references
