×

zbMATH — the first resource for mathematics

On the fast solution of Toeplitz-block linear systems arising in multivariate approximation theory. (English) Zbl 1106.65023
Summary: When constructing multivariate Padé approximants, highly structured linear systems arise in almost all existing definitions. Until now little or no attention has been paid to fast algorithms for the computation of multivariate Padé approximants, with the exception of the paper of P. R. Graves-Morris, J. R. Hughes, and G. J. Makinson [J. Inst. Math. Appl. 13, 311–320 (1974; Zbl 0284.65009)].
In this paper we show that a suitable arrangement of the unknowns and equations, for the multivariate definitions of Padé approximant under consideration, leads to a Toeplitz-block linear system with coefficient matrix of low displacement rank. Moreover, the matrix is very sparse, especially in higher dimensions.
In Section 2 we discuss this for the so-called equation lattice definition and in Section 3 for the homogeneous definition of the multivariate Padé approximant. We do not discuss definitions based on multivariate generalizations of continued fractions, or approaches that require some symbolic computations. In Section 4 we present an explicit formula for the factorization of the matrix that results from applying the displacement operator to the Toeplitz-block coefficient matrix.
We then generalize the well-known fast Gaussian elimination procedure with partial pivoting developed in I. Gohberg, T. Kailath and V.Olshevsky [Math. Comput. 64, No. 212, 1557–1576 (1995; Zbl 0848.65010)] and by G. Heinig [IMA Vol. Math. Appl. 69, 63–81 (1995; Zbl 0823.65020)], to deal with a rectangular block structure where the number and size of the blocks vary. We do not aim for a superfast solver because of the higher risk for instability. Instead we show how the developed technique can be combined with an easy interval arithmetic verification step. Numerical results illustrate the technique in Section 5.

