article

Free access

A theoretical basis for the reduction of polynomials to canonical forms

Author:

B. BuchbergerAuthors Info & Claims

ACM SIGSAM Bulletin, Volume 10, Issue 3

Pages 19 - 29

https://doi.org/10.1145/1088216.1088219

Published: 01 August 1976 Publication History

PDF eReader

Abstract

We define a certain type of bases of polynomial ideals whose usefulness stems from the fact that a number of computability problems in the theory of polynomial ideals (e.g. the problem of constructing canonical forms for polynomials) is reducible to the construction of bases of this type. We prove a characterization theorem for these bases which immediately leads to an effective method for their construction.

References

[1]

B. Buchberger, Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nuildimensionalen Polynomideal, Dissertation, Universität Innsbruck, 1965.

Google Scholar

[2]

B. Buchberger, Ein algorithmisches Kriterium für die Lösbarkeit eines algebraischen Gleichungssystems, Aequationes mathematicae, Vol. 4/3, S. 374--383, 1970.

Google Scholar

[3]

B. Buchberger, On Certain Bases of Polynomial ideals, Bericht Nr. 53, Institut für Mathematik, Universität Linz.

Google Scholar

[4]

W. Gröbner, Personal communication, Seminar d. institutes für Mathematik, Universität Innsbruck, 1964.

Google Scholar

[5]

M. Lauer, Canonical Representatives for Residue Classes of a Polynomial ideal, to appear in the Proceedings of the SIGSAM Conference 1976, ACM.

Digital Library

Google Scholar

[6]

R. Loos, Toward a Formal implementation of Computer Algebra, SIGSAM Bulletin, 8, p. 9--16, 1974.

Digital Library

Google Scholar

[7]

Z. Manna, Mathematical Theory of Computation, Mc Graw Hill, 1974.

Digital Library

Google Scholar

[8]

R. Schrader, Diplomarbeit, Math. Institut, Universität Karlsruhe, 1976.

Google Scholar

Cited By

View all

Cyphert JKincaid Z(2024)Solvable Polynomial Ideals: The Ideal Reflection for Program AnalysisProceedings of the ACM on Programming Languages10.1145/36328678:POPL(724-752)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632867
Aichinger E(2024)Strong Gröbner bases and linear algebra in multivariate polynomial rings over Euclidean domainsExpositiones Mathematicae10.1016/j.exmath.2024.12562742:6(125627)Online publication date: Dec-2024
https://doi.org/10.1016/j.exmath.2024.125627
Bonacina IBonet MLevy J(2024)Polynomial calculus for optimizationArtificial Intelligence10.1016/j.artint.2024.104208337(104208)Online publication date: Dec-2024
https://doi.org/10.1016/j.artint.2024.104208
Show More Cited By

Recommendations

Nonnegative Quadratic Forms and Bounds on Orthogonal Polynomials

We show that some nonnegative quadratic forms containing orthogonal polynomials, such as e.g. the Christoffel-Darboux kernel for x=y in the classical case, provide a lot of information about behavior of the polynomials on the real axis. We illustrate ...
Reduction of Permutation-Invariant Polynomials

Let R be a commutative ring with 1, let R X1, ,Xn /I be the polynomial algebra in the n 4 noncommuting variables X1, ,Xn over R modulo the set of commutator relations I={(X1+ +Xn) Xi=Xi (X1+ +Xn)|1 i n}. Furthermore, let G be an arbitrary group of ...
Effective Noether Irreducibility Forms and Applications
Selected papers of the 23rd annual ACM symposium on Theory of computing

Using recent absolute irreducibility testing algorithms, we derive new irreducibility forms. These are integer polynomials in variables which are the generic coefficients of a multivariate polynomial of a given degree. A (multivariate) polynomial over a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ACM SIGSAM Bulletin Volume 10, Issue 3

August 1976

36 pages

ISSN:0163-5824

DOI:10.1145/1088216

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 1976

Published in SIGSAM Volume 10, Issue 3

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

156
Total Citations
View Citations
883
Total Downloads

Downloads (Last 12 months)113
Downloads (Last 6 weeks)15

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Cyphert JKincaid Z(2024)Solvable Polynomial Ideals: The Ideal Reflection for Program AnalysisProceedings of the ACM on Programming Languages10.1145/36328678:POPL(724-752)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632867
Aichinger E(2024)Strong Gröbner bases and linear algebra in multivariate polynomial rings over Euclidean domainsExpositiones Mathematicae10.1016/j.exmath.2024.12562742:6(125627)Online publication date: Dec-2024
https://doi.org/10.1016/j.exmath.2024.125627
Bonacina IBonet MLevy J(2024)Polynomial calculus for optimizationArtificial Intelligence10.1016/j.artint.2024.104208337(104208)Online publication date: Dec-2024
https://doi.org/10.1016/j.artint.2024.104208
Bariant ABoeuf ALemoine AManterola Ayala IØygarden MPerrin LRaddum H(2024)The Algebraic FreeLunch: Efficient Gröbner Basis Attacks Against Arithmetization-Oriented PrimitivesAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68385-5_5(139-173)Online publication date: 18-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-68385-5_5
Ozdemir APailoor SBassa AFerles KBarrett CDillig I(2024)Split Gröbner Bases for Satisfiability Modulo Finite FieldsComputer Aided Verification10.1007/978-3-031-65627-9_1(3-25)Online publication date: 26-Jul-2024
https://doi.org/10.1007/978-3-031-65627-9_1
GUTNIK SSARUCHEV V(2023)INVESTIGATION OF THE INFLUENCE OF THE INFLUENCE OF CONSTANT TORQUE ON EQUILIBRIUM ORIENTATIONS OF A SATELLITE MOVING IN A CIRCULAR ORBIT WITH THE USE OF COMPUTER ALGERRA METHODSПрограммирование10.31857/S0132347423020103(27-32)Online publication date: 1-Jul-2023
https://doi.org/10.31857/S0132347423020103
Kincaid ZKoh NZhu S(2023)When Less Is More: Consequence-Finding in a Weak Theory of ArithmeticProceedings of the ACM on Programming Languages10.1145/35712377:POPL(1275-1307)Online publication date: 11-Jan-2023
https://dl.acm.org/doi/10.1145/3571237
Giesen JKahlmeyer PLaue SMitterreiter MNussbaum FStaudt C(2023)Mixed membership GaussiansJournal of Multivariate Analysis10.1016/j.jmva.2022.105141195(105141)Online publication date: May-2023
https://doi.org/10.1016/j.jmva.2022.105141
Gerlach MHerren FLang M(2023)tapir: A tool for topologies, amplitudes, partial fraction decomposition and input for reductionsComputer Physics Communications10.1016/j.cpc.2022.108544282(108544)Online publication date: Jan-2023
https://doi.org/10.1016/j.cpc.2022.108544
Cheung LZaki T(2023)An eigen-representation of the Navier–Stokes equationsJournal of Computational and Applied Mathematics10.1016/j.cam.2022.114921423:COnline publication date: 15-May-2023
https://dl.acm.org/doi/10.1016/j.cam.2022.114921
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Recommendations

Nonnegative Quadratic Forms and Bounds on Orthogonal Polynomials

Reduction of Permutation-Invariant Polynomials

Effective Noether Irreducibility Forms and Applications

Comments

Information

Published In

Publisher

Publication History

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations