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

Bostan, Alin

Journées Nationales de Calcul Formel. 3 – 7 Mai 2010, Les cours du CIRM, no. 2 (2010), pp. 75-262.

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

[01.02] Beck, Matthias; Berndt, Bruce C.; Chan, O-Yeat; Zaharescu, Alexandru Determinations of Analogues of Gauss Sums and Other Trigonometric Sums, Int. J. Number Theory, Volume 1 (2005) no. 3, pp. 333-356

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

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

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

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

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

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

[02.01] Bernstein, D. J. Multidigit multiplication for mathematicians (Preprint, available from http://cr.yp.to/papers.html)

[02.02] Bodrato, Marco; Zanoni, Alberto Integer and polynomial multiplication : towards optimal Toom-Cook matrices, ISSAC’07, ACM, New York, 2007, pp. 17-24 | DOI

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

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

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

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

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

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

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

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

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

[02.12] Cooley, James W.; Tukey, John W. 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] De, A.; Kurur, P. P.; Saha, C.; Saptharishi, R. Fast integer multiplication using modular arithmetic, STOC’08, ACM, New York, NY, USA (2008), pp. 499-506 | DOI

[02.14] Dongarra, J.; Sullivan, F. Top ten algorithms, Computing in Science & Engineering, Volume 2 (2000) no. 1, pp. 22-23

[02.15] Duhamel, P.; Vetterli, M. 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

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

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

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

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

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

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

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

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

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

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

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

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

[02.28] Nussbaumer, Henri J. 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

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

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

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

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

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

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

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

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

[02.37] Weimerskirch, André; Paar, Christof 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] Abdeljaoued, J.; Lombardi, H. Méthodes matricielles : introduction à la complexité algébrique, Mathématiques & Applications, 42, Springer-Verlag, Berlin, 2004

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

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

[03.04] Bini, D.; Capovani, M.; Romani, F.; Lotti, G. $O\left(n^{2.7799}\right)$ complexity for $n\times n$ approximate matrix multiplication, Inform. Process. Lett., Volume 8 (1979) no. 5, pp. 234-235

[03.05] Bläser, Markus 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

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

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

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

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

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

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

[03.13] Cohn, Henry; Umans, Christopher A Group-Theoretic Approach to Fast Matrix Multiplication, FOCS’03, IEEE Computer Society, Washington, DC, USA (2003), 438 pages

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

[03.15] Danilevskii, A. M The numerical solution of the secular equation, Matem. sbornik, Volume 44 (1937) no. 2, pp. 169-171 (in Russian)

[03.16] Fiduccia, Charles M. 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

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

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

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

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

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

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

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

[03.24] Ja’Ja’, Joseph On the complexity of bilinear forms with commutativity, STOC’79, ACM, New York, NY, USA (1979), pp. 197-208 | DOI

[03.25] Kaporin, I 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

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

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

[03.28] Klyuyev, V. V.; Kokovkin-Shcherbak, N. I. 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

[03.29] Krylov, A. N. 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] Laderman, Julian; Pan, Victor; Sha, Xuan He On practical algorithms for accelerated matrix multiplication, Linear Algebra Appl., Volume 162/164 (1992), pp. 557-588

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

[03.32] Landsberg, J. M. 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

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

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

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

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

[03.37] Pan, V. Ya. Strassen’s algorithm is not optimal. Trilinear technique of aggregating, uniting and canceling for constructing fast algorithms for matrix operations, SFCS ’78, IEEE Computer Society, Washington, DC, USA (1978), pp. 166-176 | DOI

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

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

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

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

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

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

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

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

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

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

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

[03.49] Storjohann, Arne 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

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

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

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

[03.53] Sýkora, Ondrej 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

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

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

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

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

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

[03.59] Winograd, Shmuel 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

