Polynomial evaluation and interpolation on special sets of points. (English) Zbl 1101.68039
Summary: We give complexity estimates for the problems of evaluation and interpolation on various polynomial bases. We focus on the particular cases when the sample points form an arithmetic or a geometric sequence, and we discuss applications, respectively, to computations with linear differential operators and to polynomial matrix multiplication.
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 12Y05 | Computational aspects of field theory and polynomials (MSC2010) |
| 13P05 | Polynomials, factorization in commutative rings |
| 68W30 | Symbolic computation and algebraic computation |
| 68W40 | Analysis of algorithms |
Keywords:
complexity estimatesSoftware:
NTLReferences:
| [1] | Abramov, S. A., Rational solutions of linear differential and difference equations with polynomial coefficients, Zh. Vychisl. Mat. i Mat. Fiz., 29, 11, 1611-1620, 1757 (1989), Engl. transl. USSR Comput. Math. Math. Phys. 7-12 · Zbl 0695.65051 |
| [2] | Aho, A. V.; Steiglitz, K.; Ullman, J. D., Evaluating polynomials at fixed sets of points, SIAM J. Comput., 4, 4, 533-539 (1975) · Zbl 0326.65027 |
| [3] | Beckermann, B.; Labahn, G., A uniform approach for Hermite Padé and simultaneous Padé approximants and their matrix-type generalizations, Numer. Algorithms, 3, 1-4, 45-54 (1992) · Zbl 0788.65017 |
| [4] | Beckermann, B.; Labahn, G., A uniform approach for the fast computation of matrix-type Padé approximants, SIAM J. Matrix Anal. Appl., 15, 3, 804-823 (1994) · Zbl 0805.65008 |
| [5] | D. Bini, V.Y. Pan, Polynomial and Matrix Computations. vol. 1. Birkhäuser, Boston Inc., Boston, MA, 1994.; D. Bini, V.Y. Pan, Polynomial and Matrix Computations. vol. 1. Birkhäuser, Boston Inc., Boston, MA, 1994. · Zbl 0809.65012 |
| [6] | Bluestein, L. I., A linear filtering approach to the computation of the discrete Fourier transform, IEEE Trans. Electroacoustics, AU-18, 451-455 (1970) |
| [7] | Borodin, A.; Moenck, R. T., Fast modular transforms, J. Comput. System Sci., 8, 3, 366-386 (1974) · Zbl 0302.68064 |
| [8] | A. Bostan, P. Gaudry, É. Schost, Linear recurrences with polynomial coefficients and computation of the Cartier-Manin operator on hyperelliptic curves, in: International Conference on Finite Fields and Applications Toulouse 2003, Lecture Notes in Computer Science, vol. 2948, Springer, Berlin, 2004, pp. 40-58.; A. Bostan, P. Gaudry, É. Schost, Linear recurrences with polynomial coefficients and computation of the Cartier-Manin operator on hyperelliptic curves, in: International Conference on Finite Fields and Applications Toulouse 2003, Lecture Notes in Computer Science, vol. 2948, Springer, Berlin, 2004, pp. 40-58. · Zbl 1119.11032 |
| [9] | Bostan, A.; Lecerf, G.; Schost, É., Tellegen’s principle into practice, (ISSAC’03 (2003), ACM Press: ACM Press New York), 37-44 · Zbl 1072.68649 |
| [10] | P. Bürgisser, M. Clausen, M.A. Shokrollahi, Algebraic complexity theory, Grundlehren der mathematischen Wissenschaften, vol. 315, Springer, Berlin, 1997.; P. Bürgisser, M. Clausen, M.A. Shokrollahi, Algebraic complexity theory, Grundlehren der mathematischen Wissenschaften, vol. 315, Springer, Berlin, 1997. · Zbl 1087.68568 |
| [11] | Cantor, D. G.; Kaltofen, E., On fast multiplication of polynomials over arbitrary algebras, Acta Inform., 28, 7, 693-701 (1991) · Zbl 0766.68055 |
| [12] | D.V. Chudnovsky, G.V. Chudnovsky, Approximations and complex multiplication according to Ramanujan, in: Ramanujan revisited (Urbana-Champaign, IL, 1987). Academic Press, Boston, MA, 1988, pp. 375-472.; D.V. Chudnovsky, G.V. Chudnovsky, Approximations and complex multiplication according to Ramanujan, in: Ramanujan revisited (Urbana-Champaign, IL, 1987). Academic Press, Boston, MA, 1988, pp. 375-472. · Zbl 0647.10002 |
| [13] | von zur Gathen, J.; Gerhard, J., Modern Computer Algebra (1999), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0936.11069 |
| [14] | C.F. Gauss, Summatio quarundam serierum singularium, Opera, vol. 2, Göttingen: Gess. d. Wiss., 1863 pp. 9-45.; C.F. Gauss, Summatio quarundam serierum singularium, Opera, vol. 2, Göttingen: Gess. d. Wiss., 1863 pp. 9-45. |
| [15] | Gerhard, J., Modular algorithms for polynomial basis conversion and greatest factorial factorization, (RWCA’00 (2000)), 125-141 |
| [16] | Giorgi, P.; Jeannerod, C.-P.; Villard, G., On the complexity of polynomial matrix computations, (ISSAC’03 (2003), ACM Press: ACM Press New York), 135-142 · Zbl 1072.68708 |
| [17] | Goldman, J.; Rota, G.-C., On the foundations of combinatorial theory, IVfinite vector spaces and Eulerian generating functions, Stud. Appl. Math., 49, 239-258 (1970) · Zbl 0212.03303 |
| [18] | Hanrot, G.; Quercia, M.; Zimmermann, P., The middle product algorithm, I. Appl. Algebra Eng. Comm. Comput., 14, 6, 415-438 (2004) · Zbl 1064.68094 |
| [19] | Heine, E., Untersuchungen über die Reihe \(1 + \frac{(1 - q^\alpha)(1 - q^\beta)}{(1 - q)(1 - q^\gamma)} \cdot x + \frac{(1 - q^\alpha)(1 - q^{\alpha + 1})(1 - q^\beta)(1 - q^{\beta + 1})}{(1 - q)(1 - q^2)(1 - q^\gamma)(1 - q^{\gamma + 1})} \cdot x^2 + ...\), J. Reine Angew. Math., 34, 285-328 (1847) · ERAM 034.0971cj |
| [20] | Horowitz, E., A fast method for interpolation using preconditioning, Inform. Proc. Lett., 1, 4, 157-163 (1972) · Zbl 0297.65005 |
| [21] | Kaltofen, E., Challenges of symbolic computationmy favorite open problems, With an additional open problem by Robert M. Corless and David J. Jeffrey, J. Symbolic Comput., 29, 6, 891-919 (2000) · Zbl 0963.68234 |
| [22] | Karatsuba, A.; Ofman, Y., Multiplication of multidigit numbers on automata, Soviet Math. Dokl., 7, 595-596 (1963) |
| [23] | D.E. Knuth, The Art of Computer Programming, vol. 2, Seminumerical Algorithms, third ed., Addison-Wesley, Reading, MA, 1998.; D.E. Knuth, The Art of Computer Programming, vol. 2, Seminumerical Algorithms, third ed., Addison-Wesley, Reading, MA, 1998. · Zbl 0895.65001 |
| [24] | R.T. Moenck, A. Borodin, Fast modular transforms via division, 13th Annual IEEE Symposium on Switching and Automata Theory, 1972, pp. 90-96.; R.T. Moenck, A. Borodin, Fast modular transforms via division, 13th Annual IEEE Symposium on Switching and Automata Theory, 1972, pp. 90-96. |
| [25] | Montgomery, P. L., An FFT extension of the elliptic curve method of factorization, Ph.D. Thesis (1992), University of California: University of California Los Angeles, CA |
| [26] | Paule, P., Greatest factorial factorization and symbolic summation, J. Symbolic Comput., 20, 3, 235-268 (1995) · Zbl 0854.68047 |
| [27] | Petkovšek, M., Hypergeometric solutions of linear recurrences with polynomial coefficients, J. Symbolic Comput., 14, 2-3, 243-264 (1992) · Zbl 0761.11008 |
| [28] | Rabiner, L. R.; Schafer, R. W.; Rader, C. M., The chirp \(z\)-transform algorithm and its application, Bell System Tech. J., 48, 1249-1292 (1969) |
| [29] | S. Roman, The Umbral Calculus. Pure and Applied Mathematics, vol. 111, Academic Press Inc., New York, 1984.; S. Roman, The Umbral Calculus. Pure and Applied Mathematics, vol. 111, Academic Press Inc., New York, 1984. · Zbl 0536.33001 |
| [30] | H.A. Rothe, Formulae de serierum reversione demonstratio universalis signis localibus combinatorico-analyticorum vicariis exhibita, Leipzig, 1793.; H.A. Rothe, Formulae de serierum reversione demonstratio universalis signis localibus combinatorico-analyticorum vicariis exhibita, Leipzig, 1793. |
| [31] | Schoenberg, I. J., On polynomial interpolation at the points of a geometric progression, Proc. Roy. Soc. Edinburgh Section A, 90, 3-4, 195-207 (1981) · Zbl 0506.41003 |
| [32] | Schönhage, A., Schnelle multiplikation von polynomen über Körpern der charakteristik 2, Acta Inform., 7, 395-398 (1977) · Zbl 0362.65011 |
| [33] | Schönhage, A.; Strassen, V., Schnelle multiplikation großer zahlen, Computing, 7, 281-292 (1971) · Zbl 0223.68007 |
| [34] | V. Shoup, 1996-2004. NTL: a library for doing number theory,; V. Shoup, 1996-2004. NTL: a library for doing number theory, |
| [35] | J. Stirling, Methodus Differentialis: sive Tractatus de Summatione et Interpolatione Serierum Infinitarum, Gul. Bowyer, London, Engl. transl. by Holliday, J. The Differential Method: A Treatise of the Summation and Interpolation of Infinite Series, vol. 1749, 1730.; J. Stirling, Methodus Differentialis: sive Tractatus de Summatione et Interpolatione Serierum Infinitarum, Gul. Bowyer, London, Engl. transl. by Holliday, J. The Differential Method: A Treatise of the Summation and Interpolation of Infinite Series, vol. 1749, 1730. |
| [36] | Storjohann, A., High-order lifting, (ISSAC’02 (2002), ACM Press: ACM Press New York), 246-254 · Zbl 1072.68698 |
| [37] | Strassen, V., Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten, Numer. Math., 20, 238-251 (1973) · Zbl 0251.65036 |
| [38] | B. Tellegen, A general network theorem with applications, Technical Report 7, Philips Research, 1952, pp. 259-269.; B. Tellegen, A general network theorem with applications, Technical Report 7, Philips Research, 1952, pp. 259-269. · Zbl 0049.42301 |
| [39] | Thomé, É., Fast computation of linear generators for matrix sequences and application to the block Wiedemann algorithm, (ISSAC’01 (2001), ACM Press: ACM Press New York), 323-331 · Zbl 1356.68296 |
| [40] | Thomé, É., Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm, J. Symbolic Comput., 33, 5, 757-775 (2002) · Zbl 1010.65024 |
| [41] | Villard, G., Computing Popov and Hermite forms of polynomial matrices, (ISSAC’96 (1996), ACM Press: ACM Press New York), 251-258 · Zbl 0914.65045 |
| [42] | R. Crandall, C. Pomerance, Prime numbers, in: A Computational Perspective, Springer, 2001, pp. xvi+545.; R. Crandall, C. Pomerance, Prime numbers, in: A Computational Perspective, Springer, 2001, pp. xvi+545. · Zbl 1088.11001 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
