Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(2)
Generic Algorithm
Linear Algebra
Related Publications
(1)
Characterizations of border bases
Subscribe
Academic
Publications
Computing border bases
Computing border bases,10.1016/j.jpaa.2005.07.006,Journal of Pure and Applied Algebra,Achim Kehrein,Martin Kreuzer
Edit
Computing border bases
(
Citations: 17
)
BibTex

RIS

RefWorks
Download
Achim Kehrein
,
Martin Kreuzer
This paper presents several algorithms that compute border bases of a zerodimensional ideal. The first relates to the FGLM algorithm as it uses a linear basis transformation. In particular, it is able to compute border bases that do not contain a reduced Gröbner basis. The second algorithm is based on a
generic algorithm
by Bernard Mourrain originally designed for computing an ideal basis that need not be a border basis. Our fully detailed algorithm computes a border basis of a zerodimensional ideal from a given set of generators. To obtain concrete instructions we appeal to a degreecompatible term ordering σ and hence compute a border basis that contains the reduced σGröbner basis. We show an example in which this computation actually has advantages over Buchberger's algorithm. Moreover, we formulate and prove two optimizations of the Border Basis Algorithm which reduce the dimensions of the
linear algebra
subproblems.
Journal:
Journal of Pure and Applied Algebra  J PURE APPL ALG
, vol. 205, no. 2, pp. 279295, 2006
DOI:
10.1016/j.jpaa.2005.07.006
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.sciencedirect.com
)
(
linkinghub.elsevier.com
)
Citation Context
(6)
...This seriousness forced European researchers to study the socalled “border bases” [9,10,
5
], see also [2]...
Tateaki Sasaki
,
et al.
Term Cancellations in Computing FloatingPoint Gröbner Bases
...We also generalize the Border Basis Algorithm ([
9
]) to the approximate setting and study the approximate membership problem for zerodimensional polynomial ideals...
...there exist closeby polynomials which define an ideal I P such that dimR(P/I) > 0), find a border basis of the smallest nearby ideal I. The idea to solve this task is similar to the idea underlying the approximate BuchbergerM¨oller algorithm: use the SVD to make the usual border basis algorithm (see [
9
], Props...
...[
9
], Prop. 18) the vector space V is repeatedly replaced by...
...The last ingredient we need is an approximate version of the computation of a stable span explained in [
9
], Prop...
...Proof. The method of the proof of [
9
], Prop...
...Combining the preceding steps, we can formulate an approximate version of the Border Basis Algorithm [
9
], Prop...
...18 in [
9
] and to add the following observation: The set O of terms computed in step B6 is indeed an order ideal...
...As mentioned in [
9
], this algorithm can be optimized substantially...
...As mentioned in [9], this algorithm can be optimized substantially. In particular, the proof of [
9
], Prop...
...This result is in good numerical agreement with the exact result in [
9
], Ex. 20...
Daniel Heldt
,
et al.
Approximate computation of zerodimensional polynomial ideals
...Kehrein and Kreuzer, et al, gave characterizations of border bases in an algebraist’s view [7, 8]. Inspired by Faug`ere’s F4 and F5 [13, 14] and Mourrain’s generic algorithm [4], Kehrein and Kreuzer present an algorithm to compute border bases for zero dimensional ideals with respect to (abbr. w.r.t.) a specified term order [
10
]...
...We remark that for a zero dimensional ideal I, the border basis in our definition is the same as that of [1, 7,
10
] (with the relations discussed in remark 2.4)...
...As for the difference between our algorithms and Kehrein and Kreuzer’s, one could reference Example 19 in [
10
]...
Yufu Chen
,
et al.
Border bases of positive dimensional polynomial ideals
...The Approximate BuchbergerMller (ABM) algorithm is presented, a new algorithm derived from the classical BM algorithm  see [2], [8], and [1]  calculating Grbner , Border  see [4], [
5
]  and Macaulay  see [9], [10]  Basis for the Approximate Vanishing Ideal...
Hennie Poulisse
.
Computational communicative algebra
...At that time, the notion of border basis was not fully established, and the following articles provided the first concise framework: [17,
18
, 19, 22]...
...For an extensive coverage of border bases we refer to [19, 17,
18
, 22]...
...For an extensive coverage of border bases we refer to [19, 17, 18, 22]. Our exposition here follows that of [
18
]...
...Tn with tjLT(g) we have t 2 Og is a reduced ( )Gröbner basis [
18
]...
SEBASTIAN POKUTTA
,
et al.
ON THE CONNECTION OF THE SHERALIADAMS CLOSURE AND BORDER BASES
References
(11)
An elimination algorithm for the computation of all zeros of a system of multivariate polynomial equations
(
Citations: 85
)
W. Auzinger
,
H. J. Stetter
Published in 1986.
Efficient computation of zerodimensional Gr篓obner bases by change of ordering
(
Citations: 36
)
P. Gianni
,
D. Lazard
,
T. Mora
Journal:
Journal of Symbolic Computation  JSC
, 1989
Characterizations of border bases
(
Citations: 24
)
Achim Kehrein
,
Martin Kreuzer
Journal:
Journal of Pure and Applied Algebra  J PURE APPL ALG
, vol. 196, no. 2, pp. 251270, 2005
An algebraist’s view on border bases
(
Citations: 21
)
Achim Kehrein
,
Martin Kreuzer
,
Lorenzo Robbiano
Computational Commutative Algebra 2
(
Citations: 216
)
M. Kreuzer
,
L. Robbiano
Published in 2005.
Sort by:
Citations
(17)
Artificial discontinuities of singleparametric Gröbner bases
JeanCharles Faugère
,
Ye Liang
Journal:
Journal of Symbolic Computation  JSC
, vol. 46, no. 4, pp. 459466, 2011
Computing Border Bases without using a Term Ordering
Stefan Kaspar
Journal:
Computing Research Repository  CORR
, vol. abs/1104.2, pp. 113, 2011
Term Cancellations in Computing FloatingPoint Gröbner Bases
(
Citations: 1
)
Tateaki Sasaki
,
Fujio Kako
Conference:
Computer Algebra in Scientific Computing  CASC
, pp. 220231, 2010
An Algebraic View to Gradient Descent Decoding
M. Borges Quintana
,
M. A. Borges Trenard
,
I. MarquezCorbella
,
E. MartinezMoro
Published in 2010.
An Algebraic View to Gradient Descent Decoding
Mijail BorgesQuintana
,
Miguel A. BorgesTrenard
,
Irene Marquez Corbella
,
Edgar MartínezMoro
Journal:
Computing Research Repository  CORR
, vol. abs/1008.4, 2010