Euclid's algorithm and the Lanczos method over finite fields |
| |
Authors: | Jeremy Teitelbaum |
| |
Institution: | 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 |
| |
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. |
| |
Keywords: | |
|
| 点击此处可从《Mathematics of Computation》浏览原始摘要信息 |
| 点击此处可从《Mathematics of Computation》下载免费的PDF全文 |
|