Skip to main content
SpringerLink
Log in

Gröbner Bases and Systems Theory

  • Published:
Multidimensional Systems and Signal Processing Aims and scope Submit manuscript

Abstract

We present the basic concepts and results of Gröbner bases theory for readers working or interested in systems theory. The concepts and methods of Gröbner bases theory are presented by examples. No prerequisites, except some notions of elementary mathematics, are necessary for reading this paper. The two main properties of Gröbner bases, the elimination property and the linear independence property, are explained. Most of the many applications of Gröbner bases theory, in particular applications in systems theory, hinge on these two properties. Also, an algorithm based on Gröbner bases for computing complete systems of solutions (“syzygies”) for linear diophantine equations with multivariate polynomial coefficients is described. Many fundamental problems of systems theory can be reduced to the problem of syzygies computation.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. B. Buchberger, An Algorithm for Finding the Bases Elements of the Residue Class Ring Modulo a Zero Dimensional Polynomial Ideal(German), Phd thesis, Univ. of Innsbruck (Austria), 1965.

    Google Scholar 

  2. B. Buchberger, “An Algorithmical Criterion for the Solvability of Algebraic Systems of Equations (German),” Aequationes Mathematicae, vol. 4, no. 3, 1970, pp. 374–383. English translation in [25].

    Google Scholar 

  3. M. Kreuzer, and L. Robbiano, Computational Commutative Algebra I, Springer Verlag, New York, 2000.

    Google Scholar 

  4. S. Wolfram, The Mathematica Book, Cambridge University Press and Wolfram Research, Inc., New York, NY, USA and 100 Trade Center Drive, Champaign, IL 61820-7237, USA, fourth edition, 1999.

    Google Scholar 

  5. A. Capani, G. Niesi, and L. Robbiano, CoCoA, A System for Doing Computations in Commuatative Algebra, 1998, Available via anonymous ftp from cocoa.dima.uniqe.it.

  6. G.-M. Greuel, G. Pfister, and H. Schönemann, Singular Reference Manual, Reports On Computer Algebra, number 12, Centre for Computer Algebra, University of Kaiserslautern, 1997, http://www.mathematik. uni-kl.de/~zca/Singular.

  7. D. Grayson, and M. Stillman, Macaulay 2: A Software System for Algebraic Geometry and Commutative Algebra, Available over the web at http://www.math.uiuc.edu/Macaulay2.

  8. B. Buchberger, “Gröbner-Bases: An Algorithmic Method in Polynomial Ideal Theory,” In N. K. Bose (Ed.), Multidimensional Systems Theory, Dodrecht: Reidel Publishing Company, 1985, chapter 6, pp. 184–232.

    Google Scholar 

  9. U. Oberst, Multidimensional Constant Linear Systems, Acta Applicandae Mathematicae, vol. 20, 1990, pp. 1–175.

    Google Scholar 

  10. J. P. Guiver, and N. K. Bose, “Causal and Weakly Causal 2-D Filters with Applications in Stabilization,” In N. K. Bose (Ed.), Multidimensional System Theory, Dordrecht: Reidel, 1985, p. 52.

    Google Scholar 

  11. E. Fornasini, “A Note on Output Feedback Stabilizability of Multivariable 2D Systems,” Systems & Control Letters, vol. 10, 1998, pp. 45–50.

    Google Scholar 

  12. L. Xu, O. Saito, and K. Abe, “Bilateral Polynomial Matrix Equation in Two Indeterminates,” Multidimensional Systems and Signal Processing, vol. 1, no. 4, 1990, pp. 363–379.

    Google Scholar 

  13. A. Logar, and B. Sturmfels, “Algorithms for the Quillen-Suslin Theorem,” J. Algebra, vol. 145, 1992, pp. 231–239.

    Google Scholar 

  14. L. Xu, O. Saito, and K. Abe, “Output Feedback Stabilizability and Stabilization Algorithms for 2D Systems,” Multidimensional Systems and Signal Processing, vol. 5, 1994, pp. 41–60.

    Google Scholar 

  15. H. Park, and C. Woodburn, “An Algorithmic Proof of Suslin's Stability Theorem for Polynomial Rings,” J. Algebra, vol. 178, 1995, pp. 277–298.

    Google Scholar 

  16. H. Park, T. Kalker, and M. Vetterli, “Gröbner Bases and Multidimensional FIR Multirate Systems,” Multidimensional Systems and Signal Processing, vol. 8, no. 1/2, 1997, pp. 11–30.

    Google Scholar 

  17. L. Xu, J. Q. Ying, and O. Saito, “Feedback Stabilization for a Class of MIMO nD Systems by Gröbner Basis Approach,” In Abstract of First International Workshop on Multidimensional Systems, Poland, 1998, pp. 88–90.

  18. S. Basu, “Multi-dimensional Filter Banks and Wavelets - A System Theoretic Perspective,” J. Franklin Inst., vol. 335B, no. 8, 1998, pp. 1367–1409.

    Google Scholar 

  19. N. K. Bose, and C. Charoenlarpnopparut, “Multivariate Matrix Factorization: New Results,” In Mathematical Theory of Networks and Systems, Proceedings of MTNS-98, Podova, Italy, 1998, pp. 97–100.

    Google Scholar 

  20. C. Charoenlarpnopparut, and N. K. Bose, “Multidimensional Filter Bank Design Using Gro¨bner Bases,” IEEE Trans. on circuits and Systems II: Analog and Digital Signal Processing, vol. 46, December 1999, pp. 1475–1486.

  21. H. Pillai, J.Wood, and E. Rogers, “Gröbner Bases and Constructive Multidimensional Behavioural Theory,” In Proc. of the Second International Workshop on Multidimensional Systems, Poland, 2000, pp. 83–89.

  22. Z. Lin, On Syzygy Modules for Polynomial Matrices, Liner Algebra and Its Applications, vol. 298, 1999, pp. 73–86.

    Google Scholar 

  23. Z. Lin, “Output Feedback Stabilizability and Stabilization of Linear n-D Systems,” In Multidimensional Signals, Circuits and Systems, Taylor & Francis, 2001, chapter 4, pp. 59–76.

  24. J. Wood, “Modules and Behaviours in nD Systems Theory,” Multidimensional Systems and Signal Processing, vol. 11, 2000, pp. 11–48.

    Google Scholar 

  25. B. Buchberger, and F. Winkler, eds. Gröbner Bases and Applications, volume 251 of London Mathematical Society Series. Proc. of the International Conference “33 Years of Groebner Bases.” Cambridge University Press, 1998.

  26. B. Buchberger, Introduction to Gröbner Bases, Cambridge University Press, 1998, pp. 3–31 in [25].

  27. B. Buchberger, T. Jebelean, F. Kriftner, M. Marin, E. Tomuţa and D. Văsaru, “A Survey on the Theorema Project,” In Wolfgang W. Küchlin (ed.), Proceedings of ISSAC' 97(the 1997 International Symposium on Symbolic and Algebraic Computation), July 21- 23, 1997, Maui, Hawaii, ACM Press, pp. 384–391, 1997.

    Google Scholar 

  28. B. Buchberger, C. Dupré, T. Jebelean, F. Kriftner, K. Nakagawa, D. Văsaru and W. Windsteiger, “The Theorema Project: A Progress Report,” In M. Kerber and M. Kohlhase (eds.), 8th Symposium on the Integration of Symbolic Computation and Mechanized Reasoning, St. Andrews, Scotland, August 6-7, Universität des Saarlandes, Germany, 2000, pp. 100–115.

    Google Scholar 

  29. W. Trinks, “On B. Buchberger's Method for Solving Systems of Algebraic Equations,” J. Number Theory, vol. 10. no. 4, 1978, pp. 475–488.

    Google Scholar 

  30. B. Buchberger, A Criterion for Detecting Unnecessary Reductions in the Construction of Gröbner Bases, In Edward W. Ng, editor, Proceedings of the International Symposium on Symbolic and Algebraic Manipulation (EUROSAM' 79), Marseille, France, volume 72 of Lecture Notes in Computer Science, Springer, 1979, pp. 3–21.

Download references

Author information

Authors and Affiliations

  1. Research Institute for Symbolic Computation, Johannes Kepler University, A4040, Linz, Austria

    Bruno Buchberger

Authors
  1. Bruno Buchberger
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Buchberger, B. Gröbner Bases and Systems Theory. Multidimensional Systems and Signal Processing 12, 223–251 (2001). https://doi.org/10.1023/A:1011949421611

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1011949421611

Search

Navigation