ANCILA research project

Asymptotic analysis of the convergence behavior of iterative methods in numerical linear algebra (01-01-2002 - 31-12-2005)

The convergence behavior of the iterative methods mentioned above is related with certain extremal problems from approximation theory. Here one asks for a polynomial of certain degree and suitably normalized which is as small as possible on the spectrum of the matrix. The applicant A. Kuijlaars studied this extremal problem for polynomials recently in an asymptotic setting. Inspired by an observation of Trefethen [7], see also [3], who noted that the Lanczos method approximates well those eigenvalues that are in a part of the spectrum where the density of eigenvalues is less than the density of an equilibrium measure, he studied in [4] the convergence of the Lanczos method with methods from potential theory. It turned out that the convergence can be described in terms of an equilibrium problem for logarithmic potentials combined with a constraint. The solution of the extremal problem provides the distribution of the Ritz values. The region where the solution is equal to the constraint is exactly equal to the region where the eigenvalues are well approximated. This analysis is valid in an asymptotic context, for large matrices and for a large number of iterations.

Subsequently these ideas were applied to the convergence of the conjugate gradient method for the solution of positive definite linear systems. In joint work with Bernhard Beckermann from Lille (France) Kuijlaars succeeded in describing the superlinear convergence in terms of an extremal problem for logarithmic potentials [1]. An asymptotic error bound

was found as an average of Green functions of varying sets. This is an extension of the known error bound in terms of the Green function of a single fixed set.

The aim of the project is to start from the new description for the convergence behavior of iterative methods recently developed by Kuijlaars and Beckermann-Kuijlaars as outlined above. This description is far from complete. Many open questions remain to be investigated.

Objectives

Following is a list of research problems we wish to focus on in the project.

1. Study of examples from the literature with a known eigenvalue distribution.

   If for a specific linear system or eigenvalue problem, the distribution of eigenvalues is known, then the obtained results can be applied in principle. Usually, the results are rather implicit, and it is not an easy task to make them explicit. In very special cases it will be possible to derive fully explicit formulas for the convergence behavior. To obtain such fully explicit formulas is not only very interesting from a theoretical point of view, but it will also give important information about related examples that do not give rise to explicit formulas. In cases where explicit formulas are impossible we ask for approximations that are able to capture the most important aspects of the convergence behavior. To a large extent these approximations will be carried out numerically.

2. Study of examples from the literature with unknown eigenvalue distribution.

   If, for an interesting example, the distribution of eigenvalues is not known in the literature, then we will first try to calculate it. Many techniques are known to do this. Maybe we have to add new techniques ourselves. If it does not seem to be possible to calculate the eigenvalue distribution, then the further analysis will be less exact. We can expect to obtain qualitative results at best, but this may still be interesting for a better understanding of the convergence.

3. Study of practical examples.

   The examples we think of in 1) and 2) are mostly of a theoretical, academic, nature. Practical examples are typically too complicated to give rise to exact formulas. We have to work with approximations. Guided by the academic examples, however, we expect to be able to obtain results in this case as well. This part of the project will be largely computational.

4. Preconditioning effects.

   In many problems the matrix involved is ill-conditioned. To accelerate the convergence and to obtain a better condition number, the linear system is modified. Many suggestions have been made for this precondioning of the matrix. A good preconditioner will also give rise to a better distribution of eigenvalues. It is very interesting to find out to what extent the new technique will be able to describe these effects. It could provide a method to compare different types of preconditioning. The first example we have in mind and which we expect to be able to treat successfully, is the incomplete LU preconditioning.

   This part of the project is very promising.

5. Extension to non-symmetric problems.

   So far, the theory only applies to symmetric problems. This is a very serious restriction. Many of the most interesting problems are non-symmetric. The extension to non-symmetric matrices will be far from trivial. New ideas are definitely required here. However, we expect to be able to contribute here as well, in particular for non-symmetric Toeplitz matrices and other specially structured matrices.

