Structured Matrix Techniques for Orthogonal Rational Functions and Rational Krylov Methods

Polynomials are a powerful tool to approximate functions. If the function of interest does not resemble a polynomial, rational function based methods might be more appropriate. The theory of polynomials is well established in the field of classical analysis. Sequences of polynomials with orthogonality properties are preferred for computations in finite precision. Many effective numerical methods for polynomials originate from numerical linear algebra. A connection between orthogonal polynomials and Krylov subspaces allows to translate theory from classical analysis to numerical linear algebra and to apply numerical procedures from numerical linear algebra to problems in classical analysis. For rational functions similar connections to rational Krylov subspaces remain unexploited. Here we develop the necessary theory to identify these connections, relate rational functions to structured matrices and develop numerical procedures based on structured matrices for problems involving rational functions. Rational Krylov subspaces are chosen as the starting point of our exposition. All structured matrix pencils that construct orthogonal and biorthogonal bases for these spaces are derived. In particular, a tridiagonal matrix pencil is shown to suffice for the construction of biorthogonal bases. This allows us to design an efficient Lanczos like iteration for rational Krylov subspaces. Generating orthogonal and biorthogonal vectors is related to the factorization of the associated Gram matrix. The displacement structure of Gram matrices related to rational Krylov spaces is studied and the ones exhibiting low displacement rank are classified. The (bi)orthogonal basis vectors for rational Krylov subspaces can be related to rational functions (bi)orthogonal with respect to a discrete (linear functional) inner product. The specific form of these discrete inner products and linear functionals is derived, these are weighted sums of function evaluations. For these specific (linear functionals) inner products, (bi)orthogonal rational functions can be directly related to rational Krylov subspaces and the corresponding structured pencils. These connections are used to propose numerical procedures based on Krylov subspaces and structured matrices for problems involving rational functions. In particular, the computation of a sequence of (bi)orthogonal rational functions is reformulated as an inverse eigenvalue problem. The latter problem is a problem in linear algebra and techniques from numerical linear algebra can be applied to solve this problem.

Publication year:2021

Accessibility:Open