Beckermann, Townsend, Wilber, and Rubin have recently drawn attention to the importance of the classical Zolotarev rational approximation problems, in their generalized forms as analyzed among others by Gonchar, Starke, Istace, Thiran, Druskin, Knizhnerman, and Simoncini, to large-scale linear algebra problems including ADI iteration, Lyapunov and Sylvester equations, and low-rank approximation [2, 3, 5, 12, 13, 18]. The paper by Beckermann and Townsend on this topic was selected for SIGEST as an exceptional contribution of recent years in the SIAM Journal on Matrix Analysis and its Applications.

Specifically, at issue here are what are traditionally called the third and fourth Zolotarev problems, for which the following names are perhaps more memorable. The Zolotarev Ratio Problem is the problem of finding a rational function of prescribed degree \(n\) with a smallest possible ratio of its maximal size on one set \(E\) in the complex plane to its minimal size on another set \(F\). The Zolotarev Sign Problem is the problem of finding a rational function with \(r\approx -1\) on \(E\) and \(r\approx 1\) on \(F\). In linear algebra applications, \(E\) and \(F\) are related to the spectra of large matrices.

Istace and Thiran showed that these two problems are mathematically equivalent [7], but no reliable method has been available for solving either of them numerically. In the first half of this talk I will present such a method, developed jointly with Heather Wilber [17]. In a fraction of a second on a laptop for typical examples, we can now compute numerical solutions to both Zolotarev problems to several digits of accuracy. Fourteen examples are displayed graphically in [17], which can be found online at https://people.maths.ox.ac.uk/trefethen/trefethen_wilber.pdf. These computations are based on the AAA and AAA-Lawson algorithms for best rational approximation [9, 10], but until 2024, these algorithms were not successful for Zolotarev problems. Wilber and I found we had to modify them for this study, and we acknowledge a crucial contribution here from Yuji Nakatsukasa.

All this falls within a familiar frame of numerical linear algebra problems of current interest. However, investigating these new algorithms has led to something new that may eventually be of deeper importance in numerical analysis, and this will be the subject of the second half of my talk. It has long been known that there are connections between rational approximation and quadrature, and these connections have been exploited in various ways, for example in the FEAST eigensolver [1, 5, 11]. Building on the new Zolotarev algorithms, we have found a general framework of this kind that appears to encompass many problems. (It may also ultimately lead to a fulfillment of a dream a few of us have had of achieving a truly numerical realization of the theory of hyperfunctions.)

I very much regret that Householder abstracts do not permit the inclusion of graphics, for a few pictures show strikingly the new connections that are emerging. (This work is being developed in unpublished memos of mine, which are not yet in a form for public circulation.) Here are four instances where rational approximation gives new insight into old methods and an easy route to methods for quadrature:

1. Trapezoidal rule on the unit circle. It has been known since Lyness and Delves in 1967 that the trapezoidal rule applied in roots of unity gives exponential accuracy for functions analytic on the unit circle. Unexpectedly, this morphs into a Zolotarev sign problem if we consider the function \(\phi (z)\) defined by \(\phi (z) = 0\) for \(|z|>1\) and \(\phi (z) = -1\) for \(|z|<1\). Rational approximations to \(\phi \) put a string of poles along the unit circle, and via residue calculus, these can be converted to trapezoidal-style quadrature rules. (The nodes are the poles, and the weights are the residues.) Exponential convergence of the rational approximations becomes equivalent to exponential convergence of the quadrature formulas.

2. Inverse Laplace transforms and Hankel contours. Another established topic is Bromwich or Fourier-Mellin or inverse-Laplace-transform quadrature involving an exponential kernel over Hankel contours in the complex plane. Here, following [16], we consider rational approximations to \(e^x\) for \(x\in (-\infty , 0 \kern .5pt]\). The poles of near-best approximations line up along Hankel contours curving around \((-\infty , 0 \kern .5pt]\), leading to near-optimal quadrature formulas.

3. Computing functions of matrices like \(A^\alpha \) and \(\log (A)\). The “three Nicks paper” [6] applied conformal maps to derive exponentially accurate quadrature formulas for computing functions of matrices, which have had impact for example in electronic structure calculations [8]. The methods required tricky derivation via elliptic functions, but it turns out that on-the-fly Zolotarev approximation can achieve the same results. This time, the approximation problem consists of finding a rational function \(r\) with \(r(x)\approx 1\) for \(x\in [m,M]\) (an interval containing the spectrum of \(A\)) and \(r(x)\approx 0\) for \(x\in (-\infty , 0 \kern .5pt]\). In the rational approximation framework, it is an easy matter to drive variant formulas for cases where, say, \(A\) is a nonsymmetric matrix with spectrum in a complex domain rather than an interval.

