Artículo

La versión final de este artículo es de uso interno de la institución.
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

In this paper we present MILONGA, a language based on functional programming concepts, which was designed for the implementation of a new generation of nonterm-rewriting elimination algorithms for multivariate polynomial solving [J. Pure Appl. Alg. 124 (1998) 101-146; J. Pure Appl. Alg. 117/118 (1997) 277-317; Appl. Alg. Eng. Commun. Comput. 11 (4) (2001) 239-296; J. Complex. 17 (1) (2001) 154-211]. These new algorithms profit from an alternative representation of multivariate polynomials by means of straight-line programs [Algebraic complexity theory, in: Handbook of Theoretical Computer Science, Elsevier, Amsterdam, 1990, pp. 634-671 (Chapter 11); Algebraic complexity theory, in: Grundlehren der mathematischen Wissenschaften, Vol. 315, Springer, Berlin, 1997] allowing an exponential improvement of theoretical complexity - With respect to computing time and memory space - Upon traditional, term-rewriting procedures. There is a strong analogy between the way how these algorithms employ straight-line programs and the way how functional programming languages treat functions as first-class citizens. Taking advantage of this circumstance, the MILONGA language enables us to analyze the relevance of the functional programming paradigm for the particular kind of task of polynomial equation solving. The paper contains an exhaustive do-it-yourself description of the programming philosophy of MILONGA, of the development of its compiler, of the operational semantics of its run-time system and of the implementation of a couple of fundamental computer algebra procedures in this language. The practical efficiency of this philosophy and implementation is outlined by comparative benchmarking on significant test examples. © 2002 IMACS. Published by Elsevier Science B.V. All rights reserved.

Registro:

Documento: Artículo
Título:Functional programming concepts and straight-line programs in computer algebra
Autor:Bruno, N.; Heintz, J.; Matera, G.; Wachenchauzer, R.
Filiación:Departamento De Computación, Facultad De Matemática, Astronomía Y Física, Ciudad Universitaria, 5000 Córdoba, Argentina
Departamento De Matemática, Facultad De Ciencias Exactas Y Naturales, CONICET, 1428 Buenos Aires, Argentina
Departamento De Matemáticas, Estadística Y Computación, Facultad De Ciencias, Universidad De Cantabria, E-39071 Santander, Spain
Instituto De Desarrollo Humano, Universidad Nacional De General Sarmiento, Campus Universitario, J.M. Gutierrez 1150, Los Polvorines, 1613 Buenos Aires, Argentina
Departamento De Computación, Facultad De Ingeniería, Universidad De Buenos Aires, Paseo Colón 850, 1063 Buenos Aires, Argentina
Palabras clave:Abstract machine; Polynomial equation solver; Symbolic computation; Algebra; Algorithms; Computer programming languages; Computer software; Polynomials; Semantics; Functional programming; Computer programming
Año:2002
Volumen:60
Número:6
Página de inicio:423
Página de fin:473
DOI: http://dx.doi.org/10.1016/S0378-4754(02)00035-6
Título revista:Mathematics and Computers in Simulation
Título revista abreviado:Math Comput Simul
ISSN:03784754
CODEN:MCSID
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03784754_v60_n6_p423_Bruno

