Kac-Rice formulas and the number of solutions of parametrized systems of polynomial equations. (English) Zbl 1502.14145

Feliu, Elisenda; Sadeghimanesh, Amirhosein

Math. Comput. 91, No. 338, 2739-2769 (2022).

Consider a parametrized system of \(n\) polynomial equations in \(n\) variables \(f_{\kappa}(t)=0,\ t\in A,\ \kappa\in B\) with \(A\subseteq \mathbb{R}^n\) and \(B\subseteq \mathbb{R}^m.\) The problem approached in this paper is to partition the parameter space \(B\) into regions where the number of solutions to the system in \(A\) is \(0,1,2,\dots,\infty.\)
A case of interest is when such a system comes from the equilibrium solutions of a system of ODEs, for instance a system of ODEs modeling a network of chemical reactions. One can, in theory, resolve this problem employing quantifier elimination or Cylindrical Algebraic Decomposition, but this is already computationally unfeasible for small systems with three or four parameters and three or four variables. A numerical approach is welcome.
The authors propose and describe in details an approach using Kac-Rice formula. With this approach they are able to compute an approximated partition of the parameter space in boxes using Monte Carlo integrals. This technique is very useful and successful in concrete examples, as one can start with a very coarse partition and keep refining it where it is still computationally feasible in an iterative matter. A more refined partition “just” requires more computation.
The strategy can handle cases with a much larger number of parameters than the exact methods and the authors provide clear and concrete examples. The algorithms are implemented in several distinct programming languages and they discuss some of the computational difficulties and limitations.

Reviewer: Rick Rischter (Itajubá)

MSC:

14Q30	Computational real algebraic geometry
13P15	Solving polynomial systems; resultants
65C05	Monte Carlo methods
65D30	Numerical integration

Keywords:

Kac-Rice formula; polynomial system; parameter region; Monte Carlo integration; multistationarity

Software:

CoNtRol; MCKR

References:

