A PhD thesis @ NALAG

TW 2011_01

Andrey Chesnokov
Eigenvalues, orthogonal functions and structured matrices
November 25, 2011

Advisor(s): Marc Van Barel

Abstract

In this thesis eigenvalues, structured matrices and orthogonal functions are studied from a practical point of view. In general, we try to exploit relations between any of these three concepts to design algorithms in the context of five problems. Each problem is closely related to one of the basic linear algebra problems: solving a system of linear equations or an eigenvalue problem.

Firstly, we study a problem arising from graph theory. There are different ways to map graphs to structured matrices, and depending on the matrix different graph-theoretic properties can be derived from their eigenvalues. An open question whether the regularity of a graph could or could not be derived from the spectrum of a certain class of structured matrices is solved.

The second aspect of the present thesis relates to a common method for eigenvalue computation, namely, a rational Lanczos method. Close relation between this algorithm and a certain minimization problem for orthogonal rational functions gives a possibility for numerical exploration of convergence properties of the algorithm without running it. Such exploration is reduced to solving a constrained weighted energy problem from logarithmic potential theory, which, in its turn, is converted to a linear system. The focus lies on this convergence exploration method.

Then a method to compute recurrence relation coefficients for bivariate polynomials, orthonormal with respect to a discrete inner product, is studied. To compute these polynomials, the inverse eigenvalue problem is posed and solved efficiently and in a stable way. This is achieved by applying Givens rotations to certain structured matrices and yields the generalized Hessenberg matrices, containing the recurrence relation coefficients.

Finally, several linear-algebraic problems with structured matrices are studied with a continuation method. Such a method defines an easy problem with a known solution and a path between this problem and the one we are wishing to solve. Instead of solving the target problem directly, the solution to the easy one is gradually transformed to the desired one. With this approach we first solve a linear system of equations with Toeplitz coefficient matrix, and later we find all the eigenvalues and eigenvectors of a symmetric diagonal-plus-semiseparable matrix. Both types of structured matrices exhibit close relation with certain classes of orthogonal functions.

Numerical experiments are included for all the proposed methods and illustrate the stability and accuracy of the methods.