×

Locating and counting equilibria of the Kuramoto model with rank-one coupling. (English) Zbl 1428.65003

Summary: The Kuramoto model describes synchronization behavior among coupled oscillators and enjoys successful application in a wide variety of fields. Many of these applications seek phase-coherent solutions, i.e., equilibria of the model. Historically, research has focused on situations where the number of oscillators, \(n\), is extremely large and can be treated as being infinite. More recently, however, applications have arisen in areas such as electrical engineering with more modest values of \(n\). For these, the equilibria can be located by finding the real solutions of a system of polynomial equations utilizing techniques from algebraic geometry. However, typical methods for solving such systems locate all complex solutions even though only the real solutions give equilibria. In this paper, we present an algorithm to locate only the real solutions of the model, thereby shortening computation time by several orders of magnitude in certain situations. This is accomplished by choosing specific equilibria representatives and the consequent algebraic decoupling of the system. The correctness of the algorithm (that it finds only and all the equilibria) is proved rigorously. Additionally, the algorithm can be implemented using interval methods, so that the equilibria can be approximated up to any given precision without significantly more computational effort. We also compare this solution approach to other computational algebraic geometric methods. Furthermore, analyzing this approach allows us to prove, asymptotically, that the maximum number of equilibria grows at the same rate as the number of complex solutions of a corresponding polynomial system. Finally, we conjecture an upper bound on the maximum number of equilibria for any number of oscillators, which generalizes the known cases and is obtained on a range of explicitly provided natural frequencies.

MSC:

65H14 Numerical algebraic geometry
14Q65 Geometric aspects of numerical algebraic geometry
34C15 Nonlinear oscillations and coupled oscillators for ordinary differential equations
68W30 Symbolic computation and algebraic computation
34C60 Qualitative investigation and simulation of ordinary differential equation models

Software:

