𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Subquadratic Computation of Vector Generating Polynomials and Improvement of the Block Wiedemann Algorithm

✍ Scribed by Emmanuel Thomé

Book ID
102600913
Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
371 KB
Volume
33
Category
Article
ISSN
0747-7171

No coin nor oath required. For personal study only.

✦ Synopsis

This paper describes a new algorithm for computing linear generators (vector generating polynomials) for matrix sequences, running in subquadratic time. This algorithm applies in particular to the sequential stage of Coppersmith's block Wiedemann algorithm. Experiments showed that our method can be substituted in place of the quadratic one proposed by Coppersmith, yielding important speedups even for realistic matrix sizes. The base fields we were interested in were finite fields of large characteristic. As an example, we have been able to compute a linear generator for a sequence of 4 × 4 matrices of length 242 304 defined over F 2 607 -1 in less than 2 days on one 667 MHz alpha ev67 CPU.

📜 SIMILAR VOLUMES

Parallel algorithm for the computation o
Parallel algorithm for the computation of characteristic polynomials of chemical graphs
✍ P. Venuvanalingam; P. Thangavel 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 413 KB

A parallel algorithm is developed for the f i t time based on Frame's method to compute the characteristic polynomials of chemical graphs. This algorithm can handle all types of graphs: ordinary, weighted, directed, and signed. Our algorithm takes only linear time in the CRCW PRAM model with O(n9) p

An Accurate and Efficient Algorithm for
An Accurate and Efficient Algorithm for the Computation of the Characteristic Polynomial of a General Square Matrix
✍ S. Rombouts; K. Heyde 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 99 KB

An algorithm is presented for the efficient and accurate computation of the coefficients of the characteristic polynomial of a general square matrix. The algorithm is especially suited for the evaluation of canonical traces in determinant quantum Monte-Carlo methods.