Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm (Q697496)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm |
scientific article; zbMATH DE number 1801682
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm |
scientific article; zbMATH DE number 1801682 |
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
0 references
0 references