[04.01] Bernstein, D. J. Removing redundancy in high-precision Newton iteration (Preprint, available from http://cr.yp.to/fastnewton.html#fastnewton-paper)

[04.02] Bernstein, Daniel J. Composing power series over a finite ring in essentially linear time, Journal of Symbolic Computation, Volume 26 (1998) no. 3, pp. 339-341

[04.03, 13.02] Bernstein, Daniel J. 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

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

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

[04.07] Brent, Richard P. 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)

[04.08] Hanrot, Guillaume; Zimmermann, Paul Newton iteration revisited, Available at http://www.loria.fr/~zimmerma/papers

[04.09] Harvey, David Faster algorithms for the square root and reciprocal of power series, Mathematics of Computation (To appear. Available at http://arxiv.org/abs/0910.1926/)

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

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

[04.12] Kedlaya, Kiran S.; Umans, Christopher Fast Modular Composition in any Characteristic, FOCS ’08 : Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Washington, DC, USA (2008), pp. 146-155 | DOI

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

[04.14] Lagrange, Joseph-Louis 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] Lipson, J. D. Newton’s Method : A Great Algebraic Algorithm, Proceedings ACM Symposium of Symbolic and Algebraic Computation, ACM Press (1976), pp. 260-270

[04.16] Newton, Isaac 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] Ritzmann, P. A fast numerical algorithm for the composition of power series with complex coefficients, Theoretical Computer Science, Volume 44 (1986), pp. 1-16

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

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

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

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

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

[05.02] Blondel, Vincent D.; Portier, Natacha 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)

[05.03, 12.12] Cerlienco, L.; Mignotte, M.; Piras, F. Suites récurrentes linéaires. Propriétés algébriques et arithmétiques, L’Enseignement Mathématique, Volume 33 (1987), pp. 67-108

[05.04] Everest, Graham; van der Poorten, Alf; Shparlinski, Igor; Ward, Thomas Recurrence sequences, Mathematical Surveys and Monographs, 104, American Mathematical Society, Providence, RI, 2003

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

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

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

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

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

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

[05.11] van der Poorten, A. J. 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)

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

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

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

[06.05, 12.09] Bostan, Alin; Lecerf, Grégoire; Schost, Éric Tellegen’s principle into practice, ISSAC’03 (Sendra, J. R., ed.), ACM Press (2003), pp. 37-44

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

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

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

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

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

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

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

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

[06.15] Ostrowski, A. 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

[06.16] Pan, V. Ya. 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

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

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

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

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

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

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

[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] Brent, Richard P.; Gustavson, Fred G.; Yun, David Y. Y. Fast solution of Toeplitz systems of equations and computation of Padé approximants, J. Algorithms, Volume 1 (1980) no. 3, pp. 259-295

[07.04] Brown, W. S. 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, ACM, New York, NY, USA (1971), pp. 195-211 | DOI

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

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

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

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

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

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

[07.12, 09.17, 11.08] Gustavson, Fred G.; Yun, David Y. Y. Fast algorithms for rational Hermite approximation and solution of Toeplitz systems, IEEE Trans. Circuits and Systems, Volume 26 (1979) no. 9, pp. 750-755

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

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

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

[07.16] Knuth, Donald E. The Art of Computer Programming, Computer Science and Information Processing, 2 : Seminumerical Algorithms, Addison-Wesley Publishing Co., Reading, Mass., 1997

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

[07.18] Lascoux, Alain 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

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

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

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

[07.22] Li, Ziming 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

[07.23] Moenck, R. T. Fast computation of GCDs, Fifth Annual ACM Symposium on Theory of Computing (Austin, Tex., 1973), Assoc. Comput. Mach., New York, 1973, pp. 142-151

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

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

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

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

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

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

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

[07.32] Sylvester, James Joseph 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] Sylvester, James Joseph 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] von zur Gathen, Joachim; Gerhard, Jürgen Modern computer algebra, Cambridge University Press, New York, 2003

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

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

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

[07.38] Yun, David Y.Y. On the equivalence of polynomial GCD and squarefree factorization problems, Proc. of the MACSYMA Users’ Conference (1977), pp. 65-70

