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
    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
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    linear generator for matrix sequences
    0 references
    Wiedemann algorithm
    0 references
    complexity reduction
    0 references
    fast Fourier transformation
    0 references
    0 references