Kybernetika 54 no. 2, 289-303, 2018

A fast numerical test of multivariate polynomial positiveness with applications

Petr Augusta and Petra AugustováDOI: 10.14736/kyb-2018-2-0289


The paper presents a simple method to check a positiveness of symmetric multivariate polynomials on the unit multi-circle. The method is based on the sampling polynomials using the fast Fourier transform. The algorithm is described and its possible applications are proposed. One of the aims of the paper is to show that presented algorithm is significantly faster than commonly used method based on the semi-definite programming expression.


stability, multidimensional systems, positive polynomials, fast Fourier transforms, numerical algorithm


12D10, 47N70, 65T50, 65Y20


  1. A. Ali and M. Ali: Identification of Box-Jenkins model for spatially interconnected systems in closed-loop. Multidimensional Systems Signal Process. 28 (2016), 1-11.   DOI:10.1007/s11045-016-0462-8
  2. P. Augusta: A numerical test of positiveness on the unit circle based on the fast Fourier transform. In: Proc. 21st Mediterranean Conference on Control and Automation, 2013, pp. 1050-1054.   DOI:10.1109/med.2013.6608850
  3. P. Augusta: A simple method for stabilisation of (2+1)D systems. In: Proc. 8th International Workshop on Multidimensional Systems, 2013, pp. 163-167.   CrossRef
  4. P. Augusta and P. Augustová: On stabilisability of 2-D MIMO shift-invariant systems. J. Franklin Inst. 350 (2013), 2949-2966.   DOI:10.1016/j.jfranklin.2013.05.021
  5. P. Augusta, B. Cichy, K. Galkowski and E. Rogers: An unconditionally stable finite difference scheme systems described by second order partial differential equations. In: Proc. IEEE 9th International Workshop on Multidimensional Systems, 2015, pp. 134-139.   DOI:10.1109/nds.2015.7332655
  6. P. Augusta, B. Cichy, K. Galkowski and E. Rogers: An unconditionally stable approximation of a circular flexible plate described by a fourth order partial differential equation. In: Proc. 21st International Conference on Methods and Models in Automation and Robotics, 2016.   DOI:10.1109/mmar.2016.7575281
  7. P. Augusta and Z. Hurák: Distributed stabilisation of spatially invariant systems - positive polynomial approach. Multidimensional Systems Signal Process. 24 (2013), 3-21.   DOI:10.1007/s11045-011-0152-5
  8. N. K. Bose: Multidimensional Systems Theory - Progress, Directions and Open Problems in Multidimensional Systems. D. Riedel Publishing Company, 1985.   DOI:10.1007/978-94-009-5225-6
  9. N. K. Bose: Multidimensional Systems Theory and Applications. Second edition. Kluwer Academic Publishers, 2003.   CrossRef
  10. B. Cichy, K. Gałkowski and E. Rogers:     CrossRef
  11. B. Cichy, K. Gałkowski, E. Rogers and A. Kummert: An approach to iterative learning control for spatio-temporal dynamics using nD discrete linear systems models. Multidimensional Systems Signal Process. 22 (2011), 83-96.   DOI:10.1007/s11045-010-0108-1
  12. B. Cichy, L. Hladowski, K. Gałkowski, A. Rauh and H. Aschemann: Iterative learning control of an electrostatic microbridge actuator with polytopic uncertainty models. IEEE Trans. Control Systems Technol. 23 (2015), 2035-2043.   DOI:10.1109/tcst.2015.2394236
  13. J. W. Cooley and J. W. Tukey: An algorithm for the machine calculation of complex Fourier series. Mathematics of Computation 19 (1965), 297-301.   DOI:10.2307/2003354
  14. B. Dumitrescu: Sum-of-squares polynomials and the stability of discrete-time systems. In: Proc. Fourth International Workshop on Multidimensional Systems, 2005, pp. 223-228.   DOI:10.1109/nds.2005.195358
  15. B. Dumitrescu: Stability test of multidimensional discrete-time systems via sum-of-squares decomposition. IEEE Trans. Circuts Systems 53 (2006), 928-936.   DOI:10.1109/tcsi.2005.859624
  16. B. Dumitrescu: Positive Trigonometric Polynomials and Signal Processing Applications. Springer, 2007.   CrossRef
  17. B. Dumitrescu: Positivstellensatz for trigonometric polynomials and multidimensional stability tests. IEEE Trans. Circuits Systems 54 (2007), 353-356.   DOI:10.1109/tcsii.2006.890409
  18. B. Dumitrescu, B. C. Şicleru and R. Ştefan: Minimax design of adjustable FIR filters using 2D polynomial methods. In: Proc. IEEE International Conference on Acoustics, Speech and Signal Processing, 2009, pp. 3181-3184.   DOI:10.1109/icassp.2009.4960300
  19. D. Henrion and A. Garulli: Positive Polynomials in Control    CrossRef
  20. T. Kaczorek: Positive 1D and 2D Systems. Springer, London 2002.   DOI:10.1007/978-1-4471-0221-2
  21. T. Kaczorek: Selected Problems of Fractional Systems Theory. Springer, Berlin 2011.   CrossRef
  22. J. Löfberg: Yalmip - a toolbox for modeling and optimization in MATLAB. In: Proc. CACSD Conference, 2004.   DOI:10.1109/cacsd.2004.1393890
  23. MATLAB: version (R2017a). MathWorks, Natick 2017.   CrossRef
  24. W. Paszke: Analysis and Synthesis of Multidimensional System Classes Using Linear Matrix Inequality Methods. University of Zielona Góra Press, Zielona Góra 2005.   CrossRef
  25. R. Rabenstein and P. Steffen: Numerical iterative methods and repetitive processes. Multidimensional Systems Signal Process. 23 (2012), 163-183.   DOI:10.1007/s11045-010-0115-2
  26. J. Ramos and G. Mercère: Subspace algorithm for identifying separable in denominator 2-D systems with deterministic-stochastic inputs. Int. J. Control 89 (2016), 2584-2610.   DOI:10.1080/00207179.2016.1172258
  27. E. Rogers, K. Gałkowski and D. H. Owens: Control Systems Theory and Applications for Linear Repetitive Processes. Springer, 2007.   CrossRef
  28. E. Rogers, K. Gałkowski, W. Paszke, K. L. Moore, P. H. Bauer, L. Hladowski and P. Dabkowski: Multidimensional control systems - case studies in design and evaluation. Multidimensional Systems Signal Process. 26 (2015), 895-939.   DOI:10.1007/s11045-015-0341-8
  29. M. G. Strintzis: Test of stability of multidimensional filters. IEEE Trans. Automat. Control 24 (1977), 432-437.   DOI:10.1109/tcs.1977.1084368
  30. J. F. Sturm: Using SeDuMi 1.02, a Matlab toolbox for optimization over symmetric cones. Optimiz. Methods Software 11 (1999), 625-653.   DOI:10.1080/10556789908805766
  31. B. Sulikowski, K. Galkowski and A. Kummert: Proportional plus integral control of ladder circuits modeled in the form of two-dimensional (2D) systems. Multidimensional Systems Signal Process. 26 (2015), 267-290.   DOI:10.1007/s11045-013-0256-1
  32. B. Sulikowski, K. Galkowski and A. Kummert: Stability and stabilisation of active ladder circuits modeled in the form of two-dimensional (2D) systems. In: Proc. IEEE 9th International Workshop on Multidimensional Systems, 2015.   DOI:10.1109/nds.2015.7332654
  33. F. Zhang: The Schur Complement and its Applications. Springer, 2005.   DOI:10.1007/b105056