Bertini; C-XSC; Macaulay2
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] J.A. Acebrón, L.L. Bonilla, C.J. Pérez Vicente, F. Ritort, and R. Spigler, {\it The Kuramoto model: A simple paradigm for synchronization phenomena}, Rev. Modern Phys., 77 (2005), pp. 137-185.
[2] J. Baillieul and C. Byrnes, {\it Geometric critical point analysis of lossless power system models}, IEEE Trans. Circuits Syst., 29 (1982), pp. 724-737. · Zbl 0523.93046
[3] K. Bar-Eli, {\it On the stability of coupled chemical oscillators}, Phys. D, 14 (1985), pp. 242-252.
[4] D.J. Bates, J.D. Hauenstein, A.J. Sommese, and C.W. Wampler, {\it Bertini: Software for Numerical Algebraic Geometry}, 2013, available at .
[5] J.C. Bronski, L. DeVille, and M.J. Park, {\it Fully synchronous solutions and the synchronization phase transition for the finite-N Kuramoto model}, Chaos, 22 (2012), 033133. · Zbl 1319.34053
[6] B. Buchberger, {\it Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal [An Algorithm for Finding the Basis Elements in the Residue Class Ring Modulo a Zero Dimensional Polynomial Ideal]}, Mathematical Institute, University of Innsbruck, Austria, 1965; English translation in J. Symbolic Comput., 41 (2006), pp. 475-511. · Zbl 1245.13020
[7] J. Canny and I. Emiris, {\it An efficient algorithm for the sparse mixed resultant}, in Proceedings of the 10th International Symposium on Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes, Lecture Notes in Comput. Sci. 673, Springer, Berlin, 1993, pp. 89-104. · Zbl 0789.65034
[8] Z. Charles and A. Zachariah, {\it Efficiently finding all power flow solutions to tree networks}, in Proceedings of the 55th Annual Allerton Conference on Communications, Control, and Computing, Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, 2017, paper ThD2.5.
[9] H. Chen, {\it Cascaded Stalling of Induction Motors in Fault-Induced Delayed Voltage Recovery (FIDVR)}, M.S. Thesis, Electrical and Computer Engineering (ECE) Department, University of Wisconsin-Madison, 2011. Available online at .
[10] T. Chen and D. Mehta, {\it On the network topology dependent solution count of the algebraic load flow equations}, IEEE Trans. Power Syst., to appear. Preprint version available online at .
[11] T. Chen, D. Mehta, and M. Niemerg, {\it A Network Topology Dependent Upper Bound on the Number of Equilibria of the Kuramoto Model}, preprint, , 2016.
[12] D. Cox, J. Little, and D. O’Shea, {\it Using Algebraic Geometry}, Springer-Verlag, New York, 2005. · Zbl 1079.13017
[13] D. Cox, J. Little, and D. O’Shea, {\it Ideals, Varieties, and Algorithms}, Springer International Publishing, Switzerland, 2015. · Zbl 1335.13001
[14] F. Dörfler and F. Bullo, {\it Synchronization and transient stability in power networks and nonuniform Kuramoto oscillators}, SIAM J. Control Optim., 50 (2012), pp. 1616-1642, . · Zbl 1264.34105
[15] F. Dörfler, M. Chertkov, and F. Bullo, {\it Synchronization in complex oscillator networks and smart grids}, Proc. Natl. Acad. Sci. USA, 110 (2013), pp. 2005-2010. · Zbl 1292.94185
[16] I. Emiris and B. Mourrain, {\it Matrices in elimination theory}, J. Symbolic Comput., 28 (1999), pp. 3-43. · Zbl 0943.13005
[17] D.R. Grayson and M.E. Stillman, {\it Macaulay2, A Software System for Research in Algebraic Geometry}, available at .
[18] R. Hammer, M. Hocks, U. Kulisch, and D. Ratz, {\it C\textup++ Toolbox for Verified Computing I: Basic Numerical Problems Theory, Algorithms, and Programs}, Springer-Verlag, Berlin, 1995. · Zbl 0828.68041
[19] J.D. Hauenstein, A.J. Sommese, and C.W. Wampler, {\it Regeneration homotopies for solving systems of polynomials}, Math. Comp., 80 (2011), pp. 345-377. · Zbl 1221.65121
[20] I.A. Hiskens and R.J. Davy, {\it Exploring the power flow solution space boundary}, IEEE Trans. Power Syst., 16 (2001), pp. 389-395.
[21] W. Krämer, {\it C-XSC: A powerful environment for reliable computations in the natural and engineering sciences}, in Proceedings of the 4th International Conference on Biomedical Engineering and Informatics (BMEI), Shanghai, 2011, pp. 2130-2134; software available at .
[22] Y. Kuramoto, {\it Self-entrainment of a population of coupled non-linear oscillators}, in Proceedings of the International Symposium on Mathematical Problems in Theoretical Physics, Kyoto University, Kyoto, Japan, 1975, Springer, Berlin, 1975, pp. 420-422. · Zbl 0335.34021
[23] Y. Kuramoto, {\it Chemical Oscillations, Waves, and Turbulence}, Springer, Berlin, 1984. · Zbl 0558.76051
[24] B.C. Lesieutre and D. Wu, {\it An efficient method to locate all the load flow solutions–Revisited}, in Proceedings of the 53rd Annual Allerton Conference on Communications, Control, and Computing, IEEE Press, Piscataway, NJ, 2015, pp. 381-388.
[25] W. Ma and S. Thorp, {\it An efficient algorithm to locate all the load flow solutions}, IEEE Trans. Power Syst., 8 (1993), 1077.
[26] F. Macaulay, {\it Some formulae in elimination}, Proc. London Math. Soc., 33 (1902), pp. 3-27. · JFM 34.0195.01
[27] D.K. Molzahn, M. Niemerg, D. Mehta, and J.D. Hauenstein, {\it Investigating the Maximum Number of Real Solutions to the Power Flow Equations: Analysis of Lossless Four-Bus Systems}, preprint, , 2016.
[28] D. Mehta, D.K. Molzahn, and K. Turitsyn, {\it Recent advances in computational methods for the power flow equations}, in Proceedings of the American Control Conference (ACC), 2016, pp. 1753-1765.
[29] D. Mehta, N.S. Daleo, F. Dörfler, and J.D. Hauenstein, {\it Algebraic geometrization of the Kuramoto model: Equilibria and stability analysis}, Chaos, 25 (2015), 053103. · Zbl 1374.34115
[30] D.K. Molzahn, B.C. Lesieutre, and H. Chen, {\it Counterexample to a continuation-based algorithm for finding all power flow solutions}, IEEE Trans. Power Syst., 28 (2013), pp. 564-565.
[31] D.K. Molzahn, D. Mehta, and M. Niemerg, {\it Toward topologically based upper bounds on the number of power flow solutions}, in Proceedings of the American Control Conference (ACC), 2016, pp. 5927-5932.
[32] A.P. Morgan and A.J. Sommese, {\it Coefficient-parameter polynomial continuation}, Appl. Math. Comput., 29 (1989), pp. 123-160. · Zbl 0664.65049
[33] J.C. Neu, {\it The method of near-identity transformations and its applications}, SIAM J. Appl. Math., 38 (1980), pp. 189-208, . · Zbl 0446.70015
[34] F.M.A. Salam, L. Ni, S. Guo, and X. Sun, {\it Parallel processing for the load flow of power systems: The approach and applications}, in Proceedings of the IEEE 28th Annual Conference on Decision and Control (CDC), 1989, pp. 2173-2178.
[35] A.J. Sommese and C.W. Wampler, {\it The Numerical Solution of Systems of Polynomials Arising in Engineering and Science}, World Scientific, River Edge, NJ, 2005. · Zbl 1091.65049
[36] H. Sompolinsky, D. Golomb, and D. Kleinfeld, {\it Global processing of visual stimuli in a neural network of coupled oscillators}, Proc. Natl. Acad. Sci. USA, 87 (1990), pp. 7200-7204.
[37] S.H. Strogatz, {\it From Kuramoto to Crawford: Exploring the onset of synchronization in populations of coupled oscillators}, Phys. D, 143 (2000), pp. 1-20. · Zbl 0983.34022
[38] B. Sturmfels, {\it Sparse elimination theory}, in Computational Algebraic Geometry and Commutative Algebra (Cortona, 1991), Sympos. Math. XXXIV, D. Eisenbud and L. Robbiano, eds., Cambridge University Press, Cambridge, UK, 1993, pp. 264-298. · Zbl 0837.13011
[39] K. Wiesenfeld, P. Colet, and S.H. Strogatz, {\it Frequency locking in Josephson arrays: Connection with the Kuramoto model}, Phys. Rev. E, 57 (1998), pp. 1563-1569.
[40] X. Xin, T. Kikkawa, and Y. Liu, {\it Analytical solutions of equilibrium points of the standard Kuramoto model: 3 and 4 oscillators}, in Proceedings of the American Control Conference (ACC), 2016, pp. 2447-2452.
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.