Title: Euclid, Padé, Lanczos, another golden braid
Authors: Bultheel, Adhemar
Van Barel, Marc #
Issue Date: 11-May-1993
Host Document: Mathematisches Kolloquium of the Universität Bremen
Conference: Mathematisches Kolloquium of the Universität Bremen location:Bremen, DE date:11 May 1993
Abstract: The Lanczos algorithm is an iterative method for solving linear systems of equations or eigenvalue problems. Although it was described by Lanczos in 1950-52, it was only applied for problems with a symmetric (or hermitian) matrix, mainly for reasons of so called breakdown problems.

It was only recently that the numerical linear algebra community developed variants that overcame these problems. The underlying techniques can be brought back to elementary steps which are basically inherent in the Euclidean algorithm. In fact, this curing ability of the Euclidean algorithm was known for quite some time in the computation of Padé approximants and in the partial realization algorithms (Berlekamp-Massey) of linear system theory. Once this connection was made, it was easy to use the Lanczos algorithm as the semen for a whole family of iterative methods which turns out to be an efficient alternative for the family of Arnoldi-type methods, both founded on a Krylov-subspace approach to the problem.

In Krylov-subspace methods, the basic problem is to orthogonalize a set of vectors generating a Krylov-subspace K_n(x_0,A) = span{x_0, A x_0,...,A^n x_0}, where A is a square matrix and x_0 a vector. When A is symmetric, Gram-Schmidt will simplify to a three-term recurrence relation. When A is not symmetric, the Gram-Schmidt procedure will not simplify and we get an Arnoldi-type algorithm. However, if we apply a two-sided or bi-orthogonalizing Gram-Schmidt, we regain the efficiency of the symmetric case and get a Lanczos-type algorithm. Unfortinately, in this situation, the Gram-Schmidt procedure may break down because we do not work with a positive definite metric. To leap over these breakdown (or near-breakdown) steps, the Euclidean algorithm will give the solution.

In this lecture we shall start with some elementary facts about the Euclidean algorithm, show its connection with Padé approximation and formal orthogonal polynomials and eventually show how all this will give rise to Lanczos-type methods based on Krylov subspace techniques.
Publication status: published
KU Leuven publication type: AMa
Appears in Collections:Numerical Analysis and Applied Mathematics Section
# (joint) last author

Files in This Item:

There are no files associated with this item.


All items in Lirias are protected by copyright, with all rights reserved.