Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

On the rational approximation of Markov functions, with applications to the computation of Markov functions of Toeplitz matrices

  • Original Paper
  • Published:
Numerical Algorithms Aims and scope Submit manuscript

Abstract

We investigate the problem of approximating the matrix function f(A) by r(A), with f a Markov function, r a rational interpolant of f, and A a symmetric Toeplitz matrix. In a first step, we obtain a new upper bound for the relative interpolation error 1 − r/f on the spectral interval of A. By minimizing this upper bound over all interpolation points, we obtain a new, simple, and sharp a priori bound for the relative interpolation error. We then consider three different approaches of representing and computing the rational interpolant r. Theoretical and numerical evidence is given that any of these methods for a scalar argument allows to achieve high precision, even in the presence of finite precision arithmetic. We finally investigate the problem of efficiently evaluating r(A), where it turns out that the relative error for a matrix argument is only small if we use a partial fraction decomposition for r following Antoulas and Mayo. An important role is played by a new stopping criterion which ensures to automatically find the degree of r leading to a small error, even in presence of finite precision arithmetic.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

Notes

  1. This includes the limiting case \(\frac {d\nu }{dx}(x) = \frac {1}{\pi \sqrt {z-\beta }}\) and \(f^{[\nu ]}(z)=1/\sqrt {z-\beta }\) for \(\alpha \to -\infty \).

  2. In most papers in the literature, the authors estimate the absolute interpolation error. However, by considering the relative error, we may monitor also the error of rational approximants of functions f being a product of a Markov function and a rational function such as the logarithm or the square root, see Examples 5.1 and 5.3.

  3. If \(\mathbb E\) is a finite union of closed intervals, it is sufficient to suppose that interpolation points in \(Int(\mathbb E)\) only have even multiplicity, and there is an even number of interpolation points in any subinterval of \(\mathbb R \setminus Int(\mathbb E)\).

  4. In other approaches like in [55, Section 6.1], the authors eliminate the term 1/(z − x) in the integral leading to bounds for the absolute error.

  5. The interested reader may observe that we do not impose a normalization condition, and hence neither T nor φ is unique, though the function G2m can be shown to be unique, see also Remark 2.3.

  6. Notice that for the critical case β close to − 1 and μ a probability measure, the above constant C behaves at worst as \(1/\text {dist}(\overline {\mathbb D},[\alpha ,\beta ])=1/(-1-\beta )\), a term which also occurs in the works of Ganelius [25] and Braess [11].

  7. However, the underlying rectangular Cauchy matrix \((\frac {1}{z_{j}-x_{k}})\) might be quite ill-conditioned, even after row or column scaling [12, Cor 4.2]. A closer analysis seems to show that the given bound for the inverse condition number is related to the rate of best rational approximants of our f on the interval [c,d].

  8. Without this positivity assumption, [27, Theorem 4.1] observed with (3.8) that, up to \(\mathcal O(\varepsilon )\), we have that \(|\widetilde R_{M}^{(j)}(z_{k}) -\widetilde f^{(j)}_{j}|\approx |\widetilde f^{(j)}_{k} -\widetilde f^{(j)}_{j}| \leq |\widetilde f^{(j)}_{k}| + |\widetilde f^{(j)}_{j}| \leq 2 |\widetilde f^{(j)}_{k}|\approx 2 |\widetilde R_{M}^{(j)}(z_{k})|\), leading to some exponentially increasing growth factor.

  9. This algorithm is based on transforming via FFT a Toeplitz-like matrix into a Cauchy-like matrix being a hierarchical matrix of hierarchical rank \(k=\mathcal O(\tau \log (n))\), and then to use the hierarchical solver of hm-toolbox, see [49, §5.1 and Table in §3.4] and [59].

  10. https://github.com/rluce/tlcomp

  11. Further explanations on Fig. 3 are given in Example 5.2 below.

  12. In the original formulation [16], Denman and Beavers gave a coupled two-term recurrence for Xk and Yk := A− 1Xk. The product form was obtained later in [14], where Yk is replaced by Mk = XkYk. These authors suggest the recurrence \(X_{k+1}=\frac {1}{2} \mu _{k} X_{k}(I + \mu _{k}^{-2} M_{k}^{-1})\), but our recurrence seems to be more suitable in case where the matrices do no longer commute due to finite precision arithmetic. It seems that this slight modification has no impact on the analysis of stability and limiting accuracy, and even hardly no impact on the (relative) error.

  13. It is interesting to compare our findings to those in [35] where the authors approach Aγ after scaling by evaluating Padé approximants at the single interpolation point z1 = ... = z2m = 1 using Stieltjes continued fractions, somehow a confluent counterpart of our approach.

