Antonio Montes

Modification of the latest grobcov.lib version

 

Descripción: Descripción: C:\Users\hmercade\Desktop\montes-small.JPG 
 
Antonio Montes

   Departament de Matemàtica Aplicada
   Universitat Politècnica de Catalunya (UPC) 
   Pau Gargallo, 14
   08028 Barcelona
   Spain
    e-mail: antonio.montes_at_upc.edu
    tel: + 34 93 4054436


Institutional links


Teaching

Courses in the period 1981-2013.

  • Computer Algebra (Facultat de Matemàtiques i Estadística). 5th course.
  • Calculus (Facultat d'Informàtica). 1st course.
  • Symbolic Computation Workshop (Facultat de Matemàtiques i Estadística).  Free in UPC.
  • Mathematical Methods 1 (Facultat de Matemàtiques i Estadística). 1st course.
  • Mathematics 1 (Facultat d'Informàtica de Barcelona). 1st course.
  • Discrete Mathematics (Facultat d'Informàtica de Barcelona). 2nd course.
  • Algebra (Facultat d'Informàtica de Barcelona). 1st course.
  • Algebra and Computing (Facultat de Matemàtiques i Estadística). 1st course.
  • Numerical Methods (Facultat d'Informàtica de Barcelona). 3rd course.
  • Analysis 2 (Facultat d'Informàtica de Barcelona). 2nd course.
  • Fonaments de Matemàtiques (Facultat d’Informàtica). 1st course.
  • Matemàtiques 2 (Facultat d’Informàtica). 1st course.

Àlgebra Computacional. Assignatura optativa de la Llicenciatura de Matemàtiques i Estadística de la Facultat de Matemàtiques i Estadística de la UPC.


Research

Main subject of interest: Computer Algebra


Last version N12 (2021) of the Singular library "grobcov.lib".

Download grobcov12.zip

The book "The Gröbner Cover" can be used as Manual of the library.

The new version of the library includes parametric locus and envelopes. 

The library contains procedures for computing:

- Comprehensive Groebner System (CGS, Kapur-Sun-Wang algorithm), see "Using Kapur-Sun-Wang Algorithm for the Gröbner Cover". A. Montes; Proc.  EACA 2012. (2012) p. 135-138.

- Canonical Groebner Cover of a parametric ideal, see "Gröbner Bases for Polynomial Systems with parameters". A. Montes, M.Wibmer; Jour.Symb.Comp. 45 (2010) 1391-1425.

- Canonical representation of constructible sets, see "Computing the canonical representation of constructible sets". J.M. Brunat, A.Montes; Math.Comput.Sci. (2016)10:165-178.

- Locus computation and taxonomy and applications to dynamic geometry, see "An Algorithm for Automatic Discovery of Algebraic Loci". F. Botana, A. Montes, T. Recio;

Comput.Aided-Design 56 (2014) 22-23.

- Envelope computation and applications (Published, in book "The Gröbner Cover", A. Montes). (2019)

- Automatic Deduction of Geometric Theorems (Published, in book "The Gröbner Cover", A. Montes). (2019)

To see instructions for the installation read the file  GC_ReadmeN12.pdf   

 

Presentation of the book “The Gröbner Cover”.  (revised)

Antonio Montes (2020)

Springer ACM Series. (January 2020), Mathematics in Computer Science.

                  ISSN 1661-8270 (print)  1661-8289 (Online)  (2020)

Paper:       http://link.springer.com/article/10.1007/s11786-019-00438-z

                  DOI      https://doi.org/10.1007/s1178

Slides:       ACA 2018 Slides

 

The Gröbner Cover.  (book)

Antonio Montes (2018)

Springer. Algorithms and Computation in Mathematics 27 (2018)

ISBN 978-3-030-03903-5                ISBN 978-3-030-03904-2   (eBook)

https://doi.org/10.107/978-3-030-03904-2 (e-Book)

https://www.springer.com/gp/book/9783030039035

This book gives a complete description of the Canonical Gröbner Cover, which is the most accurate algebraic method for discussing parametric polynomial systems. It also includes applications to Automatic Deduction of Geometric Theorems, Loci Computation and Envelopes. The Gröbner Cover It is the analogue, for parametric systems, of the Reduced Gröbner Basis for ordinary polynomial systems. It was described for the first time in  A. Montes, M. Wibmer, Gröbner bases for polynomials systems with parameters, Journal of Symbolic Computation 45 (2010) 1391-1425. The algorithms for computing the Gröbner Cover have also been developed by the author in collaboration with Hans Schönemann in the computer language Singular, in which the "grobcov.lib" library has been included. The book serves also as a kind of user manual for this library, as it contains many examples using the library, as well as comments. All the algorithms described in the book are implemented in the library.

Canonical Representation of Constructible Sets.  

Josep M. Brunat, Antonio Montes (2016)

Math. Comput. Sci (2016) 10:165-178. 

Abstract

Constructible sets are needed in many algorithms of Computer Algebra, particularly in the Gröbner Cover and other algorithms for parametric polynomial systems. In this paper we review the canonical form of constructible sets and give algorithms for computing it.

An Algebraic Taxonomy for Locus Computation in Dynamic Geometry.  

Miguel A. Abanades, Francisco Botana, Antonio Montes , Tomas Recio. (2014)

Computer-Aided Design 56 (2014) 22-33.

Abstract

The automatic determination of geometric loci is an important issue in Dynamic Geometry. In Dynamic Geometry systems, it is often the case that locus determination is purely graphical, producing an output that is not robust enough and not reusable by the given software. Moreover, extraneous objects are frequently appended to the true locus as side products of the locus determination process. In this paper, we propose a new method for locus computation in dynamic geometry. It provides an analytic, exact description of the sought locus, making possible a subsequent precise manipulation of this object by the system. Moreover, a complete taxonomy, cataloging the potentially di fferent kinds of geometric objects arising from the locus computation procedure, is introduced, allowing to easily discriminate these objects as either extraneous or as pertaining to the sought locus. Our technique takes profit of the recently developed GröbnerCover algorithm. The proposed method is illustrated through a webbased application prototype, showing that it has reached enough maturity as to be considered a practical option to be included in the next generation of dynamic geometry environments.

Software for Discussing Parametric Polynomial Systems: The Gröbner Cover.  

A. Montes and M. Wibmer. (2014)

Proceedings of Mathematical Software ICMS 2014, Seoul, August 5-9, (2014).

Lecture Notes in Computer Science LNCS 8592, p. 406-413. Springer.v

Abstract

We present the canonical GRöBNER COVER method for discussing parametric polynomial systems of equations. Its objective is to decompose the parameter space into subsets (segments) for which it exists a generalized reduced Gröbner basis in the whole segment with fixed set of leading power products on it. Wibmer's Theorem guarantees its existence. The GRöBNER COVER is designed in a joint paper of the authors, and the Singular grobcov.lib library [15] implementing it, is developed by Montes. The algorithm is canonic and groups the solutions having the same kind of properties into different disjoint segments. Even if the algorithms involved have high complexity, we show how in practice it is effective in many applications of medium difficulty. An interesting application to automatic deduction of geometric theorems is roughly described here, and another one to provide a taxonomy for exact geometrical loci computations, that is experimentally implemented in a web based application using the dynamic geometry software Geogebra, is explained in another session. 

Software Using the GRöBNER COVER for Geometrical Loci Computation and Classification.

M.A. Abánades, F. Botana, A. Montes, and T. Recio. (2014)

Proceedings of Mathematical Software ICMS 2014, Seoul, August 5-9, 2014.

Lecture Notes in Computer Science LNCS 8592, p. 492-499. Springer.

Abstract

We describe here a properly recent application of the GRöBNER COVER algorithm (GC) providing an algebraic support to Dynamic Geometry computations of geometrical loci. It provides a complete algebraic solution of locus computation as well as a suitable taxonomy allowing to distinguish the nature of the different components. We included a new algorithm LOCUS into the Singular grobcov.lib library for this purpose. A web prototype has been implemented using it in Geogebra. 

Generalizing the Steiner-Lehmus Theorem using the Gröbner Cover 

Antonio Montes, Tomás Recio. (2014)

Mathematics and Computers in Simulation, Vol. 104 (2014), 67-71.

Abstract

In this note we present an application of a new tool (the Gröbner cover method, to discuss parametric polynomial systems of equations) in the realm of automatic discovery of theorems in elementary geometry. Namely, we describe, through a relevant example, how the Gröbner cover algorithm is particularly well suited to obtain the missing hypotheses for a given geometric statement to hold true. We deal with the following problem: to describe the triangles that have at least two bisectors of equal length. The case of two inner bisectors is the well known, XIX century old, Steiner-Lehmus theorem, but the general case of inner and outer bisectors has been only recently addressed. We show how the Gröbner cover method automatically provides, while yielding more insight than through any other method, the conditions for a triangle to have two equal bisectors of whatever kind.

An Algorithm for Automatic Discovery of Algebraic Loci  

F. Botana, A. Montes, T.Recio  (2012)

Proceedings of ADG-2012, p. 53-59

We show how dynamic geometry (DG) systems can be enhanced by using computer algebra methods. In this paper we use different

Gröbner basis methods to compute geometrical loci and specially use the Gröbner Cover to define and compute normal and special

parts of geometrical loci, that can then be used inside DG programs, specially in GeoGebra.

The Singular grobcov.lib library implementing the algorithms in A. Montes, M. Wibmer, Gröbner Bases for Polynomial Systems with parameters, (JSC 45 (2010) 1391-1425). Given a parametric polynomial ideal, the function grobcov in the library computes the Gröbner Cover of the corresponding ideal that consist of a set of triplets (lpp,basis,segment) such that for every point in the segment, the basis is the reduced Gröbner basis of the specialized ideal and the lpp(set of leading power products of the basis) is fixed on the segment. The whole result is canonical and the segments are disjoint and locally closed.

Generalizing the Steiner-Lehmus Theorem using the Gröbner Cover

Antonio Montes, Tomás Recio. (2012)

ACA-2012. (2012) Sophia (Bulgaria). (submitted to Elsevier)

In this note we present an application of a new method (the Gröbner Cover method, to algorithmically discuss parametric polynomial systems of equations) in the realm of automatic discovery of theorems in elementary geometry. Namely, we describe how the Gröbner Cover is particularly well suited to yield the missing hypothesis for a given geometric statement to hold true. This is achieved by addressing the following problem: find those triangles that have at least two bisectors of equal length. The case of two inner bisectors is the well known, XIXth century old, Steiner-Lehmus theorem, but the general case of inner and outer bisectors has been only recently addressed. We will show how the Gröbner Cover method provides automatically more detail than any other method, the conditions for a triangle to have two equal bisectors of whatever kind, yielding more insight than through any other automatic method.


Using Kapur-Sun-Wang Algorithm for the Gröbner Cover.

Antonio Montes (2012)

Proceedings of EACA 2012. Ed.: J.R. Sendra, C. Villarino. Universidad de Alcalá de Henares. (2012) p. 135-138.

Kapur-Sun-Wang have recently developed a very efficient algorithm for computing Comprehensive Gröbner Systems that has moreover the required essential properties for being used as first step of the Gröbner Cover algorithm. We have implemented and adapted it inside the Singular grobcov library for computing the Gröbner Cover and there are evidences that it makes the canonical algorithm much more effective. In this note we discuss the performance of GC with KSW on a collection of examples.


La Columna de Matemática Computacional : Discusión de sistemas polinómicos con parámetros.

Antonio Montes. (2011)

La Gaceta de la RSME, 14:3, (2011), 527-544.

Prólogo de Tomás Recio

Se detalla brevemente el desarrollo histórico de los algoritmos para la discusión de sistemas de ecuaciones polinómicas con parámetros y se dan los elementos esenciales para comprender y poder utilizar el nuevo algoritmo del cubrimiento canónico de Gröbner (GröbnerCover) de un ideal paramétrico, introducido recientemente por el autor y por Michael Wibmer, de la Universidad de Aachen. A fin de que los no especialistas puedan comprender bien su significado e interés, antes de abordar el tema se hace una

introducción elemental a la teoría de las bases de Gröbner, que subyace a este nuevo algoritmo. Posteriormente se dan ejemplos donde puede apreciarse su utilidad para resolver problemas en los que aparecen ecuaciones polinómicas con parámetros.

ISSAC 2011. Software for computing the Gröbner cover.

Antonio Montes. (2011)

ACM Communication in Computer Algebra, 45, 180-182, (2011). DOI: 10:1145/2120270.2110178. ISSAC-2011.

The objective of this software presentation is to show the bahavior and applications of the Singular grobcov.lib that we have recently developed (Singular web) to compute the Gröbner cover of a parametric ideal.


ISSAC_2011_Slides.pdf. Download the slides of the talk, June 2011.

Slides presenting a Tutorial of the Singular grobcov.lib library at ISSAC-2011 in San José (California), June 2011.


Gröbner Bases for Polynomial Systems with parameters. Antonio Montes, Michael Wibmer. (2010)

Journal of Symbolic Computation 45 (2010) 1391-1425. doi:10.1016/j.jsc.2010.06.017

Gröbner bases are the computational method par excellence for studying polynomial systems. In the case of parametric polynomial systems one has to determine the reduced Gröbner basis in dependence of the values of the parameters. In this article we present the algorithm GröbnerCover which has as input a finite set of parametric polynomials and outputs a finite partition of the parameter space into locally closed subsets together with polynomial data, from which the reduced Gröbner basis for a given parameter point can immediately be determined. The partition of the parameter space is intrinsic and particularly simple if the system is homogeneous. The Singular library can be downloaded at the top at this web.


Gröbner Bases Tutorial: A Sampler of Recent Developments.  

David Cox  (2007)

Professor David Cox presented this Tutorial at ISSAC 2007. It contains an overview of the paper “Automatic Discovery of geometric theorems using MCCGS” by A. Montes and T. Recio.

Automatic discovery of geometry theorems using minimal canonical comprehensive Groebner systems. Antonio Montes, Tomás Recio. (2007)

ADG 2006, LNAI 4869, pp. 113-138, 2007.

The main idea in this paper is merging two techniques that have been recently developed. On the one hand, we consider MCCGS, standing for Minimal Canonical Comprehensive Groebner Systems, a recently introduced computational tool yielding “good” bases for ideals of polynomials over a field depending on several parameters, that specialize “well”, for instance, regarding the number of solutions for the given ideal, for different values of the parameters. The second ingredient concerns automatic theorem discovery in elementary geometry. Automatic discovery aims to obtain complementary hypotheses for a (generally false) geometric statement to become true. The paper shows how to use MCCGS for automatic discovering of theorems and gives relevant examples.

Minimal Canonical Comprehensive Gröbner System.

Montserrat Manubens, Antonio Montes.  (2009)

Journal of Symbolic Computation 44 (2009) 463-478.

This is the continuation of Montes' paper ``On the canonical discussion of polynomial systems with parameters". In this paper we define the Minimal Canonical Comprehensive Gröbner System of a parametric ideal and fix under which hypothesis it exists and is computable. An algorithm to obtain a canonical description of the segments of the Minimal Canonical CGS is given, completing so the whole MCCGS algorithm (implemented in Maple and Singular). We show its high utility for applications, like automatic theorem proving and discovering, and compare it with other existing methods. A way to detect a counterexample to deny its existence is outlined, although the high number of tests done give evidence of the existence of the Minimal Canonical CGS. 

This paper describes the principal new improvements in the DISPGB algorithm implemented in release 7.4 of dpgb74.mpl and in Singular.

 

On the canonical discussion of polynomial systems with parameters.

Antonio Montes.  (2006)
Preprint arXiv: AC/0601674. Preprint MA2-IR-06-00006

Given a parametric polynomial ideal I, the algorithm DISPGB,  introduced by the author in 2002, builds up a binary tree describing a dichotomic discussion of the different reduced Groebner bases depending on the values of the parameters. An improvement using a discriminant ideal to rewrite the tree was described by  Manubens and the author in 2005. In this paper we describe how to iterate the use of discriminants to rebuild the tree and show that this leads to an ascending discriminant chain of ideals, and the corresponding descending chain of varieties in the parameter space providing a diff-specification of the cases. From it we show that it is possible to construct canonical specifications of each diff-specification. We also prove the conjectures formulated in the previous paper.

This paper describes the principal new improvements in the DISPGB algorithm implemented in the next release 5.0 of dpgb50.mpl. This release contains further improvements that are described in a new preprint in preparation.



Some Composition Determinants 

Josep M. Brunat, Christian Krattenthaler, Alain Lascoux, Antonio Montes. (2006)
Linear Algebra and Applications. 416 (2006) 355-364. Preprint in arXiv: CO/0509157. Preprint MA2-IR-06-00005

We compute two parametric determinants in which rows and columns are indexed by compositions,
where in one determinant the entries are products of binomial coefficients, while in the other the entries
are products of powers. These results generalize previous determinant evaluations due to the first and
third author [SIAM J. Matrix Anal. and Appl. 23 (2001), 459-471] and [``A polynomial
generalization of the power-compositions determinant," {Linear and Multilinear Algebra (to appear)],
and they prove two conjectures of the second author [``Advanced determinant calculus: a complement,"
preliminary version].



 A polynomial generalization of the power-compositions determinant.  

Josep M. Brunat, Antonio Montes.  (2007)
Linear and Multilinear Algebra 55-4 (2007) 303-313. arXiv: math.CO/0601756. Preprint MA2-IR-06-00005

Let C(n,p) be the set of p-compositions of an integer n, i.e., the set of p-tuples alpha = (alpha_1, .. , alpha_p) of nonnegative integers such that
alpha
_1 + .. + alpha_p  =  n, and x = (x_1, .. ,x_p) a vector of indeterminates.  For alpha and beta two p-compositions of n, define
( x + alpha)^beta =  (x_1+alpha_1)^beta_1 ·.. ·(x_p+alpha_p)^beta_p.  In this paper we prove an explicit formula for the determinant
det (x+alpha)^beta. In the case x_1 = .. = x_p the formula gives a positive answer to a conjecture  by C.  Krattenthaler.



Improving DISPGB algorithm using the discriminant ideal. 

Montserrat Manubens, Antonio Montes.  (2006)
Journal of Symbolic Computation. 41 (2006) 1245-1263. Extended Abstract in A3L-2005 Proceedings (2005).  Preprint: arXiv: math.AC/0601763. Preprint MAII-IR-04-00015, (2004).

 In 1992, V. Weispfenning proved the existence of Comprehensive Gröbner Bases (CGB) and gave an algorithm to compute one. That algorithm was not very efficient and not canonical. Using his suggestions, A. Montes obtained in 2002 a more efficient algorithm (DISPGB) for Discussing Parametric Gröbner Bases. Inspired in its philosophy, V. Weispfenning defined, in 2002, how to obtain a Canonical Comprehensive Gröbner Basis (CCGB) for parametric polynomial ideals, and provided a constructive method.
In this paper we use Weispfenning's CCGB ideas to make substantial improvements on Montes DISPGB algorithm. It now includes rewriting of the discussion tree using the Discriminant Ideal and provides a compact and effective discussion. We also describe the new algorithms in the DPGB library containing  the improved DISPGB as well as new routines to check whether a given basis is a CGB or not, and to obtain a CGB. Examples and tests are also provided.

Improving DisPGB algorithm for parametric Gröbner bases 

Montserrat Manubens, Antonio Montes.  (2004)
Extended Abstract in Actas de EACA-2004.

We present important improvements and a thorough redesign of the algorithm DisPGB in the new release 2.1 of the  DPGB Maple library for discussing Gröbner bases with parameters. DisPGB20 provides a more compact tree discussion, avoiding incompatible branches, and producing simpler output bases. The new software is more efficient and robust and can increase the speed up to 20 times with respect to the old release.

On polynomial digraphs 

Josep M. Brunat and Antonio Montes.  (2006)
Discrete Mathematics 306-4 (2006), 401-412 .
doi: 10.1016/j.disc.2006.01.001 arXiv: math.AC/0601731. Preprint MAII-IR-04-00007, (Mai 2004). Extended Abstract in Actas de EACA-2004, Santander. 

Let Phi(x,y) be a bivariate polynomial with complex coefficients. The zeroes of Phi(x,y) are given a combinatorial structure by  considering them as arcs of a directed graph G(Phi). This paper studies the relationship between  the polynomial Phi(x,y) and the structure of G(Phi).

The Characteristic Ideal of a Finite, Connected Regular Graph 

Josep M. Brunat, Antonio Montes.  (2004)
ISSAC 2004 Proceedings, ACM (2004) 50-57, Santander. arXiv: math.AC/0601733

Let  Phi(x,y)  be  be a symmetric polynomial in  C[x,y] of partial  degree d. The   graph G(Phi) is defined by taking C as set of vertices  and the points of   V(Phi(x,y)) as edges. We study the following  problem: given a finite, connected, d-regular graph H, find the  polynomials Phi(x,y) such that G(Phi) has some connected   component isomorphic to H and, in this case, if G(Phi) has (almost)  all components isomorphic to H. The problem is solved by associating to  H a characteristic ideal which offers a new perspective to the conjecture formulated in a previous paper, and allows to reduce its scope.  In the second part, we determine the characteristic ideal  for cycles of lengths less than 6 and for complete graphs of order 6. This results provide new evidence for the conjecture.

A new algorithm for discussing Gröbner bases with parameters.  

Antonio Montes.  (2002)
Journal of Symbolic Computation 33-2 (2002) 183-208

Let F be a set of polynomials in the variables x_1,...,x_n  with coefficients in R[a_1,..a_n], where R is a
UFD and  a_1,..,a_m a set of parameters. In this paper we present a new algorithm for discussing Gröbner bases with parameters. The algorithm obtains all the cases over the parameters leading to different reduced Gröbner basis, when the parameters in F are substituted in an extension field K of R. This new algorithm improves Weispfenning  CGB algorithm,  obtaining a reduced set of compatible and disjoint cases. A final improvement determines the minimal singular variety outside of which the Gröbner basis specializes properly (generic case). These constructive methods provide a very satisfactory discussion with rich geometrical interpretation in the applications.


The power-composition determinant and its application to global optimization. 

Josep M. Brunat, Antonio Montes. (2001)
SIAM J. Matrix Anal. Appl.  23-2 (2001)  459-471.
Preprint in Actas de EACA-2000, Barcelona, September, 2000.

Let C(n,p) be the set of p-compositions of an integer n, i.e., the set of p-tuples alpha = (alpha_1,..,alpha_p) of nonnegative integers such that alpha_1 +..+ alpha_p = n. The main result of this paper is an explicit formula for the determinant of the matrix whose entries are alpha^{beta} = alpha_1^{beta_1} .. alpha_p^{beta_p} where alpha,beta  belong to C(n,p). The formula shows that the determinant is positive and has a nice factorization. As an application, it is
shown that the polynomials p_alpha(x) = (alpha_1 x_1+ .. + alpha_p x_p)^n  with  alpha in C(n,p) form a basis of the vector space H_n[x_1, .. ,x_p] of homogeneous polynomials of degree n  in p  variables. The result is of interest in the context of global optimization because it allows an explicit representation of polynomials as a difference of convex functions.  


Basic Algorithms for Specialization in Groebner Bases.  

Antonio Montes . (1999).
Actas de EACA-99. Tenerife, September 1999.

Some basic algorithms for dealing with Groebner bases with parametres are given. They allow to construct a general algorithm for a general discussion of polynomial systems with parametrs that improves the Comprehensive Groebner Basis Algorithm of Weisfenning. The complete algorithm will be given in a forthcoming paper.


Algebraic solution of the load-flow problem for a 4-nodes electrical network. 

Antonio Montes. (1998)
Mathematics & Computer in Simulation, 45 (1998) 163-174.

Using algebraic techniques to triangulate polynomial systems of equations we are able to do it for the system describing a complete four-nodes electrical network with all the paramters. The advantages of the algebraic solution compared to the numerical one are discussed.


Solving the Load Flow Problem Using the Groebner Basis.  

Antonio Montes, Jordi Castro.  (1995)
Sigsam Bulletin, 29-1 (1995) 1-13.

The load-flow problem must be solved in Electrical Engeenering very often with different values of the parameters. Theoretically, it is interessting to obtain a general solution for all values of the parameters using Gröbner basis. In this paper we compute it for a 3-nodes general network and compare the results and conditioning with usual numerical computations.


Numerical Conditioning of a System of Algebraic Equations with a Finite Number of Solutions Using Groebner Bases.   

Antonio Montes. (1993)
Sigsam Bulletin, 27-1 (1993) 12-19.

Numerical conditioning for the problem and for the algorithm in computing the roots of a 0-dimensional polynomial system are given and applied to examples triangularized using Groebner bases.


(Last update of this page: May 2020)