, ? Multidigit multiplication for mathematicians. ? Preprint, available from http
, ? The fast Fourier transform, p.252
, ? How the FFT gained acceptance. In A history of scientific computing, pp.133-140, 1987.
DOI : 10.1145/41579.41589
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.419.1457
, ? Faster integer multiplication, STOC'07?Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pp.57-66
, Faster Integer Multiplication, SIAM Journal on Computing, vol.39, issue.3, pp.979-1005
DOI : 10.1137/070711761
, Gauss and the history of the fast Fourier transform, Archive for History of Exact Sciences, vol.4, issue.3, pp.265-277
DOI : 10.1007/BF00348431
, Another polynomial homomorphism, Acta Informatica, vol.9, issue.2, pp.153-169
DOI : 10.1007/BF00268498
, Five, six, and seven-term Karatsuba-like formulae, IEEE Transactions on Computers, vol.54, issue.3, pp.362-369
DOI : 10.1109/TC.2005.49
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.182.6801
, Fast polynomial transform algorithms for digital convolution, IEEE Transactions on Acoustics, Speech, and Signal Processing, vol.28, issue.2, pp.205-215
DOI : 10.1109/TASSP.1980.1163372
, The Computational Complexity of Continued Fractions, SIAM Journal on Computing, vol.12, issue.1, pp.1-27
DOI : 10.1137/0212001
, ? The complexity of a scheme of functional elements simulating the multiplication of integers, Doklady Akademii Nauk SSSR, vol.150, pp.496-498
, Joris) ? The truncated Fourier transform and applications, ISSAC'04, pp.290-296
, Minimization of the number of arithmetic operations in the solution of linear algebraic systems of equations, USSR Computational Mathematics and Mathematical Physics, vol.5, issue.1, pp.25-43
DOI : 10.1016/0041-5553(65)90065-0
, ? 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, vol.7, issue.4, pp.491-539
, Pan (Victor), and Sha (Xuan He). ? On practical algorithms for accelerated matrix multiplication, Linear Algebra Appl, vol.162164, pp.557-588
, A noncommutative algorithm for multiplying $3 \times 3$ matrices using 23 multiplications, Bulletin of the American Mathematical Society, vol.82, issue.1, pp.126-128
DOI : 10.1090/S0002-9904-1976-13988-2
, ? The border rank of the multiplication of 2 × 2 matrices is seven, Journal of the American Mathematical Society, vol.19, issue.02, pp.447-459
DOI : 10.1090/S0894-0347-05-00506-0
, Geometry and the complexity of matrix multiplication, Bulletin of the American Mathematical Society, vol.45, issue.02, pp.247-284
DOI : 10.1090/S0273-0979-08-01176-2
, ? An algorithm for multiplication of 3 × 3 matrices, Zh. Vychisl. Mat. i Mat. Fiz, vol.26, issue.320, pp.293-294
, ? Problems related to matrix multiplication, Proceedings Courant Institute Symposium on Computational Complexity, pp.137-151, 1971.
, On the Additive Complexity of Matrix Multiplication, SIAM Journal on Computing, vol.5, issue.2, pp.187-203
DOI : 10.1137/0205016
, ? Fast matrix multiplication formulae ? report of the prospectors
, Gaussian elimination is not optimal, Numerische Mathematik, vol.13, issue.4, pp.354-356
DOI : 10.1007/BF02165411
URL : http://www.digizeitschriften.de/download/PPN362160546_0013/PPN362160546_0013___log38.pdf
, ? Relative bilinear complexity and matrix multiplication, J. Reine Angew. Math, vol.375376, pp.406-443
, ? Algebraic complexity theory In Handbook of theoretical computer science, pp.633-672
, A fast non-commutative algorithm for matrix multiplication, Mathematical foundations of computer science (Proc. Sixth Sympos., Tatranská Lomnica, pp.504-512, 1977.
DOI : 10.1007/3-540-08353-7_173
, On Winograd's Algorithm for Inner Products, IEEE Transactions on Computers, vol.19, issue.4, pp.360-361
DOI : 10.1109/T-C.1970.222926
, On the number of multiplications necessary to compute certain functions, Communications on Pure and Applied Mathematics, vol.13, issue.2, pp.165-179
DOI : 10.1002/cpa.3160230204
, ? Some remarks on fast multiplication of polynomials In Complexity of sequential and parallel numerical algorithms, Proc. Sympos, pp.181-196, 1973.
, ? Multiple-precision zero-finding methods and the complexity of elementary function evaluation, Analytic computational complexity Proceedings of a Symposium, pp.151-176, 1975.
, ? Faster algorithms for the square root and reciprocal of power series Mathematics of Computation . ? To appear, p.910, 1926.
, ? Faster exponentials of power series. ? Preprint, available from http
, On computing reciprocals of power series, Numerische Mathematik, vol.264, issue.5, pp.341-348
DOI : 10.1007/BF01436917
, ? Iterative Berechnung der reziproken Matrix, Zeitschrift für angewandte Mathematik und Physik, pp.57-59
DOI : 10.1002/zamm.19330130111
, Ein Algorithmus f??r Potenzreihendivision, Computing, vol.10, issue.1-2, pp.153-156
DOI : 10.1007/BF02242389
, Relax, but Don???t be Too Lazy, Journal of Symbolic Computation, vol.34, issue.6, pp.479-542
DOI : 10.1006/jsco.2002.0562
, Modular multiplication without trial division, Mathematics of Computation, vol.44, issue.170, pp.519-521
DOI : 10.1090/S0025-5718-1985-0777282-X
, A fast deterministic algorithm for factoring polynomials over finite fields of small characteristic, Proceedings of the 1991 international symposium on Symbolic and algebraic computation , ISSAC '91, pp.14-21
DOI : 10.1145/120694.120697
, Die Berechnungskomplexit???t von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten, Numerische Mathematik, vol.115, issue.4, pp.238-251
DOI : 10.1007/BF01436566
, Evaluating Polynomials at Fixed Sets of Points, SIAM Journal on Computing, vol.4, issue.4, pp.533-539
DOI : 10.1137/0204045
, A linear filtering approach to the computation of discrete Fourier transform, IEEE Transactions on Audio and Electroacoustics, vol.18, issue.4, pp.451-455
DOI : 10.1109/TAU.1970.1162132
, ? The residue number system, IRE-AIEE-ACM'59 Western joint computer conference, pp.146-153
, A fast method for interpolation using preconditioning, Information Processing Letters, vol.1, issue.4, pp.157-163
DOI : 10.1016/0020-0190(72)90050-6
, An algorithm for performing an inverse chirp z-transform, IEEE Transactions on Acoustics, Speech, and Signal Processing, vol.22, issue.5, pp.387-388
DOI : 10.1109/TASSP.1974.1162603
, ? An FFT extension of the elliptic curve method of factorization
, Gaussian elimination is not optimal, Numerische Mathematik, vol.13, issue.4, pp.354-356
DOI : 10.1007/BF02165411
URL : http://www.digizeitschriften.de/download/PPN362160546_0013/PPN362160546_0013___log38.pdf
, Die Berechnungskomplexit???t von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten, Numerische Mathematik, vol.115, issue.4, pp.238-251
DOI : 10.1007/BF01436566
, Polynomial Remainder Sequences and Determinants, The American Mathematical Monthly, vol.73, issue.7, pp.708-712
DOI : 10.2307/2313976
, Subresultants and Reduced Polynomial Remainder Sequences, Journal of the ACM, vol.14, issue.1, pp.128-142
DOI : 10.1145/321371.321381
, The Calculation of Multivariate Polynomial Resultants, Journal of the ACM, vol.18, issue.4, pp.515-532
DOI : 10.1145/321662.321666
, Complexity of factoring and calculating the GCD of linear ordinary differential operators, Journal of Symbolic Computation, vol.10, issue.1, pp.7-37
DOI : 10.1016/S0747-7171(08)80034-X
, Ore Principal Subresultant Coefficients in Solutions, Applicable Algebra in Engineering, Communication and Computing, vol.11, issue.3, pp.227-237
DOI : 10.1007/s002000000041
, Ore Subresultant Coefficients in Solutions, Applicable Algebra in Engineering, Communication and Computing, vol.12, issue.5, pp.421-428
DOI : 10.1007/s002000100082
, ? The analysis of algorithms, Actes du Congrès International des Mathématiciens, pp.269-274, 1970.
, ? The Art of Computer Programming, Computer Science and Information Processing, vol.2, p.762
, Euclid's Algorithm for Large Numbers, The American Mathematical Monthly, vol.45, issue.4, pp.227-233
DOI : 10.2307/2302607
, Fast computation of GCDs, Proceedings of the fifth annual ACM symposium on Theory of computing , STOC '73, pp.142-151, 1973.
DOI : 10.1145/800125.804045
, Fast Probabilistic Algorithms for Verification of Polynomial Identities, Journal of the ACM, vol.27, issue.4, pp.701-717
DOI : 10.1145/322217.322225
, ? The computational complexity of continued fractions, SYMSAC'81, pp.51-67
, The Computational Complexity of Continued Fractions, SIAM Journal on Computing, vol.12, issue.1, pp.1-27
DOI : 10.1137/0212001
, Edited and with notes by L. Sylow and S. Lie, Reprint of the second (1881) edition. Disponible en ligne à http
, ? On the theory of the transcendental solution of algebraic equations, Quarterly Journal of Pure and Applied Mathematics, vol.5, pp.337-360
, D-finite power series, Journal of Algebra, vol.122, issue.2, pp.353-373
DOI : 10.1016/0021-8693(89)90222-6
, Algebraic relations among solutions of linear differential equations, Transactions of the American Mathematical Society, vol.295, issue.2, pp.753-763
DOI : 10.1090/S0002-9947-1986-0833707-X
, The On-Line Encyclopedia of Integer Sequences
DOI : 10.1007/978-3-540-73086-6_12
, Differentiably Finite Power Series, European Journal of Combinatorics, vol.1, issue.2, pp.175-188
DOI : 10.1016/S0195-6698(80)80051-5
URL : http://doi.org/10.1016/s0195-6698(80)80051-5
, ? Enumerative combinatorics, p.581
, George A.) and Graves-Morris (Peter). ? Padé approximants, Encyclopedia of Mathematics and its Applications, vol.59, p.746
, On the continued fraction and Berlekamp's algorithm (Corresp.), IEEE Transactions on Information Theory, vol.30, issue.3, pp.541-544
DOI : 10.1109/TIT.1984.1056906
, Exact solution of linear equations usingP-adic expansions, Numerische Mathematik, vol.82, issue.1, pp.137-141
DOI : 10.1007/BF01459082
, On the equivalence between Berlekamp's and Euclid's algorithms (Corresp.), IEEE Transactions on Information Theory, vol.33, issue.3, pp.428-431
DOI : 10.1109/TIT.1987.1057299
, Extrait d'une lettre de Monsieur Ch. Hermite ?? Monsieur Paul Gordan., Journal f??r die reine und angewandte Mathematik (Crelles Journal), vol.1873, issue.76, pp.303-311
DOI : 10.1515/crll.1873.76.303
, Sur la fonction exponentielle, C. R. Math. Acad. Sci. Paris, vol.77, pp.18-24
DOI : 10.1017/CBO9780511702778.012
, ? Sur la généralisation des fractions continues algébriques, Ann. Math, vol.21, issue.2, pp.289-308
, Shift-register synthesis and BCH decoding, IEEE Transactions on Information Theory, vol.15, issue.1, pp.122-127
DOI : 10.1109/TIT.1969.1054260
, A Property of Euclid???s Algorithm and an Application to Pad?? Approximation, SIAM Journal on Applied Mathematics, vol.34, issue.4, pp.611-615
DOI : 10.1137/0134048
, Sur la repr??sentation approch??e d'une fonction par des fractions rationnelles, Annales scientifiques de l'??cole normale sup??rieure, vol.9, pp.3-93
DOI : 10.24033/asens.378
, ? Sur la généralisation des fractions continues algébriques, J. Math. Pures Appl, vol.10, issue.4, pp.291-330
, A recursive algorithm for Pad??-Hermite approximations, USSR Computational Mathematics and Mathematical Physics, vol.26, issue.2, pp.17-22
DOI : 10.1016/0041-5553(86)90003-0
, On Quadratic Approximation, SIAM Journal on Numerical Analysis, vol.11, issue.2, pp.447-460
DOI : 10.1137/0711037
, Acceleration of Euclidean Algorithm and Rational Number Reconstruction, SIAM Journal on Computing, vol.32, issue.2, pp.548-556
DOI : 10.1137/S0097539702408636
, ? Linear recurring sequences and error-correcting codes, Error Correcting Codes (Proc. Sympos, pp.47-59, 1968.
DOI : 10.1109/tit.1960.1057585
, Fast Probabilistic Algorithms for Verification of Polynomial Identities, Journal of the ACM, vol.27, issue.4, pp.701-717
DOI : 10.1145/322217.322225
, Subquadratic Computation of Vector Generating Polynomials and Improvement of the Block Wiedemann Algorithm, Journal of Symbolic Computation, vol.33, issue.5, pp.757-775
DOI : 10.1006/jsco.2002.0533
, A block Wiedemann rank algorithm, Proceedings of the 2006 international symposium on Symbolic and algebraic computation , ISSAC '06, pp.332-339
DOI : 10.1145/1145768.1145822
, Solving sparse linear equations over finite fields, IEEE Transactions on Information Theory, vol.32, issue.1, pp.54-62
DOI : 10.1109/TIT.1986.1057137
, Van Loan (Charles F.). ? Matrix computations, Johns Hopkins Studies in the Mathematical Sciences, p.698
, Doubling algorithms for Toeplitz and related equations, ICASSP '80. IEEE International Conference on Acoustics, Speech, and Signal Processing, pp.954-959
DOI : 10.1109/ICASSP.1980.1171074
, ? Digital Filters : Analysis and Design
, ? The transposition principle
, A linear filtering approach to the computation of discrete Fourier transform, IEEE Transactions on Audio and Electroacoustics, vol.18, issue.4, pp.218-219
DOI : 10.1109/TAU.1970.1162132
, Inter-reciprocity applied to electrical networks, Applied Scientific Research, Section B, vol.10, issue.1, pp.1-74
DOI : 10.1007/BF02920362
, ? A general theorem for signal-flow networks, with applications, Archiv für Elektronik und Übertragungstechnik, pp.557-561
, On Obtaining Upper Bounds on the Complexity of Matrix Multiplication, Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, pp.31-40, 1972.
DOI : 10.1007/978-1-4684-2001-2_4
, ? On the algebraic complexity of matrix multiplication, Inform. Sci., Div. Engin
, On the general theory of control systems, IRE Transactions on Automatic Control, vol.4, issue.3, pp.481-491
DOI : 10.1109/TAC.1959.1104873
, ? Tellegen's theorem and electrical networks. ? The M.I
, A fast deterministic algorithm for factoring polynomials over finite fields of small characteristic, Proceedings of the 1991 international symposium on Symbolic and algebraic computation , ISSAC '91, pp.14-21
DOI : 10.1145/120694.120697
, A New Polynomial Factorization Algorithm and its Implementation, Journal of Symbolic Computation, vol.20, issue.4, pp.363-397
DOI : 10.1006/jsco.1995.1055
, Efficient computation of minimal polynomials in algebraic extensions of finite fields, Proceedings of the 1999 international symposium on Symbolic and algebraic computation , ISSAC '99, pp.53-58
DOI : 10.1145/309831.309859
, Fast Construction of Irreducible Polynomials over Finite Fields, Journal of Symbolic Computation, vol.17, issue.5, pp.371-391
DOI : 10.1006/jsco.1994.1025
, Die Berechnungskomplexit???t von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten, Numerische Mathematik, vol.115, issue.4, pp.238-251
DOI : 10.1007/BF01436566
, ? A general network theorem, with applications, Philips Research Reports, vol.7, pp.259-269
, Solving sparse linear equations over finite fields, IEEE Transactions on Information Theory, vol.32, issue.1, pp.54-62
DOI : 10.1109/TIT.1986.1057137
, Interpolating polynomials from their values, Journal of Symbolic Computation, vol.9, issue.3, pp.375-403
DOI : 10.1016/S0747-7171(08)80018-1
URL : http://doi.org/10.1016/s0747-7171(08)80018-1
, ? Fast multiplication and its applications In Algorithmic number theory : lattices, number fields, curves and cryptography, pp.325-384
, MULTIPLE-PRECISION ZERO-FINDING METHODS AND THE COMPLEXITY OF ELEMENTARY FUNCTION EVALUATION, Analytic computational complexity (Proc. Sympos, pp.151-176, 1975.
DOI : 10.1016/B978-0-12-697560-4.50014-9
, ? Einige Resultate über Berechnungskomplexität, Jber. Deutsch. Math.-Verein, vol.78, issue.1, pp.1-8
, algorithme calcule d'abord l'inverse S = A ?1 mod X d par l'algorithme de Newton , en O(n ? M(d))
, algorithme ci-dessus avec k = d pour calculer à chaque itération d coefficients et un nouveau B (i+1)d . Si on part de B 0 = I, le résultat fournit les N premiers coefficients de A ?1 ; si B 0 = B, alors on obtient les coefficients de A ?1 B. Les deux étapes de l'algorithme ci-dessus (avec k = d) coûtent O(n ? M(d))
, le calcul de la fraction rationnelle solution de (1) demande O(n 3
, Exact solution of linear equations usingP-adic expansions, Numerische Mathematik, vol.82, issue.1, pp.137-141
DOI : 10.1007/BF01459082
, Approximate algorithms to derive exact solutions to systems of linear equations, EUROSAM '79 : Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, pp.65-73
DOI : 10.1007/3-540-09519-5_60
, Joris) ? Newton's method and FFT trading Journal of Symbolic Computation. ? To appear
, Relax, but Don???t be Too Lazy, Journal of Symbolic Computation, vol.34, issue.6, pp.479-542
DOI : 10.1006/jsco.2002.0562
, A 1 , A 0 qui lui sont toutes semblables (c'està-dire de la forme P ?1 AP , avec P inversible) Ces matrices sont définies de manière inductive. Pour passer de A i+1 à A i , on calcule s i = n/2 i matrices, notées A i,1 = A i+1 , A i,2 , . . . , A i,si = A i et définies comme suit : ? On considère la matrice U ij de type 2 i -Frobenius dont les 2 i dernières colonnes coïncident avec les 2 i dernières colonnes de A ij
, MM(n) ? D) opérations de K suffisent pour résoudre E(P, A)
, K) et deg(P ) = n, la première colonne de P (A) peut être calculée en O(MM(n) log n)
, on suppose que la matrice A est « suffisamment générique », en ce sens que la matrice U ? M n (K), dont la ?-ième colonne coïncide avec la première colonne de A ?
, elle peut être calculée en O(MM(n) log n) opérations de K. Indication : Remarquer que l'espace vectoriel V = K n admet {A ? e} 1???n comme base
, pour une matrice A « suffisamment générique », le problème E(P, A) peut se résoudre en O(MM(n) log n + M(D))
, Evaluating Polynomials at Fixed Sets of Points, SIAM Journal on Computing, vol.4, issue.4, pp.533-539
DOI : 10.1137/0204045
, Die Komplexit??t des Wurzelziehens, Computing, vol.1, issue.3, pp.221-232
DOI : 10.1007/BF02253055
, Fast algorithms for the characteristics polynomial, Theoretical Computer Science, vol.36, pp.2-3
DOI : 10.1016/0304-3975(85)90049-0
, FFT-like Multiplication of Linear Differential Operators, Journal of Symbolic Computation, vol.33, issue.1, pp.123-127
DOI : 10.1006/jsco.2000.0496
, p. 99 ? Multiplication de polynômes par transformée de Fourier discrète .p. 98 ? Multiplication de polynômes par l'algorithme . p. 101 ? Multiplication de matrices par l'algorithme, .p. 112 ? Inversion de matrices par l'algorithme de Strassen, p.117
, p. 189 ? Reconstruction de récurrences linéaires à coefficients constants par l'algorithme, Cauchy des fractions rationnelles, pp.190-190
, p. 194 ? Reconstruction d'équations algébriques et différentielles, p. 195 ? Reconstruction de récurrences linéaires à coefficients polynomiaux . . . . . . . . . . . . . . . . . . . p, p.195
, Résolution d'un système linéaire creux par l'algorithme, p.199
, Factorisation déterministe d'entiers par l'algorithme, p.229