Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 

 

Euclid's algorithm and the
Lanczos method over finite fields


Author: Jeremy Teitelbaum
Journal: Math. Comp. 67 (1998), 1665-1678
MSC (1991): Primary 11Y16, 65F10, 15A33
DOI: https://doi.org/10.1090/S0025-5718-98-00973-9
MathSciNet review: 1474657
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: This paper shows that there is a close relationship between the Euclidean algorithm for polynomials and the Lanczos method for solving sparse linear systems, especially when working over finite fields. It uses this relationship to account rigorously for the appearance of self-orthogonal vectors arising in the course of the Lanczos algorithm. It presents an improved Lanczos method which overcomes problems with self-orthogonality and compares this improved algorithm with the Euclidean algorithm.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 11Y16, 65F10, 15A33

Retrieve articles in all journals with MSC (1991): 11Y16, 65F10, 15A33


Additional Information

Jeremy Teitelbaum
Affiliation: Jeremy Teitelbaum, Department of Mathematics, Statistics, and Computer Science (M/C 249), University of Illinois at Chicago, 851 S. Morgan St., Chicago, IL 60607, USA
Email: jeremy@uic.edu

DOI: https://doi.org/10.1090/S0025-5718-98-00973-9
Received by editor(s): February 8, 1996
Additional Notes: The author is supported by the National Science Foundation.
Article copyright: © Copyright 1998 American Mathematical Society