Fast Algorithms for Zero-Dimensional Polynomial Systems using Duality

Alonso, M.-E., Becker, E., Roy, M.-F., Wörmann, T.: Zeros, multiplicities, and idempotents for zero-dimensional systems. In: Algorithms in algebraic geometry and applications (Santander, 1994), Birkhäuser, Basel, 1996, pp. 1–15 Antoniou, A.: Digital Filters: Analysis and Design. McGraw-Hill Book Co., 1979 Arnaudiès, J.-M., Valibouze, A.: Lagrange resolvents. J. Pure Appl. Algebra 117/118, 23–40, 1997, Algorithms for algebra (Eindhoven, 1996) Becker, E., Cardinal, J. P., Roy, M.-F., Szafraniec, Z.: Multivariate Bezoutians, Kronecker symbol and Eisenbud-Levine formula. In: Algorithms in algebraic geometry and applications (Santander, 1994), Birkhäuser, Basel, 1996, pp. 79–104 Becker, E., Wörmann, T.: Radical computations of zero-dimensional ideals and real root counting. Mathematics and Computers in Simulation, 42(4-6), 561–569 (1996), Symbolic computation, new trends and developments (Lille, 1993) Berlekamp, E. R.: Algebraic coding theory. McGraw-Hill Book Co., New York, 1968 Björck, G.: Functions of modulus 1 on Z n whose Fourier transforms have constant modulus, and ‘‘cyclic n-roots’’. In: Recent advances in Fourier analysis and its applications (Il Ciocco, 1989), Volume 315 of NATO Advance Science Institutes Series C: Mathematical and Physical Sciences, Kluwer Academic Publishers, Dordrecht, 1990, pp. 131–140 Bommer, R.: High order derivations and primary ideals to regular prime ideals. Arch. Math. 46(6), 511–521 (1986) Bordewijk, J. L.: Inter-reciprocity applied to electrical networks. Appl. Sci. Res. B 1, 1–74 (1956) Bosma, W., Cannon, J., Playoust, C.: The Magma algebra system. I. The user language. Journal of Symbolic Computation 24(3-4), 235–265 (1997) See also http://www.maths.usyd.edu.au:8000/u/magma/ Bostan, A., Lecerf, G., Schost, É.: Tellegen’s principle into practice. In: Symbolic and Algebraic Computation, 2003, Proceedings ISSAC’03, Philadelphia, August 2003. To appear Brent, R. P., Kung, H. T.: Fast algorithms for manipulating formal power series. J. ACM 25(4), 581–595, October 1978 Buchberger, B.: Gröbner bases: An algorithmic method in polynomial ideal theory. In: Multidimensional System Theory, Reidel, Dordrecht, 1985, pp. 374–383 Bürgisser, P., Clausen, M., Shokrollahi, A.: Algebraic Complexity Theory. Springer, 1997 Charlap, L. S., Coley, R., Robbins, D.: Enumeration of rational points on elliptic curves over finite fields. Preprint, 1991 Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. J. Symbolic Comput. 9(3), 251–280, March 1990 Cox, D., Little, J., O’Shea, D.: Using algebraic geometry. Springer-Verlag, New York, 1998 Eisenbud, D.: Commutative algebra, with a view toward algebraic geometry. Graduate Texts in Mathematics. Springer-Verlag, New York, 1995 Faugère, J.-C.: A new efficient algorithm for computing Gröbner bases (F 4). J. Pure Appl. Algebra, 139(1–3), 61–88 (1999) Proceedinds of MEGA’98 Faugère, J.-C., Gianni, P., Lazard, D., Mora, T.: Efficient computation of zero-dimensional Gröbner bases by change of ordering. J. Symbolic Comput. 16(4), 329–344 (1993) Fiduccia, C. M.: On obtaining upper bounds on the complexity of matrix multiplication. In: Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972), Plenum, New York, 1972, pp. 31–40, 187–212 Fiduccia, C. M.: On the algebraic complexity of matrix multiplication. PhD thesis, Brown Univ., Providence, RI, Center Comput. Inform. Sci., Div. Engin., 1973 Gaudry, P.: Algorithmique des courbes hyperelliptiques et applications à la cryptologie. PhD thesis, École polytechnique, 2000 Gaudry, P., Schost, É.: Modular equations for hyperelliptic curves. Technical report, École polytechnique, 2002 Giusti, M., Heintz, J., Hägele, K., Morais, J. E., Pardo, L. M., Montaña, J. L.: Lower bounds for Diophantine approximations. J. Pure Appl. Algebra 117/118, 277–317 (1997), Algorithms for algebra (Eindhoven, 1996) Giusti, M., Heintz, J., Morais, J. E., Morgenstern, J., Pardo, L. M.: Straight-line programs in geometric elimination theory. J. Pure Appl. Algebra 124, 101–146 (1998) Giusti, M., Lecerf, G., Salvy, B.: A Gröbner free alternative for polynomial system solving. J. Complexity 17(1), 154–211 (2001) Göttfert, R., Niederreiter., H.: On the minimal polynomial of the product of linear recurring sequences. Finite Fields and their Applications 1(2), 204–218 (1995), Special issue dedicated to Leonard Carlitz Gröbner, W.: La théorie des idéaux et la géométrie algébrique. In: Deuxième Colloque de Géométrie Algébrique, Liège, 1952, Georges Thone, Liège, 1952, pp. 129–144 Hopcroft, J., Musinski, J.: Duality applied to the complexity of matrix multiplication and other bilinear forms. SIAM J. Comput. 2, 1973 Kaltofen, E.: Analysis of Coppersmith’s block Wiedemann algorithm for the parallel solution of sparse linear systems. Math. Comput. 64(210), 777–806 (1995) Kaltofen, E., Corless, R. M., Jeffrey, D.J.: Challenges of symbolic computation: my favorite open problems. J. Symbolic Comput. 29(6), 891–919 (2000) Kaminski, M., Kirkpatrick, D. G., Bshouty, N. H.: Addition requirements for matrix and transposed matrix products. J. Algorithms 9(3), 354–364 (1988) Kreuzer, M., Robbiano, L.: Computational commutative algebra. 1. Springer-Verlag, Berlin, 2000 Kronecker, L.: Grundzüge einer arithmetischen Theorie der algebraischen Grössen. Journal für die reine und angewandte Mathematik 92, 1–122 (1882) Kunz, E.: Kähler differentials. Vieweg advanced lectures in Mathematics. Friedr. Vieweg & Sohn, Braunschweig, 1986 Kurosh, A.: Cours d’algèbre supérieure. Éditions Mir, Moscou, 1973 Lang, S.: Introduction to algebraic geometry. Interscience Publishers, New York, 1958 Lang, S.: Algebra, Volume 211 of Graduate Texts in Mathematics. Springer-Verlag, New York, third edition, 2002 Lazard, D.: Solving zero-dimensional algebraic systems. J. Symbolic Comput. 13, 117–133 (1992) Lazard, D., Valibouze, A.: Computing subfields: reverse of the primitive element problem. In: Computational algebraic geometry (Nice, 1992), Birkhäuser Boston, Boston, MA, 1993, pp. 163–176 Lecerf, G.: Une alternative aux méthodes de réécriture pour la résolution des systèmes algébriques. PhD thesis, École polytechnique, 2001 Lecerf, G.: Quadratic Newton iteration for systems with multiplicity. J. FoCM 2(3), 247–293 (2002) Lecerf, G.: Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers. J. Complexity, 2003. To appear Little, J.: A key equation and the computation of error values for codes from order domains. Available at http://arXiv.org/math.AC/0303299, 2003 Macaulay, F. S.: The Algebraic Theory of Modular Systems. Cambridge University Press, 1916 Mallat, S.: Foveal detection and approximation for singularities. Applied and Computational Harmonic Analysis, 2003. To appear Marinari, M. G., Mora, T., Möller, H. M.: Gröbner bases of ideals defined by functionals with an application to ideals of projective points. Applicable Algebra in Engineering, Communication and Computing 4, 103–145 (1993) Massey, J. L.: Shift-register synthesis and BCH decoding. IEEE Transactions on Information Theory, IT-15, 122–127, 1969 Mourrain, B.: Isolated points, duality and residues. J. Pure Appl. Algebra 117/118, 469–493 (1997) Algorithms for algebra (Eindhoven, 1996) Mourrain, B., Pan, V. Y.: Solving special polynomial systems by using structured matrices and algebraic residues. In: Foundations of computational mathematics (Rio de Janeiro, 1997), Springer, Berlin, 1997, pp. 287–304 Mourrain, B., Pan, V. Y.: Asymptotic acceleration of solving multivariate polynomial systems of equations. In: Proceedings STOC, ACM Press, 1998, pp. 488–496 Mourrain, B., Pan, V. Y.: Multivariate polynomials, duality, and structured matrices. J. Complexity 16(1), 110–180 (2000) Mourrain, B., Pan, V. Y., Ruatta, O.: Accelerated solution of multivariate polynomial systems of equations. SIAM J. Comput. 32(2), 435–454 (2003) Nakai, Y.: High order derivations. I. Osaka J. Math. 7, 1–27 (1970) Oberst, U.: The construction of Noetherian operators. J. Algebra 222(2), 595–620 (1999) Osborn, H.: Modules of differentials. II. Math. Ann. 175, 146–158 (1968) Paterson, M. S., Stockmeyer, L. J.: On the number of nonscalar multiplications necessary to evaluate polynomials. SIAM J. Comput. 2(1), 60–66, March 1973 Penfield, Jr. P., Spencer, R., Duinker, S.: Tellegen’s theorem and electrical networks. The M.I.T. Press, Cambridge, Mass.-London, 1970 Rouillier, F.: Solving zero-dimensional systems through the Rational Univariate Representation. Applicable Algebra in Engineering, Communication and Computing 9(5), 433–461 (1999) Saito, M., Sturmfels, B., Takayama, N.: Gröbner deformations of hypergeometric differential equations. Springer-Verlag, Berlin, 2000 Samuel, P.: Théorie algébrique des nombres. Hermann, 1971 Scheja, G., Storch, U.: Über Spurfunktionen bei vollständigen Durchschnitten. Journal für die reine und angewandte Mathematik 278/279, 174–190 (1975) Schost, É.: Sur la résolution des systèmes polynomiaux à paramètres. PhD thesis, École polytechnique, 2000 Schwartz, J. T.: Fast probabilistic algorithms for verification of polynomial identities. J. ACM 27(4), 701–717, October 1980 Shoup, V.: Fast construction of irreducible polynomials over finite fields. J. Symbolic Comput. 17(5), 371–391 (1994) Shoup, V.: Efficient computation of minimal polynomials in algebraic extensions of finite fields. In: Proceedings of the 1999 International Symposium on Symbolic and Algebraic Computation (Vancouver, BC), New York, 1999, pp. 53–58 ACM Strassen, V.: Gaussian elimination is not optimal. Numer. Math. 13, 354–356 (1969) Tellegen, B.: A general network theorem, with applications. Philips Research Reports 7, 259–269 (1952) Thiong~Ly., J.-A.: Note for computing the minimum polynomial of elements in large finite fields. In: Coding theory and applications (Toulon, 1988), Volume 388 of Lecture Notes in Comput. Sci., Springer, New York, 1989, pp. 185–192 von~zur Gathen, J., Gerhard, J.: Modern computer algebra. Cambridge University Press, New York, 1999 Wiedemann, D.: Solving sparse linear equations over finite fields. IEEE Transactions on informations theory IT-32, 54–62, 1986 Zippel, R.: Probabilistic algorithms for sparse polynomials. In: Symbolic and algebraic computation, number~72 in Lecture Notes in Computer Science, Berlin, 1979. Springer. Proceedings EUROSAM ‘79, Marseille, 1979, pp. 216–226