[08.01] Abel, Niels Henrik Œ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 (Abramowitz, Milton; Stegun, Irene A., eds.), Dover Publications Inc., New York, 1992 (Reprint of the 1972 edition)

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

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

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

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

[08.07] Harley, Rev. Robert 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] Harris, William A.; Sibuya, Yasutaka The reciprocals of solutions of linear ordinary differential equations, Advances in Mathematics, Volume 58 (1985) no. 2, pp. 119-132

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

[08.10] Salvy, Bruno; Zimmermann, Paul 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

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

[08.12] Sloane, N. J. A. 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/.)

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

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

[08.15] Tannery, Jules 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 Disponible en ligne à http://gallica.bnf.fr.)

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

[09.02] Beckermann, B.; Labahn, G. 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

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

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

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

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

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

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

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

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

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

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

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

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

[09.16] Gragg, William B.; Gustavson, Fred G.; Warner, Daniel D.; Yun, David Y. Y. 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)

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

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

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

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

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

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

[09.24] Massey, James L. Shift-register synthesis and $\mathrm{BCH}$ decoding, IEEE Trans. Information Theory, Volume IT-15 (1969), pp. 122-127

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[10.01] Coppersmith, Don Solving homogeneous linear equations over $\mathrm{GF}\left(2\right)$ via block Wiedemann algorithm, Math. Comp., Volume 62 (1994) no. 205, pp. 333-350

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

[10.03] Giesbrecht, M.; Lobo, A.; Saunders, B. D. Certifying inconsistency of sparse linear systems, Proceedings of the 1998 International Symposium on Symbolic and Algebraic Computation (Rostock), ACM, New York (1998), p. 113-119 (electronic)

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

[10.05] Kaltofen, Erich; Saunders, B. David 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

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

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

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

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

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

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

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

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

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

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

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

[11.07] Golub, Gene H.; Van Loan, Charles F. Matrix computations, Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 1996

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

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

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

[11.12] Kaltofen, Erich 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

[11.13] Levinson, Norman 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

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

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

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

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

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

[12.01] Antoniou, A. Digital Filters : Analysis and Design, McGraw-Hill Book Co., 1979

[12.03] Ben-Or, M.; Tiwari, P. A deterministic algorithm for sparse multivariate polynomial interpolation, STOC’88, ACM Press (1988), pp. 301-309

[12.04] Bernstein, D. J. The transposition principle (http://cr.yp.to/transposition.html)

[12.05] Bluestein, Leo I. 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] Bordewijk, J. L. Inter-reciprocity applied to electrical networks, Appl. Sci. Res. B., Volume 6 (1956), pp. 1-74

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

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

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

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

[12.14] Fettweis, A. 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] Fiduccia, C. M. 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

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

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

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

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

[12.22] Kaltofen, Erich 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

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

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

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

[12.26] Lecerf, G.; 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

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

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

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

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

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

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

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

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

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

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

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

[13.06, 16.07] Bostan, Alin; Gaudry, Pierrick; Schost, Éric 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

[13.07] Brent, R. P. 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

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

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

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

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

[14.04] Moenck, Robert T.; Carter, John H. 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, Springer-Verlag, London, UK (1979), pp. 65-73

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

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

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

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

[15.01] Bostan, A.; Chyzak, F.; Ollivier, F.; Salvy, B.; Schost, É.; Sedoglavic, A. Fast computation of power series solutions of systems of differential equations, SODA’07, SIAM (2007), pp. 1012-1021 (Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, New Orleans, Louisiana)

[15.04] van der Hoeven, Joris Newton’s method and FFT trading, Journal of Symbolic Computation (To appear. Available at http://hal.archives-ouvertes.fr/hal-00434307/fr/)

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

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

[16.04] Bostan, A.; Chyzak, F.; Li, Z.; Salvy, B. Common multiples of linear ordinary differential and difference operators (In preparation)

[16.05] Bostan, Alin; Chyzak, Frédéric; Le Roux, Nicolas Products of ordinary differential operators by evaluation and interpolation, ISSAC’08, ACM, New York, 2008, pp. 23-30

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

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

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