MSC:
65F05 Direct numerical methods for linear systems and matrix inversion
15A23 Factorization of matrices
41A21 Padé approximation
65G20 Algorithms with automatic result verification
65G30 Interval and finite arithmetic
Software:
INTLAB
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Brent, R.P.: Stability of fast algorithms for structured linear systems. In: Kailath, T., Sayed, A.H. (eds.) Fast Reliable Algorithms for Matrices with Structure, pp. 103–116. SIAM, Philadelphia, Pennsylvania (1999)
[2] Bultheel, A.: Epsilon and qd algorithms for matrix- and 2D-Padé approximation. Technical Report TW57, Department of Computer Science, K.U. Leuven (1982)
[3] Bultheel, A.: Low displacement-rank problems in 2-D Padé approximation. In: Outils et modèles mathématiques pour l’automatique, l’analyse de systèmes et le traitement du signal, vol. 2, pp. 563–576. Editions du CNRS, Paris (1982)
[4] A. Bultheel. Recursive computation of triangular 2D-Padé approximants. Technical report, Department of Computer Science, K.U. Leuven (1982)
[5] Bunch, J.R.: Stability of methods for solving Toeplitz systems of equations. SIAM J. Sci. Statist. Comput. 6(2), 349–364 (1985) · Zbl 0569.65019
[6] Chaffy, C.: \(\text{({P}adé)}_ y\) of \(\text{({P}adé)}_ x\) approximants of \({F}(x,y)\) . In: Cuyt, A. (ed.) Nonlinear Numerical Methods and Rational Approximation (Wilrijk, 1987), pp. 155–166. Reidel, Dordrecht (1988)
[7] Chisholm, J.S.R.: Rational approximants defined from double power series. Math. Comput. 27, 841–848 (1973) · Zbl 0278.41015
[8] Critchfield, C.L., Gammel, J.L.: Rational approximants for inverse functions of two variables. Rocky Mt. J. Math. 4, 339–349 (1974) · Zbl 0294.65008
[9] Cuyt, A.: Padé Approximants for Operators: Theory and Applications, vol. 1065 of Lecture Notes in Mathematics. Springer, Berlin Heidelberg New York (1984) · Zbl 0538.41024
[10] Cuyt, A.: How well can the concept of Padé approximant be generalized to the multivariate case? J. Comput. Appl. Math. 105(1–2), 25–50 (1999) · Zbl 0945.41012
[11] Cuyt, A., Verdonk, B.: General order Newton–Padé approximants for multivariate functions. Numer. Math. 43(2), 293–307 (1984) · Zbl 0513.41008
[12] Cuyt, A., Verdonk, B.: A review of branched continued fraction theory for the construction of multivariate rational approximants. Appl. Numer. Math. 4(2–4), 263–271 (1988) · Zbl 0644.65012
[13] Cuyt, A., Verdonk, B.: The need for knowledge and reliability in numeric computation: Case study of multivariate Padé approximation. Acta Appl. Math. 33, 273–302 (1993) · Zbl 0799.65012
[14] Gohberg, I., Kailath, T., Olshevsky, V.: Fast Gaussian elimination with partial pivoting for matrices with displacement structure. Math. Comput. 64(212), 1557–1576 (1995) · Zbl 0848.65010
[15] Gohberg, I., Olshevsky, V.: Complexity of multiplication with vectors for structured matrices. Linear Algebra Appl. 202, 163–192 (1994) · Zbl 0803.65053
[16] Gončar, A.A.: A local condition for the single-valuedness of analytic functions of several variables. Math. USSR Sb. 22(2), 305–322 (1974) · Zbl 0302.32004
[17] Graves-Morris, P.R., Hughes Jones, R., Makinson, G.J.: The calculation of some rational approximants in two variables. J. Inst. Math. Appl. 13, 311–320 (1974) · Zbl 0284.65009
[18] Guillaume, P.: Nested multivariate Padé approximants. J. Comput. Appl. Math. 82(1–2), 149–158 (1997) · Zbl 0888.65004
[19] Heinig, G.: Inversion of generalized Cauchy matrices and other classes of structured matrices. In: Linear algebra for signal processing (Minneapolis, MN, 1992), vol. 69 of IMA Vol. Math. Appl., pp. 63–81. Springer, Berlin Heidelberg New York(1995) · Zbl 0823.65020
[20] Hughes Jones, R.: General rational approximants in \({N}\) -variables. J. Approx. Theory 16(3), 201–233 (1976) · Zbl 0316.41011
[21] Hughes Jones, R., Makinson, G.J.: The generation of Chisholm rational polynomial approximants to power series in two variables. J. Inst. Math. Appl. 13, 299–310 (1974) · Zbl 0284.65008
[22] Kailath, T., Kung, S.Y., Morf, M.: Displacement ranks of matrices and linear equations. J. Math. Anal. Appl. 68(2), 395–407 (1979) · Zbl 0433.15001
[23] Karan, B.M., Srivastava, M.C.: A new multidimensional rational approximant. J. Indian Inst. Sci. 67(9–10), 351–360 (1987) · Zbl 0686.41015
[24] Karlsson, J., Wallin, H.: Rational approximation by an interpolation procedure in several variables. In: Saff, E.B., Varga, R.S. (eds.) Padé and Rational Approximation: Theory and Applications (Proc. Internat. Sympos., Univ. South Florida, Tampa, Fla., 1976), pp. 83–100. Academic Press, Berlin Heidelberg New York (1977) · Zbl 0368.41011
[25] Kuchminskaya, K.I.: Corresponding and associated branching continued fractions for a double power series. Dokl. Akad. Nauk Ukr. SSR, Ser. A 7, 613–617, 669 (1978) · Zbl 0418.40003
[26] Levin, D.: General order Padé-type rational approximants defined from double power series. J. Inst. Math. Appl. 18(1), 1–8 (1976) · Zbl 0352.41015
[27] Levy, B., Morf, M., Kung, S.-Y.: Some algorithms for the recursive input-output modeling of 2-d systems. Technical Report LIDS-P-962, MIT, Cambridge (1979)
[28] Lutterodt, C.H.: A two-dimensional analogue of Padé approximant theory. J. Phys. A 7, 1027–1037 (1974) · Zbl 0288.32002
[29] Lutterodt, C.H.: Addendum to: ”A two-dimensional analogue of Padé approximant theory” (J. Phys. A 7 (1974), 1027–1037). J. Phys. A 8, 427–428 (1975) · Zbl 0345.32001
[30] Lutterodt, C.H.: Rational approximants to holomorphic functions in \(n\) -dimensions. J. Math. Anal. Appl. 53(1), 89–98 (1976) · Zbl 0319.32005
[31] Paraskevopoulos, P.N.: Padé-type order reduction of two-dimensional systems. IEEE Trans. Circuits Syst. 27, 413–416 (1980) · Zbl 0442.93016
[32] Rump, S.M.: Kleine Fehlerschranken bei Matrixproblemen. PhD thesis, Universität Karlsruhe (1980) · Zbl 0437.65036
[33] Rump, S.M.: INTLAB – INTerval LABoratory. In: Csendes, T. (ed.) Developments in Reliable Computing, pp. 77–104. Kluwer, Dordrecht (1999) · Zbl 0949.65046
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.