[1]	R. J. Adler and J. E. Taylor. 2007. Random Fields and Geometry, 1st ed. Springer-Verlag, New York. · Zbl 1149.60003
[2]	Aliprantis, Charalambos D., Principles of Real Analysis, xiii+285 pp. (1981), North-Holland Publishing Co., New York-Amsterdam · Zbl 0472.28001
[3]	Auffinger, Antonio, Random matrices and complexity of spin glasses, Comm. Pure Appl. Math., 165-201 (2013) · Zbl 1269.82066
[4]	Aza\"{\i }s, Jean-Marc, Level Sets and Extrema of Random Processes and Fields, xii+393 pp. (2009), John Wiley & Sons, Inc., Hoboken, NJ · Zbl 1168.60002
[5]	C. P. Bagowski, J. Besser, C. R. Frey, and J. E. Ferrell. 2003. The JNK cascade as a biochemical switch in mammalian cells: Ultrasensitive and all-or-none responses, Curr. Biol. 13, no. 4, 315-320.
[6]	Basu, Saugata, Random fields and the enumerative geometry of lines on real and complex hypersurfaces, Math. Ann., 1773-1810 (2019) · Zbl 1423.14303
[7]	Basu, Saugata, Algorithms in real algebraic geometry, Algorithms and Computation in Mathematics, x+662 pp. (2006), Springer-Verlag, Berlin · Zbl 1102.14041
[8]	Bihan, Fr\'{e}d\'{e}ric, Lower bounds for positive roots and regions of multistationarity in chemical reaction networks, J. Algebra, 367-411 (2020) · Zbl 1453.92120
[9]	Bradford, Russell, Truth table invariant cylindrical algebraic decomposition, J. Symbolic Comput., 1-35 (2016) · Zbl 1351.68314
[10]	V. Chickarmane, C. Troein, U. A. Nuber, H. M. Sauro, and C. Peterson. 2006. Transcriptional dynamics of the embryonic stem cell switch, PLOS Comput. Biol. 9, no. 2, 123.
[11]	C. Conradi, E. Feliu, M. Mincheva, and C. Wiuf. 2017. Identifying parameter regions for multistationarity, PLOS Comput. Biol. 13, no. 10, 1005751.
[12]	Conradi, Carsten, Switching in mass action networks based on linear inequalities, SIAM J. Appl. Dyn. Syst., 110-134 (2012) · Zbl 1235.37034
[13]	Conradi, Carsten, Multistationarity in the space of total concentrations for systems that admit a monomial parametrization, Bull. Math. Biol., 4174-4209 (2019) · Zbl 1427.92039
[14]	C. Conradi and M. Mincheva. 2014. Catalytic constants enable the emergence of bistability in dual phosphorylation, J. R. S. Interface, 11, no. 95.
[15]	Corvez, Solen, Automated deduction in geometry. Using computer algebra tools to classify serial manipulators, Lecture Notes in Comput. Sci., 31-43 (2004), Springer, Berlin · Zbl 1202.68489
[16]	Cox, David A., Using algebraic geometry, Graduate Texts in Mathematics, xii+572 pp. (2005), Springer, New York · Zbl 1079.13017
[17]	P. Donnell, M. Banaji, A. Marginean, and C. Pantea. 2014. CoNtRol: an open source framework for the analysis of chemical reaction networks, Bioinformatics, 30, no. 11, 1633-1634.
[18]	Edelman, Alan, How many zeros of a random polynomial are real?, Bull. Amer. Math. Soc. (N.S.), 1-37 (1995) · Zbl 0820.34038
[19]	P. Ellison, M. Feinberg, H. Ji, and D. Knight, Chemical reaction network toolbox, version 2.2. Available online at http://www.crnt.osu.edu/CRNTWin, 2012.
[20]	England, Matthew, ISSAC’15-Proceedings of the 2015 ACM International Symposium on Symbolic and Algebraic Computation. Improving the use of equational constraints in cylindrical algebraic decomposition, 165-172 (2015), ACM, New York · Zbl 1346.68283
[21]	England, Matthew, Cylindrical algebraic decomposition with equational constraints, J. Symbolic Comput., 38-71 (2020) · Zbl 1432.68599
[22]	Evans, Steven N., The expected number of zeros of a random system of \(p\)-adic polynomials, Electron. Comm. Probab., 278-290 (2006) · Zbl 1130.60010
[23]	M. Feinberg, Chemical reaction network structure and the stability of complex isothermal reactors-II. Multiple steady states for networks of deficiency one, Chem. Eng. Sci. 43 (1988), no. 1, 1-25.
[24]	Feinberg, Martin, The existence and uniqueness of steady states for a class of chemical reaction networks, Arch. Rational Mech. Anal., 311-370 (1995) · Zbl 0853.92024
[25]	Feinberg, Martin, Foundations of chemical reaction network theory, Applied Mathematical Sciences, xxix+454 pp. (2019), Springer, Cham · Zbl 1420.92001
[26]	Feliu, Elisenda, The kinetic space of multistationarity in dual phosphorylation, J. Dynam. Differential Equations, 825-852 (2022) · Zbl 1496.92028
[27]	E. Feliu and C. Wiuf. 2013. A computational method to preclude multistationarity in networks of interacting species, Bioinformatics, 29, no. 18, 2327-2334.
[28]	E. Feliu and C. Wiuf. 2013. Simplifying biochemical models with intermediate species, J. R. Soc. Interface, 10, no. 87, 20130484. · Zbl 1278.92012
[29]	J. Gerhard, D. Jeffrey, and G. Moroz. 2010. A package for solving parametric polynomial systems, ACM Commun. Comput. Algebra, 43, no. 3-4, 61-72. · Zbl 1322.68281
[30]	J. Gunawardena, Chemical reaction network theory for in-silico biologists, Available online at http://vcp.med.harvard.edu/papers/crnt, 2003.
[31]	Hahn, T., Cuba-a library for multidimensional numerical integration, Comput. Phys. Comm., 78-95 (2005) · Zbl 1196.65052
[32]	Joshi, Badal, Atoms of multistationarity in chemical reaction networks, J. Math. Chem., 153-178 (2013) · Zbl 1352.92186
[33]	Kac, M., On the average number of real roots of a random algebraic equation, Bull. Amer. Math. Soc., 314-320 (1943) · Zbl 0060.28602
[34]	V. B. Kothamachu, E. Feliu, L. Cardelli, and O. S. Soyer. 2015. Unlimited multistability and boolean logic in microbial signalling, J. R. Soc. Interface, 12, no. 108, 20150234.
[35]	Lazard, Daniel, Solving parametric polynomial systems, J. Symbolic Comput., 636-667 (2007) · Zbl 1156.14044
[36]	Mayr, Ernst W., The complexity of the word problems for commutative semigroups and polynomial ideals, Adv. in Math., 305-329 (1982) · Zbl 0506.03007
[37]	Mayr, Ernst W., Dimension-dependent bounds for Gr\"{o}bner bases of polynomial ideals, J. Symbolic Comput., 78-94 (2013) · Zbl 1258.13032
[38]	M\"{u}ller, Stefan, Sign conditions for injectivity of generalized polynomial maps with applications to chemical reaction networks and real algebraic geometry, Found. Comput. Math., 69-97 (2016) · Zbl 1382.92272
[39]	K. M. Nam, B. M. Gyori, S. V. Amethyst, D. J. Bates, and J. Gunawardena. 2020. Robustness and parameter geography in post-translational modification systems, PLOS Comput. Biol. 16, no. 5, 1007573.
[40]	L. Nicolaescu, On the Kac-Rice formula, Available online at https://www.researchgate.net/publication/267039543_On_the_Kac-Rice_formula, 2014.
[41]	A. B. Owen, Monte Carlo theory, methods and examples, http://statweb.stanford.edu/ owen/mc/, 2013.
[42]	P\'{e}rez Mill\'{a}n, Mercedes, Chemical reaction systems with toric steady states, Bull. Math. Biol., 1027-1065 (2012) · Zbl 1251.92016
[43]	Rainal, A. J., Origin of Rice’s formula, IEEE Trans. Inform. Theory, 1383-1387 (1988) · Zbl 0672.60047
[44]	Rice, S. O., Mathematical analysis of random noise, Bell System Tech. J., 282-332 (1944) · Zbl 0063.06485
[45]	Rudin, Walter, Principles of Mathematical Analysis, International Series in Pure and Applied Mathematics, x+342 pp. (1976), McGraw-Hill Book Co., New York-Auckland-D\"{u}sseldorf · Zbl 0346.26002
[46]	Rudin, Walter, Real and Complex Analysis, xiv+416 pp. (1987), McGraw-Hill Book Co., New York · Zbl 0925.00005
[47]	A. H. Sadeghimanesh, Polynomial superlevel set representation of the multistationarity region of chemical reaction networks, Preprint, 2003.07764, 2020.
[48]	A. H. Sadeghimanesh and M. England, Improving algebraic tools to study bifurcation sequences of population models, CASC 2021 Extended Abstracts, Sirius Mathematics Centre https://siriusmathcenter.ru/pr_img/1918100371/20210914/13241784/Program_010w, 7-10, 2021.
[49]	Sadeghimanesh, AmirHosein, The multistationarity structure of networks with intermediates and a binomial core network, Bull. Math. Biol., 2428-2462 (2019) · Zbl 1417.92058
[50]	A. H. Sadeghimanesh and E. Feliu, MCKR implementation, version 1.0. Available online at http://doi.org/10.5281/zenodo.4085079, 2020.
[51]	A. H. Sadeghimanesh and E. Feliu, MCKR repository of computations, version 1.0.0. Available online at https://doi.org/10.5281/zenodo.4026954, 2020.
[52]	T. Shiraishi, S. Matsuyama, and H. Kitano. 2010. Large-scale analysis of network bistability for human cancers, PLOS Comput. Biol. 6 no. 7, 1000851.
[53]	Taylor, Jonathan E., Inference in adaptive regression via the Kac-Rice formula, Ann. Statist., 743-770 (2016) · Zbl 1337.62304
[54]	Wang, Liming, On the number of steady states in a multiple futile cycle, J. Math. Biol., 29-52 (2008) · Zbl 1141.92022
[55]	Ylvisarer, N. Donald, The expected number of zeros of a stationary Gaussian process, Ann. Math. Statist., 1043-1046 (1965) · Zbl 0139.34201