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

Alin Bostan

doi:10.5802/ccirm.9

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

Alin Bostan

Les cours du CIRM, Tome 1 (2010) no. 2, pp. 75-262.

Publié le : 2010-08-30

DOI : 10.5802/ccirm.9

@article{CCIRM_2010__1_2_75_0,
     author = {Alin Bostan},
     title = {Algorithmes rapides pour les polyn\^omes,  s\'eries formelles et matrices},
     journal = {Les cours du CIRM},
     pages = {75--262},
     publisher = {CIRM},
     volume = {1},
     number = {2},
     year = {2010},
     doi = {10.5802/ccirm.9},
     language = {fr},
     url = {https://ccirm.centre-mersenne.org/articles/10.5802/ccirm.9/}
}

TY  - JOUR
AU  - Alin Bostan
TI  - Algorithmes rapides pour les polynômes,  séries formelles et matrices
JO  - Les cours du CIRM
PY  - 2010
SP  - 75
EP  - 262
VL  - 1
IS  - 2
PB  - CIRM
UR  - https://ccirm.centre-mersenne.org/articles/10.5802/ccirm.9/
DO  - 10.5802/ccirm.9
LA  - fr
ID  - CCIRM_2010__1_2_75_0
ER  -

%0 Journal Article
%A Alin Bostan
%T Algorithmes rapides pour les polynômes,  séries formelles et matrices
%J Les cours du CIRM
%D 2010
%P 75-262
%V 1
%N 2
%I CIRM
%U https://ccirm.centre-mersenne.org/articles/10.5802/ccirm.9/
%R 10.5802/ccirm.9
%G fr
%F CCIRM_2010__1_2_75_0

Alin Bostan. Algorithmes rapides pour les polynômes,  séries formelles et matrices. Les cours du CIRM, Tome 1 (2010) no. 2, pp. 75-262. doi : 10.5802/ccirm.9. https://ccirm.centre-mersenne.org/articles/10.5802/ccirm.9/

Bibliographie
Cité par

[01.01] Alfred V. Aho; John E. Hopcroft; Jeffrey D. Ullman The design and analysis of computer algorithms, Addison-Wesley Publishing Co., 1974 | Zbl

[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, Volume 1 (2005) no. 3, pp. 333-356 | MR | Zbl

[01.03, 03.11] Peter Bürgisser; Michael Clausen; M. Amin Shokrollahi Algebraic complexity theory, Grundlehren Math. Wiss., 315, Springer-Verlag, Berlin, 1997 | MR | Zbl

[01.04, 07.10] Keith O. Geddes; Stephen R. Czapor; George Labahn Algorithms for Computer Algebra, Kluwer Academic Publishers, 1992 | Zbl

[01.05] Torbjörn Granlund GNU Multiple Precision Arithmetic Library (2006) http://swox.com/gmp

[01.06] Daniel Richardson Some Undecidable Problems Involving Elementary Functions of a Real Variable, Journal of Symbolic Logic, Volume 33 (1968) no. 4, pp. 514-520 | DOI | MR | Zbl

[01.07] Daniel Richardson How to recognize zero, Journal of Symbolic Computation, Volume 24 (1997) no. 6, pp. 627-645 | DOI | MR | Zbl

[01.08, 12.35] Joachim von zur Gathen; Jürgen Gerhard Modern computer algebra, Cambridge University Press, New York, 1999 | Zbl

[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, New York, 2007, pp. 17-24 | DOI | Zbl

[02.03] E. Oran Brigham The fast Fourier transform, Prentice-Hall, 1974 | Zbl

[02.04] Peter Bürgisser; Martin Lotz Lower bounds on the bounded coefficient complexity of bilinear maps, J. ACM, Volume 51 (2004) no. 3, pp. 464-482 | DOI | MR | Zbl

[02.05] D. G. Cantor; E. Kaltofen On Fast Multiplication of Polynomials over Arbitrary Algebras, Acta Informatica, Volume 28 (1991) no. 7, pp. 693-701 | DOI | MR | Zbl

[02.06] M. Cenk; C. K. Koc; F. Ozbudak Polynomial Multiplication over Finite Fields Using Field Extensions and Interpolation, ARITH ’09 (2009), pp. 84-91 | DOI

[02.07] Jaewook Chung; M. Anwar Hasan Asymmetric Squaring Formulae, ARITH ’07 : Proc. of the 18th IEEE Symp. on Computer Arithmetic (2007), pp. 113-122 | DOI

[02.08] S. Cook On the minimum computation time of functions, Harvard University (1966) (Ph. D. Thesis)

[02.09] S. A. Cook; S. O. Aanderaa On the minimum computation time of functions, Transactions of the American Mathematical Society, Volume 142 (1969), pp. 291-314 | DOI | MR | Zbl

[02.10] James W. Cooley How the FFT gained acceptance, A history of scientific computing (Princeton, NJ, 1987) (ACM Press Hist. Ser.), ACM, New York, 1990, pp. 133-140 | MR

[02.11] James W. Cooley; John W. Tukey An algorithm for the machine calculation of complex Fourier series, Mathematics of Computation, Volume 19 (1965), pp. 297-301 | DOI | MR | Zbl

[02.12] James W. Cooley; John W. Tukey On the Origin and Publication of the FFT Paper, Current Contents, Volume 33 (1993) no. 51–52, pp. 8-9 http://www.garfield.library.upenn.edu/classics1993/A1993MJ84500001.pdf

[02.13] A. De; P. P. Kurur; C. Saha; R. Saptharishi Fast integer multiplication using modular arithmetic, STOC’08 (2008), pp. 499-506 | DOI | Zbl

[02.14] J. Dongarra; F. Sullivan Top ten algorithms, Computing in Science & Engineering, Volume 2 (2000) no. 1, pp. 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, Volume 19 (1990) no. 4, pp. 259-299 | DOI | MR | Zbl

[02.16] M. Frigo; S. G Johnson The Design and Implementation of FFTW3, Proceedings of the IEEE, Volume 93 (2005) no. 2, pp. 216-231

[02.17] Martin Fürer Faster integer multiplication, STOC’07—Proceedings of the 39th Annual ACM Symposium on Theory of Computing, ACM, New York, 2007, pp. 57-66 | DOI | Zbl

[02.18] Martin Fürer Faster integer multiplication, SIAM J. Comput., Volume 39 (2009) no. 3, pp. 979-1005 | DOI | MR | Zbl

[02.19] W. M. Gentleman; G. Sande Fast Fourier Transforms : for fun and profit, AFIPS’66 (1966), pp. 563-578 | DOI

[02.20, 12.18, 15.03] Guillaume Hanrot; Michel Quercia; Paul Zimmermann The Middle Product Algorithm I, Appl. Algebra Engrg. Comm. Comput., Volume 14 (2004) no. 6, pp. 415-438 | DOI | MR | Zbl

[02.21] Michael T. Heideman; Don H. Johnson; C. Sidney Burrus Gauss and the history of the fast Fourier transform, Arch. Hist. Exact Sci., Volume 34 (1985) no. 3, pp. 265-277 | DOI | MR | Zbl

[02.22] Michael Kaminski A lower bound for polynomial multiplication, Theoret. Comput. Sci., Volume 40 (1985) no. 2-3, pp. 319-322 | DOI | MR | Zbl

[02.23] A. Karatsuba; Y. Ofman Multiplication of multidigit numbers on automata, Soviet Physics Doklady, Volume 7 (1963), pp. 595-596

[02.24] Robert T. Moenck Another polynomial homomorphism, Acta Informat., Volume 6 (1976) no. 2, pp. 153-169 | MR | Zbl

[02.25] Peter L. Montgomery Five, Six, and Seven-Term Karatsuba-Like Formulae, IEEE Trans. Comput., Volume 54 (2005) no. 3, pp. 362-369 | DOI | Zbl

[02.26] Jacques Morgenstern Note on a lower bound of the linear complexity of the fast Fourier transform, J. Assoc. Comput. Mach., Volume 20 (1973), pp. 305-306 | DOI | MR | Zbl

[02.27] Thom Mulders On Short Multiplications and Divisions, Applicable Algebra in Engineering, Communication and Computing, Volume 11 (2000) no. 1, pp. 69-88 | DOI | MR | Zbl

[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, Volume 28 (1980) no. 2, pp. 205-215 | MR | Zbl

[02.29] Henri J. Nussbaumer Fast Fourier transform and convolution algorithms, Springer Series in Information Sciences, 2, Springer-Verlag, Berlin, 1981 | MR | Zbl

[02.30] M. S. Paterson; M. J. Fischer; A. R. Meyer An improved overlap argument for on-line multiplication, Complexity of computation, AMS, 1974, pp. 97-111 | Zbl

[02.31] A. Schönhage Schnelle Multiplikation von Polynomen über Körpern der Charakteristik 2, Acta Informat., Volume 7 (1976/77) no. 4, pp. 395-398 | Zbl

[02.32] A. Schönhage; V. Strassen Schnelle Multiplikation großer Zahlen, Computing, Volume 7 (1971), pp. 281-292 | DOI | Zbl

[02.33, 07.31] V. Strassen The computational complexity of continued fractions, SIAM J. Comput., Volume 12 (1983) no. 1, pp. 1-27 | DOI | MR | Zbl

[02.34] A. L. Toom The complexity of a scheme of functional elements simulating the multiplication of integers, Doklady Akademii Nauk SSSR, Volume 150 (1963), pp. 496-498 | MR | Zbl

[02.35] Joris van der Hoeven The truncated Fourier transform and applications, ISSAC’04, ACM, New York, 2004, pp. 290-296 | MR | Zbl

[02.36] Charles Van Loan Computational frameworks for the fast Fourier transform, Frontiers in Applied Mathematics, 10, SIAM, Philadelphia, PA, 1992 | MR | Zbl

[02.37] André Weimerskirch; Christof Paar Generalizations of the Karatsuba Algorithm for Efficient Implementations, Eprint, 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 | Zbl

[03.02, 12.02] W. Baur; V. Strassen The complexity of partial derivatives, Theoretical Computer Science, Volume 22 (1983), pp. 317-330 | DOI | MR | Zbl

[03.03] D. Bini Relations between exact and approximate bilinear algorithms. Applications, Calcolo, Volume 17 (1980) no. 1, pp. 87-97 | DOI | MR | Zbl

[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., Volume 8 (1979) no. 5, pp. 234-235 | Zbl

[03.05] Markus Bläser A $\frac{5}{2} n^{2}$ -lower bound for the multiplicative complexity of $n \times n$ -matrix multiplication, STACS 2001 (Dresden) (Lecture Notes in Comput. Sci.), Volume 2010, Springer, Berlin, 2001, pp. 99-109 | DOI | MR | Zbl

[03.06] Markus Bläser On the complexity of the multiplication of matrices of small formats, J. Complexity, Volume 19 (2003) no. 1, pp. 43-60 | DOI | MR | Zbl

[03.07, 06.04] A. Borodin; I. Munro Evaluation of polynomials at many points, Information Processing Letters, Volume 1 (1971) no. 2, pp. 66-68 | DOI | Zbl

[03.08, 04.06, 15.02] R. P. Brent; H. T. Kung Fast algorithms for manipulating formal power series, Journal of the ACM, Volume 25 (1978) no. 4, pp. 581-595 | DOI | MR | Zbl

[03.09] James R. Bunch; John E. Hopcroft Triangular factorization and inversion by fast matrix multiplication, Math. Comp., Volume 28 (1974), pp. 231-236 | DOI | MR | Zbl

[03.10] P. Bürgisser; M. Karpinski; T. Lickteig Some computational problems in linear algebra as hard as matrix multiplication, Comput. Complexity, Volume 1 (1991) no. 2, pp. 131-155 | DOI | MR | Zbl

[03.12] H. Cohn; R. Kleinberg; B. Szegedy; C. Umans Group-theoretic Algorithms for Matrix Multiplication, FOCS’05 (2005), pp. 379-388 | DOI

[03.13] Henry Cohn; Christopher Umans A Group-Theoretic Approach to Fast Matrix Multiplication, FOCS’03 (2003), 438 pages | Zbl

[03.14] Don Coppersmith; Shmuel Winograd Matrix multiplication via arithmetic progressions, J. Symbolic Comput., Volume 9 (1990) no. 3, pp. 251-280 | DOI | MR | Zbl

[03.15] A. M Danilevskii The numerical solution of the secular equation, Matem. sbornik, Volume 44 (1937) no. 2, pp. 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, New York, 1972, pp. 31-40 | MR | Zbl

[03.17] P. C. Fischer; R. L. Probert Efficient procedures for using matrix algorithms, Automata, languages and programming, Springer, Berlin, 1974, p. 413-427. LNCS, Vol. 14 | Zbl

[03.18] Patrick C. Fischer Further schemes for combining matrix algorithms, Automata, languages and programming, Springer, Berlin, 1974, p. 428-436. LNCS, Vol. 14 | MR | Zbl

[03.19] Mark Giesbrecht Nearly optimal algorithms for canonical matrix forms, SIAM J. Comput., Volume 24 (1995) no. 5, pp. 948-969 | DOI | MR | Zbl

[03.20] Richard Harter The optimality of Winograd’s formula, Commun. ACM, Volume 15 (1972) no. 5, 352 pages | DOI | MR | Zbl

[03.21, 12.19] J. Hopcroft; J. Musinski Duality applied to the complexity of matrix multiplication and other bilinear forms, SIAM Journal on Computing, Volume 2 (1973), pp. 159-173 | DOI | MR | Zbl

[03.22] J. E. Hopcroft; L. R. Kerr On minimizing the number of multiplications necessary for matrix multiplication, SIAM J. Appl. Math., Volume 20 (1971), pp. 30-36 | DOI | MR | Zbl

[03.23] S. Huss-Lederman; E. M. Jacobson; A. Tsao; T. Turnbull; J. R. Johnson Implementation of Strassen’s algorithm for matrix multiplication, Supercomputing’96 (1996) (32 pp.) | DOI

[03.24] Joseph Ja’Ja’ On the complexity of bilinear forms with commutativity, STOC’79 (1979), pp. 197-208 | DOI | MR | Zbl

[03.25] I Kaporin The aggregation and cancellation techniques as a practical tool for faster matrix multiplication, Theoretical Computer Science, Volume 315 (2004) no. 2-3, pp. 469-510 | DOI | MR | Zbl

[03.26] Igor Kaporin A practical algorithm for faster matrix multiplication, Numer. Linear Algebra Appl., Volume 6 (1999) no. 8, pp. 687-700 | DOI | MR | Zbl

[03.27, 16.10] Walter Keller-Gehrig Fast algorithms for the characteristic polynomial, Theoret. Comput. Sci., Volume 36 (1985) no. 2-3, pp. 309-317 | DOI | MR | Zbl

[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, Volume 5 (1965), pp. 25-43 | DOI | Zbl

[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, Volume 7 (1931) no. 4, pp. 491-539 (in Russian)

[03.30] Julian Laderman; Victor Pan; Xuan He Sha On practical algorithms for accelerated matrix multiplication, Linear Algebra Appl., Volume 162/164 (1992), pp. 557-588 | DOI | MR | Zbl

[03.31] Julian D. Laderman A noncommutative algorithm for multiplying $3 \times 3$ matrices using $23$ muliplications, Bull. Amer. Math. Soc., Volume 82 (1976) no. 1, pp. 126-128 | DOI | MR | Zbl

[03.32] J. M. Landsberg The border rank of the multiplication of $2 \times 2$ matrices is seven, J. Amer. Math. Soc., Volume 19 (2006) no. 2, pp. 447-459 | DOI | Zbl

[03.33] J. M. Landsberg Geometry and the complexity of matrix multiplication, Bull. Amer. Math. Soc. (N.S.), Volume 45 (2008) no. 2, pp. 247-284 | DOI | MR | Zbl

[03.34] O. M. Makarov An algorithm for multiplication of $3 \times 3$ matrices, Zh. Vychisl. Mat. i Mat. Fiz., Volume 26 (1986) no. 2, p. 293-294, 320 | MR

[03.35] I. Munro Problems related to matrix multiplication, Proceedings Courant Institute Symposium on Computational Complexity, October 1971 (1973), pp. 137-151

[03.36] V. Pan Computation schemes for a product of matrices and for the inverse matrix, Uspehi Mat. Nauk, Volume 27 (1972) no. 5(167), pp. 249-250 | MR

[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, SFCS ’78 (1978), pp. 166-176 | DOI | MR

[03.38] V. Ya. Pan New fast algorithms for matrix operations, SIAM J. Comput., Volume 9 (1980) no. 2, pp. 321-342 | DOI | MR | Zbl

[03.39] V. Ya. Pan New combinations of methods for the acceleration of matrix multiplication, Comput. Math. Appl., Volume 7 (1981) no. 1, pp. 73-125 | MR | Zbl

[03.40] Victor Pan How can we speed up matrix multiplication ?, SIAM Rev., Volume 26 (1984) no. 3, pp. 393-415 | MR | Zbl

[03.41] Victor Pan How to multiply matrices faster, Lecture Notes in Computer Science, 179, Springer-Verlag, Berlin, 1984 | MR | Zbl

[03.42, 04.17] M. S. Paterson; L. J. Stockmeyer On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials, SIAM J. Comput., Volume 2 (1973) no. 1, pp. 60-66 | DOI | MR | Zbl

[03.43] Clément Pernet; Arne Storjohann Faster algorithms for the characteristic polynomial, ISSAC’07, ACM, New York, 2007, pp. 307-314 | Zbl

[03.44] Robert L. Probert On the additive complexity of matrix multiplication, SIAM J. Comput., Volume 5 (1976) no. 2, pp. 187-203 | DOI | MR | Zbl

[03.45] Ran Raz On the complexity of matrix product, SIAM J. Comput., Volume 32 (2003) no. 5, pp. 1356-1369 | DOI | MR | Zbl

[03.46] A. Schönhage Unitäre Transformationen grosser Matrizen, Numer. Math., Volume 20 (1972/73), pp. 409-417 | DOI | Zbl

[03.47] A. Schönhage Partial and total matrix multiplication, SIAM J. Comput., Volume 10 (1981) no. 3, pp. 434-455 | DOI | MR | Zbl

[03.48] Warren D. Smith Fast matrix multiplication formulae – report of the prospectors (2002) (Preprint, available at http://www.math.temple.edu/~wds/prospector.pdf)

[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, pp. 368-377 | DOI | MR

[03.50, 06.19] V. Strassen Gaussian Elimination is Not Optimal, Numerische Mathematik, Volume 13 (1969), pp. 354-356 | DOI | MR | Zbl

[03.51] V. Strassen Relative bilinear complexity and matrix multiplication, J. Reine Angew. Math., Volume 375/376 (1987), pp. 406-443 | MR | Zbl

[03.52] Volker Strassen Algebraic complexity theory, Handbook of theoretical computer science, Vol. A, Elsevier, Amsterdam, 1990, pp. 633-672 | MR | Zbl

[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, Berlin, 1977, p. 504-512. Lecture Notes in Comput. Sci., Vol. 53 | DOI | Zbl

[03.54] L. G. Valiant The complexity of computing the permanent, Theoret. Comput. Sci., Volume 8 (1979) no. 2, pp. 189-201 | MR | Zbl

[03.55] Abraham Waksman On Winograd’s algorithm for inner products, IEEE Trans. Comput., Volume C-19 (1970) no. 4, pp. 360-361 | DOI | MR | Zbl

[03.56] S. Winograd A new algorithm for inner-product, IEEE Transactions on Computers, Volume 17 (1968), pp. 693-694 | DOI | Zbl

[03.57] S. Winograd On multiplication of $2 \times 2$ matrices, Linear Algebra and Appl., Volume 4 (1971), pp. 381-388 | DOI | MR | Zbl

[03.58] Shmuel Winograd On the number of multiplications necessary to compute certain functions, Comm. Pure Appl. Math., Volume 23 (1970), pp. 165-179 | DOI | MR | Zbl

[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, New York, 1973, pp. 181-196 | MR | Zbl

[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, Volume 26 (1998) no. 3, pp. 339-341 | MR | Zbl

[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.), Volume 44, Cambridge Univ. Press, 2008, pp. 325-384 | MR | Zbl

[04.04, 16.06] Alin Bostan; Philippe Flajolet; Bruno Salvy; Éric Schost Fast Computation of Special Resultants, Journal of Symbolic Computation, Volume 41 (2006) no. 1, pp. 1-29 | DOI | MR | Zbl

[04.05, 12.10] Alin Bostan; Bruno Salvy; Éric Schost Power series composition and change of basis, ISSAC’08, ACM, New York, 2008, pp. 269-276 | Zbl

[04.07] Richard P. Brent Multiple-precision zero-finding methods and the complexity of elementary function evaluation, Analytic computational complexity, Academic Press, New York, 1976, pp. 151-176 (Proceedings of a Symposium held at Carnegie-Mellon University, Pittsburgh, Pa., 1975) | DOI | Zbl

[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/) | MR | Zbl

[04.10] David Harvey Faster exponentials of power series (Preprint, available from http://arxiv.org/abs/0911.3110) | Zbl

[04.11] A. H. Karp; P. Markstein High-precision division and square root, ACM Transactions on Mathematical Software, Volume 23 (1997) no. 4, pp. 561-589 | DOI | MR | Zbl

[04.12] 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), pp. 146-155 | DOI | Zbl

[04.13] H. T. Kung On computing reciprocals of power series, Numerische Mathematik, Volume 22 (1974), pp. 341-348 | DOI | MR | Zbl

[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, Volume 24 (1768), pp. 251-326

[04.15] J. D. Lipson Newton’s Method : A Great Algebraic Algorithm, Proceedings ACM Symposium of Symbolic and Algebraic Computation (1976), pp. 260-270 | Zbl

[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, Volume 44 (1986), pp. 1-16 | DOI | MR | Zbl

[04.19] A. Schönhage The fundamental theorem of algebra in terms of computational complexity (1982) (Technical report)

[04.20] G. Schulz Iterative Berechnung der reziproken Matrix, Zeitschrift für angewandte Mathematik und Physik, Volume 13 (1933), pp. 57-59 | DOI | Zbl

[04.21] M. Sieveking An algorithm for division of powerseries, Computing, Volume 10 (1972), pp. 153-156 | DOI | MR | Zbl

[04.22, 15.05] Joris van der Hoeven Relax, but don’t be too lazy, Journal of Symbolic Computation, Volume 34 (2002) no. 6, pp. 479-542 | DOI | MR | Zbl

[05.01] Manindra Agrawal; Neeraj Kayal; Nitin Saxena PRIMES is in P, Annals of Mathematics. Second Series, Volume 160 (2004) no. 2, pp. 781-793 | DOI | MR | Zbl

[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, Volume 351/352 (2002), pp. 91-98 (Fourth special issue on linear systems and control) | DOI | MR | Zbl

[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, Volume 33 (1987), pp. 67-108 | Zbl

[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 | Zbl

[05.05] C. M. Fiduccia An efficient formula for linear recurrences, SIAM Journal on Computing, Volume 14 (1985) no. 1, pp. 106-112 | DOI | MR | Zbl

[05.06] J. C. P. Miller; D. J. Spencer Brown An algorithm for evaluation of remote terms in a linear recurrence sequence, Computer Journal, Volume 9 (1966), pp. 188-190 | DOI | MR | Zbl

[05.07, 06.13] R. T. Moenck; A. Borodin Fast modular transforms via division, Thirteenth Annual IEEE Symposium on Switching and Automata Theory (1972), pp. 90-96 | Zbl

[05.08] Peter L. Montgomery Modular multiplication without trial division, Mathematics of Computation, Volume 44 (1985) no. 170, pp. 519-521 | DOI | MR | Zbl

[05.09, 12.29] V. Shoup A Fast Deterministic Algorithm for Factoring Polynomials over Finite Fields of Small Characteristic, ISSAC’91 (1991), pp. 14-21 | Zbl

[05.10, 06.20, 12.33] V. Strassen Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten, Numerische Mathematik, Volume 20 (1972/73), pp. 238-251 | DOI | Zbl

[05.11] A. J. van der Poorten Some facts that should be better known, especially about rational functions, Number theory and applications, Kluwer, Dordrecht, 1989, pp. 497-528 (Proceedings of a Conference held at Banff, AB, 1988) | Zbl

[06.01, 16.01] A. V. Aho; K. Steiglitz; J. D. Ullman Evaluating polynomials at fixed sets of points, SIAM Journal on Computing, Volume 4 (1975) no. 4, pp. 533-539 | DOI | MR | Zbl

[06.02] L. I. Bluestein A linear filtering approach to the computation of the discrete Fourier transform, IEEE Trans. Electroacoustics, Volume AU-18 (1970), pp. 451-455 | DOI | Zbl

[06.03] A. Borodin; R. T. Moenck Fast modular transforms, Comput. Sys. Sci., Volume 8 (1974) no. 3, pp. 366-386 | MR | Zbl

[06.05, 12.09] Alin Bostan; Grégoire Lecerf; Éric Schost Tellegen’s principle into practice, ISSAC’03 (2003), pp. 37-44 | Zbl

[06.06, 16.08] Alin Bostan; Éric Schost Polynomial evaluation and interpolation on special sets of points, Journal of Complexity, Volume 21 (2005) no. 4, pp. 420-446 | DOI | MR | Zbl

[06.07] C. M. Fiduccia Polynomial evaluation via the division algorithm : The fast Fourier transform revisited., 4th ACM Symposium on Theory of Computing (1972), pp. 88-93 | Zbl

[06.08] Harvey L. Garner The residue number system, IRE-AIEE-ACM’59 Western joint computer conference (1959), pp. 146-153 | DOI

[06.09] Carl Friedrich Gauss Disquisitiones arithmeticae, Translated into English by Arthur A. Clarke, S. J, Yale University Press, New Haven, Conn., 1966 | Zbl

[06.10] L. E. Heindel; E. Horowitz On decreasing the computing time for modular arithmetic, 12th symposium on switching and automata theory (1971), pp. 126-128 | DOI

[06.11] E. Horowitz A fast Method for Interpolation Using Preconditioning, Information Processing Letters, Volume 1 (1972) no. 4, pp. 157-163 | DOI | MR | Zbl

[06.12] Russell M. Mersereau An algorithm for performing an inverse chirp $z$ -transform, IEEE Trans. Acoust. Speech Signal Processing, Volume ASSP-22 (1974) no. 5, pp. 387-388 | DOI | MR

[06.14] P. L. Montgomery An FFT extension of the elliptic curve method of factorization, University of California, Los Angeles CA (1992) (Ph. D. Thesis) | MR

[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, pp. 40-48 | Zbl

[06.16] V. Ya. Pan Methods of computing values of polynomials, Russian Mathematical Surveys, Volume 21 (1966) no. 1, pp. 105-136 http://stacks.iop.org/0036-0279/21/i=1/a=R03 | DOI | Zbl

[06.17] L. R. Rabiner; R. W. Schafer; C. M. Rader The chirp $z$ -transform algorithm and its application, Bell System Tech. J., Volume 48 (1969), pp. 1249-1292 | DOI | MR

[06.18] Victor Shoup; Roman Smolensky Lower bounds for polynomial evaluation and interpolation problems, Computational Complexity, Volume 6 (1996/97) no. 4, pp. 301-311 | DOI | MR | Zbl

[06.21] A. Svoboda; M. Valach Operátorové obvody (Operational circuits), Stroje na Zpracování Informací (Information Processing Machines), Volume 3 (1955), pp. 247-295

[06.22] H. Takahasi; Y. Ishibashi A new method for exact calculation by a digital computer, Information Processing in Japan (1961), pp. 28-42 | Zbl

[06.23] E. Waring Problems concerning interpolations, Philosophical Transactions of the Royal Society of London, Volume 59 (1779), pp. 59-67

[07.01] L. M. Berkovich; V. G. Tsirulik Differential resultants and some of their applications, Differentsial $^{'}$ nye Uravneniya, Volume 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) | Zbl

[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), pp. 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, Volume 1 (1980) no. 3, pp. 259-295 | Zbl

[07.04] 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), pp. 195-211 | DOI | MR | Zbl

[07.05] W. S. Brown; J. F. Traub On Euclid’s algorithm and the theory of subresultants, J. Assoc. Comput. Mach., Volume 18 (1971), pp. 505-514 | DOI | MR | Zbl

[07.06] Marc Chardin Differential resultants and subresultants, Fundamentals of computation theory (Gosen, 1991) (Lecture Notes in Comput. Sci.), Volume 529, Springer, Berlin, 1991, pp. 180-189 | DOI | MR | Zbl

[07.07] G. E. Collins Polynomial remainder sequences and determinants, Amer. Math. Monthly, Volume 73 (1966), pp. 708-712 | DOI | MR | Zbl

[07.08] George E. Collins Subresultants and reduced polynomial remainder sequences, J. Assoc. Comput. Mach., Volume 14 (1967), pp. 128-142 | DOI | MR | Zbl

[07.09] George E. Collins The calculation of multivariate polynomial resultants, J. Assoc. Comput. Mach., Volume 18 (1971), pp. 515-532 | DOI | MR | Zbl

[07.11] D. Yu. Grigoriev Complexity of factoring and calculating the GCD of linear ordinary differential operators, J. Symbolic Comput., Volume 10 (1990) no. 1, pp. 7-37 | DOI | MR | Zbl

[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, Volume 26 (1979) no. 9, pp. 750-755 | DOI | MR | Zbl

[07.13] Hoon Hong Ore principal subresultant coefficients in solutions, Appl. Algebra Engrg. Comm. Comput., Volume 11 (2001) no. 3, pp. 227-237 | DOI | MR | Zbl

[07.14] Hoon Hong Ore subresultant coefficients in solutions, Appl. Algebra Engrg. Comm. Comput., Volume 12 (2001) no. 5, pp. 421-428 | DOI | MR | Zbl

[07.15] Donald E. Knuth The analysis of algorithms, Actes du Congrès International des Mathématiciens (Nice, 1970), Tome 3, Gauthier-Villars, Paris, 1971, pp. 269-274 | Zbl

[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 | Zbl

[07.17] Serge Lang Algebra, Graduate Texts in Mathematics, 211, Springer-Verlag, New York, 2002 | Zbl

[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 | Zbl

[07.19] D. H. Lehmer Euclid’s Algorithm for Large Numbers, Amer. Math. Monthly, Volume 45 (1938) no. 4, pp. 227-233 | DOI | MR | Zbl

[07.20] Z. Li; I. Nemes A modular algorithm for computing greatest common right divisors of Ore polynomials, ISSAC’97 (1997), pp. 282-289 | Zbl

[07.21] Ziming Li A subresultant theory for Ore polynomials with applications, ISSAC’98 (1998), pp. 132-139 | MR | Zbl

[07.22] Ziming Li Greatest common right divisors, least common left multiples, and subresultants of Ore polynomials, Mathematics mechanization and applications, Academic Press, San Diego, CA, 2000, pp. 297-324 | DOI | MR

[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, pp. 142-151 | DOI | MR | Zbl

[07.24] Niels Möller On Schönhage’s algorithm and subquadratic integer GCD computation, Math. Comp., Volume 77 (2008) no. 261, pp. 589-607 | DOI | Zbl

[07.25] V. Y. Pan; X. Wang Acceleration of Euclidean algorithm and extensions, ISSAC’02 (2002), pp. 207-213

[07.26] A. Schönhage Schnelle Berechnung von Kettenbruchentwicklugen, Acta Inform., Volume 1 (1971), pp. 139-144 | DOI | Zbl

[07.27] A. Schönhage Probabilistic computation of integer polynomial GCDs, J. Algorithms, Volume 9 (1988) no. 3, pp. 365-371 | MR | Zbl

[07.28, 10.07] J. T. Schwartz Fast probabilistic algorithms for verification of polynomial identities, J. Assoc. Comput. Mach., Volume 27 (1980) no. 4, pp. 701-717 | DOI | MR | Zbl

[07.29] D. Stehlé; P. Zimmermann A binary recursive Gcd algorithm, ANTS-VI (Lecture Notes in Computer Science), Volume 3076 (2004), pp. 411-425 | MR | Zbl

[07.30] V. Strassen The computational complexity of continued fractions, SYMSAC’81 (1981), pp. 51-67 | DOI | Zbl

[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., New York, 1839, pp. 40-53

[07.33] James Joseph Sylvester A method of determining by mere inspection the derivatives from two equations of any degree, Philos. Mag., Volume 16 (1840) no. 101, pp. 132-135

[07.34] Joachim von zur Gathen; Jürgen Gerhard Modern computer algebra, Cambridge University Press, New York, 2003 | Zbl

[07.35] Joachim von zur Gathen; Thomas Lücking Subresultants revisited, Theoret. Comput. Sci., Volume 297 (2003) no. 1-3, pp. 199-239 | DOI | MR | Zbl

[07.36] Chee Yap Fundamental Problems in Algorithmic Algebra, Oxford Univ. Press, 2000 | Zbl

[07.37] David Y.Y. Yun On square-free decomposition algorithms, SYMSAC’76 (1976), pp. 26-35 | DOI

[07.38] David Y.Y. Yun On the equivalence of polynomial GCD and squarefree factorization problems, Proc. of the MACSYMA Users’ Conference (1977), pp. 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] Handbook of mathematical functions with formulas, graphs, and mathematical tables (Milton Abramowitz; Irene A. Stegun, eds.), Dover Publications Inc., New York, 1992 (Reprint of the 1972 edition) | Zbl

[08.03] Alin Bostan Algorithmique efficace pour des opérations de base en Calcul formel, École polytechnique, December (2003) (Ph. D. Thesis) | Zbl

[08.04] Alin Bostan; Frédéric Chyzak; Grégoire Lecerf; Bruno Salvy; Éric Schost Differential equations for algebraic functions, ISSAC’07 (2007), pp. 25-32 | DOI | Zbl

[08.05] L. Comtet Analyse Combinatoire, PUF, Paris, 1970 (2 volumes) | MR | Zbl

[08.06, 13.09] Philippe Flajolet; Bruno Salvy The SIGSAM Challenges : Symbolic Asymptotics in Practice, SIGSAM Bulletin, Volume 31 (1997) no. 4, pp. 36-47 | DOI

[08.07] Rev. Robert Harley On the theory of the transcendental solution of algebraic equations, Quarterly Journal of Pure and Applied Mathematics, Volume 5 (1862), pp. 337-360

[08.08] William A. Harris; Yasutaka Sibuya The reciprocals of solutions of linear ordinary differential equations, Advances in Mathematics, Volume 58 (1985) no. 2, pp. 119-132 | MR | Zbl

[08.09] L. Lipshitz $D$ -Finite Power Series, Journal of Algebra, Volume 122 (1989) no. 2, pp. 353-373 | MR | Zbl

[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, Volume 20 (1994) no. 2, pp. 163-177 | DOI | Zbl

[08.11] Michael F. Singer Algebraic relations among solutions of linear differential equations, Transactions of the American Mathematical Society, Volume 295 (1986) no. 2, pp. 753-763 | DOI | MR | Zbl

[08.12] N. J. A. Sloane The On-Line Encyclopedia of Integer Sequences, 2006 http://www.research.att.com/~njas/sequences/ (Published electronically at http://www.research.att.com/~njas/sequences/.) | Zbl

[08.13] R. P. Stanley Differentiably Finite Power Series, European Journal of Combinatorics, Volume 1 (1980) no. 2, pp. 175-188 | DOI | MR | Zbl

[08.14] Richard P. Stanley Enumerative combinatorics, 2, Cambridge University Press, 1999 | Zbl

[08.15] Jules Tannery Propriétés des intégrales des équations différentielles linéaires à coefficients variables, Faculté des Sciences de Paris (1874) (Thèse de doctorat ès sciences mathématiques)

[09.01] George A. Baker; Peter Graves-Morris Padé approximants, Encyclopedia of Mathematics and its Applications, 59, Cambridge University Press, Cambridge, 1996 | Zbl

[09.02] B. Beckermann; G. Labahn A uniform approach for the fast computation of matrix-type Padé approximants, SIAM J. Matrix Anal. Appl., Volume 15 (1994) no. 3, pp. 804-823 | DOI | Zbl

[09.03] Bernhard Beckermann A reliable method for computing $M$ -Padé approximants on arbitrary staircases, J. Comput. Appl. Math., Volume 40 (1992) no. 1, pp. 19-42 | MR | Zbl

[09.04] Bernhard Beckermann; George Labahn Fraction-free computation of matrix rational interpolants and matrix GCDs, SIAM J. Matrix Anal. Appl., Volume 22 (2000) no. 1, pp. 114-144 | DOI | MR | Zbl

[09.06] S. Cabay; G. Labahn A fast, reliable algorithm for calculating Padé-Hermite forms, ISSAC’89 (1989), pp. 95-100 | DOI

[09.07] S. Cabay; G. Labahn; B. Beckermann On the theory and computation of nonperfect Padé-Hermite approximants, J. Comput. Appl. Math., Volume 39 (1992) no. 3, pp. 295-313 | Zbl

[09.08] Stanley Cabay; Dong Koo Choi Algebraic computations of scaled Padé fractions, SIAM J. Comput., Volume 15 (1986) no. 1, pp. 243-270 | DOI | Zbl

[09.09] Unjeng Cheng On the continued fraction and Berlekamp’s algorithm, IEEE Trans. Inform. Theory, Volume 30 (1984) no. 3, pp. 541-544 | DOI | MR | Zbl

[09.10] J. Della Dora; C. Dicrescenzo Approximants de Padé-Hermite. I. Théorie, Numer. Math., Volume 43 (1984) no. 1, pp. 23-39 | Zbl

[09.11] J. Della Dora; C. Dicrescenzo Approximants de Padé-Hermite. II. Programmation, Numer. Math., Volume 43 (1984) no. 1, pp. 41-57 | Zbl

[09.12] Harm Derksen An algorithm to compute generalized Padé-Hermite forms (1994) no. 9403 (Report)

[09.13, 14.01] John D. Dixon Exact solution of linear equations using $p$ -adic expansions, Numer. Math., Volume 40 (1982) no. 1, pp. 137-141 | MR | Zbl

[09.14] Jean-Louis Dornstetter On the equivalence between Berlekamp’s and Euclid’s algorithms, IEEE Trans. Inform. Theory, Volume 33 (1987) no. 3, pp. 428-431 | DOI | MR | Zbl

[09.15, 14.02] Pascal Giorgi; Claude-Pierre Jeannerod; Gilles Villard On the complexity of polynomial matrix computations, ISSAC’03 (2003), pp. 135-142 | Zbl

[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, pp. 39-42 Algorithms and theory in filtering and control (Lexington, Ky., 1980) | DOI | Zbl

[09.18] G. H. Hardy; E. M. Wright An introduction to the theory of numbers, Oxford University Press, Oxford, 2008 | Zbl

[09.19] C. Hermite Extrait d’une lettre de Monsieur Ch. Hermite à Monsieur Paul Gordan, J. Reine Angew. Math., Volume 78 (1873), pp. 303-311 | MR

[09.20] C. Hermite Sur la fonction exponentielle, C. R. Math. Acad. Sci. Paris, Volume 77 (1873), pp. 18-24 | Zbl

[09.21] C. Hermite Sur la généralisation des fractions continues algébriques, Ann. Math., Volume 21 (1893) no. 2, pp. 289-308 | Zbl

[09.22] M. A. H. Khan High-order differential approximants, J. Comput. Appl. Math., Volume 149 (2002) no. 2, pp. 457-468 | DOI | MR | Zbl

[09.23] K. Mahler Perfect systems, Compositio Math., Volume 19 (1968), p. 95-166 (1968) | MR | Zbl

[09.24] James L. Massey Shift-register synthesis and $BCH$ decoding, IEEE Trans. Information Theory, Volume IT-15 (1969), pp. 122-127 | DOI | MR | Zbl

[09.25] Robert J. McEliece; James B. Shearer A property of Euclid’s algorithm and an application to Padé approximation, SIAM J. Appl. Math., Volume 34 (1978) no. 4, pp. 611-615 | Zbl

[09.26] W. H. Mills Continued fractions and linear recurrences, Math. Comp., Volume 29 (1975), pp. 173-180 | DOI | MR | Zbl

[09.27] H. Padé Sur la Représentation Approchée d’une Fonction par des Fractions Rationelles, Ann. Sci. École Norm. Sup., Volume 9 (1892), pp. 3-93 | DOI | MR | Zbl

[09.28] H. Padé Sur la généralisation des fractions continues algébriques, J. Math. Pures Appl., Volume 10 (1894) no. 4, pp. 291-330 | Zbl

[09.29] Victor Y. Pan; Xinmao Wang On rational number reconstruction and approximation, SIAM J. Comput., Volume 33 (2004) no. 2, pp. 502-503 | MR | Zbl

[09.30] Stefan Paszkowski Recurrence relations in Padé-Hermite approximation, J. Comput. Appl. Math., Volume 19 (1987) no. 1, pp. 99-107 | MR | Zbl

[09.31] A. V. Sergeyev A recursive algorithm for Padé-Hermite approximations, USSR Comput. Maths Math. Phys, Volume 26 (1986) no. 2, pp. 17-22 | DOI | Zbl

[09.32] R. E. Shafer On quadratic approximation, SIAM J. Numer. Anal., Volume 11 (1974), pp. 447-460 | DOI | MR | Zbl

[09.33] Y. Tourigny; Ph. G. Drazin The asymptotic behaviour of algebraic approximants, R. Soc. Lond. Proc. Ser. A Math. Phys. Eng. Sci., Volume 456 (2000) no. 1997, pp. 1117-1137 | DOI | MR | Zbl

[09.34] M. Van Barel; A. Bultheel A general module-theoretic framework for vector M-Padé and matrix rational interpolation, Numer. Algorithms, Volume 3 (1992) no. 1-4, pp. 451-461 | DOI | Zbl

[09.35] Marc Van Barel; Adhemar Bultheel The computation of nonperfect Padé-Hermite approximants, Numer. Algorithms, Volume 1 (1991) no. 3, pp. 285-304 | Zbl

[09.36] Xinmao Wang; Victor Y. Pan Acceleration of Euclidean algorithm and rational number reconstruction, SIAM J. Comput., Volume 32 (2003) no. 2, pp. 548-556 | DOI | MR | Zbl

[09.37] L. R. Welch; R. A. Scholtz Continued fractions and Berlekamp’s algorithm, IEEE Trans. Inform. Theory, Volume 25 (1979) no. 1, pp. 19-27 | DOI | MR | Zbl

[09.38] N. Zierler Linear recurring sequences and error-correcting codes, Error Correcting Codes (Proc. Sympos. Math. Res. Center, Madison, Wis., 1968), Wiley, 1968, pp. 47-59 | MR | Zbl

[10.01] Don Coppersmith Solving homogeneous linear equations over $GF (2)$ via block Wiedemann algorithm, Math. Comp., Volume 62 (1994) no. 205, pp. 333-350 | MR | Zbl

[10.02] Richard A. DeMillo; Richard J. Lipton A probabilistic remark on algebraic program testing, Inform. Process. Lett., Volume 7 (1978) no. 4, pp. 193-195 | DOI | Zbl

[10.03] 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), p. 113-119 (electronic) | Zbl

[10.04] Mark Giesbrecht Fast computation of the Smith form of a sparse integer matrix, Comput. Complexity, Volume 10 (2001) no. 1, pp. 41-69 | DOI | MR | Zbl

[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.), Volume 539, Springer, Berlin, 1991, pp. 29-38 | DOI | MR | Zbl

[10.06] Thom Mulders Certified sparse linear system solving, J. Symbolic Comput., Volume 38 (2004) no. 5, pp. 1343-1373 | DOI | MR | Zbl

[10.08] E. Thomé Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm, J. Symbolic Comput., Volume 33 (2002) no. 5, pp. 757-775 | DOI | MR | Zbl

[10.09] William J. Turner A block Wiedemann rank algorithm, ISSAC’06, ACM, New York, 2006, pp. 332-339 | MR | Zbl

[10.10] G. Villard Further analysis of Coppersmith’s block Wiedemann algorithm for the solution of sparse linear systems (extended abstract), ISSAC’97 (1997), pp. 32-39 | DOI | Zbl

[10.11, 12.36] D. Wiedemann Solving sparse linear equations over finite fields, IEEE Transactions on Information Theory, Volume IT-32 (1986), pp. 54-62 | DOI | MR | Zbl

[10.12] Richard Zippel Probabilistic algorithms for sparse polynomials, EUROSAM’79 (Lecture Notes in Comput. Sci.), Volume 72, Springer, Berlin, 1979, pp. 216-226 | MR | Zbl

[11.01] Robert R. Bitmead; Brian D. O. Anderson Asymptotically fast solution of Toeplitz and related systems of linear equations, Linear Algebra Appl., Volume 34 (1980), pp. 103-116 | DOI | MR | Zbl

[11.02] Alin Bostan; Claude-Pierre Jeannerod; Éric Schost Solving structured linear systems with large displacement rank, Theoret. Comput. Sci., Volume 407 (2008) no. 1-3, pp. 155-181 | DOI | MR | Zbl

[11.04] Jean-Paul Cardinal On a property of Cauchy-like matrices, C. R. Acad. Sci. Paris Sér. I Math., Volume 328 (1999) no. 11, pp. 1089-1093 | DOI | MR | Zbl

[11.05] I. Gohberg; V. Olshevsky Complexity of multiplication with vectors for structured matrices, Linear Algebra Appl., Volume 202 (1994), pp. 163-192 | DOI | MR | Zbl

[11.06] I. C. Gohberg; A. A. Semencul On the inversion of finite Toeplitz matrices and their continuous analogues (In Russian), Mat. Issled., Volume 7 (1972) no. 2, pp. 201-223 | Zbl

[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 | Zbl

[11.09] T. Kailath; S. Y. Kung; M. Morf Displacement ranks of a matrix, Bull. Amer. Math. Soc. (N.S.), Volume 1 (1979) no. 5, pp. 769-773 | DOI | MR | Zbl

[11.10] Thomas Kailath; Sun Yuan Kung; Martin Morf Displacement ranks of matrices and linear equations, J. Math. Anal. Appl., Volume 68 (1979) no. 2, pp. 395-407 | MR | Zbl

[11.11] Erich Kaltofen Asymptotically fast solution of Toeplitz-like singular linear systems, ISSAC’94 (1994), pp. 297-304 | DOI | Zbl

[11.12] Erich Kaltofen Analysis of Coppersmith’s block Wiedemann algorithm for the parallel solution of sparse linear systems, Math. Comp., Volume 64 (1995) no. 210, pp. 777-806 | MR | Zbl

[11.13] Norman Levinson The Wiener RMS (root mean square) error criterion in filter design and prediction, J. Math. Phys. Mass. Inst. Tech., Volume 25 (1947), pp. 261-278 | MR

[11.14] M. Morf Doubling algorithms for Toeplitz and related equations, IEEE Conference on Acoustics, Speech, and Signal Processing (1980), pp. 954-959 | DOI

[11.15] Victor Pan On computations with dense structured matrices, Math. Comp., Volume 55 (1990) no. 191, pp. 179-190 | MR | Zbl

[11.16] Victor Y. Pan Structured matrices and polynomials, Birkhäuser Boston Inc., Boston, MA, 2001 (Unified superfast algorithms) | Zbl

[11.17] Victor Y. Pan; Ailong Zheng Superfast algorithms for Cauchy-like matrix computations and extensions, Linear Algebra Appl., Volume 310 (2000) no. 1-3, pp. 83-108 | MR | Zbl

[11.18] William F. Trench An algorithm for the inversion of finite Toeplitz matrices, J. Soc. Indust. Appl. Math., Volume 12 (1964), pp. 515-522 | DOI | MR | Zbl

[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, STOC’88 (1988), pp. 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, Volume 10 (1968), pp. 218-219

[12.06] J. L. Bordewijk Inter-reciprocity applied to electrical networks, Appl. Sci. Res. B., Volume 6 (1956), pp. 1-74 | DOI | MR | Zbl

[12.07] A. Bostan; G. Lecerf; B. Salvy; É. Schost; B. Wiebelt Complexity issues in bivariate polynomial factorization, ISSAC’04, ACM, New York, 2004, pp. 42-49 | Zbl

[12.08] A. Bostan; É. Schost On the complexities of multipoint evaluation and interpolation, Theoret. Comput. Sci., Volume 329 (2004) no. 1–3, pp. 223-235 | DOI | MR | Zbl

[12.11] J. Canny; E. Kaltofen; L. Yagati Solving systems of non-linear polynomial equations faster, ISSAC’89 (1989), pp. 121-128

[12.13] Eleanor Chu; Alan George Inside the FFT black box, CRC Press, 2000 (Serial and parallel fast Fourier transform algorithms) | Zbl

[12.14] A. Fettweis A general theorem for signal-flow networks, with applications, Archiv für Elektronik und Übertragungstechnik, Volume 25 (1971) no. 12, pp. 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, New York, 1972, pp. 31-40 | MR

[12.16] C. M. Fiduccia On the algebraic complexity of matrix multiplication, Brown Univ., Providence, RI, Center Comput. Inform. Sci., Div. Engin. (1973) (Ph. D. Thesis)

[12.17] J.-C. Gilbert; G. Le Vey; J. Masse La différentiation automatique de fonctions représentées par des programmes (1991) (Technical report)

[12.20] R. E. Kalman On the General Theory of Control Systems, IRE Transactions on Automatic Control, Volume 4 (1959) no. 3, pp. 481-491 | DOI

[12.21] E. Kaltofen; R. M. Corless; D. J. Jeffrey Challenges of symbolic computation : my favorite open problems, Journal of Symbolic Computation, Volume 29 (2000) no. 6, pp. 891-919 | DOI | MR

[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.), Volume 673, Springer, Berlin, 1993, pp. 195-212 | DOI | MR | Zbl

[12.23] Erich Kaltofen Computational differentiation and algebraic complexity theory, Workshop Report on First Theory Institute on Computational Differentiation (1993), pp. 28-30

[12.24] M. Kaminski; D. G. Kirkpatrick; N. H. Bshouty Addition requirements for matrix and transposed matrix products, Journal of Algorithms, Volume 9 (1988) no. 3, pp. 354-364 | MR | Zbl

[12.25] Donald E. Knuth; Christos H. Papadimitriou Duality in addition chains, Bulletin of the European Association for Theoretical Computer Science, Volume 13 (1981), pp. 2-4

[12.26] G. Lecerf; É. Schost Fast Multivariate Power Series Multiplication in Characteristic Zero, SADIO Electronic Journal on Informatics and Operations Research, Volume 5 (2003) no. 1, pp. 1-10 | Zbl

[12.27] P. Penfield; R. Spence; S. Duinker Tellegen’s theorem and electrical networks, The M.I.T. Press, Cambridge, Mass.-London, 1970

[12.28] Steven Roman The umbral calculus, Pure and Applied Mathematics, 111, Academic Press Inc. [Harcourt Brace Jovanovich Publishers], New York, 1984 | MR | Zbl

[12.30] V. Shoup A new polynomial factorization algorithm and its implementation, Journal of Symbolic Computation, Volume 20 (1995) no. 4, pp. 363-397 | MR | Zbl

[12.31] V. Shoup Efficient computation of minimal polynomials in algebraic extensions of finite fields, ISSAC’99 (1999), pp. 53-58

[12.32] Victor Shoup Fast construction of irreducible polynomials over finite fields, J. Symbolic Comput., Volume 17 (1994) no. 5, pp. 371-391 | DOI | MR | Zbl

[12.34] B. Tellegen A general network theorem, with applications, Philips Research Reports, Volume 7 (1952), pp. 259-269 | MR | Zbl

[12.37] R. Zippel Interpolating polynomials from their values, Journal of Symbolic Computation, Volume 9 (1990) no. 3, pp. 375-403 | MR | Zbl

[13.01] Michael Beeler; R. Gosper; Richard Schroeppel HAKMEM, Artificial Intelligence Memo No. 239, MIT, 1972 http://www.inwap.com/pdp10/hbaker/hakmem/hakmem.html

[13.03] Peter B. Borwein On the complexity of calculating factorials, Journal of Algorithms, Volume 6 (1985) no. 3, pp. 376-380 | MR | Zbl

[13.04] A. Bostan; F. Chyzak; T. Cluzeau; B. Salvy Low complexity algorithms for linear recurrences, ISSAC’06, ACM, New York, 2006, pp. 31-38 | Zbl

[13.05] Alin Bostan; Thomas Cluzeau; Bruno Salvy Fast Algorithms for Polynomial Solutions of Linear Differential Equations, ISSAC’05 (2005), pp. 45-52 | DOI | Zbl

[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., Volume 36 (2007) no. 6, pp. 1777-1806 | DOI | MR | Zbl

[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, New York, 1976, pp. 151-176 | Zbl

[13.08] D. V. Chudnovsky; G. V. Chudnovsky Approximations and complex multiplication according to Ramanujan, Ramanujan revisited, Academic Press, MA, 1988, pp. 375-472 | Zbl

[13.10] P. Kogge; H. Stone A parallel algorithm for the efficient solution of a general class of recurrence equations, IEEE Trans. Comp., Volume C-22 (1973), pp. 786-793 | DOI | MR | Zbl

[13.11] V. Strassen Einige Resultate über Berechnungskomplexität, Jber. Deutsch. Math.-Verein., Volume 78 (1976/77) no. 1, pp. 1-8 | Zbl

[14.03] Claude-Pierre Jeannerod; Gilles Villard Essentially optimal computation of the inverse of generic polynomial matrices, J. Complexity, Volume 21 (2005) no. 1, pp. 72-86 | DOI | MR | Zbl

[14.04] 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 (Lecture Notes in Computer Science), Volume 72 (1979), pp. 65-73 | MR | Zbl

[14.05] Arne Storjohann High-Order Lifting, ISSAC’02 (2002), pp. 246-254 (Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, July 07–10, 2002, Université de Lille, France) | Zbl

[14.06] Arne Storjohann High-order lifting and integrality certification, J. Symbolic Comput., Volume 36 (2003) no. 3-4, pp. 613-648 | DOI | MR | Zbl

[14.07] Arne Storjohann The shifted number system for fast linear algebra on integer matrices, J. Complexity, Volume 21 (2005) no. 4, pp. 609-650 | DOI | MR | Zbl

[14.08] Arne Storjohann; Gilles Villard Computing the rank and a small nullspace basis of a polynomial matrix, ISSAC’05, ACM, New York, 2005, pp. 309-316 | Zbl

[15.01] 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), pp. 1012-1021 (Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, New Orleans, Louisiana) | Zbl

[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/) | MR | Zbl

[16.02] H. Alt Square rooting is as difficult as multiplication, Computing, Volume 21 (1978/79) no. 3, pp. 221-232 | MR | Zbl

[16.03] Jonathan M. Borwein; Bruno Salvy A proof of a recurrence for Bessel moments, Experiment. Math., Volume 17 (2008) no. 2, pp. 223-230 | DOI | MR | Zbl

[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, New York, 2008, pp. 23-30 | Zbl

[16.09] R. P. Brent; J. F. Traub On the complexity of composition and generalized composition of power series, SIAM Journal on Computing, Volume 9 (1980) no. 1, pp. 54-66 | DOI | MR | Zbl

[16.11] H. T. Kung; D. M. Tong Fast algorithms for partial fraction decomposition, SIAM J. Comput., Volume 6 (1977) no. 3, pp. 582-593 | DOI | MR | Zbl

[16.12] Joris van der Hoeven FFT-like multiplication of linear differential operators, J. Symbolic Comput., Volume 33 (2002) no. 1, pp. 123-127 | DOI | MR | Zbl

Cité par Sources :