References

  1. Achieser, N.I.: Elements of the Theory of Elliptic Functions. American Mathematical Society, Providence (1990)

    Google Scholar 

  2. Abramowitz, M., Stegun, I.A.: Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, Volume 55 of National Bureau of Standards Applied Mathematics Series. For Sale by the Superintendent of Documents, U.S. Government Printing Office. Washington, D.C. (1964)

  3. Badea, C., Beckermann, B.: Spectral sets. In: Hogben, L. (ed.) Handb. Linear Algebr., chapter 37. 2nd edn., pp 613–638. CRC Press (2013)

  4. Benzi, M., Boito, P.: Matrix functions in network analysis. Gamm-Mitteilungen 43 (2020)

  5. Berrut, J.-P., Baltensperger, R., Mittelmann, H.D.: Recent developments in barycentric rational interpolation. In: Trends and Applications in Constructive Approximation, ISNM International Series of Numerical Mathematics, pp 27–51. Birkhäuser, Basel (2005)

  6. B: Beckermann Optimally scaled Newton iterations for the matrix square root (2013)

  7. Baker, G.A. Jr, Graves-Morris, P.: Padé Approximants, Volume 59 of Encyclopedia of Mathematics and Its Applications, 2nd edn. Cambridge University Press, Cambridge (1996)

    Google Scholar 

  8. Bisch, J.: Fonctions de matrices de Toeplitz symétriques. PhD thesis, Université de Lille (France) (2021)

  9. Beckermann, B., Reichel, L.: Error estimates and evaluation of matrix functions via the Faber transform. SIAM J. Numer. Anal. 47(5), 3849–3883 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  10. Braess, D.: Nonlinear Approximation Theory, Volume 7 of Springer Series in Computational Mathematics. Springer, Berlin (1986)

    Google Scholar 

  11. Braess, D.: Rational approximation of Stieltjes functions by the Carathéodory-Fejèr method. Constr. Approx. 3(1), 43–50 (1987)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  13. Byers, R., Xu, H.: A new scaling for Newton’s iteration for the polar decomposition and its backward stability. SIAM J Matrix Anal. Appl. 30(2), 822–843 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  14. Cheng, S., Higham, N.J., Kenney, C., Laub, A.: Approximating the logarithm of a matrix to specified accuracy. SIAM J Matrix Anal. Appl. 22, 1112–1125 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  15. Chun, J., Kailath, T.: Displacement structure for Hankel, Vandermonde, and related (derived) matrices. Linear Algebra and its Appl. 151(C), 199–227 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  16. Denman, E.D., Beavers, A.N.: The matrix sign function and computations in systems. Appl. Math. Comput. 2(1), 63–94 (1976)

    MathSciNet  MATH  Google Scholar 

  17. Davies, P.I., Higham, N.J.: A Schur-Parlett algorithm for computing matrix functions. SIAM J Matrix Anal. Appl. 25(2), 464–485 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  18. Estrada, E., Higham, D.J.: Network properties revealed through matrix functions. SIAM Rev. 52, 696–714 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  19. Embree, M., Ionita, A.C.: Pseudospectra of Loewner matrix pencils. Realization and Model Reduction of Dynamical Systems: A Festschrift in Honor of the 70th Birthday of Thanos Antoulas Beattie, Benner, Embree, Lefteriu, Gugercin, eds. (2022)

  20. Ellacott, S.W.: On the Faber transform and efficient numerical rational approximation. SIAM J. Numer. Anal. 20(5), 989–1000 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  21. Fasi, M.: Optimality of the Paterson-Stockmeyer method for evaluating matrix polynomials and rational matrix functions. Lin. Alg. Appli. 574, 182–200 (2019)

    Article  MathSciNet  MATH  Google Scholar 

  22. Filip, S.-I., Nakatsukasa, Y., Trefethen, L.N., Beckermann, B.: Rational minimax approximation via adaptive barycentric representations. SIAM J. Sci. Comput. 40(4), A2427–A2455 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  23. Freud, G.: Orthogonal Polynomials. Pergamon Press, Oxford (1971)

    MATH  Google Scholar 

  24. Gaier, D.: Lectures on Complex Approximation, 1st edn. Birkhäuser, Boston (1987)

    Book  MATH  Google Scholar 

  25. Ganelius, T.: Degree of rational approximation. In: Lectures on approximation and value distribution volume 79 of Sém. Math. Sup, pp 9–78. Presses Univ, Montréal (1982)

  26. Gohberg, I., Kailath, T., Olshevsky, V.: Fast Gaussian elimination with partial pivoting for matrices with displacement structure. Math Comp. 64(212), 1557–1576 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  27. Graves-Morris, P.R.: Practical, reliable, rational interpolation. J. Inst. Math. Appl. 25(3), 267–286 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  28. Graves-Morris, P.R.: Efficient reliable rational interpolation. In: Pade approximation and its applications (Amsterdam, 1980)́, volume 888 of Lecture Notes in Math, pp 28–63. Springer, Berlin (1981)

  29. Golub, G.H., Meurant, G.: Matrices, Moments and Quadrature with Applications. Princeton series in applied mathematics. Princeton University Press, Princeton (2010)

    MATH  Google Scholar 

  30. Gonchar, A.A.: On Markov’s theorem for multipoint padé approximants. Math. USSR-Sb, 34(4), 449–459 (1978)

    Article  MATH  Google Scholar 

  31. Gonchar, A.A.: On the speed of rational approximation of some analytic functions. Math. USSR-Sb, 34(2), 131–145 (1978)

    Article  MATH  Google Scholar 

  32. Henrici, P.: Applied and Computational Complex Analysis. vol. 2 Pure and Applied Mathematics. Wiley, New York (1977)

    MATH  Google Scholar 

  33. Higham, N.J.: Accuracy and Stability of Numerical Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA 2nd edn (2002)

  34. Higham, N.J.: Functions of matrices. Society for Industrial and Applied Mathematics (SIAM). Philadelphia, PA, Theory and computation (2008)

  35. Higham, N.J., Lin, L.: An improved Schur–Padé algorithm for fractional powers of a matrix and their Fréchet derivatives. SIAM J. Matrix Anal. Appl. 34, 07 (2013)

    Article  MATH  Google Scholar 

  36. Hochbruck, M., Ostermann, A.: Exponential integrators. Acta Numerica 19, 209–286 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  37. Heinig, G., Rost, K.: Algebraic Methods for Toeplitz-like Matrices and Operators Operator Theory: Advances and Applications, vol. 13. Basel, Birkhäuser (1984)

    Book  MATH  Google Scholar 

  38. Heinig, G., Rost, K.: Structure, Matrices with Displacement Generalized Bezoutians, and Moebius Transformations, pp 203–230. Birkhäuser, Basel (1989)

    MATH  Google Scholar 

  39. Kailath, T., Kung, S.-Y., Morf, M.: Displacement ranks of a matrix. Bull. Amer. Math Soc. 1(5), 769–773 (1979)

    Article  MathSciNet  MATH  Google Scholar 

  40. Kressner, D., Luce, R.: Fast computation of the matrix exponential for a Toeplitz matrix. SIAM J Matrix Anal. Appl. 39(1), 23–47 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  41. Knizhnerman, L.: Padé-Faber approximation of Markov functions on real-symmetric compact sets. Mathematical Notes 86(1-2), 81–92 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  42. Kailath, T., Sayed, A.H.: Structure, displacement theory and applications. SIAM Rev. 37(3), 297–386 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  43. Kielbasiński, A., Zieliński, P., Ziȩtak, K.: Higham’s scaled method for polar decomposition and numerical matrix-inversion Technical report Institute of Mathematics and Computer Science Report I18/2007/P-045 (2007)

  44. Lagomasino, G.L.: Szegö’s Theorem for polynomials orthogonal with respect to varying measures, Orthogonal polynomials and their applications. L Notes in Math. 1329, 255–260 (1986)

    Google Scholar 

  45. Lagomasino, G.L.: On the assymptotics of the ratio of orthogonal polynomials and the convergence of multipoint padé approximants. Math. USSR-Sb., 56, 216–229 (1987)

    Google Scholar 

  46. Mayo, A.J., Antoulas, A.C.: A framework for the solution of the generalized realization problem. Linear Algebra and its Appl. 425(2), 634–662 (2007). Special Issue in honor of Paul Fuhrmann

    Article  MathSciNet  MATH  Google Scholar 

  47. Meinardus, G.: Approximation of Functions: Theory and Numerical Methods. Expanded Translation of the German Edition. Translated by Larry L. Schumaker Springer Tracts in Natural Philosophy, vol. 13. Springer, New York (1967)

    Google Scholar 

  48. Massei, S., Robol, L.: Rational Krylov for Stieltjes matrix functions: convergence and pole selection. BIT Numer. Math. 61, 237–273 (2021)

    Article  MathSciNet  MATH  Google Scholar 

  49. Massei, S., Robol, L., Kressner, D.: hm-toolbox: Matlab software for HODLR and HSS matrices. SIAM J. Sci. Comput. 42(2), C43–C68 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  50. Ng, T.W., Tsang, C.Y.: Chebyshev-Blaschke products: solutions to certain approximation problems and differential equations. J. Comput. Appl. Math. 277, 106–114 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  51. Pan, V.: Decreasing the displacement rank of a matrix. SIAM J. Matrix Anal. Appl. 14(1), 118–121 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  52. Rutishauser, H.: Betrachtungen zur Quadratwurzeliteration. Monatshefte für Mathematik 67(5), 452–464 (1963)

    Article  MathSciNet  MATH  Google Scholar 

  53. Salazar Celis, O.: Practical rational interpolation of exact and inexact data, Theory and Algorithms. PhD thesis, Universiteit Antwerpen Belgium (2008)

  54. Shuman, D.I., Narang, S.K., Frossard, P., Ortega, A., Vandergheynst, P.: The emerging field of signal processing on graphs: extending high-dimensional data analysis to networks and other irregular domains. IEEE Signal Process. Mag. 30(3), 83–98 (2013)

    Article  Google Scholar 

  55. Stahl, H., Totik, V.: General Orthogonal polynomials, Volume 43 of Encyclopedia of Mathematics and Its Applications. Cambridge University Press, Cambridge (1992)

    Book  Google Scholar 

  56. Stahl, H.: Strong asymptotics for orthonormal polynomials with varying weights. Acta. Sci. Math. (Szeged), 66(1-2), 147–192 (2000)

    MathSciNet  MATH  Google Scholar 

  57. Stoll, M.: A literature survey of matrix methods for data science. GAMM-Mitteilungen, 43(3) (2020)

  58. Szegö, G.: Orthogonal polynomials. American Mathematical Society, Providence, R.I. 4th edn, American Mathematical Society, Colloquium Publications, Vol. XXIII (1975)

  59. Xia, J., Xi, Y., Gu, M.: A superfast structured solver for Toeplitz linear systems via randomized sampling. SIAM J Matrix Anal. Appl. 33(3), 837–858 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  60. Zolotarev, E.I.: Application of elliptic functions to questions of functions deviating least and most from zero. Zap. Imp. Akad. Nauk 30, 1–59 (1877)

    Google Scholar 

Download references

Acknowledgements

The authors want to thank Stefan Güttel, Marcel Schweitzer, and Leonid Knizhnerman for carefully reading a draft of this manuscript, and for their useful comments.

Funding

Partial financial support was received from the Labex CEMPI (ANR-11-LABX-0007-01).

Author information

Authors and Affiliations

  1. Laboratoire Paul Painlevé UMR 8524, Département de Mathématiques, Université de Lille, F-59655, Villeneuve d’Ascq, France

    Bernhard Beckermann & Joanna Bisch

  2. Gurobi Optimization, LLC., 9450 SW Gemini Dr, 90729, Beaverton, OR, USA

    Robert Luce

Authors
  1. Bernhard Beckermann
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Joanna Bisch
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Robert Luce
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Bernhard Beckermann.

Ethics declarations

Conflict of interest

The authors declare no competing interests.

Additional information

Publisher’s note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Beckermann, B., Bisch, J. & Luce, R. On the rational approximation of Markov functions, with applications to the computation of Markov functions of Toeplitz matrices. Numer Algor 91, 109–144 (2022). https://doi.org/10.1007/s11075-022-01256-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11075-022-01256-4

Keywords

Mathematics Subject Classification (2010)

Search

Navigation