Volume 6, Issue 4 (Vol. 6, No. 4, 2020)
mmr 2020, 6(4): 549-562 |
Back to browse issues page
Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
Poukhajouei S, Goli S, Hashemi A. Border Basis of an Ideal of Points and its Application in Experimental Design and Regression. mmr 2020; 6 (4) :549-562
URL: http://mmr.khu.ac.ir/article-1-2879-en.html
URL: http://mmr.khu.ac.ir/article-1-2879-en.html
1- Isfahan university of Technology
2- Isfahan university of Technology ,amir.hashemi@cc.iut.ac.ir
2- Isfahan university of Technology ,
Abstract: (2522 Views)
Introduction
Border bases are a generalization of Gröbner bases for zero-dimensional ideals which have attracted the interest of many researchers recently. More precisely, border bases provide a new method to find a structurally stable monomial basis for the residue class ring of a polynomial ideal and this yields a special generating set for the ideal possessing many nice properties.
Given a finite set of points, finding the set of all polynomials vanishing on it (so-called either ideal of points or vanishing ideal of the set of points) has numerous applications in several fields in Mathematics and other sciences. In 1982, Buchberger and Möller proposed an algorithm to compute a Gröbner basis for an ideal of points. This algorithm proceeds by performing Gaussian elimination on a generalized Vandermonde matrix. In 2006, Farr and Gao presented an incremental algorithm to compute a Gröbner basis for an ideal of points. The main goal of their paper is to calculate a Gröbner basis for the vanishing ideal of any finite set of points under any monomial ordering, and for points with nontrivial multiplicities they adapt their algorithm to compute the vanishing ideal via Taylor expansions.
The method of border bases is a beneficial tool to obtain a set of polynomial models identified by experimental design and regression. The utilization of Gröbner bases theory in experimental design was introduced by Pistone and Wynn. However, using Gröbner bases we cannot find all possible models which form structure of an order ideal for an experiment. For example, if we consider the design {(-1,1),(1,1),(0,0),(1,0),(0,-1)}, the model {
} cannot be computed by Gröbner bases method. This fact is expected this method relies on monomial orderings.
Material and methods
In this paper, we first present the Buchberger-Möller and Farr-Gao algorithms and then by applying these algorithms, we describe an algorithm which computes a border basis for the ideal of points corresponding to the input set of points with nontrivial multiplicity. In addition, we focus on presenting different models related to an experiment by using the concept of monomial bases for the residue class ring of a polynomial ideal.
Results and discussion
As we mentioned earlier, Buchberger-Möller algorithm is an efficient algorithm to compute a Gröbner basis for an ideal of points. We describe a simpler presentation of this algorithm in which we use the function NormalForm which receives as input a linear polynomial p and a Gr
bner basis G = {
, . . . , 
} of linear polynomials in 
, . . . , 
and returns f and q=[
, . . . , 
] where f is the remainder of the division of p by G and p=
+· · ·+
+r. Furthermore, we compare the efficiency of this algorithm with the function VanishingIdeal of Maple.
Given a finite set of points, we consider the case in which some points in the set have nontrivial multiplicity. Based on the Farr-Gao algorithm, we prepare an algorithm that computes a border basis for the vanishing ideal of the finite set of points by using Taylor expansions.
Suppose that n is the number of factors in an experiment. An experimental design is a finite set
of points. The set of all polynomials vanishing at the design is called a design ideal.
Regression analysis is a useful statistical process for the investigation of relationships between a response (or dependent) variable and one or more predictor (or independent) variables. When there is more than one predictor variable in a regression model, the model is a multiple linear regression model which we can call polynomial model. Suppose a random sample of size n is given (then we have exactly n data points are observed from (Y,X). The expession
error?
is the model for multiple linear regression where
's are called slopes or regression coefficients. Also, representing the merged effects of the predictor variables on the response variable is called interaction effect. By using multiple linear regression, we can analyze models containing interaction effects. For example, let us consider the following model
+error.
By substituting
and 
, we have a multiple linear regression as follows
+error.
In addition, multiple R-squared or R2 is a statistical measure that states the square of the relationship between the predicted response value and response value. It should be noted that multiple R-squared is always any value between 0 and 1, where a value closer to 1 informing that a greater proportion of variance is computed for the model. Statistically, a high multiple R-squared shows a well-fitting regression model. Also in multiple regression, tolerance is used as an indicator of multicollinearity. Tolerance may be said to be the opposite of the coefficient of determination and is obtained as
. All other things equal, researchers desire higher levels of tolerance, as low levels of tolerance are known to affect adversely the results associated with a multiple regression analysis. The smaller the tolerance of a variable, the more redundant is its contribution to the regression (i.e., it is redundant with the contribution of other independent variables). In the regression equation, if the tolerance of any of the variables is equal to zero (or very close to zero), the regression equation cannot be evaluated (the matrix is said to be ill-conditioned in this case, and it cannot be inverted).
Conclusion
The following conclusions were drawn from this research.
Border bases are a generalization of Gröbner bases for zero-dimensional ideals which have attracted the interest of many researchers recently. More precisely, border bases provide a new method to find a structurally stable monomial basis for the residue class ring of a polynomial ideal and this yields a special generating set for the ideal possessing many nice properties.
Given a finite set of points, finding the set of all polynomials vanishing on it (so-called either ideal of points or vanishing ideal of the set of points) has numerous applications in several fields in Mathematics and other sciences. In 1982, Buchberger and Möller proposed an algorithm to compute a Gröbner basis for an ideal of points. This algorithm proceeds by performing Gaussian elimination on a generalized Vandermonde matrix. In 2006, Farr and Gao presented an incremental algorithm to compute a Gröbner basis for an ideal of points. The main goal of their paper is to calculate a Gröbner basis for the vanishing ideal of any finite set of points under any monomial ordering, and for points with nontrivial multiplicities they adapt their algorithm to compute the vanishing ideal via Taylor expansions.
The method of border bases is a beneficial tool to obtain a set of polynomial models identified by experimental design and regression. The utilization of Gröbner bases theory in experimental design was introduced by Pistone and Wynn. However, using Gröbner bases we cannot find all possible models which form structure of an order ideal for an experiment. For example, if we consider the design {(-1,1),(1,1),(0,0),(1,0),(0,-1)}, the model {
} cannot be computed by Gröbner bases method. This fact is expected this method relies on monomial orderings. Material and methods
In this paper, we first present the Buchberger-Möller and Farr-Gao algorithms and then by applying these algorithms, we describe an algorithm which computes a border basis for the ideal of points corresponding to the input set of points with nontrivial multiplicity. In addition, we focus on presenting different models related to an experiment by using the concept of monomial bases for the residue class ring of a polynomial ideal.
Results and discussion
As we mentioned earlier, Buchberger-Möller algorithm is an efficient algorithm to compute a Gröbner basis for an ideal of points. We describe a simpler presentation of this algorithm in which we use the function NormalForm which receives as input a linear polynomial p and a Gr
bner basis G = { , . . . , } of linear polynomials in , . . . , and returns f and q=[, . . . , ] where f is the remainder of the division of p by G and p=+· · ·++r. Furthermore, we compare the efficiency of this algorithm with the function VanishingIdeal of Maple. Given a finite set of points, we consider the case in which some points in the set have nontrivial multiplicity. Based on the Farr-Gao algorithm, we prepare an algorithm that computes a border basis for the vanishing ideal of the finite set of points by using Taylor expansions.
Suppose that n is the number of factors in an experiment. An experimental design is a finite set
of points. The set of all polynomials vanishing at the design is called a design ideal.Regression analysis is a useful statistical process for the investigation of relationships between a response (or dependent) variable and one or more predictor (or independent) variables. When there is more than one predictor variable in a regression model, the model is a multiple linear regression model which we can call polynomial model. Suppose a random sample of size n is given (then we have exactly n data points are observed from (Y,X). The expession
error?is the model for multiple linear regression where
's are called slopes or regression coefficients. Also, representing the merged effects of the predictor variables on the response variable is called interaction effect. By using multiple linear regression, we can analyze models containing interaction effects. For example, let us consider the following model+error.By substituting
and , we have a multiple linear regression as follows+error.In addition, multiple R-squared or R2 is a statistical measure that states the square of the relationship between the predicted response value and response value. It should be noted that multiple R-squared is always any value between 0 and 1, where a value closer to 1 informing that a greater proportion of variance is computed for the model. Statistically, a high multiple R-squared shows a well-fitting regression model. Also in multiple regression, tolerance is used as an indicator of multicollinearity. Tolerance may be said to be the opposite of the coefficient of determination and is obtained as
. All other things equal, researchers desire higher levels of tolerance, as low levels of tolerance are known to affect adversely the results associated with a multiple regression analysis. The smaller the tolerance of a variable, the more redundant is its contribution to the regression (i.e., it is redundant with the contribution of other independent variables). In the regression equation, if the tolerance of any of the variables is equal to zero (or very close to zero), the regression equation cannot be evaluated (the matrix is said to be ill-conditioned in this case, and it cannot be inverted). Conclusion
The following conclusions were drawn from this research.
- We present a simpler variant of Buchberger- Möller algorithm (which seems to be easier for the implementation issue) for computing a border basis for an ideal of points.
- We present an algorithm that incrementally computes a border basis for the vanishing ideal of any finite set of points in which some points have multiplicity.
- We provide good statistical polynomial models which are more suitable for practical applications due to the stability of border bases models compared with Gröbner bases models../files/site1/files/64/6.pdf
Keywords: Border basis, Ideal of points, Buchberger-Möller algorithm, Experimental design, Regression.
Type of Study: Original Manuscript |
Subject:
alg
Received: 2018/11/18 | Revised: 2021/02/13 | Accepted: 2019/03/2 | Published: 2021/01/29 | ePublished: 2021/01/29
Received: 2018/11/18 | Revised: 2021/02/13 | Accepted: 2019/03/2 | Published: 2021/01/29 | ePublished: 2021/01/29
Send email to the article author
| Rights and permissions | |
 |
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. |
