Functional programming concepts and straight-line programs in computer algebra

Mostrar todas las versiones(2)

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 (199...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Bruno, N., Heintz, J., Matera, G., Wachenchauzer, R.
Formato: JOUR
Materias:
Abstract machine
Polynomial equation solver
Symbolic computation
Algebra
Algorithms
Computer programming languages
Computer software
Polynomials
Semantics
Functional programming
Computer programming
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_03784754_v60_n6_p423_Bruno
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:paper_03784754_v60_n6_p423_Bruno
record_format dspace
spelling todo:paper_03784754_v60_n6_p423_Bruno2023-10-03T15:33:06Z Functional programming concepts and straight-line programs in computer algebra Bruno, N. Heintz, J. Matera, G. Wachenchauzer, R. Abstract machine Polynomial equation solver Symbolic computation Algebra Algorithms Computer programming languages Computer software Polynomials Semantics Functional programming Computer programming 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. Fil:Matera, G. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_03784754_v60_n6_p423_Bruno
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic Abstract machine
Polynomial equation solver
Symbolic computation
Algebra
Algorithms
Computer programming languages
Computer software
Polynomials
Semantics
Functional programming
Computer programming
spellingShingle Abstract machine
Polynomial equation solver
Symbolic computation
Algebra
Algorithms
Computer programming languages
Computer software
Polynomials
Semantics
Functional programming
Computer programming
Bruno, N.
Heintz, J.
Matera, G.
Wachenchauzer, R.
Functional programming concepts and straight-line programs in computer algebra
topic_facet Abstract machine
Polynomial equation solver
Symbolic computation
Algebra
Algorithms
Computer programming languages
Computer software
Polynomials
Semantics
Functional programming
Computer programming
description 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.
format JOUR
author Bruno, N.
Heintz, J.
Matera, G.
Wachenchauzer, R.
author_facet Bruno, N.
Heintz, J.
Matera, G.
Wachenchauzer, R.
author_sort Bruno, N.
title Functional programming concepts and straight-line programs in computer algebra
title_short Functional programming concepts and straight-line programs in computer algebra
title_full Functional programming concepts and straight-line programs in computer algebra
title_fullStr Functional programming concepts and straight-line programs in computer algebra
title_full_unstemmed Functional programming concepts and straight-line programs in computer algebra
title_sort functional programming concepts and straight-line programs in computer algebra
url http://hdl.handle.net/20.500.12110/paper_03784754_v60_n6_p423_Bruno
work_keys_str_mv AT brunon functionalprogrammingconceptsandstraightlineprogramsincomputeralgebra
AT heintzj functionalprogrammingconceptsandstraightlineprogramsincomputeralgebra
AT materag functionalprogrammingconceptsandstraightlineprogramsincomputeralgebra
AT wachenchauzerr functionalprogrammingconceptsandstraightlineprogramsincomputeralgebra
_version_ 1807318330481049600

Ejemplares similares