×

Some examples for solving systems of algebraic equations by calculating Gröbner bases. (English) Zbl 0602.65032

The paper presents a number of experiments with the algorithm of B. Buchberger for calculating Gröbner bases in the form described by F. Winkler, B. Buchberger, F. Lichtenberger and H. Rolletschek [ACM Trans. Math. Software 11, 66-78 (1985; Zbl 0575.68047)]. Fifteen sample systems of algebraic equations are considered involving different coefficient domains and problem types. This gives an illustration of the range and applicability as well as of the current limitations of the method. In particular, the results show that proper choices of the variable ordering and term ordering have a critical influence on the computation time and memory utilization. Some comments about ”optimal” variable orderings and the selection of valid solutions of the systems are presented.
Reviewer: W.C.Rheinboldt

MSC:

65H10 Numerical computation of solutions to systems of equations
65C20 Probabilistic models, generic numerical methods in probability and statistics

Citations:

Zbl 0575.68047

Software:

REDUCE
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Buchberger, B., Ein Algorithmus zum Auflinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal, PhD Thesis, University of Innsbruck (1965) · Zbl 1245.13020
[2] Buehberger, B., Ein algorithmisehes Kriterimn fuer die Loesbarkeit eines algebraischen Gleichungssystems, Aequ. Math., 4, 374-383 (1970)
[3] Buchberger, B., Groebner Bases: An Algorithmic Method in Polynomial Ideal Theory, (Bose, N. K., Progress, directions and open problems in multhlimensional systems theory (1985), Reidel: Reidel Dordrecht), 184-232 · Zbl 0587.13009
[4] Butcher, C. J., An application of the Runge Kutta space, BIT Computer Sciem’e Numerical Mcuhematies, 24, 425-440 (1984) · Zbl 0555.65045
[5] Collins, G. E.; Loos, R. G., SAC-2-Symbolie and Algebraic Computation version 2, a computer algebra system, ALDES-ALgorithm DEScription language, ACM SIGSAM Bulletin, 14, 2 (1980)
[6] Collins, G. E.; Loos, R. G., Real zeros of polynomials, (Buchberger, B.; Collins, G.; Loos, R., Computer algebra-symbolic and algebraic eontputatian (1982), Springer: Springer Vienna) · Zbl 0533.68038
[7] Ebert, G. L., Some comments on the modular approach to Groebner bases. ACM SIGSAM Bulletht 17, No., 2, 28-32 (1983) · Zbl 0527.13001
[8] Gebauer, R.; Kredel, H., Common distributive polynomial system, Technical Report, lnstitut fü Angewandte Mathematik, Universitiit Heidelberg (1983)
[9] Gebauer, R.; Kredel, H., Buehberger algorithm system, Technical Report, lnstitut für Angewandte Mathematik, Universitfit Heidelberg (1983), (see also ACM SIGSAM Bulletin 18, No. 1, 19)
[10] Gebauer, R.; Kredel, H., Real soution system.for algebraic equathms, Technical Report, Institut ffir Angewandte Matbematik, Universitiit Heidelberg (1984)
[11] Gebauer, R,; Kredel, H., A note to: “Solution of a general system of algebraic equations”. ACM SIGSAM Ballethl 18, No., 3, 5-6 (1984)
[12] Gerdt, V. P.; Shavaehka, A. B.; Zharkov, A., Computer algebra application for classification of integral non-linear evolution equations, J. Symbolic Computation, 1, 101-107 (1985) · Zbl 0577.35099
[13] Gonnet, G. H.; Char, B. W.; Geddes, K. O., Solution of a general system of equations. ACM SIGSAM Bullet#l 17, 4, No. 3, 48-49 (1983)
[14] Hearn, A. C., (REDUCE user’s manual, version 3.2. (1985), The Rand Corporation: The Rand Corporation Santa Monica)
[15] Henrici, P., Discrete variable methods of ordinary differential equations (1960), Wiley: Wiley New York · Zbl 0202.45201
[16] Kaltofen, E., Factorisation of polynomials, (Buchberger, B.; Collins, G.; Loos, R., Comnputer algebra—symbolic and algebraic computation (1982), Springer: Springer Vienna) · Zbl 0519.68059
[17] Raksanyi, A.; Walter, E., (Une application du calcul formel: le test des propriétés structurelles des modè1es d’état. Une application du calcul formel: le test des propriétés structurelles des modè1es d’état, Proceedings of CoJference “Algorithmique, Calcul Formel, Arithmétique” (1983), Publications de l’Université: Publications de l’Université de Saint-Etienne)
[18] Rose, M.; Gebauer, R.; KredeI, H.; Kung, l, H., Exemplifying the workability of the Buchberger algorithm for computation of general equilibrium by a model published in Shoven (1983) (1984), Departments of Economics and Applied Mathematics: Departments of Economics and Applied Mathematics University of Heidelberg
[19] Sehrader, R., Zur konstruktiven Idealtheorie (Diplomarbeit) (1976), Mathematisches Institiit II: Mathematisches Institiit II Université.t Karlsruhe
[20] Shoven, J. B., Applied general equilibrium tax modelling, IMF Staff Papers, 394-419 (1983)
[21] Stoer, J.; Bulirsch, R., Introcduction to numerical analysis (1979), Springer: Springer New York
[22] Trinks, W. L., Ueber Buchbergers Verfahren Systeme algebraischer Gleichungen zu loesen, J. Number Theor, 10, 475-488 (1978) · Zbl 0404.13004
[23] Trinks, W. L., On improving approximate results of Buchberger’s algorithm by Newton’s method. ACM SIGSAM Bulleth7 18, No., 3, 5-6 (1984)
[24] Wrinkler, F.; Buchberger, B.; Lichtenberger, F.; Rolletschek, H., An algorithm for constructing canonical bases (Groebner bases) of polynomial ideals, ACM/TOMS, 11, 66-78 (1985) · Zbl 0575.68047
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.