Antonio Montes

   Departament de Matemàtica Aplicada II
   Universitat Politècnica de Catalunya (UPC)
   Edifici Omega
   Jordi Girona 1-3
   08034 Barcelona
   Spain
    e-mail: antonio.montes@upc.edu
    tel: + 34 93 4131 77 04 (Secretary: +34 93 41376 80)
    fax: + 34 93 413 77 01

Institutional links

Teaching

Courses in the period 1981-2006

  • Computer Algebra (Facultat de Matemàtiques i Estadística). 5th course. Mathematics
  • 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. Statistics
  • 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. Mathematics
  • Numerical Methods (Facultat d'Informàtica de Barcelona). 3rd course.
  • Analysis 2 (Facultat d'Informàtica de Barcelona). 2nd course.

Apunts d'Àlgebra Computacional. A. Montes. Available at Facultat de Matemàtiques i Estadística:

Research

Main subject of interest: Computer Algebra

See  RedEACA,  http://medicis.polytechnique.fr/  and  Computer Algebra Internet Resources page to find information about CA sites, mailing lists, news groups, courses, books, journals, events, and more information about Computer Algebra.

Some recent papers

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

Preprint. October 2009.

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.

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

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.

NEW  DPGB RELEASE 7.4 is now available.  Download dpgb7. (Maple 8)

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

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.

Jour. Symb. Comp. 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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
Math. & Comp. in Simul., 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.
Sigsam Bull., 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.
Sigsam Bull., 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: November 27, 2007)