6. Randomly distributed eigenvalues.

   A certain convergence behavior is predicted by the theory depending on the asymptotic distribution of eigenvalues. Experiments show that the eigenvalues have to follow the limiting distributions quite well, in order to have valid results. If one chooses eigenvalues from a known distribution randomly, then the result will be quite poor for moderately sized matrices. It is a problem to describe this effect. We have an intuitive feeling for the situation, but a more concrete description will be most welcome.

Design and methodology

At this moment the research is centered around the applicants. They are the driving forces behind the project and will be actively involved in its developments. They will intensely monitor the assistant that we ask for in this project. The Department of Mathematics of the Katholieke Universiteit Leuven will provide logistical support for the assistant.

The project has two important parts, the theoretical part and the computational part. In order to obtain satisfactory results both parts should be developed together. Potential theory [6] plays a major role in the theoretical part. The applicant A. Kuijlaars is familiar with this area and he contributed to its development [4,5]. This theoretical foundation is basic for the project. The contibution of M. Van Barel is essential for the computational part. To fruitfully continue the research it is necessary to expand the scope to more realistic situations. Being an expert in the field of numerical linear algebra, he is familiar with the large scale computations that are necessary to apply the theoretical results.

In addition, it is necessary that a research assistant can be hired, whose primary task is to work on the project. The assistant will be trained in both the theoretical and the computational parts. If succesfull, his/her research will lead to a Ph.D. degree in science.

We intend to establish a close collaboration between the parties involved in the project. We regularly have meetings to monitor the progress of the project. Joint seminars will be held. We intend to have active collaboration with foreign groups. continue the research it is necessary to expand the scope to more realistic situations. Being an expert in the field of numerical linear algebra, he is familiar with the large scale computations that are necessary to apply the theoretical results.

In addition, it is necessary that a research assistant can be hired, whose primary task is to work on the project. The assistant will be trained in both the theoretical and the computational parts. If succesfull, his/her research will lead to a Ph.D. degree in science.

We intend to establish a close collaboration between the parties involved in the project. We regularly have meetings to monitor the progress of the project. Joint seminars will be held. We intend to have active collaboration with foreign groups.

Even though both applicants will be involved in all aspects of the project, their specific contributions will be different, due to their different backgrounds and expertises. A. Kuijlaars will be responsible for the development and supervision of the theoretical aspects. In particular new contributions to the convergence results will rely on his expertise in approximation theory and potential theory. M. Van Barel will be responsible for the development and supervision of the numerical and computational aspects of the project.

We strongly intend to have joint papers in major international journals.

Relevant recent literature

1. B. Beckermann and A.B.J. Kuijlaars, Superlinear convergence of Conjugate Gradients, to appear in SIAM J. Numer. Anal.
2. A. Bultheel and M. Van Barel, Linear Algebra, Rational Approximation and Orthogonal Polynomials, Studies in Computational Mathematics vol. 6, North Holland, Elsevier Science, Amsterdam, 464 pages, 1997.
3. T.A. Driscoll, K-C. Toh, and L.N. Trefethen, From potential theory to matrix iterations in six steps, SIAM Review 40 (1998), 547-578.
4. A.B.J. Kuijlaars, Which eigenvalues are found by the Lanczos method? SIAM J. Matrix Anal. Appl. 22 (2000), 306-321.
5. A.B.J. Kuijlaars and W. Van Assche, Extremal polynomials on discrete sets, Proc. London Math. Soc. 79 (1999), 191-221.
6. E.B. Saff and V. Totik, Logarithmic Potentials with External Fields, Springer-Verlag, Berlin, 1997.
7. L.N. Trefethen and D. Bau III, Numerical Linear Algebra, SIAM, Philadelphia, 1997.
8. M. Van Barel and A. Bultheel, A look-ahead algorithm for the solution of block Toeplitz systems, Linear Algebra and its applications 254 (1997), 291-335.