Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Buchberger's_algorithm> ?p ?o. }
Showing items 1 to 32 of
32
with 100 items per page.
- Buchberger's_algorithm abstract "In computational algebraic geometry and computational commutative algebra, Buchberger's algorithm is a method of transforming a given set of generators for a polynomial ideal into a Gröbner basis with respect to some monomial order. It was invented by Austrian mathematician Bruno Buchberger. One can view it as a generalization of the Euclidean algorithm for univariate GCD computation and of Gaussian elimination for linear systems.A crude version of this algorithm to find a basis for an ideal I of a polynomial ring R proceeds as follows:Input A set of polynomials F that generates IOutput A Gröbner basis G for I G := F For every fi, fj in G, denote by gi the leading term of fi with respect to the given ordering, and by aij the least common multiple of gi and gj. Choose two polynomials in G and let Sij = (aij / gi) fi − (aij / gj) fj (Note that the leading terms here will cancel by construction). Reduce Sij, with the multivariate division algorithm relative to the set G until the result is not further reducible. If the result is non-zero, add it to G. Repeat steps 1-4 until all possible pairs are considered, including those involving the new polynomials added in step 4. Output GThe polynomial Sij is commonly referred to as the S-polynomial, where S refers to subtraction (Buchberger) or Syzygy (others). The pair of polynomials with which it is associated is commonly referred to as critical pair.There are numerous ways to improve this algorithm beyond what has been stated above. For example, one could reduce all the new elements of F relative to each other before adding them. If the leading terms of fi and fj share no variables in common, then Sij will always reduce to 0 (if we use only fi and fj for reduction), so we needn't calculate it at all.The algorithm terminates because it is consistently increasing the size of the monomial ideal generated by the leading terms of our set F, and Dickson's lemma (or the Hilbert basis theorem) guarantees that any such ascending chain must eventually become constant. Unfortunately, it may take a very long time to terminate, corresponding to the fact that Gröbner bases can be extremely large. Thus, it has large storage requirements (space complexity). Also, the time complexity of the algorithm is doubly exponential in the input data, which implies that its worst-case behavior can be very slow.Further methods for computing Gröbner bases include the Faugère F4 algorithm, based on the same mathematics as the Buchberger algorithm, and involutive approaches, based on ideas from Differential algebra.".
- Buchberger's_algorithm wikiPageExternalLink Buchberger%27s_algorithm.
- Buchberger's_algorithm wikiPageID "696317".
- Buchberger's_algorithm wikiPageRevisionID "593013003".
- Buchberger's_algorithm hasPhotoCollection Buchberger's_algorithm.
- Buchberger's_algorithm id "p/b110980".
- Buchberger's_algorithm title "Buchberger algorithm".
- Buchberger's_algorithm title "Buchberger's Algorithm".
- Buchberger's_algorithm urlname "BuchbergersAlgorithm".
- Buchberger's_algorithm subject Category:Algebraic_geometry.
- Buchberger's_algorithm subject Category:Commutative_algebra.
- Buchberger's_algorithm subject Category:Computer_algebra.
- Buchberger's_algorithm subject Category:Rewriting_systems.
- Buchberger's_algorithm type Artifact100021939.
- Buchberger's_algorithm type Instrumentality103575240.
- Buchberger's_algorithm type Object100002684.
- Buchberger's_algorithm type PhysicalEntity100001930.
- Buchberger's_algorithm type RewritingSystems.
- Buchberger's_algorithm type System104377057.
- Buchberger's_algorithm type Whole100003553.
- Buchberger's_algorithm comment "In computational algebraic geometry and computational commutative algebra, Buchberger's algorithm is a method of transforming a given set of generators for a polynomial ideal into a Gröbner basis with respect to some monomial order. It was invented by Austrian mathematician Bruno Buchberger.".
- Buchberger's_algorithm label "Algorithme de Buchberger".
- Buchberger's_algorithm label "Buchberger's algorithm".
- Buchberger's_algorithm label "Buchberger-Algorithmus".
- Buchberger's_algorithm sameAs Buchberger-Algorithmus.
- Buchberger's_algorithm sameAs Algorithme_de_Buchberger.
- Buchberger's_algorithm sameAs m.033jys.
- Buchberger's_algorithm sameAs Q997962.
- Buchberger's_algorithm sameAs Q997962.
- Buchberger's_algorithm sameAs Buchberger's_algorithm.
- Buchberger's_algorithm wasDerivedFrom Buchberger's_algorithm?oldid=593013003.
- Buchberger's_algorithm isPrimaryTopicOf Buchberger's_algorithm.