Referencias:

  • Abdeljaoued, J., The Berkowitz algorithm, maple and computing the characteristic polynomial in an arbitrary commutative ring (1997) Comput. Alg.: Maple Tech. Newslett., 4 (3), pp. 21-32
  • Aho, A., Sethi, R., Ullman, J., (1986) Compilers - Principles, Techniques and Tools, , Addison-Wesley, Reading, MA
  • Berz, M., Bischof, C., Corliss, G., Griewank, A., Computational differentiation: Techniques, applications, and tools (1996) SIAM Proceedings Series List, , SIAM, Philadelphia
  • Bird, R., (1998) Introduction to Functional Programming Using Haskell, 2nd Edition, , Prentice-Hall, Englewood Cliffs, NJ
  • Bruno, N., (1998) Esquemas de compilación de circuitos aritméticos uniformes representados por medio de funciones generatrices, , Master's Thesis, FaMAF, Universidad de Córdoba, Argentina
  • Canny, J., A toolkit for nonlinear algebra (1994) Proceedings of the Workshop on the Algorithmic Foundations of Robotics (WAFR'94), , K. Goldberg (Ed.), San Francisco, CA, 17-19 February, ACM SIGSAM, SAME, A.K. Peters, Wellesley, MA, 1995
  • Castaño, B., Heintz, J., Llovet, J., Martínez, R., On the data structure straight-line program and its implementation in symbolic computation (2000) Math. Comput. Simulat., 51, pp. 497-528
  • Cohen, H., A course in computational algebraic number theory (1993) Graduate Texts in Mathematics, 138. , Springer, Berlin
  • Davenport, J., Siret, Y., Tournier, E., (1993) Computer Algebra: Systems and Algorithms for Algebraic Computation, , Academic Press, San Diego
  • Diaz, A., (1997) Foxbox: A system for manipulating symbolic objects in black box representation, , Ph.D. Thesis, Rensselaer Polytechnic Institute, New York
  • Faddeev, D., Faddeeva, V., (1963) Computational methods of linear algebra, , Freeman, San Francisco
  • Freeman, T.S., Imirzian, G.M., Kaltofen, E., Yagati, L., DAGWOOD - A system for manipulating polynomials given by straight-line programs (1988) ACM Trans. Math. Software, 14 (3), pp. 218-240
  • Giusti, M., Hägele, K., Heintz, J., Morais, J.E., Montaña, J.L., Pardo, L.M., Lower bounds for diophantine approximation (1997) J. Pure Appl. Alg., 117-118, pp. 277-317
  • Giusti, M., Hägele, K., Lecerf, G., Marchand, J., Salvy, B., The projective Noether Maple package: Computing the dimension of a projective variety (2000) J. Symb. Comput., 30 (3), pp. 291-307
  • Giusti, M., Heintz, J., La détermination des points isolés et de la dimension d'une variété algébrique peut se faire en temps polynomial (1993) Proceedings of the Symposia Matematica on Computational Algebraic Geometry and Commutative Algebra, 34, pp. 216-256. , D. Eisenbud, L. Robbiano (Eds.), Cambridge University Press, Cambridge
  • Giusti, M., Heintz, J., Morais, J.E., Morgenstern, J., Pardo, L.M., Straight-line programs in geometric elimination theory (1998) J. Pure Appl. Alg., 124, pp. 101-146
  • Giusti, M., Heintz, J., Morais, J.E., Pardo, L.M., When polynomial equation systems can be solved fast? (1995) Lecture Notes in Computer Science, 948, pp. 205-231. , G. Cohen, H. Giusti, T. Mora (Eds.), Proceedings of the AAECC-11 on Applied Algebra, Algebraic Algorithms and Error Correcting Codes, Springer, Berlin
  • Giusti, M., Lecerf, G., Salvy, B., A Gröbner free alternative for polynomial system solving (2001) J. Complex., 17 (1), pp. 154-211
  • Gonzalez-Vega, L., The needs of industry for polynomial system solving: A report from the frisco project (1998) SAC Newslett., 3, pp. 21-46
  • Griewank, A., Corliss, G., Automatic differentiation of algorithms: Theory, implementation, and application (1991) SIAM Proceedings Series List, , SIAM, Philadelphia
  • Heintz, J., Definability and fast quantifier elimination in algebraically closed fields (1983) Theor. Comput. Sci., 24 (3), pp. 239-277
  • Heintz, J., Krick, T., Puddu, S., Sabia, J., Waissbein, A., Deformation techniques for efficient polynomial equation solving (2000) J. Complex., 16 (1), pp. 70-109
  • Heintz, J., Matera, G., Waissbein, A., On the time-space complexity of geometric elimination procedures (2001) Appl. Alg. Eng. Commun. Comput., 11 (4), pp. 239-296
  • Heintz, J., Sieveking, M., Absolute primality of polynomials is decidable in random polynomial-time in the number of variables (1981) Lecture Notes in Computer Science, 115, pp. 16-28. , S. Even, O. Kariv (Eds.), Proceedings of the Eighth International Colloquium on Automata, Languages and Programming (ICALP'81), Acre (Akko), Israel, 13-17 July 1981
  • Heintz, J., Schnorr, C.P., Testing polynomials which are easy to compute (1982) Logic and Algorithmic, Monographie de l'Enseignement Mathématique, 30, pp. 237-254. , Université de Genève, Imprimerie Kundig, Genève
  • Hutton, G., Meijer, E., Functional pearls. Monadic parsing in Haskell (1998) J. Func. Program., 8 (4), pp. 437-444
  • Johnsson, T., (1987) Compiling lazy functional languages, , Ph.D. Thesis, Department of Computing Science, Chalmers University of Technology
  • Jones, R., Lins, R., Garbage collection (1996) Algorithms for Automatic Dynamic Memory Management, , Wiley, Chichester
  • Krick, T., Pardo, L.M., A computational method for diophantine approximation (1996) Progress in Mathematics, 143, pp. 193-254. , L. González-Vega, T. Recio (Eds.), Proceedings of MEGA'94 on Algorithms in Algebraic Geometry and Applications, Birkhäuser, Basel
  • Kronecker, L., Grundzüge einer arithmetischen theorie de algebraischen grössen (1882) J. Reine Angew. Math., 92, pp. 1-122
  • (2002) LiDIA, A library for computational number theory, , http://www.informatik.tu-darmstadt.de/Tl/LiDIA, TU Darmstodt
  • Mahajan, M., Vinay, V., Determinant: Old algorithms, new insight (1999) SIAM J. Discrete Math., 12 (4), pp. 474-490
  • Matera, G., Integration of multivariate rational functions given by straight-line programs (1995) Proceedings of the AAECC-11 on Applied Algebra, Algebraic Algorithms and Error Correcting Codes, 948. , G. Cohen, H. Giusti, T. Mora (Eds.), Lecture Notes in Computer Science, Springer, Berlin
  • Matera, G., (1997) Sobre la complejidad en espacio y tiempo de la eliminación geométrica, , Ph.D. Thesis, Universidad de Buenos Aires, Argentina
  • Matera, G., Probabilistic algorithms for geometric elimination (1999) Appl. Alg. Eng. Commun. Comput., 9 (6), pp. 463-520
  • Moses, J., Algebraic simplification: A guide for the perplexed (1971) Commun. ACM, 14, pp. 548-560
  • Pardo, L.M., How lower and upper complexity bounds meet in elimination theory (1995) Proceedings of the AAECC-11 on Applied Algebra, Algebraic Algorithms and Error Correcting Codes, 948. , G. Cohen, H. Giusti, T. Mora (Eds.), Lecture Notes in Computer Science, Springer, Berlin
  • Peterson, J., Hammond, K., (1997) Report on the programming language Haskell: A non-strict purely functional language, Version 1.4, , Department of Computer Science, Yale University
  • Rall, L., Corliss, G., An introduction to automatic differentiation (1996) Computational Differentiation: Technique, Applications, and Tools, SIAM Proceedings Series List, pp. 1-18. , M. Berz, C. Bischof, G. Corliss, A. Griewank (Eds.), SIAM, Philadelphia
  • Schwartz, J.T., Fast probabilistic algorithms for verification of polynomial identities (1980) J. Assoc. Comput. Mach., 27 (4), pp. 701-717
  • Schönhage, A., Strassen, V., Schnelle multiplikation großer zahlen (1971) Computing, 7, pp. 281-292
  • Strassen, V., Vermeidung von divisionen (1973) J. Reine Angew. Math, 264, pp. 182-202
  • Thompson, S., Haskell, (1999) The Craft of Functional Programming, 2nd Edition, , Addison-Wesley, Reading, MA
  • Wadler, P., Deforestation: Transforming programs to eliminate trees (1990) Theor. Comput. Sci., 73, pp. 231-248
  • Wadler, P., The essence of functional programming (1992) Proceedings of the 19th Symposium on Principles of Programming Languages, , ACM Press, Albuquerque
  • Wadler, P., Monads for functional programming (1995) Advanced Functional Programming, Lecture Notes in Computer Science, 925. , J. Jeuring, E. Meijer (Eds.), Springer, Berlin
  • Winkler, F., Polynomial algorithms in computer algebra (1996) Texts and Monographs in Symbolic Computation, , Springer, Wien
  • Zippel, R., Probabilistic algorithms for sparse polynomials (1979) Proceedings of the EUROSAM'79, 72, pp. 216-226. , Lecture Notes in Computer Science

Citas:

---------- APA ----------
Bruno, N., Heintz, J., Matera, G. & Wachenchauzer, R. (2002) . Functional programming concepts and straight-line programs in computer algebra. Mathematics and Computers in Simulation, 60(6), 423-473.
http://dx.doi.org/10.1016/S0378-4754(02)00035-6
---------- CHICAGO ----------
Bruno, N., Heintz, J., Matera, G., Wachenchauzer, R. "Functional programming concepts and straight-line programs in computer algebra" . Mathematics and Computers in Simulation 60, no. 6 (2002) : 423-473.
http://dx.doi.org/10.1016/S0378-4754(02)00035-6
---------- MLA ----------
Bruno, N., Heintz, J., Matera, G., Wachenchauzer, R. "Functional programming concepts and straight-line programs in computer algebra" . Mathematics and Computers in Simulation, vol. 60, no. 6, 2002, pp. 423-473.
http://dx.doi.org/10.1016/S0378-4754(02)00035-6
---------- VANCOUVER ----------
Bruno, N., Heintz, J., Matera, G., Wachenchauzer, R. Functional programming concepts and straight-line programs in computer algebra. Math Comput Simul. 2002;60(6):423-473.
http://dx.doi.org/10.1016/S0378-4754(02)00035-6