4. Gauss-Legendre and other quadrature formulas on \([-1,1]\). Ordinary Gauss-Legendre quadrature and other formulas for integration over \([-1,1]\) can be given the same kind of derivation, which is related to how Gauss originally derived his method in 1814 and was later exploited by Takahasi and Mori [14, 15]. Now the rational approximation problem is to find a function \(r(z)\) that closely approximates \(\log ((z+1)/(z-1))\) on a Bernstein ellipse enclosing \([-1,1]\).

In summary, these are the connections that are emerging:

References

• [1]  A. P. Austin and L. N. Trefethen, Computing eigenvalues of real symmetric matrices with rational filters in real arithmetic, SIAM J. Sci. Comput., 37 (2015), A1365–A1387.

• [2]  B. Beckermann and A. Townsend, Bounds on the singular values of matrices with displacement structure, SIAM Rev., 61 (2019), 319–344.

• [3]  V. Druskin, L. Knizhnerman, and V. Simoncini, Analysis of the rational Krylov subspace and ADI methods for solving the Lyapunov equation, SIAM J. Numer. Anal., 49 (2011), 1875–1898.

• [4]  A. A. Gonchar, Zolotarev problems connected with rational functions, Math. USSR-Sb., 7 (1969), 623–635.

• [5]  S. Güttel, E. Polizzi, P. T. P. Tang, and G. Viaud, Zolotarev quadrature rules and load balancing for the FEAST eigensolver, SIAM J. Sci. Comput., 37 (2015), A2100–A2122.

• [6]  N. Hale, N. J. Higham, and L. N. Trefethen, Computing \(A^\alpha \), \(\log (A)\), and related matrix functions by contour integrals, SIAM J. Numer. Anal., 46 (2008), 2505–2523.

• [7]  M.-P. Istace and J.-P. Thiran, On the third and fourth Zolotarev problems in the complex plane, SIAM J. Numer. Anal., 32 (1995), 249–259.

• [8]  L. Lin, J. Lu, L. Ying, R. Car, and W. E, Fast algorithm for extracting the diagonal of the inverse matrix with application to the electronic structure analysis of metallic systems, Commun. Math. Sci., 130 (2009), 204511.

• [9]  Y. Nakatsukasa, O. Sète, and L. N. Trefethen, The AAA algorithm for rational approximation, SIAM J. Sci. Comput., 40 (2018), A1494–A1522.

• [10]  Y. Nakatsukasa and L. N. Trefethen, An algorithm for real and complex rational minimax approximation, SIAM J. Sci. Comput., 42 (2020), A3157–A3179.

• [11]  E. Polizzi, Density-matrix-based algorithm for solving eigenvalue problems, Phys. Rev. B, 79 (2009), 115112.

• [12]  D. Rubin, A. Townsend, and H. Wilber, Bounding Zolotarev numbers using Faber rational functions, Constr. Approx., 56 (2022), 207–232.

• [13]  G. Starke, Optimal alternating direction implicit parameters for nonsymmetric systems of linear equations, SIAM J. Numer. Anal., 28 (1991), 1431–1445.

• [14]  H. Takahasi and M. Mori, Estimation of errors in the numerical quadrature of analytic functions, Appl. Anal., 1 (1971), 201–229.

• [15]  L. N. Trefethen, Is Gauss quadrature better than Clenshaw-Curtis?, SIAM Rev., 50 (2008), 67–87.

• [16]  L. N. Trefethen, J. A. C. Weideman, and T. Schmelzer, Talbot quadratures and rational approximations, BIT Numer. Math., 46 (2006), 653–670.

• [17]  L. N. Trefethen and H. D. Wilber, Computation of Zolotarev rational functions, SIAM J. Sci. Comp., submitted. (https://people.maths.ox.ac.uk/trefethen /trefethen_wilber.pdf)

• [18]  H. D. Wilber, Computing Numerically with Rational Functions, PhD thesis, Dept. of Mathematics, Cornell U., 2021.