Centre de diffusion de revues académiques mathématiques

 
 
 
 

Les cours du CIRM

Table des matières de ce fascicule | Article précédent | Article suivant
Alin Bostan
Algorithmes rapides pour les polynômes, séries formelles et matrices
Les cours du CIRM, 1 no. 2: Journées Nationales de Calcul Formel (2010), p. 75-262, doi: 10.5802/ccirm.9
Article PDF

Bibliographie

[01.01] Alfred V. Aho, John E. Hopcroft & Jeffrey D. Ullman, The design and analysis of computer algorithms, Addison-Wesley Publishing Co., 1974  MR 413592 |  Zbl 0326.68005
[01.02] Matthias Beck, Bruce C. Berndt, O-Yeat Chan & Alexandru Zaharescu, “Determinations of Analogues of Gauss Sums and Other Trigonometric Sums”, Int. J. Number Theory 1 (2005) no. 3, p. 333-356  MR 2175096 |  Zbl 1088.11064
[01.03, 03.11] Peter Bürgisser, Michael Clausen & M. Amin Shokrollahi, Algebraic complexity theory, Grundlehren Math. Wiss. 315, Springer-Verlag, Berlin, 1997  Zbl 1087.68568
[01.04, 07.10] Keith O. Geddes, Stephen R. Czapor & George Labahn, Algorithms for Computer Algebra, Kluwer Academic Publishers, 1992  Zbl 0805.68072
[01.05] Torbjörn Granlund, GNU Multiple Precision Arithmetic Library, 2006
[01.06] Daniel Richardson, “Some Undecidable Problems Involving Elementary Functions of a Real Variable”, Journal of Symbolic Logic 33 (1968) no. 4, p. 514-520  MR 239976 |  Zbl 0175.27404
[01.07] Daniel Richardson, “How to recognize zero”, Journal of Symbolic Computation 24 (1997) no. 6, p. 627-645  MR 1487790 |  Zbl 0917.11062
[01.08, 12.35] Joachim von zur Gathen & Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, 1999  Zbl 0936.11069
[02.01] D. J. Bernstein, “Multidigit multiplication for mathematicians”, Preprint, available from http://cr.yp.to/papers.html
[02.02] Marco Bodrato & Alberto Zanoni, Integer and polynomial multiplication : towards optimal Toom-Cook matrices, ISSAC’07, ACM, 2007, p. 17–24 Article |  MR 2396179 |  Zbl 1190.68084
[02.03] E. Oran Brigham, The fast Fourier transform, Prentice-Hall, 1974  Zbl 0375.65052
[02.04] Peter Bürgisser & Martin Lotz, “Lower bounds on the bounded coefficient complexity of bilinear maps”, J. ACM 51 (2004) no. 3, p. 464-482 Article |  MR 2145861 |  Zbl 1192.68312
[02.05] D. G. Cantor & E. Kaltofen, “On Fast Multiplication of Polynomials over Arbitrary Algebras”, Acta Informatica 28 (1991) no. 7, p. 693-701  MR 1129288 |  Zbl 0766.68055
[02.06] M. Cenk, C. K. Koc & F. Ozbudak, Polynomial Multiplication over Finite Fields Using Field Extensions and Interpolation, in ARITH ’09, IEEE Computer Society, 2009, p. 84-91 Article
[02.07] Jaewook Chung & M. Anwar Hasan, Asymmetric Squaring Formulae, in ARITH ’07 : Proc. of the 18th IEEE Symp. on Computer Arithmetic, IEEE, 2007, p. 113-122 Article
[02.08] S. Cook, On the minimum computation time of functions, Ph. D. Thesis, Harvard University, 1966
[02.09] S. A. Cook & S. O. Aanderaa, “On the minimum computation time of functions”, Transactions of the American Mathematical Society 142 (1969), p. 291-314  MR 249212 |  Zbl 0188.33402
[02.10] James W. Cooley, How the FFT gained acceptance, A history of scientific computing (Princeton, NJ, 1987), ACM Press Hist. Ser., ACM, 1990, p. 133–140  MR 1203104
[02.11] James W. Cooley & John W. Tukey, “An algorithm for the machine calculation of complex Fourier series”, Mathematics of Computation 19 (1965), p. 297-301  MR 178586 |  Zbl 0127.09002
[02.12] James W. Cooley & John W. Tukey, “On the Origin and Publication of the FFT Paper”, Current Contents 33 (1993) no. 51–52, p. 8-9
[02.13] A. De, P. P. Kurur, C. Saha & R. Saptharishi, Fast integer multiplication using modular arithmetic, in STOC’08, ACM, 2008, p. 499-506 Article |  MR 2582908 |  Zbl pre05485562
[02.14] J. Dongarra & F. Sullivan, “Top ten algorithms”, Computing in Science & Engineering 2 (2000) no. 1, p. 22-23
[02.15] P. Duhamel & M. Vetterli, “Fast Fourier transforms : a tutorial review and a state of the art”, Signal Processing. An Interdisciplinary Journal 19 (1990) no. 4, p. 259-299  MR 1048328 |  Zbl 0704.65106
[02.16] M. Frigo & S. G Johnson, “The Design and Implementation of FFTW3”, Proceedings of the IEEE 93 (2005) no. 2, p. 216-231
[02.17] Martin Fürer, Faster integer multiplication, STOC’07—Proceedings of the 39th Annual ACM Symposium on Theory of Computing, ACM, 2007, p. 57–66 Article |  MR 2402428 |  Zbl 1179.68198
[02.18] Martin Fürer, “Faster integer multiplication”, SIAM J. Comput. 39 (2009) no. 3, p. 979-1005 Article |  MR 2538847 |  Zbl 1192.68926
[02.19] W. M. Gentleman & G. Sande, Fast Fourier Transforms : for fun and profit, in AFIPS’66, ACM, 1966, p. 563-578 Article
[02.20, 12.18, 15.03] Guillaume Hanrot, Michel Quercia & Paul Zimmermann, “The Middle Product Algorithm I”, Appl. Algebra Engrg. Comm. Comput. 14 (2004) no. 6, p. 415-438  Zbl 1064.68094
[02.21] Michael T. Heideman, Don H. Johnson & C. Sidney Burrus, “Gauss and the history of the fast Fourier transform”, Arch. Hist. Exact Sci. 34 (1985) no. 3, p. 265-277  MR 815154 |  Zbl 0577.01027
[02.22] Michael Kaminski, “A lower bound for polynomial multiplication”, Theoret. Comput. Sci. 40 (1985) no. 2-3, p. 319-322 Article |  MR 835422 |  Zbl 0607.94010
[02.23] A. Karatsuba & Y. Ofman, “Multiplication of multidigit numbers on automata”, Soviet Physics Doklady 7 (1963), p. 595-596
[02.24] Robert T. Moenck, “Another polynomial homomorphism”, Acta Informat. 6 (1976) no. 2, p. 153-169  MR 408306 |  Zbl 0312.68024
[02.25] Peter L. Montgomery, “Five, Six, and Seven-Term Karatsuba-Like Formulae”, IEEE Trans. Comput. 54 (2005) no. 3, p. 362-369 Article |  Zbl 1171.11329
[02.26] Jacques Morgenstern, “Note on a lower bound of the linear complexity of the fast Fourier transform”, J. Assoc. Comput. Mach. 20 (1973), p. 305-306  MR 331867 |  Zbl 0258.65120
[02.27] Thom Mulders, “On Short Multiplications and Divisions”, Applicable Algebra in Engineering, Communication and Computing 11 (2000) no. 1, p. 69-88  MR 1817699 |  Zbl 0968.68200
[02.28] Henri J. Nussbaumer, “Fast polynomial transform algorithms for digital convolution”, Institute of Electrical and Electronics Engineers. Transactions on Acoustics, Speech, and Signal Processing 28 (1980) no. 2, p. 205-215  MR 563380 |  Zbl 0524.65093
[02.29] Henri J. Nussbaumer, Fast Fourier transform and convolution algorithms, Springer Series in Information Sciences 2, Springer-Verlag, Berlin, 1981  MR 606376 |  Zbl 0476.65097
[02.30] M. S. Paterson, M. J. Fischer & A. R. Meyer, An improved overlap argument for on-line multiplication, Complexity of computation, AMS, 1974, p. 97–111  MR 423875 |  Zbl 0301.68059
[02.31] A. Schönhage, “Schnelle Multiplikation von Polynomen über Körpern der Charakteristik 2”, Acta Informat. 7 (1976/77) no. 4, p. 395-398  MR 436663 |  Zbl 0362.65011
[02.32] A. Schönhage & V. Strassen, “Schnelle Multiplikation großer Zahlen”, Computing 7 (1971), p. 281-292  MR 292344 |  Zbl 0223.68007
[02.33, 07.31] V. Strassen, “The computational complexity of continued fractions”, SIAM J. Comput. 12 (1983) no. 1, p. 1-27  Zbl 0543.68026
[02.34] A. L. Toom, “The complexity of a scheme of functional elements simulating the multiplication of integers”, Doklady Akademii Nauk SSSR 150 (1963), p. 496-498  MR 156494 |  Zbl 0203.15604
[02.35] Joris van der Hoeven, The truncated Fourier transform and applications, ISSAC’04, ACM, 2004, p. 290–296  MR 2126956 |  Zbl 1064.65158
[02.36] Charles Van Loan, Computational frameworks for the fast Fourier transform, Frontiers in Applied Mathematics 10, SIAM, Philadelphia, PA, 1992  MR 1153025 |  Zbl 0757.65154
[02.37] André Weimerskirch & Christof Paar, “Generalizations of the Karatsuba Algorithm for Efficient Implementations” 2006, Cryptology ePrint Archive : Report 2006/224, available at http://eprint.iacr.org/2006/224
[03.01] J. Abdeljaoued & H. Lombardi, Méthodes matricielles : introduction à la complexité algébrique, Mathématiques & Applications 42, Springer-Verlag, Berlin, 2004  MR 2046056 |  Zbl 1087.65041
[03.02, 12.02] W. Baur & V. Strassen, “The complexity of partial derivatives”, Theoretical Computer Science 22 (1983), p. 317-330  MR 693063 |  Zbl 0498.68028
[03.03] D. Bini, “Relations between exact and approximate bilinear algorithms. Applications”, Calcolo 17 (1980) no. 1, p. 87-97 Article |  MR 605920 |  Zbl 0459.65028
[03.04] D. Bini, M. Capovani, F. Romani & G. Lotti, “$O(n^{2.7799})$ complexity for $n\times n$ approximate matrix multiplication”, Inform. Process. Lett. 8 (1979) no. 5, p. 234-235  MR 534068 |  Zbl 0395.68048
[03.05] Markus Bläser, A ${5\over 2}n^2$-lower bound for the multiplicative complexity of $n\times n$-matrix multiplication, STACS 2001 (Dresden), Lecture Notes in Comput. Sci. 2010, Springer, 2001, p. 99–109 Article |  MR 1890782 |  Zbl 0981.68710
[03.06] Markus Bläser, “On the complexity of the multiplication of matrices of small formats”, J. Complexity 19 (2003) no. 1, p. 43-60  MR 1951322 |  Zbl 1026.68062
[03.07, 06.04] A. Borodin & I. Munro, “Evaluation of polynomials at many points”, Information Processing Letters 1 (1971) no. 2, p. 66-68  Zbl 0226.65036
[03.08, 04.06, 15.02] R. P. Brent & H. T. Kung, “Fast algorithms for manipulating formal power series”, Journal of the ACM 25 (1978) no. 4, p. 581-595  Zbl 0388.68052
[03.09] James R. Bunch & John E. Hopcroft, “Triangular factorization and inversion by fast matrix multiplication”, Math. Comp. 28 (1974), p. 231-236  MR 331751 |  Zbl 0276.15006
[03.10] P. Bürgisser, M. Karpinski & T. Lickteig, “Some computational problems in linear algebra as hard as matrix multiplication”, Comput. Complexity 1 (1991) no. 2, p. 131-155 Article |  MR 1134946 |  Zbl 0774.68056
[03.12] H. Cohn, R. Kleinberg, B. Szegedy & C. Umans, Group-theoretic Algorithms for Matrix Multiplication, in FOCS’05, IEEE Computer Society, 2005, p. 379-388 Article
[03.13] Henry Cohn & Christopher Umans, A Group-Theoretic Approach to Fast Matrix Multiplication, in FOCS’03, IEEE Computer Society, 2003
[03.14] Don Coppersmith & Shmuel Winograd, “Matrix multiplication via arithmetic progressions”, J. Symbolic Comput. 9 (1990) no. 3, p. 251-280  MR 1056627 |  Zbl 0702.65046
[03.15] A. M Danilevskii, “The numerical solution of the secular equation”, Matem. sbornik 44 (1937) no. 2, p. 169-171, (in Russian)
[03.16] Charles M. Fiduccia, On obtaining upper bounds on the complexity of matrix multiplication, Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972), Plenum, 1972, p. 31–40  MR 391577
[03.17] P. C. Fischer & R. L. Probert, Efficient procedures for using matrix algorithms, Automata, languages and programming, Springer, 1974, p. 413–427. LNCS, Vol. 14  MR 428786 |  Zbl 0284.68039
[03.18] Patrick C. Fischer, Further schemes for combining matrix algorithms, Automata, languages and programming, Springer, 1974, p. 428–436. LNCS, Vol. 14  MR 428787 |  Zbl 0284.68040
[03.19] Mark Giesbrecht, “Nearly optimal algorithms for canonical matrix forms”, SIAM J. Comput. 24 (1995) no. 5, p. 948-969  MR 1350753 |  Zbl 0839.65043
[03.20] Richard Harter, “The optimality of Winograd’s formula”, Commun. ACM 15 (1972) no. 5 Article |  MR 314249 |  Zbl 0232.65036
[03.21, 12.19] J. Hopcroft & J. Musinski, “Duality applied to the complexity of matrix multiplication and other bilinear forms”, SIAM Journal on Computing 2 (1973), p. 159-173  MR 471439 |  Zbl 0294.65022
[03.22] J. E. Hopcroft & L. R. Kerr, “On minimizing the number of multiplications necessary for matrix multiplication”, SIAM J. Appl. Math. 20 (1971), p. 30-36  MR 274293 |  Zbl 0215.55501
[03.23] S. Huss-Lederman, E. M. Jacobson, A. Tsao, T. Turnbull & J. R. Johnson, Implementation of Strassen’s algorithm for matrix multiplication, in Supercomputing’96, IEEE Computer Society, 32 pp., 1996 Article
[03.24] Joseph Ja’Ja’, On the complexity of bilinear forms with commutativity, in STOC’79, ACM, 1979, p. 197-208 Article |  MR 564631
[03.25] I Kaporin, “The aggregation and cancellation techniques as a practical tool for faster matrix multiplication”, Theoretical Computer Science 315 (2004) no. 2-3, p. 469-510  MR 2073062 |  Zbl 1057.65020
[03.26] Igor Kaporin, “A practical algorithm for faster matrix multiplication”, Numer. Linear Algebra Appl. 6 (1999) no. 8, p. 687-700  MR 1736386 |  Zbl 0982.65048
[03.27, 16.10] Walter Keller-Gehrig, “Fast algorithms for the characteristic polynomial”, Theoret. Comput. Sci. 36 (1985) no. 2-3, p. 309-317  Zbl 0565.68041
[03.28] V. V. Klyuyev & N. I. Kokovkin-Shcherbak, “On the minimization of the number of arithmetic operations for the solution of linear algebraic systems of equations”, USSR Computational Mathematics and Mathematical Physics 5 (1965), p. 25-43  Zbl 0159.20403
[03.29] A. N. Krylov, “On the numerical solution of the equation by which in technical questions frequencies of small oscillations of material systems are determined”, Izv. Akad. Nauk SSSR 7 (1931) no. 4, p. 491-539, (in Russian)  JFM 57.1454.02
[03.30] Julian Laderman, Victor Pan & Xuan He Sha, “On practical algorithms for accelerated matrix multiplication”, Linear Algebra Appl. 162/164 (1992), p. 557-588  MR 1148417 |  Zbl 0748.65043
[03.31] Julian D. Laderman, “A noncommutative algorithm for multiplying $3\times 3$ matrices using $23$ muliplications”, Bull. Amer. Math. Soc. 82 (1976) no. 1, p. 126-128  MR 395320 |  Zbl 0322.65021
[03.32] J. M. Landsberg, “The border rank of the multiplication of $2\times 2$ matrices is seven”, J. Amer. Math. Soc. 19 (2006) no. 2, p. 447-459  MR 2188132 |  Zbl 1088.68069
[03.33] J. M. Landsberg, “Geometry and the complexity of matrix multiplication”, Bull. Amer. Math. Soc. (N.S.) 45 (2008) no. 2, p. 247-284  MR 2383305 |  Zbl 1145.68054
[03.34] O. M. Makarov, “An algorithm for multiplication of $3\times 3$ matrices”, Zh. Vychisl. Mat. i Mat. Fiz. 26 (1986) no. 2, p. 293-294, 320  MR 835700 |  Zbl 0614.65036
[03.35] I. Munro, Problems related to matrix multiplication, in R. Rustin, éd., Proceedings Courant Institute Symposium on Computational Complexity, October 1971, Algorithmics Press, 1973, p. 137-151
[03.36] V. Pan, “Computation schemes for a product of matrices and for the inverse matrix”, Uspehi Mat. Nauk 27 (1972) no. 5(167), p. 249-250  MR 395194 |  Zbl 0261.65025
[03.37] V. Ya. Pan, Strassen’s algorithm is not optimal. Trilinear technique of aggregating, uniting and canceling for constructing fast algorithms for matrix operations, in SFCS ’78, IEEE Computer Society, 1978, p. 166-176 Article |  MR 539838
[03.38] V. Ya. Pan, “New fast algorithms for matrix operations”, SIAM J. Comput. 9 (1980) no. 2, p. 321-342  MR 568817 |  Zbl 0446.68034
[03.39] V. Ya. Pan, “New combinations of methods for the acceleration of matrix multiplication”, Comput. Math. Appl. 7 (1981) no. 1, p. 73-125  MR 593557 |  Zbl 0465.68019
[03.40] Victor Pan, “How can we speed up matrix multiplication ?”, SIAM Rev. 26 (1984) no. 3, p. 393-415  MR 750457 |  Zbl 0563.65028
[03.41] Victor Pan, How to multiply matrices faster, Lecture Notes in Computer Science 179, Springer-Verlag, Berlin, 1984  MR 765701 |  Zbl 0548.65022
[03.42, 04.17] M. S. Paterson & L. J. Stockmeyer, “On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials”, SIAM J. Comput. 2 (1973) no. 1, p. 60-66  MR 314238 |  Zbl 0262.65033
[03.43] Clément Pernet & Arne Storjohann, Faster algorithms for the characteristic polynomial, ISSAC’07, ACM, 2007, p. 307–314  MR 2402276
[03.44] Robert L. Probert, “On the additive complexity of matrix multiplication”, SIAM J. Comput. 5 (1976) no. 2, p. 187-203  MR 408311 |  Zbl 0328.65029
[03.45] Ran Raz, “On the complexity of matrix product”, SIAM J. Comput. 32 (2003) no. 5, p. 1356-1369 Article |  MR 2001277 |  Zbl 1026.68060
[03.46] A. Schönhage, “Unitäre Transformationen grosser Matrizen”, Numer. Math. 20 (1972/73), p. 409-417  MR 327019 |  Zbl 0252.65031
[03.47] A. Schönhage, “Partial and total matrix multiplication”, SIAM J. Comput. 10 (1981) no. 3, p. 434-455  MR 623057 |  Zbl 0462.68018
[03.48] Warren D. Smith, “Fast matrix multiplication formulae – report of the prospectors”, Preprint, available at http://www.math.temple.edu/~wds/prospector.pdf, 2002
[03.49] Arne Storjohann, Deterministic computation of the Frobenius form (extended abstract), 42nd IEEE Symposium on Foundations of Computer Science (Las Vegas, NV, 2001), IEEE Computer Soc., Los Alamitos, CA, 2001, p. 368–377  MR 1948725
[03.50, 06.19] V. Strassen, “Gaussian Elimination is Not Optimal”, Numerische Mathematik 13 (1969), p. 354-356  Zbl 0185.40101
[03.51] V. Strassen, “Relative bilinear complexity and matrix multiplication”, J. Reine Angew. Math. 375/376 (1987), p. 406-443  MR 882307 |  Zbl 0621.68026
[03.52] Volker Strassen, Algebraic complexity theory, Handbook of theoretical computer science, Vol. A, Elsevier, 1990, p. 633–672  MR 1127177 |  Zbl 0900.68247
[03.53] Ondrej Sýkora, A fast non-commutative algorithm for matrix multiplication, Mathematical foundations of computer science (Proc. Sixth Sympos., Tatranská Lomnica, 1977), Springer, 1977, p. 504–512. Lecture Notes in Comput. Sci., Vol. 53  MR 464684 |  Zbl 0354.68068
[03.54] L. G. Valiant, “The complexity of computing the permanent”, Theoret. Comput. Sci. 8 (1979) no. 2, p. 189-201  MR 526203 |  Zbl 0415.68008
[03.55] Abraham Waksman, “On Winograd’s algorithm for inner products”, IEEE Trans. Comput. C-19 (1970) no. 4, p. 360-361  MR 455534 |  Zbl 0196.17104
[03.56] S. Winograd, “A new algorithm for inner-product”, IEEE Transactions on Computers 17 (1968), p. 693-694  Zbl 0174.46703
[03.57] S. Winograd, “On multiplication of $2\times 2$ matrices”, Linear Algebra and Appl. 4 (1971), p. 381-388  MR 297115 |  Zbl 0225.68018
[03.58] Shmuel Winograd, “On the number of multiplications necessary to compute certain functions”, Comm. Pure Appl. Math. 23 (1970), p. 165-179  MR 260150 |  Zbl 0191.15804
[03.59] Shmuel Winograd, Some remarks on fast multiplication of polynomials, Complexity of sequential and parallel numerical algorithms (Proc. Sympos., Carnegie-Mellon Univ., Pittsburgh, Pa., 1973), Academic Press, 1973, p. 181–196  MR 375839 |  Zbl 0273.65033
[04.01] D. J. Bernstein, “Removing redundancy in high-precision Newton iteration”, Preprint, available from http://cr.yp.to/fastnewton.html#fastnewton-paper
[04.02] Daniel J. Bernstein, “Composing power series over a finite ring in essentially linear time”, Journal of Symbolic Computation 26 (1998) no. 3, p. 339-341  MR 1633872 |  Zbl 0934.68129
[04.03, 13.02] Daniel J. Bernstein, Fast multiplication and its applications, Algorithmic number theory : lattices, number fields, curves and cryptography, Math. Sci. Res. Inst. Publ. 44, Cambridge Univ. Press, 2008, p. 325–384  MR 2467550 |  Zbl pre05532106
[04.04, 16.06] Alin Bostan, Philippe Flajolet, Bruno Salvy & Éric Schost, “Fast Computation of Special Resultants”, Journal of Symbolic Computation 41 (2006) no. 1, p. 1-29 Article |  MR 2194883 |  Zbl 1121.13037
[04.05, 12.10] Alin Bostan, Bruno Salvy & Éric Schost, Power series composition and change of basis, ISSAC’08, ACM, 2008, p. 269–276
[04.07] Richard P. Brent, Multiple-precision zero-finding methods and the complexity of elementary function evaluation, Analytic computational complexity, Academic Press, 1976, p. 151–176  MR 423869 |  Zbl 0342.65031
[04.08] Guillaume Hanrot & Paul Zimmermann, “Newton iteration revisited”, Available at http://www.loria.fr/~zimmerma/papers
[04.09] David Harvey, “Faster algorithms for the square root and reciprocal of power series”, Mathematics of Computation , To appear. Available at http://arxiv.org/abs/0910.1926/
[04.10] David Harvey, “Faster exponentials of power series”, Preprint, available from http://arxiv.org/abs/0911.3110
[04.11] A. H. Karp & P. Markstein, “High-precision division and square root”, ACM Transactions on Mathematical Software 23 (1997) no. 4, p. 561-589  MR 1671702 |  Zbl 0912.65038
[04.12] Kiran S. Kedlaya & Christopher Umans, Fast Modular Composition in any Characteristic, in FOCS ’08 : Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, 2008, p. 146-155 Article
[04.13] H. T. Kung, “On computing reciprocals of power series”, Numerische Mathematik 22 (1974), p. 341-348  MR 351045 |  Zbl 0274.65009
[04.14] Joseph-Louis Lagrange, “Nouvelle méthode pour résoudre les équations littérales par le moyen des séries”, Mémoires de l’Académie Royale des Sciences et Belles-Lettres de Berlin 24 (1768), p. 251-326
[04.15] J. D. Lipson, Newton’s Method : A Great Algebraic Algorithm, in Proceedings ACM Symposium of Symbolic and Algebraic Computation, ACM Press, 1976, p. 260-270  Zbl 0454.65035
[04.16] Isaac Newton, La méthode des fluxions, et les suites infinies, de Bure aîné, 1740, Traduction française par G. Buffon du texte de 1671 de Newton. Disponible en ligne à http://gallica.bnf.fr.
[04.18] P. Ritzmann, “A fast numerical algorithm for the composition of power series with complex coefficients”, Theoretical Computer Science 44 (1986), p. 1-16  MR 858688 |  Zbl 0632.68039
[04.19] A. Schönhage, The fundamental theorem of algebra in terms of computational complexity, Technical report, Univ. Tübingen, 1982
[04.20] G. Schulz, “Iterative Berechnung der reziproken Matrix”, Zeitschrift für angewandte Mathematik und Physik 13 (1933), p. 57-59  JFM 59.0535.04
[04.21] M. Sieveking, “An algorithm for division of powerseries”, Computing 10 (1972), p. 153-156  MR 312701 |  Zbl 0251.68023
[04.22, 15.05] Joris van der Hoeven, “Relax, but don’t be too lazy”, Journal of Symbolic Computation 34 (2002) no. 6, p. 479-542  MR 1943041 |  Zbl 1011.68189
[05.01] Manindra Agrawal, Neeraj Kayal & Nitin Saxena, “PRIMES is in P”, Annals of Mathematics. Second Series 160 (2004) no. 2, p. 781-793  MR 2123939 |  Zbl 1071.11070
[05.02] Vincent D. Blondel & Natacha Portier, “The presence of a zero in an integer linear recurrent sequence is NP-hard to decide”, Linear Algebra and its Applications 351/352 (2002), p. 91-98, Fourth special issue on linear systems and control  MR 1917474 |  Zbl 1007.93047
[05.03, 12.12] L. Cerlienco, M. Mignotte & F. Piras, “Suites récurrentes linéaires. Propriétés algébriques et arithmétiques”, L’Enseignement Mathématique 33 (1987), p. 67-108  Zbl 0626.10008
[05.04] Graham Everest, Alf van der Poorten, Igor Shparlinski & Thomas Ward, Recurrence sequences, Mathematical Surveys and Monographs 104, American Mathematical Society, Providence, RI, 2003  MR 1990179 |  Zbl 1033.11006
[05.05] C. M. Fiduccia, “An efficient formula for linear recurrences”, SIAM Journal on Computing 14 (1985) no. 1, p. 106-112  MR 774930 |  Zbl 0561.68033
[05.06] J. C. P. Miller & D. J. Spencer Brown, “An algorithm for evaluation of remote terms in a linear recurrence sequence”, Computer Journal 9 (1966), p. 188-190  MR 195240 |  Zbl 0151.21101
[05.07, 06.13] R. T. Moenck & A. Borodin, Fast modular transforms via division, in Thirteenth Annual IEEE Symposium on Switching and Automata Theory, 1972, p. 90-96
[05.08] Peter L. Montgomery, “Modular multiplication without trial division”, Mathematics of Computation 44 (1985) no. 170, p. 519-521  MR 777282 |  Zbl 0559.10006
[05.09, 12.29] V. Shoup, A Fast Deterministic Algorithm for Factoring Polynomials over Finite Fields of Small Characteristic, in ISSAC’91, ACM Press, 1991, p. 14-21  Zbl 0955.11500
[05.10, 06.20, 12.33] V. Strassen, “Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten”, Numerische Mathematik 20 (1972/73), p. 238-251  MR 324947 |  Zbl 0251.65036
[05.11] A. J. van der Poorten, Some facts that should be better known, especially about rational functions, Number theory and applications, Kluwer, 1989, p. 497–528  Zbl 0687.10007
[06.01, 16.01] A. V. Aho, K. Steiglitz & J. D. Ullman, “Evaluating polynomials at fixed sets of points”, SIAM Journal on Computing 4 (1975) no. 4, p. 533-539  MR 398151 |  Zbl 0326.65027
[06.02] L. I. Bluestein, “A linear filtering approach to the computation of the discrete Fourier transform”, IEEE Trans. Electroacoustics AU-18 (1970), p. 451-455
[06.03] A. Borodin & R. T. Moenck, “Fast modular transforms”, Comput. Sys. Sci. 8 (1974) no. 3, p. 366-386  MR 371144 |  Zbl 0302.68064
[06.05, 12.09] Alin Bostan, Grégoire Lecerf & Éric Schost, Tellegen’s principle into practice, in J. R. Sendra, éd., ISSAC’03, ACM Press, 2003, p. 37-44  Zbl 1072.68649
[06.06, 16.08] Alin Bostan & Éric Schost, “Polynomial evaluation and interpolation on special sets of points”, Journal of Complexity 21 (2005) no. 4, p. 420-446  MR 2152715 |  Zbl 1101.68039
[06.07] C. M. Fiduccia, Polynomial evaluation via the division algorithm : The fast Fourier transform revisited., in 4th ACM Symposium on Theory of Computing, 1972, p. 88-93  Zbl 0346.42009
[06.08] Harvey L. Garner, The residue number system, in IRE-AIEE-ACM’59 Western joint computer conference, ACM, 1959, p. 146-153 Article
[06.09] Carl Friedrich Gauss, Disquisitiones arithmeticae, Translated into English by Arthur A. Clarke, S. J, Yale University Press, New Haven, Conn., 1966  MR 197380 |  Zbl 0136.32301
[06.10] L. E. Heindel & E. Horowitz, On decreasing the computing time for modular arithmetic, in 12th symposium on switching and automata theory, IEEE, 1971, p. 126-128
[06.11] E. Horowitz, “A fast Method for Interpolation Using Preconditioning”, Information Processing Letters 1 (1972) no. 4, p. 157-163  MR 315864 |  Zbl 0297.65005
[06.12] Russell M. Mersereau, “An algorithm for performing an inverse chirp $z$-transform”, IEEE Trans. Acoust. Speech Signal Processing ASSP-22 (1974) no. 5, p. 387-388  MR 413451
[06.14] P. L. Montgomery, An FFT extension of the elliptic curve method of factorization, Ph. D. Thesis, University of California, Los Angeles CA, 1992  MR 2688742
[06.15] A. Ostrowski, On two problems in abstract algebra connected with Horner’s rule, Studies in mathematics and mechanics presented to Richard von Mises, 1954, p. 40–48  MR 66030 |  Zbl 0056.35204
[06.16] V. Ya. Pan, “Methods of computing values of polynomials”, Russian Mathematical Surveys 21 (1966) no. 1, p. 105-136  Zbl 0173.17802
[06.17] L. R. Rabiner, R. W. Schafer & C. M. Rader, “The chirp $z$-transform algorithm and its application”, Bell System Tech. J. 48 (1969), p. 1249-1292  MR 243724
[06.18] Victor Shoup & Roman Smolensky, “Lower bounds for polynomial evaluation and interpolation problems”, Computational Complexity 6 (1996/97) no. 4, p. 301-311  MR 1613682 |  Zbl 0895.68075
[06.21] A. Svoboda & M. Valach, “Operátorové obvody (Operational circuits)”, Stroje na Zpracování Informací (Information Processing Machines) 3 (1955), p. 247-295  MR 96376
[06.22] H. Takahasi & Y. Ishibashi, “A new method for exact calculation by a digital computer”, Information Processing in Japan (1961), p. 28-42  Zbl 0121.12103
[06.23] E. Waring, “Problems concerning interpolations”, Philosophical Transactions of the Royal Society of London 59 (1779), p. 59-67
[07.01] L. M. Berkovich & V. G. Tsirulik, “Differential resultants and some of their applications”, Differentsial nye Uravneniya 22 (1986) no. 5, p. 750-757, 914, English translation in : Differential Equations, Plenum Publ. Corp., Vol. 22, no. 5, pp. 530–536. NY Plenum 1986  MR 846502 |  Zbl 0611.34007
[07.02] É. Bézout, “Recherches sur le degré des équations résultantes de l’évanouissement des inconnues”, Histoire de l’académie royale des science (1764), p. 288-338
[07.03, 09.05, 11.03] Richard P. Brent, Fred G. Gustavson & David Y. Y. Yun, “Fast solution of Toeplitz systems of equations and computation of Padé approximants”, J. Algorithms 1 (1980) no. 3, p. 259-295  Zbl 0475.65018
[07.04] W. S. Brown, On Euclid’s algorithm and the computation of polynomial greatest common divisors, in SYMSAC ’71 : Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, ACM, 1971, p. 195-211 Article
[07.05] W. S. Brown & J. F. Traub, “On Euclid’s algorithm and the theory of subresultants”, J. Assoc. Comput. Mach. 18 (1971), p. 505-514  MR 303684 |  Zbl 0226.65041
[07.06] Marc Chardin, Differential resultants and subresultants, Fundamentals of computation theory (Gosen, 1991), Lecture Notes in Comput. Sci. 529, Springer, 1991, p. 180–189  MR 1136080 |  Zbl 0925.12002
[07.07] G. E. Collins, “Polynomial remainder sequences and determinants”, Amer. Math. Monthly 73 (1966), p. 708-712  MR 199216 |  Zbl 0147.29505
[07.08] George E. Collins, “Subresultants and reduced polynomial remainder sequences”, J. Assoc. Comput. Mach. 14 (1967), p. 128-142  MR 215512 |  Zbl 0152.35403
[07.09] George E. Collins, “The calculation of multivariate polynomial resultants”, J. Assoc. Comput. Mach. 18 (1971), p. 515-532  MR 298921 |  Zbl 0226.65042
[07.11] D. Yu. Grigoriev, “Complexity of factoring and calculating the GCD of linear ordinary differential operators”, J. Symbolic Comput. 10 (1990) no. 1, p. 7-37  MR 1081258 |  Zbl 0728.68067
[07.12, 09.17, 11.08] Fred G. Gustavson & David Y. Y. Yun, “Fast algorithms for rational Hermite approximation and solution of Toeplitz systems”, IEEE Trans. Circuits and Systems 26 (1979) no. 9, p. 750-755  MR 549385 |  Zbl 0416.65008
[07.13] Hoon Hong, “Ore principal subresultant coefficients in solutions”, Appl. Algebra Engrg. Comm. Comput. 11 (2001) no. 3, p. 227-237  MR 1815132 |  Zbl 1006.16030
[07.14] Hoon Hong, “Ore subresultant coefficients in solutions”, Appl. Algebra Engrg. Comm. Comput. 12 (2001) no. 5, p. 421-428  MR 1864611 |  Zbl 1006.16031
[07.15] Donald E. Knuth, The analysis of algorithms, Actes du Congrès International des Mathématiciens (Nice, 1970), Tome 3, Gauthier-Villars, 1971, p. 269–274  MR 423865 |  Zbl 0279.68041
[07.16] Donald E. Knuth, The Art of Computer Programming, Computer Science and Information Processing 2 : Seminumerical Algorithms, Addison-Wesley Publishing Co., Reading, Mass., 1997  MR 378456
[07.17] Serge Lang, Algebra, Graduate Texts in Mathematics 211, Springer-Verlag, New York, 2002  MR 1878556 |  Zbl 0984.00001
[07.18] Alain Lascoux, Symmetric functions and combinatorial operators on polynomials, CBMS Regional Conference Series in Mathematics 99, Published for the Conference Board of the Mathematical Sciences, Washington, DC, 2003  MR 2017492 |  Zbl 1039.05066
[07.19] D. H. Lehmer, “Euclid’s Algorithm for Large Numbers”, Amer. Math. Monthly 45 (1938) no. 4, p. 227-233  MR 1524250 |  JFM 64.0149.01
[07.20] Z. Li & I. Nemes, A modular algorithm for computing greatest common right divisors of Ore polynomials, in ISSAC’97, ACM, 1997, p. 282-289  MR 1809996 |  Zbl 0927.16043
[07.21] Ziming Li, A subresultant theory for Ore polynomials with applications, in ISSAC’98, ACM, 1998, p. 132-139  MR 1805177 |  Zbl 0922.16015
[07.22] Ziming Li, Greatest common right divisors, least common left multiples, and subresultants of Ore polynomials, Mathematics mechanization and applications, Academic Press, 2000, p. 297–324  MR 1784030
[07.23] R. T. Moenck, Fast computation of GCDs, Fifth Annual ACM Symposium on Theory of Computing (Austin, Tex., 1973), Assoc. Comput. Mach., New York, 1973, p. 142–151  MR 455528 |  Zbl 0306.68027
[07.24] Niels Möller, “On Schönhage’s algorithm and subquadratic integer GCD computation”, Math. Comp. 77 (2008) no. 261, p. 589-607  MR 2353968 |  Zbl 1165.11003
[07.25] V. Y. Pan & X. Wang, Acceleration of Euclidean algorithm and extensions, in Teo Mora, éd., ISSAC’02, ACM, 2002, p. 207-213  MR 2035251 |  Zbl 1072.68691
[07.26] A. Schönhage, “Schnelle Berechnung von Kettenbruchentwicklugen”, Acta Inform. 1 (1971), p. 139-144  Zbl 0223.68008
[07.27] A. Schönhage, “Probabilistic computation of integer polynomial GCDs”, J. Algorithms 9 (1988) no. 3, p. 365-371  MR 955145 |  Zbl 0651.68045
[07.28, 10.07] J. T. Schwartz, “Fast probabilistic algorithms for verification of polynomial identities”, J. Assoc. Comput. Mach. 27 (1980) no. 4, p. 701-717  MR 594695 |  Zbl 0452.68050
[07.29] D. Stehlé & P. Zimmermann, A binary recursive Gcd algorithm, in ANTS-VI, Lecture Notes in Computer Science, Springer, 2004, p. 411-425  MR 2138011 |  Zbl 1125.11362
[07.30] V. Strassen, The computational complexity of continued fractions, in SYMSAC’81, ACM, 1981, p. 51-67 Article |  Zbl 0486.68029
[07.32] James Joseph Sylvester, On rational derivation from equations of coexistence, that is to say, a new and extended theory of elimination, 1839–40, The Collected mathematical papers of James Joseph Sylvester, Baker, H. F., 1839, p. 40–53
[07.33] James Joseph Sylvester, “A method of determining by mere inspection the derivatives from two equations of any degree”, Philos. Mag. 16 (1840) no. 101, p. 132-135
[07.34] Joachim von zur Gathen & Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, 2003  MR 2001757 |  Zbl 1055.68168
[07.35] Joachim von zur Gathen & Thomas Lücking, “Subresultants revisited”, Theoret. Comput. Sci. 297 (2003) no. 1-3, p. 199-239  MR 1981147 |  Zbl 1045.68168
[07.36] Chee Yap, Fundamental Problems in Algorithmic Algebra, Oxford Univ. Press, 2000  MR 1740761 |  Zbl 0999.68261
[07.37] David Y.Y. Yun, On square-free decomposition algorithms, in SYMSAC’76, ACM, 1976, p. 26-35 Article |  Zbl 0498.13006
[07.38] David Y.Y. Yun, On the equivalence of polynomial GCD and squarefree factorization problems, in Proc. of the MACSYMA Users’ Conference, 1977, p. 65-70
[08.01] Niels Henrik Abel, Œuvres complètes. Tome II, Éditions Jacques Gabay, Sceaux, 1992, Edited and with notes by L. Sylow and S. Lie, Reprint of the second (1881) edition. Disponible en ligne à http://gallica.bnf.fr.
[08.02] Milton Abramowitz & Irene A. Stegun (éd.), Handbook of mathematical functions with formulas, graphs, and mathematical tables, Dover Publications Inc., New York, 1992, Reprint of the 1972 edition  MR 1225604
[08.03] Alin Bostan, Algorithmique efficace pour des opérations de base en Calcul formel, Ph. D. Thesis, École polytechnique, 2003
[08.04] Alin Bostan, Frédéric Chyzak, Grégoire Lecerf, Bruno Salvy & Éric Schost, Differential equations for algebraic functions, in ISSAC’07, ACM Press, 2007, p. 25-32 Article |  MR 2396180 |  Zbl 1190.68085
[08.05] L. Comtet, Analyse Combinatoire, PUF, Paris, 1970, 2 volumes  Zbl 0221.05002
[08.06, 13.09] Philippe Flajolet & Bruno Salvy, “The SIGSAM Challenges : Symbolic Asymptotics in Practice”, SIGSAM Bulletin 31 (1997) no. 4, p. 36-47 Article
[08.07] Rev. Robert Harley, “On the theory of the transcendental solution of algebraic equations”, Quarterly Journal of Pure and Applied Mathematics 5 (1862), p. 337-360
[08.08] William A. Harris & Yasutaka Sibuya, “The reciprocals of solutions of linear ordinary differential equations”, Advances in Mathematics 58 (1985) no. 2, p. 119-132  MR 814747 |  Zbl 0581.12013
[08.09] L. Lipshitz, “$D$-Finite Power Series”, Journal of Algebra 122 (1989) no. 2, p. 353-373  MR 999079 |  Zbl 0695.12018
[08.10] Bruno Salvy & Paul Zimmermann, “Gfun : a Maple package for the manipulation of generating and holonomic functions in one variable”, ACM Transactions on Mathematical Software 20 (1994) no. 2, p. 163-177 Article |  Zbl 0888.65010
[08.11] Michael F. Singer, “Algebraic relations among solutions of linear differential equations”, Transactions of the American Mathematical Society 295 (1986) no. 2, p. 753-763  MR 833707 |  Zbl 0593.12014
[08.12] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, 2006, Published electronically at http://www.research.att.com/~njas/sequences/.
[08.13] R. P. Stanley, “Differentiably Finite Power Series”, European Journal of Combinatorics 1 (1980) no. 2, p. 175-188  MR 587530 |  Zbl 0445.05012
[08.14] Richard P. Stanley, Enumerative combinatorics 2, Cambridge University Press, 1999  MR 1676282 |  Zbl 0928.05001
[08.15] Jules Tannery, Propriétés des intégrales des équations différentielles linéaires à coefficients variables, Thèse de doctorat ès sciences mathématiques, Faculté des Sciences de Paris, Disponible en ligne à http://gallica.bnf.fr., 1874  JFM 07.0184.01
[09.01] George A. Baker & Peter Graves-Morris, Padé approximants, Encyclopedia of Mathematics and its Applications 59, Cambridge University Press, Cambridge, 1996  MR 1383091 |  Zbl 0923.41001
[09.02] B. Beckermann & G. Labahn, “A uniform approach for the fast computation of matrix-type Padé approximants”, SIAM J. Matrix Anal. Appl. 15 (1994) no. 3, p. 804-823  MR 1282696 |  Zbl 0805.65008
[09.03] Bernhard Beckermann, “A reliable method for computing $M$-Padé approximants on arbitrary staircases”, J. Comput. Appl. Math. 40 (1992) no. 1, p. 19-42  MR 1167913 |  Zbl 0810.65014
[09.04] Bernhard Beckermann & George Labahn, “Fraction-free computation of matrix rational interpolants and matrix GCDs”, SIAM J. Matrix Anal. Appl. 22 (2000) no. 1, p. 114-144  MR 1779720 |  Zbl 0973.65007
[09.06] S. Cabay & G. Labahn, A fast, reliable algorithm for calculating Padé-Hermite forms, in ISSAC’89, ACM, 1989, p. 95-100 Article
[09.07] S. Cabay, G. Labahn & B. Beckermann, “On the theory and computation of nonperfect Padé-Hermite approximants”, J. Comput. Appl. Math. 39 (1992) no. 3, p. 295-313  MR 1164293 |  Zbl 0810.65013
[09.08] Stanley Cabay & Dong Koo Choi, “Algebraic computations of scaled Padé fractions”, SIAM J. Comput. 15 (1986) no. 1, p. 243-270  MR 822203 |  Zbl 0633.30008
[09.09] Unjeng Cheng, “On the continued fraction and Berlekamp’s algorithm”, IEEE Trans. Inform. Theory 30 (1984) no. 3, p. 541-544  MR 751325 |  Zbl 0552.94014
[09.10] J. Della Dora & C. Dicrescenzo, “Approximants de Padé-Hermite. I. Théorie”, Numer. Math. 43 (1984) no. 1, p. 23-39  MR 726360 |  Zbl 0537.65013
[09.11] J. Della Dora & C. Dicrescenzo, “Approximants de Padé-Hermite. II. Programmation”, Numer. Math. 43 (1984) no. 1, p. 41-57  MR 726361 |  Zbl 0537.65014
[09.12] Harm Derksen, An algorithm to compute generalized Padé-Hermite forms, Technical report 9403, Dept. of Math., Catholic University Nijmegen, 1994
[09.13, 14.01] John D. Dixon, “Exact solution of linear equations using $p$-adic expansions”, Numer. Math. 40 (1982) no. 1, p. 137-141  Zbl 0492.65016
[09.14] Jean-Louis Dornstetter, “On the equivalence between Berlekamp’s and Euclid’s algorithms”, IEEE Trans. Inform. Theory 33 (1987) no. 3, p. 428-431  MR 885401 |  Zbl 0633.94019
[09.15, 14.02] Pascal Giorgi, Claude-Pierre Jeannerod & Gilles Villard, On the complexity of polynomial matrix computations, in ISSAC’03, ACM, 2003, p. 135-142  Zbl 1072.68708
[09.16] William B. Gragg, Fred G. Gustavson, Daniel D. Warner & David Y. Y. Yun, “On fast computation of superdiagonal Padé fractions”, Math. Programming Stud. (1982) no. 18, p. 39-42, Algorithms and theory in filtering and control (Lexington, Ky., 1980)  MR 656936 |  Zbl 0501.65006
[09.18] G. H. Hardy & E. M. Wright, An introduction to the theory of numbers, Oxford University Press, Oxford, 2008  MR 2445243 |  Zbl 1159.11001
[09.19] C. Hermite, “Extrait d’une lettre de Monsieur Ch. Hermite à Monsieur Paul Gordan”, J. Reine Angew. Math. 78 (1873), p. 303-311  JFM 05.0252.01
[09.20] C. Hermite, “Sur la fonction exponentielle”, C. R. Math. Acad. Sci. Paris 77 (1873), p. 18-24  JFM 05.0248.01
[09.21] C. Hermite, “Sur la généralisation des fractions continues algébriques”, Ann. Math. 21 (1893) no. 2, p. 289-308  JFM 25.0325.02
[09.22] M. A. H. Khan, “High-order differential approximants”, J. Comput. Appl. Math. 149 (2002) no. 2, p. 457-468  MR 1937295 |  Zbl 1013.65003
[09.23] K. Mahler, “Perfect systems”, Compositio Math. 19 (1968), p. 95-166 (1968) Numdam |  MR 239099 |  Zbl 0168.31303
[09.24] James L. Massey, “Shift-register synthesis and ${\rm BCH}$ decoding”, IEEE Trans. Information Theory IT-15 (1969), p. 122-127  MR 242556 |  Zbl 0167.18101
[09.25] Robert J. McEliece & James B. Shearer, “A property of Euclid’s algorithm and an application to Padé approximation”, SIAM J. Appl. Math. 34 (1978) no. 4, p. 611-615  MR 491634 |  Zbl 0384.10006
[09.26] W. H. Mills, “Continued fractions and linear recurrences”, Math. Comp. 29 (1975), p. 173-180  MR 369276 |  Zbl 0298.10021
[09.27] H. Padé, “Sur la Représentation Approchée d’une Fonction par des Fractions Rationelles”, Ann. Sci. École Norm. Sup. 9 (1892), p. 3-93  JFM 24.0360.02
[09.28] H. Padé, “Sur la généralisation des fractions continues algébriques”, J. Math. Pures Appl. 10 (1894) no. 4, p. 291-330  JFM 25.0681.01
[09.29] Victor Y. Pan & Xinmao Wang, “On rational number reconstruction and approximation”, SIAM J. Comput. 33 (2004) no. 2, p. 502-503  MR 2048454 |  Zbl 1101.68997
[09.30] Stefan Paszkowski, “Recurrence relations in Padé-Hermite approximation”, J. Comput. Appl. Math. 19 (1987) no. 1, p. 99-107  MR 901218 |  Zbl 0624.41021
[09.31] A. V. Sergeyev, “A recursive algorithm for Padé-Hermite approximations”, USSR Comput. Maths Math. Phys 26 (1986) no. 2, p. 17-22  Zbl 0621.65005
[09.32] R. E. Shafer, “On quadratic approximation”, SIAM J. Numer. Anal. 11 (1974), p. 447-460  MR 358161 |  Zbl 0253.65006
[09.33] Y. Tourigny & Ph. G. Drazin, “The asymptotic behaviour of algebraic approximants”, R. Soc. Lond. Proc. Ser. A Math. Phys. Eng. Sci. 456 (2000) no. 1997, p. 1117-1137  MR 1809955 |  Zbl 0971.41007
[09.34] M. Van Barel & A. Bultheel, “A general module-theoretic framework for vector M-Padé and matrix rational interpolation”, Numer. Algorithms 3 (1992) no. 1-4, p. 451-461  MR 1199391 |  Zbl 0780.41014
[09.35] Marc Van Barel & Adhemar Bultheel, “The computation of nonperfect Padé-Hermite approximants”, Numer. Algorithms 1 (1991) no. 3, p. 285-304  MR 1135298 |  Zbl 0753.65013
[09.36] Xinmao Wang & Victor Y. Pan, “Acceleration of Euclidean algorithm and rational number reconstruction”, SIAM J. Comput. 32 (2003) no. 2, p. 548-556  MR 1969404 |  Zbl 1031.68149
[09.37] L. R. Welch & R. A. Scholtz, “Continued fractions and Berlekamp’s algorithm”, IEEE Trans. Inform. Theory 25 (1979) no. 1, p. 19-27  MR 514928 |  Zbl 0388.94014
[09.38] N. Zierler, Linear recurring sequences and error-correcting codes, Error Correcting Codes (Proc. Sympos. Math. Res. Center, Madison, Wis., 1968), Wiley, 1968, p. 47–59  MR 249191 |  Zbl 0181.22402
[10.01] Don Coppersmith, “Solving homogeneous linear equations over ${\rm GF}(2)$ via block Wiedemann algorithm”, Math. Comp. 62 (1994) no. 205, p. 333-350  MR 1192970 |  Zbl 0805.65046
[10.02] Richard A. DeMillo & Richard J. Lipton, “A probabilistic remark on algebraic program testing”, Inform. Process. Lett. 7 (1978) no. 4, p. 193-195  Zbl 0397.68011
[10.03] M. Giesbrecht, A. Lobo & B. D. Saunders, Certifying inconsistency of sparse linear systems, in Proceedings of the 1998 International Symposium on Symbolic and Algebraic Computation (Rostock), ACM, 1998, p. 113-119 (electronic)  MR 1805174 |  Zbl 0919.65017
[10.04] Mark Giesbrecht, “Fast computation of the Smith form of a sparse integer matrix”, Comput. Complexity 10 (2001) no. 1, p. 41-69  MR 1867308 |  Zbl 0992.65039
[10.05] Erich Kaltofen & B. David Saunders, On Wiedemann’s method of solving sparse linear systems, Applied algebra, algebraic algorithms and error-correcting codes (New Orleans, LA, 1991), Lecture Notes in Comput. Sci. 539, Springer, 1991, p. 29–38  MR 1229306 |  Zbl 0778.65034
[10.06] Thom Mulders, “Certified sparse linear system solving”, J. Symbolic Comput. 38 (2004) no. 5, p. 1343-1373  MR 2168719 |  Zbl 1137.65345
[10.08] E. Thomé, “Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm”, J. Symbolic Comput. 33 (2002) no. 5, p. 757-775  MR 1919913 |  Zbl 1010.65024
[10.09] William J. Turner, A block Wiedemann rank algorithm, ISSAC’06, ACM, 2006, p. 332–339  MR 2289139
[10.10] G. Villard, Further analysis of Coppersmith’s block Wiedemann algorithm for the solution of sparse linear systems (extended abstract), in ISSAC’97, ACM, 1997, p. 32-39 Article |  Zbl 0917.65041
[10.11, 12.36] D. Wiedemann, “Solving sparse linear equations over finite fields”, IEEE Transactions on Information Theory IT-32 (1986), p. 54-62  Zbl 0607.65015
[10.12] Richard Zippel, Probabilistic algorithms for sparse polynomials, EUROSAM’79, Lecture Notes in Comput. Sci. 72, Springer, 1979, p. 216–226  MR 575692 |  Zbl 0418.68040
[11.01] Robert R. Bitmead & Brian D. O. Anderson, “Asymptotically fast solution of Toeplitz and related systems of linear equations”, Linear Algebra Appl. 34 (1980), p. 103-116  MR 591427 |  Zbl 0458.65018
[11.02] Alin Bostan, Claude-Pierre Jeannerod & Éric Schost, “Solving structured linear systems with large displacement rank”, Theoret. Comput. Sci. 407 (2008) no. 1-3, p. 155-181  MR 2463004 |  Zbl 1169.65023
[11.04] Jean-Paul Cardinal, “On a property of Cauchy-like matrices”, C. R. Acad. Sci. Paris Sér. I Math. 328 (1999) no. 11, p. 1089-1093  MR 1696212 |  Zbl 0933.65025
[11.05] I. Gohberg & V. Olshevsky, “Complexity of multiplication with vectors for structured matrices”, Linear Algebra Appl. 202 (1994), p. 163-192  MR 1288487 |  Zbl 0803.65053
[11.06] I. C. Gohberg & A. A. Semencul, “On the inversion of finite Toeplitz matrices and their continuous analogues (In Russian)”, Mat. Issled. 7 (1972) no. 2, p. 201-223  MR 353038 |  Zbl 0288.15004
[11.07] Gene H. Golub & Charles F. Van Loan, Matrix computations, Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 1996  MR 1417720
[11.09] T. Kailath, S. Y. Kung & M. Morf, “Displacement ranks of a matrix”, Bull. Amer. Math. Soc. (N.S.) 1 (1979) no. 5, p. 769-773  MR 537629 |  Zbl 0417.65015
[11.10] Thomas Kailath, Sun Yuan Kung & Martin Morf, “Displacement ranks of matrices and linear equations”, J. Math. Anal. Appl. 68 (1979) no. 2, p. 395-407  MR 533501 |  Zbl 0433.15001
[11.11] Erich Kaltofen, Asymptotically fast solution of Toeplitz-like singular linear systems, in ISSAC’94, ACM, 1994, p. 297-304 Article |  Zbl 0978.15500
[11.12] Erich Kaltofen, “Analysis of Coppersmith’s block Wiedemann algorithm for the parallel solution of sparse linear systems”, Math. Comp. 64 (1995) no. 210, p. 777-806  MR 1270621 |  Zbl 0828.65035
[11.13] Norman Levinson, “The Wiener RMS (root mean square) error criterion in filter design and prediction”, J. Math. Phys. Mass. Inst. Tech. 25 (1947), p. 261-278  MR 19257
[11.14] M. Morf, Doubling algorithms for Toeplitz and related equations, in IEEE Conference on Acoustics, Speech, and Signal Processing, 1980, p. 954-959
[11.15] Victor Pan, “On computations with dense structured matrices”, Math. Comp. 55 (1990) no. 191, p. 179-190  MR 1023051 |  Zbl 0703.47022
[11.16] Victor Y. Pan, Structured matrices and polynomials, Birkhäuser Boston Inc., Boston, MA, 2001, Unified superfast algorithms  MR 1843842 |  Zbl 0996.65028
[11.17] Victor Y. Pan & Ailong Zheng, “Superfast algorithms for Cauchy-like matrix computations and extensions”, Linear Algebra Appl. 310 (2000) no. 1-3, p. 83-108  MR 1753169 |  Zbl 0971.65024
[11.18] William F. Trench, “An algorithm for the inversion of finite Toeplitz matrices”, J. Soc. Indust. Appl. Math. 12 (1964), p. 515-522  MR 173681 |  Zbl 0131.36002
[12.01] A. Antoniou, Digital Filters : Analysis and Design, McGraw-Hill Book Co., 1979
[12.03] M. Ben-Or & P. Tiwari, A deterministic algorithm for sparse multivariate polynomial interpolation, in STOC’88, ACM Press, 1988, p. 301-309
[12.04] D. J. Bernstein, “The transposition principle”, http://cr.yp.to/transposition.html
[12.05] Leo I. Bluestein, “A linear filtering approach to the computation of the discrete Fourier transform”, IEEE Northeast Electronics Research and Engineering Meeting 10 (1968), p. 218-219
[12.06] J. L. Bordewijk, “Inter-reciprocity applied to electrical networks”, Appl. Sci. Res. B. 6 (1956), p. 1-74  MR 79954 |  Zbl 0072.43203
[12.07] A. Bostan, G. Lecerf, B. Salvy, É. Schost & B. Wiebelt, Complexity issues in bivariate polynomial factorization, ISSAC’04, ACM, 2004, p. 42–49  MR 2126923 |  Zbl 1134.68595
[12.08] A. Bostan & É. Schost, “On the complexities of multipoint evaluation and interpolation”, Theoret. Comput. Sci. 329 (2004) no. 1–3, p. 223-235  MR 2103649 |  Zbl 1086.68150
[12.11] J. Canny, E. Kaltofen & L. Yagati, Solving systems of non-linear polynomial equations faster, in ISSAC’89, ACM Press, 1989, p. 121-128
[12.13] Eleanor Chu & Alan George, Inside the FFT black box, CRC Press, 2000, Serial and parallel fast Fourier transform algorithms  MR 1740143
[12.14] A. Fettweis, “A general theorem for signal-flow networks, with applications”, Archiv für Elektronik und Übertragungstechnik 25 (1971) no. 12, p. 557-561
[12.15] C. M. Fiduccia, On obtaining upper bounds on the complexity of matrix multiplication, Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972), Plenum, 1972, p. 31–40  MR 391577
[12.16] C. M. Fiduccia, On the algebraic complexity of matrix multiplication, Ph. D. Thesis, Brown Univ., Providence, RI, Center Comput. Inform. Sci., Div. Engin., 1973
[12.17] J.-C. Gilbert, G. Le Vey & J. Masse, La différentiation automatique de fonctions représentées par des programmes, Technical report, RR INRIA 1557, 1991
[12.20] R. E. Kalman, “On the General Theory of Control Systems”, IRE Transactions on Automatic Control 4 (1959) no. 3, p. 481-491
[12.21] E. Kaltofen, R. M. Corless & D. J. Jeffrey, “Challenges of symbolic computation : my favorite open problems”, Journal of Symbolic Computation 29 (2000) no. 6, p. 891-919  MR 1765929 |  Zbl 0963.68234
[12.22] Erich Kaltofen, Analysis of Coppersmith’s block Wiedemann algorithm for the parallel solution of sparse linear systems, Applied algebra, algebraic algorithms and error-correcting codes, Lecture Notes in Comput. Sci. 673, Springer, 1993, p. 195–212  MR 1251979 |  Zbl 0801.65024
[12.23] Erich Kaltofen, Computational differentiation and algebraic complexity theory, in Workshop Report on First Theory Institute on Computational Differentiation, 1993, p. 28-30
[12.24] M. Kaminski, D. G. Kirkpatrick & N. H. Bshouty, “Addition requirements for matrix and transposed matrix products”, Journal of Algorithms 9 (1988) no. 3, p. 354-364  MR 955144 |  Zbl 0653.65032
[12.25] Donald E. Knuth & Christos H. Papadimitriou, “Duality in addition chains”, Bulletin of the European Association for Theoretical Computer Science 13 (1981), p. 2-4
[12.26] G. Lecerf & É. Schost, “Fast Multivariate Power Series Multiplication in Characteristic Zero”, SADIO Electronic Journal on Informatics and Operations Research 5 (2003) no. 1, p. 1-10
[12.27] P. Penfield, R. Spence & S. Duinker, Tellegen’s theorem and electrical networks, The M.I.T. Press, Cambridge, Mass.-London, 1970  MR 282747
[12.28] Steven Roman, The umbral calculus, Pure and Applied Mathematics 111, Academic Press Inc. [Harcourt Brace Jovanovich Publishers], New York, 1984  MR 741185 |  Zbl 0536.33001
[12.30] V. Shoup, “A new polynomial factorization algorithm and its implementation”, Journal of Symbolic Computation 20 (1995) no. 4, p. 363-397  MR 1384454 |  Zbl 0854.11074
[12.31] V. Shoup, Efficient computation of minimal polynomials in algebraic extensions of finite fields, in ISSAC’99, ACM Press, 1999, p. 53-58  MR 1802067
[12.32] Victor Shoup, “Fast construction of irreducible polynomials over finite fields”, J. Symbolic Comput. 17 (1994) no. 5, p. 371-391  MR 1289997 |  Zbl 0815.11059
[12.34] B. Tellegen, “A general network theorem, with applications”, Philips Research Reports 7 (1952), p. 259-269  MR 51142 |  Zbl 0049.42301
[12.37] R. Zippel, “Interpolating polynomials from their values”, Journal of Symbolic Computation 9 (1990) no. 3, p. 375-403  MR 1056633 |  Zbl 0702.65011
[13.01] Michael Beeler, R. Gosper & Richard Schroeppel, HAKMEM, Artificial Intelligence Memo No. 239, MIT, 1972
[13.03] Peter B. Borwein, “On the complexity of calculating factorials”, Journal of Algorithms 6 (1985) no. 3, p. 376-380  MR 800727 |  Zbl 0576.68027
[13.04] A. Bostan, F. Chyzak, T. Cluzeau & B. Salvy, Low complexity algorithms for linear recurrences, ISSAC’06, ACM, 2006, p. 31–38  MR 2289098
[13.05] Alin Bostan, Thomas Cluzeau & Bruno Salvy, Fast Algorithms for Polynomial Solutions of Linear Differential Equations, in ISSAC’05, ACM Press, 2005, p. 45-52 Article |  MR 2280528
[13.06, 16.07] Alin Bostan, Pierrick Gaudry & Éric Schost, “Linear recurrences with polynomial coefficients and application to integer factorization and Cartier-Manin operator”, SIAM J. Comput. 36 (2007) no. 6, p. 1777-1806  MR 2299425 |  Zbl pre05222850
[13.07] R. P. Brent, Multiple-precision zero-finding methods and the complexity of elementary function evaluation, Analytic computational complexity (Proc. Sympos., Carnegie-Mellon Univ., Pittsburgh, Pa., 1975), Academic Press, 1976, p. 151–176  MR 423869 |  Zbl 0342.65031
[13.08] D. V. Chudnovsky & G. V. Chudnovsky, Approximations and complex multiplication according to Ramanujan, Ramanujan revisited, Academic Press, 1988, p. 375–472  MR 938975 |  Zbl 0647.10002
[13.10] P. Kogge & H. Stone, “A parallel algorithm for the efficient solution of a general class of recurrence equations”, IEEE Trans. Comp. C-22 (1973), p. 786-793  MR 395307 |  Zbl 0262.68015
[13.11] V. Strassen, “Einige Resultate über Berechnungskomplexität”, Jber. Deutsch. Math.-Verein. 78 (1976/77) no. 1, p. 1-8  MR 438807 |  Zbl 0361.68070
[14.03] Claude-Pierre Jeannerod & Gilles Villard, “Essentially optimal computation of the inverse of generic polynomial matrices”, J. Complexity 21 (2005) no. 1, p. 72-86  MR 2112743 |  Zbl 1101.68956
[14.04] Robert T. Moenck & John H. Carter, Approximate algorithms to derive exact solutions to systems of linear equations, in EUROSAM ’79 : Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, Lecture Notes in Computer Science, Springer-Verlag, 1979, p. 65-73  MR 575681 |  Zbl 0435.65023
[14.05] Arne Storjohann, High-Order Lifting, in Teo Mora, éd., ISSAC’02, ACM Press, Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, July 07–10, 2002, Université de Lille, France, 2002, p. 246-254  Zbl 1072.68698
[14.06] Arne Storjohann, “High-order lifting and integrality certification”, J. Symbolic Comput. 36 (2003) no. 3-4, p. 613-648  MR 2004044 |  Zbl 1059.15020
[14.07] Arne Storjohann, “The shifted number system for fast linear algebra on integer matrices”, J. Complexity 21 (2005) no. 4, p. 609-650  MR 2152725 |  Zbl 1101.68045
[14.08] Arne Storjohann & Gilles Villard, Computing the rank and a small nullspace basis of a polynomial matrix, ISSAC’05, ACM, 2005, p. 309–316  MR 2280562
[15.01] A. Bostan, F. Chyzak, F. Ollivier, B. Salvy, É. Schost & A. Sedoglavic, Fast computation of power series solutions of systems of differential equations, in SODA’07, SIAM, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, New Orleans, Louisiana, 2007, p. 1012-1021  MR 2485252
[15.04] Joris van der Hoeven, “Newton’s method and FFT trading”, Journal of Symbolic Computation , To appear. Available at http://hal.archives-ouvertes.fr/hal-00434307/fr/  Zbl 1192.13017
[16.02] H. Alt, “Square rooting is as difficult as multiplication”, Computing 21 (1978/79) no. 3, p. 221-232  MR 620210 |  Zbl 0392.68037
[16.03] Jonathan M. Borwein & Bruno Salvy, “A proof of a recurrence for Bessel moments”, Experiment. Math. 17 (2008) no. 2, p. 223-230  MR 2433887 |  Zbl 1172.33309
[16.04] A. Bostan, F. Chyzak, Z. Li & B. Salvy, “Common multiples of linear ordinary differential and difference operators”, In preparation
[16.05] Alin Bostan, Frédéric Chyzak & Nicolas Le Roux, Products of ordinary differential operators by evaluation and interpolation, ISSAC’08, ACM, 2008, p. 23–30  MR 2500369
[16.09] R. P. Brent & J. F. Traub, “On the complexity of composition and generalized composition of power series”, SIAM Journal on Computing 9 (1980) no. 1, p. 54-66  MR 557825 |  Zbl 0447.68033
[16.11] H. T. Kung & D. M. Tong, “Fast algorithms for partial fraction decomposition”, SIAM J. Comput. 6 (1977) no. 3, p. 582-593  MR 495188 |  Zbl 0357.68036
[16.12] Joris van der Hoeven, “FFT-like multiplication of linear differential operators”, J. Symbolic Comput. 33 (2002) no. 1, p. 123-127  MR 1876315 |  Zbl 1006.16029
Copyright Cellule MathDoc 2017 | Crédit | Plan du site