Algorithmes rapides pour les polynômes, séries formelles et matrices

 Access to full text

 Full (PDF)

1. Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman, The design and analysis of computer algorithms, (1974), Addison-Wesley Publishing Co. Zbl0326.68005MR413592
2. 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), 333-356 Zbl1088.11064MR2175096
3. Peter Bürgisser, Michael Clausen, M. Amin Shokrollahi, Algebraic complexity theory, 315 (1997), Springer-Verlag, Berlin Zbl1087.68568
4. Keith O. Geddes, Stephen R. Czapor, George Labahn, Algorithms for Computer Algebra, (1992), Kluwer Academic Publishers Zbl0805.68072
5. Torbjörn Granlund, GNU Multiple Precision Arithmetic Library, (2006), http://swox.com/gmp 
6. Daniel Richardson, Some Undecidable Problems Involving Elementary Functions of a Real Variable, Journal of Symbolic Logic 33 (1968), 514-520 Zbl0175.27404MR239976
7. Daniel Richardson, How to recognize zero, Journal of Symbolic Computation 24 (1997), 627-645 Zbl0917.11062MR1487790
8. Joachim von zur Gathen, Jürgen Gerhard, Modern computer algebra, (1999), Cambridge University Press, New York Zbl0936.11069
9. D. J. Bernstein, Multidigit multiplication for mathematicians 
10. Marco Bodrato, Alberto Zanoni, Integer and polynomial multiplication : towards optimal Toom-Cook matrices, ISSAC’07 (2007), 17-24, ACM, New York Zbl1190.68084MR2396179
11. E. Oran Brigham, The fast Fourier transform, (1974), Prentice-Hall Zbl0375.65052
12. Peter Bürgisser, Martin Lotz, Lower bounds on the bounded coefficient complexity of bilinear maps, J. ACM 51 (2004), 464-482 Zbl1192.68312MR2145861
13. D. G. Cantor, E. Kaltofen, On Fast Multiplication of Polynomials over Arbitrary Algebras, Acta Informatica 28 (1991), 693-701 Zbl0766.68055MR1129288
14. M. Cenk, C. K. Koc, F. Ozbudak, Polynomial Multiplication over Finite Fields Using Field Extensions and Interpolation, ARITH ’09 (2009), 84-91, IEEE Computer Society 
15. Jaewook Chung, M. Anwar Hasan, Asymmetric Squaring Formulae, ARITH ’07 : Proc. of the 18th IEEE Symp. on Computer Arithmetic (2007), 113-122, IEEE 
16. S. Cook, On the minimum computation time of functions, (1966) 
17. S. A. Cook, S. O. Aanderaa, On the minimum computation time of functions, Transactions of the American Mathematical Society 142 (1969), 291-314 Zbl0188.33402MR249212
18. James W. Cooley, How the FFT gained acceptance, A history of scientific computing (Princeton, NJ, 1987) (1990), 133-140, ACM, New York MR1203104
19. James W. Cooley, John W. Tukey, An algorithm for the machine calculation of complex Fourier series, Mathematics of Computation 19 (1965), 297-301 Zbl0127.09002MR178586
20. James W. Cooley, John W. Tukey, On the Origin and Publication of the FFT Paper, Current Contents 33 (1993), 8-9 
21. A. De, P. P. Kurur, C. Saha, R. Saptharishi, Fast integer multiplication using modular arithmetic, STOC’08 (2008), 499-506, ACM, New York, NY, USA Zbl1231.68289MR2582908
22. J. Dongarra, F. Sullivan, Top ten algorithms, Computing in Science & Engineering 2 (2000), 22-23 
23. P. Duhamel, M. Vetterli, Fast Fourier transforms : a tutorial review and a state of the art, Signal Processing. An Interdisciplinary Journal 19 (1990), 259-299 Zbl0704.65106MR1048328
24. M. Frigo, S. G Johnson, The Design and Implementation of FFTW3, Proceedings of the IEEE 93 (2005), 216-231 
25. Martin Fürer, Faster integer multiplication, STOC’07—Proceedings of the 39th Annual ACM Symposium on Theory of Computing (2007), 57-66, ACM, New York Zbl1179.68198MR2402428
26. Martin Fürer, Faster integer multiplication, SIAM J. Comput. 39 (2009), 979-1005 Zbl1192.68926MR2538847
27. W. M. Gentleman, G. Sande, Fast Fourier Transforms : for fun and profit, AFIPS’66 (1966), 563-578, ACM, New York, NY, USA 
28. Guillaume Hanrot, Michel Quercia, Paul Zimmermann, The Middle Product Algorithm I, Appl. Algebra Engrg. Comm. Comput. 14 (2004), 415-438 Zbl1064.68094
29. Michael T. Heideman, Don H. Johnson, C. Sidney Burrus, Gauss and the history of the fast Fourier transform, Arch. Hist. Exact Sci. 34 (1985), 265-277 Zbl0577.01027MR815154
30. Michael Kaminski, A lower bound for polynomial multiplication, Theoret. Comput. Sci. 40 (1985), 319-322 Zbl0607.94010MR835422
31. A. Karatsuba, Y. Ofman, Multiplication of multidigit numbers on automata, Soviet Physics Doklady 7 (1963), 595-596 
32. Robert T. Moenck, Another polynomial homomorphism, Acta Informat. 6 (1976), 153-169 Zbl0312.68024MR408306
33. Peter L. Montgomery, Five, Six, and Seven-Term Karatsuba-Like Formulae, IEEE Trans. Comput. 54 (2005), 362-369 Zbl1171.11329
34. Jacques Morgenstern, Note on a lower bound of the linear complexity of the fast Fourier transform, J. Assoc. Comput. Mach. 20 (1973), 305-306 Zbl0258.65120MR331867
35. Thom Mulders, On Short Multiplications and Divisions, Applicable Algebra in Engineering, Communication and Computing 11 (2000), 69-88 Zbl0968.68200MR1817699
36. 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), 205-215 Zbl0524.65093MR563380
37. Henri J. Nussbaumer, Fast Fourier transform and convolution algorithms, 2 (1981), Springer-Verlag, Berlin Zbl0476.65097MR606376
38. M. S. Paterson, M. J. Fischer, A. R. Meyer, An improved overlap argument for on-line multiplication, Complexity of computation (1974), 97-111, AMS Zbl0301.68059MR423875
39. A. Schönhage, Schnelle Multiplikation von Polynomen über Körpern der Charakteristik 2, Acta Informat. 7 (1976/77), 395-398 Zbl0362.65011MR436663
40. A. Schönhage, V. Strassen, Schnelle Multiplikation großer Zahlen, Computing 7 (1971), 281-292 Zbl0223.68007MR292344
41. V. Strassen, The computational complexity of continued fractions, SIAM J. Comput. 12 (1983), 1-27 Zbl0543.68026
42. A. L. Toom, The complexity of a scheme of functional elements simulating the multiplication of integers, Doklady Akademii Nauk SSSR 150 (1963), 496-498 Zbl0203.15604MR156494
43. Joris van der Hoeven, The truncated Fourier transform and applications, ISSAC’04 (2004), 290-296, ACM, New York Zbl1064.65158MR2126956
44. Charles Van Loan, Computational frameworks for the fast Fourier transform, 10 (1992), SIAM, Philadelphia, PA Zbl0757.65154MR1153025
45. André Weimerskirch, Christof Paar, Generalizations of the Karatsuba Algorithm for Efficient Implementations, Eprint (2006) 
46. J. Abdeljaoued, H. Lombardi, Méthodes matricielles : introduction à la complexité algébrique, 42 (2004), Springer-Verlag, Berlin Zbl1087.65041MR2046056
47. W. Baur, V. Strassen, The complexity of partial derivatives, Theoretical Computer Science 22 (1983), 317-330 Zbl0498.68028MR693063
48. D. Bini, Relations between exact and approximate bilinear algorithms. Applications, Calcolo 17 (1980), 87-97 Zbl0459.65028MR605920
49. D. Bini, M. Capovani, F. Romani, G. Lotti, $O\left(n^{2.7799}\right)$ complexity for $n\times n$ approximate matrix multiplication, Inform. Process. Lett. 8 (1979), 234-235 Zbl0395.68048MR534068
50. Markus Bläser, A $\frac{5}{2}{n}^2$-lower bound for the multiplicative complexity of $n\times n$-matrix multiplication, STACS 2001 (Dresden) 2010 (2001), 99-109, Springer, Berlin Zbl0981.68710MR1890782
51. Markus Bläser, On the complexity of the multiplication of matrices of small formats, J. Complexity 19 (2003), 43-60 Zbl1026.68062MR1951322
52. A. Borodin, I. Munro, Evaluation of polynomials at many points, Information Processing Letters 1 (1971), 66-68 Zbl0226.65036
53. R. P. Brent, H. T. Kung, Fast algorithms for manipulating formal power series, Journal of the ACM 25 (1978), 581-595 Zbl0388.68052
54. James R. Bunch, John E. Hopcroft, Triangular factorization and inversion by fast matrix multiplication, Math. Comp. 28 (1974), 231-236 Zbl0276.15006MR331751
55. P. Bürgisser, M. Karpinski, T. Lickteig, Some computational problems in linear algebra as hard as matrix multiplication, Comput. Complexity 1 (1991), 131-155 Zbl0774.68056MR1134946
56. H. Cohn, R. Kleinberg, B. Szegedy, C. Umans, Group-theoretic Algorithms for Matrix Multiplication, FOCS’05 (2005), 379-388, IEEE Computer Society 
57. Henry Cohn, Christopher Umans, A Group-Theoretic Approach to Fast Matrix Multiplication, FOCS’03 (2003), IEEE Computer Society, Washington, DC, USA 
58. Don Coppersmith, Shmuel Winograd, Matrix multiplication via arithmetic progressions, J. Symbolic Comput. 9 (1990), 251-280 Zbl0702.65046MR1056627
59. A. M Danilevskii, The numerical solution of the secular equation, Matem. sbornik 44 (1937), 169-171 
60. 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) (1972), 31-40, Plenum, New York MR391577
61. P. C. Fischer, R. L. Probert, Efficient procedures for using matrix algorithms, Automata, languages and programming (1974), 413-427. LNCS, Vol. 14, Springer, Berlin Zbl0284.68039MR428786
62. Patrick C. Fischer, Further schemes for combining matrix algorithms, Automata, languages and programming (1974), 428-436. LNCS, Vol. 14, Springer, Berlin Zbl0284.68040MR428787
63. Mark Giesbrecht, Nearly optimal algorithms for canonical matrix forms, SIAM J. Comput. 24 (1995), 948-969 Zbl0839.65043MR1350753
64. Richard Harter, The optimality of Winograd’s formula, Commun. ACM 15 (1972) Zbl0232.65036MR314249
65. J. Hopcroft, J. Musinski, Duality applied to the complexity of matrix multiplication and other bilinear forms, SIAM Journal on Computing 2 (1973), 159-173 Zbl0294.65022MR471439
66. J. E. Hopcroft, L. R. Kerr, On minimizing the number of multiplications necessary for matrix multiplication, SIAM J. Appl. Math. 20 (1971), 30-36 Zbl0215.55501MR274293
67. S. Huss-Lederman, E. M. Jacobson, A. Tsao, T. Turnbull, J. R. Johnson, Implementation of Strassen’s algorithm for matrix multiplication, Supercomputing’96 (1996), IEEE Computer Society, Washington, DC, USA 
68. Joseph Ja’Ja’, On the complexity of bilinear forms with commutativity, STOC’79 (1979), 197-208, ACM, New York, NY, USA MR564631
69. I Kaporin, The aggregation and cancellation techniques as a practical tool for faster matrix multiplication, Theoretical Computer Science 315 (2004), 469-510 Zbl1057.65020MR2073062
70. Igor Kaporin, A practical algorithm for faster matrix multiplication, Numer. Linear Algebra Appl. 6 (1999), 687-700 Zbl0982.65048MR1736386
71. Walter Keller-Gehrig, Fast algorithms for the characteristic polynomial, Theoret. Comput. Sci. 36 (1985), 309-317 Zbl0565.68041
72. 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), 25-43 Zbl0159.20403
73. 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), 491-539 
74. Julian Laderman, Victor Pan, Xuan He Sha, On practical algorithms for accelerated matrix multiplication, Linear Algebra Appl. 162/164 (1992), 557-588 Zbl0748.65043MR1148417
75. Julian D. Laderman, A noncommutative algorithm for multiplying $3\times 3$ matrices using $23$ muliplications, Bull. Amer. Math. Soc. 82 (1976), 126-128 Zbl0322.65021MR395320
76. J. M. Landsberg, The border rank of the multiplication of $2\times 2$ matrices is seven, J. Amer. Math. Soc. 19 (2006), 447-459 Zbl1088.68069MR2188132
77. J. M. Landsberg, Geometry and the complexity of matrix multiplication, Bull. Amer. Math. Soc. (N.S.) 45 (2008), 247-284 Zbl1145.68054MR2383305
78. O. M. Makarov, An algorithm for multiplication of $3\times 3$ matrices, Zh. Vychisl. Mat. i Mat. Fiz. 26 (1986), 293-294, 320 Zbl0614.65036MR835700
79. I. Munro, Problems related to matrix multiplication, Proceedings Courant Institute Symposium on Computational Complexity, October 1971 (1973), 137-151, Algorithmics Press, New York 
80. V. Pan, Computation schemes for a product of matrices and for the inverse matrix, Uspehi Mat. Nauk 27 (1972), 249-250 Zbl0261.65025MR395194
81. V. Ya. Pan, Strassen’s algorithm is not optimal. Trilinear technique of aggregating, uniting and canceling for constructing fast algorithms for matrix operations, SFCS ’78 (1978), 166-176, IEEE Computer Society, Washington, DC, USA MR539838
82. V. Ya. Pan, New fast algorithms for matrix operations, SIAM J. Comput. 9 (1980), 321-342 Zbl0446.68034MR568817
83. V. Ya. Pan, New combinations of methods for the acceleration of matrix multiplication, Comput. Math. Appl. 7 (1981), 73-125 Zbl0465.68019MR593557
84. Victor Pan, How can we speed up matrix multiplication ?, SIAM Rev. 26 (1984), 393-415 Zbl0563.65028MR750457
85. Victor Pan, How to multiply matrices faster, 179 (1984), Springer-Verlag, Berlin Zbl0548.65022MR765701
86. M. S. Paterson, L. J. Stockmeyer, On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials, SIAM J. Comput. 2 (1973), 60-66 Zbl0262.65033MR314238
87. Clément Pernet, Arne Storjohann, Faster algorithms for the characteristic polynomial, ISSAC’07 (2007), 307-314, ACM, New York Zbl1190.68032MR2402276
88. Robert L. Probert, On the additive complexity of matrix multiplication, SIAM J. Comput. 5 (1976), 187-203 Zbl0328.65029MR408311
89. Ran Raz, On the complexity of matrix product, SIAM J. Comput. 32 (2003), 1356-1369 Zbl1026.68060MR2001277
90. A. Schönhage, Unitäre Transformationen grosser Matrizen, Numer. Math. 20 (1972/73), 409-417 Zbl0252.65031MR327019
91. A. Schönhage, Partial and total matrix multiplication, SIAM J. Comput. 10 (1981), 434-455 Zbl0462.68018MR623057
92. Warren D. Smith, Fast matrix multiplication formulae – report of the prospectors, (2002) 
93. Arne Storjohann, Deterministic computation of the Frobenius form (extended abstract), 42nd IEEE Symposium on Foundations of Computer Science (Las Vegas, NV, 2001) (2001), 368-377, IEEE Computer Soc., Los Alamitos, CA MR1948725
94. V. Strassen, Gaussian Elimination is Not Optimal, Numerische Mathematik 13 (1969), 354-356 Zbl0185.40101
95. V. Strassen, Relative bilinear complexity and matrix multiplication, J. Reine Angew. Math. 375/376 (1987), 406-443 Zbl0621.68026MR882307
96. Volker Strassen, Algebraic complexity theory, Handbook of theoretical computer science, Vol. A (1990), 633-672, Elsevier, Amsterdam Zbl0900.68247MR1127177
97. Ondrej Sýkora, A fast non-commutative algorithm for matrix multiplication, Mathematical foundations of computer science (Proc. Sixth Sympos., Tatranská Lomnica, 1977) (1977), 504-512. Lecture Notes in Comput. Sci., Vol. 53, Springer, Berlin Zbl0354.68068MR464684
98. L. G. Valiant, The complexity of computing the permanent, Theoret. Comput. Sci. 8 (1979), 189-201 Zbl0415.68008MR526203
99. Abraham Waksman, On Winograd’s algorithm for inner products, IEEE Trans. Comput. C-19 (1970), 360-361 Zbl0196.17104MR455534
100. S. Winograd, A new algorithm for inner-product, IEEE Transactions on Computers 17 (1968), 693-694 Zbl0174.46703
101. S. Winograd, On multiplication of $2\times 2$ matrices, Linear Algebra and Appl. 4 (1971), 381-388 Zbl0225.68018MR297115
102. Shmuel Winograd, On the number of multiplications necessary to compute certain functions, Comm. Pure Appl. Math. 23 (1970), 165-179 Zbl0191.15804MR260150
103. Shmuel Winograd, Some remarks on fast multiplication of polynomials, Complexity of sequential and parallel numerical algorithms (Proc. Sympos., Carnegie-Mellon Univ., Pittsburgh, Pa., 1973) (1973), 181-196, Academic Press, New York Zbl0273.65033MR375839
104. D. J. Bernstein, Removing redundancy in high-precision Newton iteration 
105. Daniel J. Bernstein, Composing power series over a finite ring in essentially linear time, Journal of Symbolic Computation 26 (1998), 339-341 Zbl0934.68129MR1633872
106. Daniel J. Bernstein, Fast multiplication and its applications, Algorithmic number theory : lattices, number fields, curves and cryptography 44 (2008), 325-384, Cambridge Univ. Press Zbl1208.68239MR2467550
107. Alin Bostan, Philippe Flajolet, Bruno Salvy, Éric Schost, Fast Computation of Special Resultants, Journal of Symbolic Computation 41 (2006), 1-29 Zbl1121.13037MR2194883
108. Alin Bostan, Bruno Salvy, Éric Schost, Power series composition and change of basis, ISSAC’08 (2008), 269-276, ACM, New York 
109. Richard P. Brent, Multiple-precision zero-finding methods and the complexity of elementary function evaluation, Analytic computational complexity (1976), 151-176, Academic Press, New York Zbl0342.65031MR423869
110. Guillaume Hanrot, Paul Zimmermann, Newton iteration revisited, Available at 
111. David Harvey, Faster algorithms for the square root and reciprocal of power series, Mathematics of Computation Zbl1217.65052
112. David Harvey, Faster exponentials of power series Zbl1217.65052
113. A. H. Karp, P. Markstein, High-precision division and square root, ACM Transactions on Mathematical Software 23 (1997), 561-589 Zbl0912.65038MR1671702
114. Kiran S. Kedlaya, Christopher Umans, Fast Modular Composition in any Characteristic, FOCS ’08 : Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science (2008), 146-155, IEEE Computer Society, Washington, DC, USA 
115. H. T. Kung, On computing reciprocals of power series, Numerische Mathematik 22 (1974), 341-348 Zbl0274.65009MR351045
116. 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), 251-326 
117. J. D. Lipson, Newton’s Method : A Great Algebraic Algorithm, Proceedings ACM Symposium of Symbolic and Algebraic Computation (1976), 260-270, ACM Press Zbl0454.65035
118. Isaac Newton, La méthode des fluxions, et les suites infinies, (1740), de Bure aîné 
119. P. Ritzmann, A fast numerical algorithm for the composition of power series with complex coefficients, Theoretical Computer Science 44 (1986), 1-16 Zbl0632.68039MR858688
120. A. Schönhage, The fundamental theorem of algebra in terms of computational complexity, (1982) 
121. G. Schulz, Iterative Berechnung der reziproken Matrix, Zeitschrift für angewandte Mathematik und Physik 13 (1933), 57-59 Zbl59.0535.04
122. M. Sieveking, An algorithm for division of powerseries, Computing 10 (1972), 153-156 Zbl0251.68023MR312701
123. Joris van der Hoeven, Relax, but don’t be too lazy, Journal of Symbolic Computation 34 (2002), 479-542 Zbl1011.68189MR1943041
124. Manindra Agrawal, Neeraj Kayal, Nitin Saxena, PRIMES is in P, Annals of Mathematics. Second Series 160 (2004), 781-793 Zbl1071.11070MR2123939
125. 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), 91-98 Zbl1007.93047MR1917474
126. 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), 67-108 Zbl0626.10008
127. Graham Everest, Alf van der Poorten, Igor Shparlinski, Thomas Ward, Recurrence sequences, 104 (2003), American Mathematical Society, Providence, RI Zbl1033.11006MR1990179
128. C. M. Fiduccia, An efficient formula for linear recurrences, SIAM Journal on Computing 14 (1985), 106-112 Zbl0561.68033MR774930
129. J. C. P. Miller, D. J. Spencer Brown, An algorithm for evaluation of remote terms in a linear recurrence sequence, Computer Journal 9 (1966), 188-190 Zbl0151.21101MR195240
130. R. T. Moenck, A. Borodin, Fast modular transforms via division, Thirteenth Annual IEEE Symposium on Switching and Automata Theory (1972), 90-96 
131. Peter L. Montgomery, Modular multiplication without trial division, Mathematics of Computation 44 (1985), 519-521 Zbl0559.10006MR777282
132. V. Shoup, A Fast Deterministic Algorithm for Factoring Polynomials over Finite Fields of Small Characteristic, ISSAC’91 (1991), 14-21, ACM Press Zbl0955.11500
133. V. Strassen, Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten, Numerische Mathematik 20 (1972/73), 238-251 Zbl0251.65036MR324947
134. A. J. van der Poorten, Some facts that should be better known, especially about rational functions, Number theory and applications (1989), 497-528, Kluwer, Dordrecht Zbl0687.10007
135. A. V. Aho, K. Steiglitz, J. D. Ullman, Evaluating polynomials at fixed sets of points, SIAM Journal on Computing 4 (1975), 533-539 Zbl0326.65027MR398151
136. L. I. Bluestein, A linear filtering approach to the computation of the discrete Fourier transform, IEEE Trans. Electroacoustics AU-18 (1970), 451-455 
137. A. Borodin, R. T. Moenck, Fast modular transforms, Comput. Sys. Sci. 8 (1974), 366-386 Zbl0302.68064MR371144
138. Alin Bostan, Grégoire Lecerf, Éric Schost, Tellegen’s principle into practice, ISSAC’03 (2003), 37-44, ACM Press Zbl1072.68649
139. Alin Bostan, Éric Schost, Polynomial evaluation and interpolation on special sets of points, Journal of Complexity 21 (2005), 420-446 Zbl1101.68039MR2152715
140. C. M. Fiduccia, Polynomial evaluation via the division algorithm : The fast Fourier transform revisited., 4th ACM Symposium on Theory of Computing (1972), 88-93 Zbl0346.42009
141. Harvey L. Garner, The residue number system, IRE-AIEE-ACM’59 Western joint computer conference (1959), 146-153, ACM, NY, USA 
142. Carl Friedrich Gauss, Disquisitiones arithmeticae, (1966), Yale University Press, New Haven, Conn. Zbl0136.32301MR197380
143. L. E. Heindel, E. Horowitz, On decreasing the computing time for modular arithmetic, 12th symposium on switching and automata theory (1971), 126-128, IEEE 
144. E. Horowitz, A fast Method for Interpolation Using Preconditioning, Information Processing Letters 1 (1972), 157-163 Zbl0297.65005MR315864
145. Russell M. Mersereau, An algorithm for performing an inverse chirp $z$-transform, IEEE Trans. Acoust. Speech Signal Processing ASSP-22 (1974), 387-388 MR413451
146. P. L. Montgomery, An FFT extension of the elliptic curve method of factorization, (1992) MR2688742
147. A. Ostrowski, On two problems in abstract algebra connected with Horner’s rule, Studies in mathematics and mechanics presented to Richard von Mises (1954), 40-48 Zbl0056.35204MR66030
148. V. Ya. Pan, Methods of computing values of polynomials, Russian Mathematical Surveys 21 (1966), 105-136 Zbl0173.17802
149. L. R. Rabiner, R. W. Schafer, C. M. Rader, The chirp $z$-transform algorithm and its application, Bell System Tech. J. 48 (1969), 1249-1292 MR243724
150. Victor Shoup, Roman Smolensky, Lower bounds for polynomial evaluation and interpolation problems, Computational Complexity 6 (1996/97), 301-311 Zbl0895.68075MR1613682
151. A. Svoboda, M. Valach, Operátorové obvody (Operational circuits), Stroje na Zpracování Informací (Information Processing Machines) 3 (1955), 247-295 MR96376
152. H. Takahasi, Y. Ishibashi, A new method for exact calculation by a digital computer, Information Processing in Japan (1961), 28-42 Zbl0121.12103
153. E. Waring, Problems concerning interpolations, Philosophical Transactions of the Royal Society of London 59 (1779), 59-67 
154. L. M. Berkovich, V. G. Tsirulik, Differential resultants and some of their applications, Differentsialnye Uravneniya 22 (1986), 750-757, 914 Zbl0611.34007MR846502
155. É. Bézout, Recherches sur le degré des équations résultantes de l’évanouissement des inconnues, Histoire de l’académie royale des science (1764), 288-338 
156. 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), 259-295 Zbl0475.65018
157. W. S. Brown, On Euclid’s algorithm and the computation of polynomial greatest common divisors, SYMSAC ’71 : Proceedings of the second ACM symposium on Symbolic and algebraic manipulation (1971), 195-211, ACM, New York, NY, USA 
158. W. S. Brown, J. F. Traub, On Euclid’s algorithm and the theory of subresultants, J. Assoc. Comput. Mach. 18 (1971), 505-514 Zbl0226.65041MR303684
159. Marc Chardin, Differential resultants and subresultants, Fundamentals of computation theory (Gosen, 1991) 529 (1991), 180-189, Springer, Berlin Zbl0925.12002MR1136080
160. G. E. Collins, Polynomial remainder sequences and determinants, Amer. Math. Monthly 73 (1966), 708-712 Zbl0147.29505MR199216
161. George E. Collins, Subresultants and reduced polynomial remainder sequences, J. Assoc. Comput. Mach. 14 (1967), 128-142 Zbl0152.35403MR215512
162. George E. Collins, The calculation of multivariate polynomial resultants, J. Assoc. Comput. Mach. 18 (1971), 515-532 Zbl0226.65042MR298921
163. D. Yu. Grigoriev, Complexity of factoring and calculating the GCD of linear ordinary differential operators, J. Symbolic Comput. 10 (1990), 7-37 Zbl0728.68067MR1081258
164. 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), 750-755 Zbl0416.65008MR549385
165. Hoon Hong, Ore principal subresultant coefficients in solutions, Appl. Algebra Engrg. Comm. Comput. 11 (2001), 227-237 Zbl1006.16030MR1815132
166. Hoon Hong, Ore subresultant coefficients in solutions, Appl. Algebra Engrg. Comm. Comput. 12 (2001), 421-428 Zbl1006.16031MR1864611
167. Donald E. Knuth, The analysis of algorithms, Actes du Congrès International des Mathématiciens (Nice, 1970), Tome 3 (1971), 269-274, Gauthier-Villars, Paris Zbl0279.68041MR423865
168. Donald E. Knuth, The Art of Computer Programming, 2 : Seminumerical Algorithms (1997), Addison-Wesley Publishing Co., Reading, Mass. Zbl0895.68055MR378456
169. Serge Lang, Algebra, 211 (2002), Springer-Verlag, New York Zbl0984.00001MR1878556
170. Alain Lascoux, Symmetric functions and combinatorial operators on polynomials, 99 (2003), Published for the Conference Board of the Mathematical Sciences, Washington, DC Zbl1039.05066MR2017492
171. D. H. Lehmer, Euclid’s Algorithm for Large Numbers, Amer. Math. Monthly 45 (1938), 227-233 MR1524250
172. Z. Li, I. Nemes, A modular algorithm for computing greatest common right divisors of Ore polynomials, ISSAC’97 (1997), 282-289, ACM, New York Zbl0927.16043MR1809996
173. Ziming Li, A subresultant theory for Ore polynomials with applications, ISSAC’98 (1998), 132-139, ACM, New York Zbl0922.16015MR1805177
174. Ziming Li, Greatest common right divisors, least common left multiples, and subresultants of Ore polynomials, Mathematics mechanization and applications (2000), 297-324, Academic Press, San Diego, CA MR1784030
175. R. T. Moenck, Fast computation of GCDs, Fifth Annual ACM Symposium on Theory of Computing (Austin, Tex., 1973) (1973), 142-151, Assoc. Comput. Mach., New York Zbl0306.68027MR455528
176. Niels Möller, On Schönhage’s algorithm and subquadratic integer GCD computation, Math. Comp. 77 (2008), 589-607 Zbl1165.11003MR2353968
177. V. Y. Pan, X. Wang, Acceleration of Euclidean algorithm and extensions, ISSAC’02 (2002), 207-213, ACM, New York Zbl1072.68691MR2035251
178. A. Schönhage, Schnelle Berechnung von Kettenbruchentwicklugen, Acta Inform. 1 (1971), 139-144 Zbl0223.68008
179. A. Schönhage, Probabilistic computation of integer polynomial GCDs, J. Algorithms 9 (1988), 365-371 Zbl0651.68045MR955145
180. J. T. Schwartz, Fast probabilistic algorithms for verification of polynomial identities, J. Assoc. Comput. Mach. 27 (1980), 701-717 Zbl0452.68050MR594695
181. D. Stehlé, P. Zimmermann, A binary recursive Gcd algorithm, ANTS-VI 3076 (2004), 411-425, Springer Zbl1125.11362MR2138011
182. V. Strassen, The computational complexity of continued fractions, SYMSAC’81 (1981), 51-67, ACM, New York, NY, USA Zbl0486.68029
183. 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 (1839), 40-53, Baker, H. F., New York 
184. James Joseph Sylvester, A method of determining by mere inspection the derivatives from two equations of any degree, Philos. Mag. 16 (1840), 132-135 
185. Joachim von zur Gathen, Jürgen Gerhard, Modern computer algebra, (2003), Cambridge University Press, New York Zbl1055.68168MR2001757
186. Joachim von zur Gathen, Thomas Lücking, Subresultants revisited, Theoret. Comput. Sci. 297 (2003), 199-239 Zbl1045.68168MR1981147
187. Chee Yap, Fundamental Problems in Algorithmic Algebra, (2000), Oxford Univ. Press Zbl0999.68261MR1740761
188. David Y.Y. Yun, On square-free decomposition algorithms, SYMSAC’76 (1976), 26-35, ACM, New York, NY, USA Zbl0498.13006
189. David Y.Y. Yun, On the equivalence of polynomial GCD and squarefree factorization problems, Proc. of the MACSYMA Users’ Conference (1977), 65-70 
190. Niels Henrik Abel, Œuvres complètes. Tome II, (1992), Éditions Jacques Gabay, Sceaux 
191. Handbook of mathematical functions with formulas, graphs, and mathematical tables, (1992), AbramowitzMiltonM., New York MR1225604
192. Alin Bostan, Algorithmique efficace pour des opérations de base en Calcul formel, (2003) 
193. Alin Bostan, Frédéric Chyzak, Grégoire Lecerf, Bruno Salvy, Éric Schost, Differential equations for algebraic functions, ISSAC’07 (2007), 25-32, ACM Press Zbl1190.68085MR2396180
194. L. Comtet, Analyse Combinatoire, (1970), PUF, Paris Zbl0221.05002
195. Philippe Flajolet, Bruno Salvy, The SIGSAM Challenges : Symbolic Asymptotics in Practice, SIGSAM Bulletin 31 (1997), 36-47 
196. Rev. Robert Harley, On the theory of the transcendental solution of algebraic equations, Quarterly Journal of Pure and Applied Mathematics 5 (1862), 337-360 
197. William A. Harris, Yasutaka Sibuya, The reciprocals of solutions of linear ordinary differential equations, Advances in Mathematics 58 (1985), 119-132 Zbl0581.12013MR814747
198. L. Lipshitz, $D$-Finite Power Series, Journal of Algebra 122 (1989), 353-373 Zbl0695.12018MR999079
199. 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), 163-177 Zbl0888.65010
200. Michael F. Singer, Algebraic relations among solutions of linear differential equations, Transactions of the American Mathematical Society 295 (1986), 753-763 Zbl0593.12014MR833707
201. N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, (2006) Zbl1274.11001
202. R. P. Stanley, Differentiably Finite Power Series, European Journal of Combinatorics 1 (1980), 175-188 Zbl0445.05012MR587530
203. Richard P. Stanley, Enumerative combinatorics, 2 (1999), Cambridge University Press Zbl0928.05001MR1676282
204. Jules Tannery, Propriétés des intégrales des équations différentielles linéaires à coefficients variables, (1874) 
205. George A. Baker, Peter Graves-Morris, Padé approximants, 59 (1996), Cambridge University Press, Cambridge Zbl0923.41001MR1383091
206. B. Beckermann, G. Labahn, A uniform approach for the fast computation of matrix-type Padé approximants, SIAM J. Matrix Anal. Appl. 15 (1994), 804-823 Zbl0805.65008MR1282696
207. Bernhard Beckermann, A reliable method for computing $M$-Padé approximants on arbitrary staircases, J. Comput. Appl. Math. 40 (1992), 19-42 Zbl0810.65014MR1167913
208. Bernhard Beckermann, George Labahn, Fraction-free computation of matrix rational interpolants and matrix GCDs, SIAM J. Matrix Anal. Appl. 22 (2000), 114-144 Zbl0973.65007MR1779720
209. S. Cabay, G. Labahn, A fast, reliable algorithm for calculating Padé-Hermite forms, ISSAC’89 (1989), 95-100, ACM, New York, NY, USA 
210. S. Cabay, G. Labahn, B. Beckermann, On the theory and computation of nonperfect Padé-Hermite approximants, J. Comput. Appl. Math. 39 (1992), 295-313 Zbl0810.65013MR1164293
211. Stanley Cabay, Dong Koo Choi, Algebraic computations of scaled Padé fractions, SIAM J. Comput. 15 (1986), 243-270 Zbl0633.30008MR822203
212. Unjeng Cheng, On the continued fraction and Berlekamp’s algorithm, IEEE Trans. Inform. Theory 30 (1984), 541-544 Zbl0552.94014MR751325
213. J. Della Dora, C. Dicrescenzo, Approximants de Padé-Hermite. I. Théorie, Numer. Math. 43 (1984), 23-39 Zbl0537.65013MR726360
214. J. Della Dora, C. Dicrescenzo, Approximants de Padé-Hermite. II. Programmation, Numer. Math. 43 (1984), 41-57 Zbl0537.65014MR726361
215. Harm Derksen, An algorithm to compute generalized Padé-Hermite forms, (1994) 
216. John D. Dixon, Exact solution of linear equations using $p$-adic expansions, Numer. Math. 40 (1982), 137-141 Zbl0492.65016
217. Jean-Louis Dornstetter, On the equivalence between Berlekamp’s and Euclid’s algorithms, IEEE Trans. Inform. Theory 33 (1987), 428-431 Zbl0633.94019MR885401
218. Pascal Giorgi, Claude-Pierre Jeannerod, Gilles Villard, On the complexity of polynomial matrix computations, ISSAC’03 (2003), 135-142, ACM, New York Zbl1072.68708
219. William B. Gragg, Fred G. Gustavson, Daniel D. Warner, David Y. Y. Yun, On fast computation of superdiagonal Padé fractions, Math. Programming Stud. (1982), 39-42 Zbl0501.65006MR656936
220. G. H. Hardy, E. M. Wright, An introduction to the theory of numbers, (2008), Oxford University Press, Oxford Zbl1159.11001MR2445243
221. C. Hermite, Extrait d’une lettre de Monsieur Ch. Hermite à Monsieur Paul Gordan, J. Reine Angew. Math. 78 (1873), 303-311 
222. C. Hermite, Sur la fonction exponentielle, C. R. Math. Acad. Sci. Paris 77 (1873), 18-24 
223. C. Hermite, Sur la généralisation des fractions continues algébriques, Ann. Math. 21 (1893), 289-308 Zbl25.0325.02
224. M. A. H. Khan, High-order differential approximants, J. Comput. Appl. Math. 149 (2002), 457-468 Zbl1013.65003MR1937295
225. K. Mahler, Perfect systems, Compositio Math. 19 (1968), 95-166 (1968) Zbl0168.31303MR239099
226. James L. Massey, Shift-register synthesis and $\mathrm{BCH}$ decoding, IEEE Trans. Information Theory IT-15 (1969), 122-127 Zbl0167.18101MR242556
227. Robert J. McEliece, James B. Shearer, A property of Euclid’s algorithm and an application to Padé approximation, SIAM J. Appl. Math. 34 (1978), 611-615 Zbl0384.10006MR491634
228. W. H. Mills, Continued fractions and linear recurrences, Math. Comp. 29 (1975), 173-180 Zbl0298.10021MR369276
229. H. Padé, Sur la Représentation Approchée d’une Fonction par des Fractions Rationelles, Ann. Sci. École Norm. Sup. 9 (1892), 3-93 
230. H. Padé, Sur la généralisation des fractions continues algébriques, J. Math. Pures Appl. 10 (1894), 291-330 
231. Victor Y. Pan, Xinmao Wang, On rational number reconstruction and approximation, SIAM J. Comput. 33 (2004), 502-503 Zbl1101.68997MR2048454
232. Stefan Paszkowski, Recurrence relations in Padé-Hermite approximation, J. Comput. Appl. Math. 19 (1987), 99-107 Zbl0624.41021MR901218
233. A. V. Sergeyev, A recursive algorithm for Padé-Hermite approximations, USSR Comput. Maths Math. Phys 26 (1986), 17-22 Zbl0621.65005
234. R. E. Shafer, On quadratic approximation, SIAM J. Numer. Anal. 11 (1974), 447-460 Zbl0253.65006MR358161
235. Y. Tourigny, Ph. G. Drazin, The asymptotic behaviour of algebraic approximants, R. Soc. Lond. Proc. Ser. A Math. Phys. Eng. Sci. 456 (2000), 1117-1137 Zbl0971.41007MR1809955
236. M. Van Barel, A. Bultheel, A general module-theoretic framework for vector M-Padé and matrix rational interpolation, Numer. Algorithms 3 (1992), 451-461 Zbl0780.41014MR1199391
237. Marc Van Barel, Adhemar Bultheel, The computation of nonperfect Padé-Hermite approximants, Numer. Algorithms 1 (1991), 285-304 Zbl0753.65013MR1135298
238. Xinmao Wang, Victor Y. Pan, Acceleration of Euclidean algorithm and rational number reconstruction, SIAM J. Comput. 32 (2003), 548-556 Zbl1031.68149MR1969404
239. L. R. Welch, R. A. Scholtz, Continued fractions and Berlekamp’s algorithm, IEEE Trans. Inform. Theory 25 (1979), 19-27 Zbl0388.94014MR514928
240. N. Zierler, Linear recurring sequences and error-correcting codes, Error Correcting Codes (Proc. Sympos. Math. Res. Center, Madison, Wis., 1968) (1968), 47-59, Wiley Zbl0181.22402MR249191
241. Don Coppersmith, Solving homogeneous linear equations over $\mathrm{GF}\left(2\right)$ via block Wiedemann algorithm, Math. Comp. 62 (1994), 333-350 Zbl0805.65046MR1192970
242. Richard A. DeMillo, Richard J. Lipton, A probabilistic remark on algebraic program testing, Inform. Process. Lett. 7 (1978), 193-195 Zbl0397.68011
243. M. Giesbrecht, A. Lobo, B. D. Saunders, Certifying inconsistency of sparse linear systems, Proceedings of the 1998 International Symposium on Symbolic and Algebraic Computation (Rostock) (1998), 113-119 (electronic), ACM, New York Zbl0919.65017MR1805174
244. Mark Giesbrecht, Fast computation of the Smith form of a sparse integer matrix, Comput. Complexity 10 (2001), 41-69 Zbl0992.65039MR1867308
245. 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) 539 (1991), 29-38, Springer, Berlin Zbl0778.65034MR1229306
246. Thom Mulders, Certified sparse linear system solving, J. Symbolic Comput. 38 (2004), 1343-1373 Zbl1137.65345MR2168719
247. E. Thomé, Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm, J. Symbolic Comput. 33 (2002), 757-775 Zbl1010.65024MR1919913
248. William J. Turner, A block Wiedemann rank algorithm, ISSAC’06 (2006), 332-339, ACM, New York MR2289139
249. G. Villard, Further analysis of Coppersmith’s block Wiedemann algorithm for the solution of sparse linear systems (extended abstract), ISSAC’97 (1997), 32-39, ACM, New York, NY, USA Zbl0917.65041
250. D. Wiedemann, Solving sparse linear equations over finite fields, IEEE Transactions on Information Theory IT-32 (1986), 54-62 Zbl0607.65015
251. Richard Zippel, Probabilistic algorithms for sparse polynomials, EUROSAM’79 72 (1979), 216-226, Springer, Berlin Zbl0418.68040MR575692
252. Robert R. Bitmead, Brian D. O. Anderson, Asymptotically fast solution of Toeplitz and related systems of linear equations, Linear Algebra Appl. 34 (1980), 103-116 Zbl0458.65018MR591427
253. Alin Bostan, Claude-Pierre Jeannerod, Éric Schost, Solving structured linear systems with large displacement rank, Theoret. Comput. Sci. 407 (2008), 155-181 Zbl1169.65023MR2463004
254. Jean-Paul Cardinal, On a property of Cauchy-like matrices, C. R. Acad. Sci. Paris Sér. I Math. 328 (1999), 1089-1093 Zbl0933.65025MR1696212
255. I. Gohberg, V. Olshevsky, Complexity of multiplication with vectors for structured matrices, Linear Algebra Appl. 202 (1994), 163-192 Zbl0803.65053MR1288487
256. I. C. Gohberg, A. A. Semencul, On the inversion of finite Toeplitz matrices and their continuous analogues (In Russian), Mat. Issled. 7 (1972), 201-223 Zbl0288.15004MR353038
257. Gene H. Golub, Charles F. Van Loan, Matrix computations, (1996), Johns Hopkins University Press, Baltimore, MD Zbl0865.65009MR1417720
258. T. Kailath, S. Y. Kung, M. Morf, Displacement ranks of a matrix, Bull. Amer. Math. Soc. (N.S.) 1 (1979), 769-773 Zbl0417.65015MR537629
259. Thomas Kailath, Sun Yuan Kung, Martin Morf, Displacement ranks of matrices and linear equations, J. Math. Anal. Appl. 68 (1979), 395-407 Zbl0433.15001MR533501
260. Erich Kaltofen, Asymptotically fast solution of Toeplitz-like singular linear systems, ISSAC’94 (1994), 297-304, ACM, New York, NY, USA Zbl0978.15500
261. Erich Kaltofen, Analysis of Coppersmith’s block Wiedemann algorithm for the parallel solution of sparse linear systems, Math. Comp. 64 (1995), 777-806 Zbl0828.65035MR1270621
262. Norman Levinson, The Wiener RMS (root mean square) error criterion in filter design and prediction, J. Math. Phys. Mass. Inst. Tech. 25 (1947), 261-278 MR19257
263. M. Morf, Doubling algorithms for Toeplitz and related equations, IEEE Conference on Acoustics, Speech, and Signal Processing (1980), 954-959 
264. Victor Pan, On computations with dense structured matrices, Math. Comp. 55 (1990), 179-190 Zbl0703.47022MR1023051
265. Victor Y. Pan, Structured matrices and polynomials, (2001), Birkhäuser Boston Inc., Boston, MA Zbl0996.65028MR1843842
266. Victor Y. Pan, Ailong Zheng, Superfast algorithms for Cauchy-like matrix computations and extensions, Linear Algebra Appl. 310 (2000), 83-108 Zbl0971.65024MR1753169
267. William F. Trench, An algorithm for the inversion of finite Toeplitz matrices, J. Soc. Indust. Appl. Math. 12 (1964), 515-522 Zbl0131.36002MR173681
268. A. Antoniou, Digital Filters : Analysis and Design, (1979), McGraw-Hill Book Co. 
269. M. Ben-Or, P. Tiwari, A deterministic algorithm for sparse multivariate polynomial interpolation, STOC’88 (1988), 301-309, ACM Press 
270. D. J. Bernstein, The transposition principle 
271. Leo I. Bluestein, A linear filtering approach to the computation of the discrete Fourier transform, IEEE Northeast Electronics Research and Engineering Meeting 10 (1968), 218-219 
272. J. L. Bordewijk, Inter-reciprocity applied to electrical networks, Appl. Sci. Res. B. 6 (1956), 1-74 Zbl0072.43203MR79954
273. A. Bostan, G. Lecerf, B. Salvy, É. Schost, B. Wiebelt, Complexity issues in bivariate polynomial factorization, ISSAC’04 (2004), 42-49, ACM, New York Zbl1134.68595MR2126923
274. A. Bostan, É. Schost, On the complexities of multipoint evaluation and interpolation, Theoret. Comput. Sci. 329 (2004), 223-235 Zbl1086.68150MR2103649
275. J. Canny, E. Kaltofen, L. Yagati, Solving systems of non-linear polynomial equations faster, ISSAC’89 (1989), 121-128, ACM Press 
276. Eleanor Chu, Alan George, Inside the FFT black box, (2000), CRC Press Zbl0935.65149MR1740143
277. A. Fettweis, A general theorem for signal-flow networks, with applications, Archiv für Elektronik und Übertragungstechnik 25 (1971), 557-561 
278. 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) (1972), 31-40, Plenum, New York MR391577
279. C. M. Fiduccia, On the algebraic complexity of matrix multiplication, (1973) 
280. J.-C. Gilbert, G. Le Vey, J. Masse, La différentiation automatique de fonctions représentées par des programmes, (1991) 
281. R. E. Kalman, On the General Theory of Control Systems, IRE Transactions on Automatic Control 4 (1959), 481-491 
282. E. Kaltofen, R. M. Corless, D. J. Jeffrey, Challenges of symbolic computation : my favorite open problems, Journal of Symbolic Computation 29 (2000), 891-919 Zbl0963.68234MR1765929
283. 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 673 (1993), 195-212, Springer, Berlin Zbl0801.65024MR1251979
284. Erich Kaltofen, Computational differentiation and algebraic complexity theory, Workshop Report on First Theory Institute on Computational Differentiation (1993), 28-30 
285. M. Kaminski, D. G. Kirkpatrick, N. H. Bshouty, Addition requirements for matrix and transposed matrix products, Journal of Algorithms 9 (1988), 354-364 Zbl0653.65032MR955144
286. Donald E. Knuth, Christos H. Papadimitriou, Duality in addition chains, Bulletin of the European Association for Theoretical Computer Science 13 (1981), 2-4 
287. G. Lecerf, É. Schost, Fast Multivariate Power Series Multiplication in Characteristic Zero, SADIO Electronic Journal on Informatics and Operations Research 5 (2003), 1-10 Zbl1209.68618
288. P. Penfield, R. Spence, S. Duinker, Tellegen’s theorem and electrical networks, (1970), The M.I.T. Press, Cambridge, Mass.-London MR282747
289. Steven Roman, The umbral calculus, 111 (1984), Academic Press Inc. [Harcourt Brace Jovanovich Publishers], New York Zbl0536.33001MR741185
290. V. Shoup, A new polynomial factorization algorithm and its implementation, Journal of Symbolic Computation 20 (1995), 363-397 Zbl0854.11074MR1384454
291. V. Shoup, Efficient computation of minimal polynomials in algebraic extensions of finite fields, ISSAC’99 (1999), 53-58, ACM Press, New York MR1802067
292. Victor Shoup, Fast construction of irreducible polynomials over finite fields, J. Symbolic Comput. 17 (1994), 371-391 Zbl0815.11059MR1289997
293. B. Tellegen, A general network theorem, with applications, Philips Research Reports 7 (1952), 259-269 Zbl0049.42301MR51142
294. R. Zippel, Interpolating polynomials from their values, Journal of Symbolic Computation 9 (1990), 375-403 Zbl0702.65011MR1056633
295. Michael Beeler, R. Gosper, Richard Schroeppel, HAKMEM, (1972), MIT 
296. Peter B. Borwein, On the complexity of calculating factorials, Journal of Algorithms 6 (1985), 376-380 Zbl0576.68027MR800727
297. A. Bostan, F. Chyzak, T. Cluzeau, B. Salvy, Low complexity algorithms for linear recurrences, ISSAC’06 (2006), 31-38, ACM, New York MR2289098
298. Alin Bostan, Thomas Cluzeau, Bruno Salvy, Fast Algorithms for Polynomial Solutions of Linear Differential Equations, ISSAC’05 (2005), 45-52, ACM Press, NY Zbl06459429MR2280528
299. 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), 1777-1806 Zbl1210.11126MR2299425
300. 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) (1976), 151-176, Academic Press, New York Zbl0342.65031MR423869
301. D. V. Chudnovsky, G. V. Chudnovsky, Approximations and complex multiplication according to Ramanujan, Ramanujan revisited (1988), 375-472, Academic Press, MA Zbl0647.10002MR938975
302. P. Kogge, H. Stone, A parallel algorithm for the efficient solution of a general class of recurrence equations, IEEE Trans. Comp. C-22 (1973), 786-793 Zbl0262.68015MR395307
303. V. Strassen, Einige Resultate über Berechnungskomplexität, Jber. Deutsch. Math.-Verein. 78 (1976/77), 1-8 Zbl0361.68070MR438807
304. Claude-Pierre Jeannerod, Gilles Villard, Essentially optimal computation of the inverse of generic polynomial matrices, J. Complexity 21 (2005), 72-86 Zbl1101.68956MR2112743
305. Robert T. Moenck, John H. Carter, Approximate algorithms to derive exact solutions to systems of linear equations, EUROSAM ’79 : Proceedings of the International Symposiumon on Symbolic and Algebraic Computation 72 (1979), 65-73, Springer-Verlag, London, UK Zbl0435.65023MR575681
306. Arne Storjohann, High-Order Lifting, ISSAC’02 (2002), 246-254, ACM Press Zbl1072.68698
307. Arne Storjohann, High-order lifting and integrality certification, J. Symbolic Comput. 36 (2003), 613-648 Zbl1059.15020MR2004044
308. Arne Storjohann, The shifted number system for fast linear algebra on integer matrices, J. Complexity 21 (2005), 609-650 Zbl1101.68045MR2152725
309. Arne Storjohann, Gilles Villard, Computing the rank and a small nullspace basis of a polynomial matrix, ISSAC’05 (2005), 309-316, ACM, New York Zbl06459463MR2280562
310. A. Bostan, F. Chyzak, F. Ollivier, B. Salvy, É. Schost, A. Sedoglavic, Fast computation of power series solutions of systems of differential equations, SODA’07 (2007), 1012-1021, SIAM Zbl1302.65180MR2485252
311. Joris van der Hoeven, Newton’s method and FFT trading, Journal of Symbolic Computation Zbl1192.13017
312. H. Alt, Square rooting is as difficult as multiplication, Computing 21 (1978/79), 221-232 Zbl0392.68037MR620210
313. Jonathan M. Borwein, Bruno Salvy, A proof of a recurrence for Bessel moments, Experiment. Math. 17 (2008), 223-230 Zbl1172.33309MR2433887
314. A. Bostan, F. Chyzak, Z. Li, B. Salvy, Common multiples of linear ordinary differential and difference operators Zbl1308.68161
315. Alin Bostan, Frédéric Chyzak, Nicolas Le Roux, Products of ordinary differential operators by evaluation and interpolation, ISSAC’08 (2008), 23-30, ACM, New York Zbl1297.65050MR2500369
316. R. P. Brent, J. F. Traub, On the complexity of composition and generalized composition of power series, SIAM Journal on Computing 9 (1980), 54-66 Zbl0447.68033MR557825
317. H. T. Kung, D. M. Tong, Fast algorithms for partial fraction decomposition, SIAM J. Comput. 6 (1977), 582-593 Zbl0357.68036MR495188
318. Joris van der Hoeven, FFT-like multiplication of linear differential operators, J. Symbolic Comput. 33 (2002), 123-127 Zbl1006.16029MR1876315

1. Grégoire Lecerf, Factorisation des polynômes à plusieurs variables