Functional programming concepts and straight-line programs in computer algebra

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

Detalles Bibliográficos
Autor principal: Matera, Guillermo
Publicado: 2002
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:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03784754_v60_n6_p423_Bruno
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 paper:paper_03784754_v60_n6_p423_Bruno
record_format dspace
spelling paper:paper_03784754_v60_n6_p423_Bruno2023-06-08T15:40:21Z Functional programming concepts and straight-line programs in computer algebra Matera, Guillermo 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. 2002 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03784754_v60_n6_p423_Bruno 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
Matera, Guillermo
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.
author Matera, Guillermo
author_facet Matera, Guillermo
author_sort Matera, Guillermo
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
publishDate 2002
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03784754_v60_n6_p423_Bruno
http://hdl.handle.net/20.500.12110/paper_03784754_v60_n6_p423_Bruno
work_keys_str_mv AT materaguillermo functionalprogrammingconceptsandstraightlineprogramsincomputeralgebra
_version_ 1768544598918955008

Ejemplares similares