Amœbas and structural stability of multidimensional systems: a test algorithm based on Monte-Carlo integration

Abstract

Given a Laurent polynomial $F \in \mathbb {C}[z_1^{\pm 1}, \ldots , z_n^{\pm 1}]$, its amœba $\mathcal A_F$ is the image by $z=(z_1, \ldots , z_n)\in (\mathbb {C}^*)^n \longmapsto (\log |z_1|, \ldots , \log |z_n|)\in \mathbb {R}^n$ of the algebraic zero set $V(F)=\{z\in (\mathbb {C}^*)^n\,;\, F(z)=0\}$ of the complex torus $\mathbb {T}^n :=(\mathbb {C}^*)^n$. We relate here the question of the BIBO stability of a multilinear discrete time invariant system with a regular transfer function $G(z_1, ..., z_n)/F(z_1, \ldots , z_n)$, where $F, G\in \mathbb {C}[z_1, ..., z_n]$ are coprime or more precisely structural stability, with the geometrical study of the amœba $\mathcal A_F$. A criterion for strong and weak structural stability is expressed in terms of the position of $\varvec{0}=(0, \ldots , 0)\in \mathbb {R}^n$ with respect to the amœba $\mathcal {A}_{F}$. Then we propose a Monte-Carlo integration based algorithm in order to test the structural stability of a given such system. The proposed algorithm is not limited by the curse of dimensionality, as opposed to the state-of-the-art methods: It can be applied to any number of variables n. Several illustrative examples are presented and discussed.

1 Introduction

Let $n\in \mathbb {N}$ and consider the set of multi-indexed complex-valued signals

$$\begin{aligned} \mathbb {C}^{[\mathbb {Z}^n]}:=\{ u=(u_{k})_{k\in \mathbb {Z}^n}: \mathbb {Z}^n \longmapsto \mathbb {C}\,;\, \text{ with } \text{ finite } \text{ support }\}. \end{aligned}$$

A multilinear discrete time invariant system S,

$$\begin{aligned} (u_k)_{k\in \mathbb {Z}^n} \in \mathbb {C}^{[\mathbb {Z}^n]} {\longmapsto } (v_k)_{k\in \mathbb {Z}^n} = S\{(u_k)_{k\in \mathbb {Z}^n}\} = \Big ( \sum \limits _{p \in \mathbb {Z}^n} h_p u_{k-p}\Big )_{k\in \mathbb {Z}^n} \end{aligned}$$

is said to be BIBO (Bounded-Input, Bounded-Output) stable if for a bounded input signal u, its output v is bounded. That is,

$$\begin{aligned} (u_{k})\in \ell _\mathbb {C}^{\infty }(\mathbb {Z}^{n}) \Longrightarrow (v_{k})\in \ell _\mathbb {C}^{\infty }(\mathbb {Z}^{n}). \end{aligned}$$

A fundamental theorem states that the system S is BIBO stable if and only if its impulse response $(h_k)_{k\in \mathbb {Z}^n}$ belongs to $\ell ^1_\mathbb {C}(\mathbb {Z}^n)$, that is

$$\begin{aligned} \sum _{k\in \mathbb {Z}^n} |h_k| < +\infty . \end{aligned}$$

(1)

One meets the problem of BIBO stability during the design of linear systems. Such systems find their applications in several practical areas related to signal processing (such as geophysics, medical imagery, processing of radar and sonar data) and to control theory (Benidir, 1991).

Since $\ell ^1_\mathbb {C}(\mathbb {Z}^n) \hookrightarrow \ell ^2_\mathbb {C}(\mathbb {Z}^n)$, condition (1) implies that $\sum \limits _{k\in \mathbb {Z}^n} |h_k|^2< +\infty$, which corresponds to the fact that the system S is asymptotically stable (or stationary). BIBO stability thus constitutes a stronger requirement than asymptotic stability.

In this paper, we are concerned with multilinear discrete time-invariant systems which admit a rational transfer function, as

$$\begin{aligned} \frac{B(z_1^{-1}, \ldots , z_n^{-1})}{A(z_1^{-1}, \ldots , z_n^{-1})} = z^\gamma \frac{G(z_1, \ldots , z_n)}{F(z_1, \ldots , z_n)}\in \mathbb {C}(z_1, \ldots , z_n), \end{aligned}$$

(2)

where $\gamma \in \mathbb {Z}^n$ and $G,F\in \mathbb {C}[z_1, \ldots , z_n]$ are coprime in $\mathbb {C}[z_1, \ldots , z_n]$ with $z^{\gamma }=z^{\gamma _{1}}_1\cdots z^{\gamma _{n}}_n$. They are called discrete n-rational filters. In case the rational function

$$\begin{aligned} z\in \mathbb {T}^n:=(\mathbb {C}^*)^n \longmapsto G(z)/F(z), \end{aligned}$$

where $\mathbb {C}^* := \mathbb {C}\setminus \{0\}$, is regular about the n-dimensional torus

$$\begin{aligned} \mathbb {S}_1^n = \{z=(e^{i\theta _1}, \ldots , e^{i\theta _n})\,;\, \theta =(\theta _{1}, \ldots , \theta _{n}) \in (\mathbb {R}/2\pi \mathbb {Z})^n\}, \end{aligned}$$

(3)

that is G and F have no common zeroes on $\mathbb S_1^n$, then the two following assertions are equivalent for such a discrete n-rational filter S:

$$\begin{aligned} \begin{aligned}&(i)\ S \ \mathrm{is\ BIBO\ stable} \\&(ii)\ F^{-1} (\{\varvec{0}\}) \cap \{z\in \mathbb {C}^n\,;\, |z_j|\le 1\ \textrm{for}\ j=1, \ldots , n\} = \emptyset . \end{aligned} \end{aligned}$$

(4)

The characterization of stability given in (ii) is called structural stability (Bouzidi et al., 2019).

The subject of BIBO stability of discrete n-rational systems has a very long and rich history, with several criteria available in the classical literature (see (Huang, 1972; Justice & Shanks, 1973; Anderson & Jury, 1974; Schussler, 1976; Bose, 1977; Goodman, 1977; Bistritz, 1999)). Also, several algorithms, both symbolic and numeric have been proposed for testing these criteria. The problem is completely solved for $n=2$. For moderate n, say $n=3, 4$, one can find in the literature very efficient algorithms with available packages implemented e.g in Singular, Sage or Maple. To our knowledge, the problem of testing the BIBO stability is however still open for large n and or high degree.

We intend in this paper to introduce a novel approach on structural stability, based on the notion of amœba of an algebraic hypersurface in $\mathbb {T}^n$. The objective is to escape from the curse of dimensionality. In addition, we hope that the approach is interesting in itself, by the connections it establishes between tropical geometry and systems theory in signal processing and control theory.

The notion of amoeba was introduced by Gelfand, Krapanov and Zelevinsky in 1994 in their pioneer book on multidimensional determinants (Gelfand et al., 1994). The amœba $\mathcal A_F$ of F (one should better say of the zero set $F^{-1}(\{\varvec{0}\})$ of F in $\mathbb {T}^n$) when F is a Laurent polynomial in n variables (in particular a polynomial in n variables) is the image of $F^{-1}(\{\varvec{0}\})$ under the log absolute value map ${{\,\mathrm{\textrm{Log}}\,}}: z \mapsto (\log |z_1|, \ldots , \log |z_n|)$. We refer to Bogdanov et al. (2016), Bogdanov and Sadykov (2020), Nisse and Sadykov (2019) for algorithmic computation of polynomial amœbas. Readers interested in interactive visualization of 2 or 3 variables amœbas are invited to see the recent website www.amoebas.ru. Visualization in dimension 4 is also considered through slices of amœbas

1.1 Outline

This paper is organized as follows. Section §2 provides a state of the art on the problem of testing structural stability for n-rational systems. The section §3 provides a recall of the concept of amœbas, in view of the role it could play in relation with the establishment of our criterion on structural stability. In section §4, we will formulate our criterion within the frame of amœba and enlarge the notion of structural stability into that of weak structural stability. In section §5, we design a numerical algorithm using the Monte-Carlo integration method, to test the structural stability of a given rational system of n variables. The proposed method does not stuck from the curse of dimensionality as opposed to the state-of-the-art methods.

1.2 Notation

Throughout the paper, we will use the boldface notation $\varvec{0} = (0, \ldots , 0)$ for the zero vector of dimension $n > 1$. We write $\deg _i F(z_1, \ldots , z_n)$ for the degree of F, with respect to the variable $z_i$.

2 State of the art

In the case of a multilinear discrete time-invariant system, the following theorems due to DeCarlo et al. (1977) and Strintzis (1977) constitute important equivalent conditions to (ii) and easier to handle.

Theorem 1

(DeCarlo et al. 1977) Condition (ii) is equivalent to

$$\begin{aligned} {\left\{ \begin{array}{ll} F(z_{1}, 1, ...,1)\ne 0, &{} |z_{1}|\le 1, \\ F(1, z_{2}, 1, ...,1)\ne 0, &{}|z_{2}|\le 1, \\ \ \qquad \vdots &{} \vdots \\ F(1, \ldots , 1,z_{n})\ne 0, &{}|z_{n}|\le 1, \\ F(z_{1}, \ldots , z_{n})\ne 0, &{} |z_{1}|=\cdots =|z_{n}|=1. \end{array}\right. } \end{aligned}$$

Theorem 2

(Strintzis 1977) Condition (ii) is equivalent to

$$\begin{aligned} {\left\{ \begin{array}{ll} F( 0, ...,0,z_{n})\ne 0,&{}|z_{n}|\le 1, \\ F( 0, ...,0,z_{n-1},z_{n})\ne 0, &{} |z_{n-1}|\le 1, |z_{n}|=1 \\ \qquad \vdots &{} \vdots \\ F(0, z_{2}...,z_{n})\ne 0, &{}|z_{2}|\le 1,\quad |z_{i}|=1, i=3, \ldots , n, \\ F(z_{1}, z_{2}...,z_{n})\ne 0, &{}|z_{1}|\le 1,\quad |z_{i}|=1, i=2, \ldots , n. \end{array}\right. } \end{aligned}$$

With these criteria, the original problem of dimension n in the unit closed polydisc $\overline{\mathbb {D}}^n$ is converted into n or $n+1$ easier sub problems of lower dimensions, on reduced subsets of $\overline{\mathbb {D}}^n$. Most of the existing criteria on the structural stability are developed from Theorems 1 and 2.

Recently Y. Bouzidi, A. Quadrat and F. Rouiller have proposed a method for the implementation of the structural stability of the n-dimensional case (Bouzidi et al., 2015; Bouzidi & Rouillier, 2016; Bouzidi et al., 2019). Their starting point is the theorem 1 and they focused on testing the last condition

$$\begin{aligned} F(z_{1}, \ldots , z_{n})\ne 0, \quad |z_{1}|=\cdots =|z_{n}|=1 \quad \text{ for } \quad n\ge 2 \end{aligned}$$

(5)

in the particular case where $F\in \mathbb {R}[z_{1}, \ldots , z_{n}]$. The n first conditions of the theorem 1, being easy, are tested using the 1-D Bistritz test (Bistritz, 1984). An algorithmic procedure for testing (5) has been proposed using some computer algebra methods namely the Cylindrical Algebraic Decomposition (CAD) and the Rational Univariate Representation (RUR) (Bouzidi et al., 2019). The implementation is proposed using some packages that they have developed under Maple which make their approach efficient in practice for moderate n.

We mention that Dumitrescu also has proposed a method for testing the condition (5). His approach is based on sum of squares decomposition but it provides only a sufficient condition (see (Dumitrescu, 2006)).

Alternative methods have been introduced by M. Najim, I. Serban and F. Turcu. These methods are based on the introduction of so-called Schur coefficients families in several variables, the goal being to obtain a multidimensional Schur-Cohn criterion (see Serban and Najim (2006, 2007a, 2007b, 2007c)). We present hereafter the basic steps of their method.

Let

$$\begin{aligned} F(z_1, \ldots , z_n) = \sum \limits _{\alpha \in \textrm{Supp}\, F\subset \mathbb {N}^n} c_\alpha \, z^\alpha \quad (c_\alpha \in \mathbb {C}^*) \end{aligned}$$

with total degree $\delta _F$ in the n variables $z_1, \ldots , z_n$. For any ${\varvec{\omega }}=(e^{i\omega _1}, \ldots , e^{i\omega _{n-1}})$ define $F_{\varvec{\omega }}\in \mathbb {C}[Y]$ by

$$\begin{aligned} F_{\varvec{\omega }}(Y)= F(e^{i\omega _1}Y, \ldots , e^{i\omega _{n-1}}Y, Y) \in \mathbb {C}[Y]. \end{aligned}$$

Let also $F_{\varvec{\omega }}^{\#}$ be the reciprocal polynomial defined by

$$\begin{aligned} F_{\varvec{\omega }}^{\#}(Y) = Y^{\delta _F} \overline{F_{\varvec{\omega }}(1/\overline{Y})}. \end{aligned}$$

Theorem 3

(Serban and Najim 2007b) Consider $(\gamma _{k}({\varvec{\omega }}))$ the functional Schur coefficients of the one variable function $F_{\varvec{\omega }}^{\#}/F_{\varvec{\omega }}$. The following statements are equivalent

• a) F has no zeroes in $\overline{\mathbb {D}}^{n}$.

• b) $F_{{\varvec{\omega }}}$ has no zeroes in $\overline{\mathbb {D}}$ for any ${\varvec{\omega }}=(e^{i\omega _1}, \ldots , e^{i\omega _{n-1}})$ .

• c) $|\gamma _{k}({\varvec{\omega }})|<1$ for any ${\varvec{\omega }}=(e^{i\omega _1}, \ldots , e^{i\omega _{n-1}})$ and any $k=0, \ldots , \delta _{F}-1$.

Such equivalence allows to split the n-dimensional problem given in item a) to the $\delta _F$ sub problems in item c), of $n-1$ variables, on the unit polycircle of dimension $n-1$. A test for conditions b) or equivalently c), can be performed in an efficient way for $n=2$ and for small degrees $\delta _{F}$. However there is no rule for big values of n and $\delta _{F}$. In particular, the graphical inspection of the plot of $|\gamma _k({\varvec{\omega }})|$, adopted in Serban and Najim (2007b) to check the validity of c), can hardly be applied for $n > 3$.

More generally, all the methods presented so far are effective in practice only when n is low. To our knowledge, there is still no method capable of answering the question of BIBO stability beyond $n = 4$.

The problem of testing the structural stability of a discrete n-rational filter thus appeals to investigate new strategies.

We propose to revisit the problem following a tropical geometry approach. This leads to a reformulation of the condition ii) in (4) as a new criterion for structural stability. This expresses in terms of a set membership problem, for one specific point, namely the origin of $\mathbb {R}^n$. Next we devise a numerical algorithm to provide an answer to the membership problem.

3 Concept of amœbas

To proceed, let us recall the log absolute value map mentioned in the introduction and defined by:

$$\begin{aligned} {{\,\mathrm{\textrm{Log}}\,}}|\cdot |: \mathbb {T}^n \rightarrow \mathbb {R}^n ; \quad z = (z_1, \ldots , z_n) \mapsto (\log |z_1|, \ldots , \log |z_n|) \end{aligned}$$

(6)

For $x = (x_1, \ldots , x_n) \in \mathbb {R}^n$, the associated set ${{\,\mathrm{\textrm{Log}}\,}}^{-1}(x)$ is then given by

$$\begin{aligned} {{\,\mathrm{\textrm{Log}}\,}}^{-1}(x) = \left\{ (e^{i\theta _1 + x_1}, \ldots , e^{i\theta _n+x_n}) \,;\, \theta =(\theta _{1}, \ldots , \theta _{n}) \in (\mathbb {R}/2\pi \mathbb {Z})^n \right\} \end{aligned}$$

(7)

Let

$$\begin{aligned} F = \sum \limits _{\alpha \in \textrm{Supp}\, F \subset \mathbb {Z}^n} c_\alpha z^\alpha \in \mathbb {C}[z_1^{\pm 1}, \ldots , z_n^{\pm 1}] \quad (c_\alpha \in \mathbb {C}^*,\ z^\alpha := z_1^{\alpha _1} \cdots z_n^{\alpha _n}) \end{aligned}$$

(8)

be a Laurent polynomial with zero set $F^{-1}(\{\varvec{0}\})$ in the complex torus $\mathbb {T}^n$. Let $\Delta (F)$ be the Newton polytope of F, that is the closed convex hull in $\mathbb {R}^n$ of the set $\textrm{Supp}\, F := \{\alpha \in \mathbb {Z}^n\,;\, c_\alpha \not =0\}$. We will always suppose that F is a true Laurent polynomial in n variables, which means that $\dim _{\mathbb {R}^n} \Delta (F)$, that is the dimension of the affine subspace of $\mathbb {R}^n$ generated by $\Delta (F)$ is maximal, that is equal to n.

Let $\mathcal A_F$ be the amœba of F, that is the closed image ${{{\,\mathrm{\textrm{Log}}\,}}} (F^{-1}(\{\varvec{0}\})\subset \mathbb {R}^n$ of the map

$$\begin{aligned} z\in F^{-1}(\{\varvec{0}\}) \subset \mathbb {T}^n {\mathop {\longmapsto }\limits ^{{{\,\mathrm{\textrm{Log}}\,}}}} (\log |z_1|, \ldots , \log |z_n|) \in \mathbb {R}^n. \end{aligned}$$

From the geometric point of view, the complement $\mathbb {R}^n \setminus \mathcal A_F$ is a 1-convex open subset of $\mathbb {R}^n$, which amounts to saying that its open connected components $E_\iota$ are convex. The number of such open connected components is bounded by the number of points in $\Delta (F)\cap \mathbb {Z}^n$ (Forsberg et al., 2000). Let $\mathscr {E}_F$ be the finite set whose elements are such components $E_\iota$. Each ${{{\,\mathrm{\textrm{Log}}\,}}}^{-1}(E)$, where $E\in \mathscr {E}_F$, is a Reinhardt domain in $\mathbb {T}^n$, that is a subdomain which is invariant under the pointwise multiplicative action of the real torus $\{(e^{i\theta _1}, \ldots , e^{i\theta _n})\,;\, \theta =(\theta _{1}, \ldots , \theta _{n}) \in (\mathbb {R}/2\pi \mathbb {Z})^n\}$. Moreover it can be described as the maximal domain of convergence of a unique Laurent series $\sum _{k\ge 0} \gamma _{E,k} z^{\alpha _{E,k}}$, $\alpha _{E,k}\in \mathbb {Z}^n$, whose sum represents $z\mapsto 1/F(z)$ in ${{\,\mathrm{\textrm{Log}}\,}}^{-1}(E)$. A key point is that there is in fact a bijection between the finite set $\mathscr {E}_F$ and the family of all possible Laurent expansions (with domains of convergence precisely ${{\,\mathrm{\textrm{Log}}\,}}^{-1}(E)$ for $E\in \mathcal E_F$) for 1/F along the monomials $z^\alpha$ for $\alpha \in \mathbb {Z}^n$ (Forsberg et al., 2000).

Remark 1

(the case $n=1$) In the case where $n=1$, the amœba $\mathcal A_F$ consists in a finite number of points $-\infty< \log |a_1|< \cdots< \log |a_N| < +\infty$ on the real line with $F^{-1}(\{\varvec{0}\})=\{a_1, \ldots , a_N\}\in (\mathbb {C}^{*})^{N}$. Each of the $N+2$ circular domains

$$\begin{aligned} \{z\in \mathbb {C}^*\,;\, |z|<|a_1|\}, \ldots , \{z\in \mathbb {C}^*\,;\, |a_j|<|z|<|a_{j+1}|\}, \ldots , \{z\in \mathbb {C}^*\,;\, |z|> |a_N|\}, \end{aligned}$$

is the domain of convergence of a Laurent series which sum represents 1/F in the corresponding domain. The domain $C=\{z\in \mathbb {C}^*\,;\, |z|> |a_N|\}$ is, among such list, the only one for which the associated Laurent expansion in C is of the form $1/F(z) = \sum _{k\ge -M} \gamma _{C,k} z^{-k}$ for some $M\in \mathbb {Z}$ and hence the sequence $(\gamma _{C,k})_{k\in \mathbb {Z}}$ can be interpreted as the impulse response of a rational (realizable) discrete 1-dimensional filter.

One can associate (Passare & Rullgård, 2004) to each $E\in \mathscr {E}_F$ a multiplicity $\nu _E = (\nu _{E,1}, \ldots , \nu _{E,n})\in \Delta (F)\cap \mathbb {Z}^n$, where $\nu _{E,j}$ is the degree of the loop

$$\begin{aligned} \theta _j \in \mathbb {Z}/(2\pi \mathbb {Z}) \longmapsto F(\zeta _{E,1},\dots ,\zeta _{E,j} e^{i\theta _j},\dots ,\zeta _{E,n}) \end{aligned}$$

(9)

when $(\zeta _{E,1}, \ldots , \zeta _{E,n})$ is an arbitrary point in E, the degree of the loop (9) being independent on the choice of such point $\zeta _E$ in E. For each point $\alpha \in \Delta (F) \cap \mathbb {Z}^n$, there is at most one component $E_\alpha \in \mathscr {E}_F$ such that $\nu _{E_\alpha } = \{\alpha \}$. If such is the case, let $\sigma _\alpha$ be the unique face of $\Delta (F)$ which contains $\alpha$ in its relative interior or (if no such face exists) equals $\{\alpha \}$ : for example, if $\alpha$ is a vertex of $\Delta (F)$, $\sigma _\alpha = \{\alpha \}$, while when $\alpha$ lies in the interior of $\Delta (F)$, $\sigma _\alpha = \Delta (F)$, etc. Then the cone

$$\begin{aligned} \Gamma _\alpha = \big \{x\in \mathbb {R}^n\,;\, \sigma _\alpha = \{\xi \in \Delta (F)\,;\, \langle \xi ,x\rangle =\max _{u\in \Delta (F)} \langle u,x\rangle \}\big \} \end{aligned}$$

is the recession cone of $E_\alpha$, that is the largest cone $\Gamma$ of $\mathbb {R}^n$ such that $E_\alpha + \Gamma \subset E_\alpha$. Such recession cone equals $\{\varvec{0}\}$ whenever $\alpha$ lies in the interior of $\Delta (F)$, hence the corresponding component $E_\alpha$ is, if it exists, bounded in this case. When $\alpha$ belongs to the boundary of $\Delta (F)$, the dimension of the recession cone is maximal (thus equal to n) if and only if $\alpha$ is a vertex of $\Delta (F)$. If $\alpha$ is a point of $\partial \Delta (F)\cap \mathbb {Z}^n$ which is not a vertex of $\Delta (F)$, then, if $E_\alpha$ exists, it is unbounded. A major point is that any vertex $\alpha$ of $\Delta (F)$ is the multiplicity $\nu _{E_\alpha }$ of a unique unbounded component $E_\alpha$. Thus the cardinal of $\mathscr {E}_F$ lies between the number or vertices of $\Delta (F)$ and the cardinal of $\Delta (F)\cap \mathbb {Z}^n$ (Forsberg et al., 2000).

4 Structural stability and amœbas

4.1 Domain of stability

Let S be a multilinear discrete time invariant system with transfer function (2). Our first observation is that the condition $z \mapsto G(z)/F(z)$ is regular about

$$\begin{aligned} {{\,\mathrm{\textrm{Log}}\,}}^{-1}(\{\varvec{0}\}) = \{z = (e^{i\theta _1}, \ldots , e^{i\theta _n})\,;\, \theta \in (\mathbb {R}/(2\pi \mathbb {Z}))^n\} \end{aligned}$$

is equivalent to the fact that its polar set $F^{-1}(\{\varvec{0}\})$ in $\mathbb {T}^n$ does not intersect ${{\,\mathrm{\textrm{Log}}\,}}^{-1}(\{\varvec{0}\})$ which amounts to say that $\varvec{0} \in \mathbb {R}^n\setminus \mathcal A_F$. One can then state the following result.

Theorem 4

Suppose that $\varvec{0}\in \mathbb {R}^n \setminus \mathcal A_F$, where $\dim _{\mathbb {R}^n} \Delta (F)=n$. A necessary and sufficient condition for a discrete n-rational filter S with the rational function (2) as transfer function to be (strongly) structural stable is that $\xi = {\varvec{0}} \in \textrm{Supp}\, F$ and $x=\varvec{0} \in E_{\varvec{0}}$.

Remark 2

(Why strong structural stability?) We speak here about strong structural stability (which is the usual notion as described so far) in order to differentiate it with the weaker one that we will introduce next in Definition 2.

Proof

Suppose that S is structurally stable, which means that F is coprime with $z_1\cdots z_n$ and does not vanish in $\overline{\mathbb {D}}^n = \{z\in \mathbb {C}^n\,;\, |z_1|\le 1, \ldots , |z_n|\le 1\}$. Since $\{z=(z_1, \ldots , z_n)\in \mathbb {T}^n\,;\, 0<|z_1|\le 1, \ldots , 0<|z_n|\le 1\}$ equals the Reinhardt domain ${{\,\mathrm{\textrm{Log}}\,}}^{-1} \big (\{x=(x_1, \ldots , x_n)\in \mathbb {R}^n\,;\, x_1\le 0, \ldots , x_n\le 0\}\big )$ then the cone $\varvec{\Gamma }^- := \{x=(x_1, \ldots , x_n)\in \mathbb {R}^n\,;\, x_1\le 0, \ldots , x_n\le 0\}$ lies entirely in some connected component $E= E_\alpha \in \mathscr {E}_F$. Now the cone $\varvec{\Gamma }^{-}$ is n-dimensional, therefore $\alpha$ is necessarily a vertex of $\Delta (F)$. It follows from the fact that $\textrm{Supp}\, F \subset \mathbb {N}^n$ (because F is a polynomial in $z_1 \ldots , z_n$) that the only possible vertex of $\Delta (F)$ for such a situation to occur is that $\alpha = \varvec{0}$, which implies that $\varvec{0} \in \textrm{Supp}\, F$. Since $\varvec{\Gamma }^- \subset E_{\varvec{0}}$, one has in particular that $x=\varvec{0} \in E_{\varvec{0}}$.

Conversely, suppose that $\textbf{0 }\in \textrm{Supp}\, F$ and $\textbf{0 }\in E_{\varvec{0}}$. Then $E_{\varvec{0}}$ is unbounded since $\textbf{0}$ is a vertex of $\Delta (F)$. The recession cone

$$\begin{aligned} \Gamma _{\varvec{0}}= \big \{x\in \mathbb {R}^n\,;\, \{\varvec{0}\} = \{\xi \in \Delta (F)\,;\, \langle \xi ,x\rangle =\max _{u\in \Delta (F)} \langle u,x\rangle \}\big \} \end{aligned}$$

of the unbounded connected component $E_{\varvec{0}}$ of $\mathbb {R}^n \setminus \mathcal A_F$ contains $\varvec{\Gamma }^-$, as it is immediate to check. This implies that $z\mapsto 1/F(z)$ is holomorphic in the Reinhardt domain $\{z=(z_1, \ldots , z_n)\in \mathbb {T}^n\,;\, 0<|z_j| \le 1\}$, which means that F does not vanish there. Since F is coprime with $z_1 \cdots z_n$, F cannot vanish on the union of the coordinate axis either, which implies that the n-rational filter S is structurally stable. $\square$

Theorem 4 suggests to introduce two concepts related to the structural stability property.

Definition 1

(Structural stability domain) Let S be a discrete n-rational filter with a rational function (2) (with its properties, together with the condition $\dim _{\mathbb {R}^n} \Delta (F)=n$) as transfer function. If $\varvec{0} \in \textrm{Supp}\, F$, the connected component $E_{\varvec{0}}$ of $\mathbb {R}^n \setminus \mathcal A_F$ is called the structural stability domain of the n-filter S. If $\varvec{0} \notin \textrm{Supp}\, F$, one decides that the structural stability domain of S is empty.

Definition 2

(Structural weak stability) Let S be a discrete n-rational filter with a rational function (2) as in Definition 1. The discrete n-rational filter S is said to be structurally weakly stable if $\varvec{0}\in \textrm{Supp}\, F$ and $\varvec{0}$ belongs to the topological boundary of the connected component $E_{\varvec{0}}$, which is part of the contour of $\mathcal A_F$. If it is the case, the component $E_{\varvec{0}}$ is called the weak structural stability domain of the discrete n-rational filter S ; otherwise the weak structural domain of S is considered as empty.

4.2 Ronkin function

Consider the Laurent polynomial $F(z) = \sum a_\alpha z^\alpha$ defined in (8), with zero set $F^{-1}(\{\varvec{0}\})$ in the complex torus $(\mathbb {C}^{*})^{n}$ and with Newton polytope $\Delta (F)$.

The Ronkin function of F, denoted by $R_{F}$, is defined as the convex function

$$\begin{aligned} R_{F}: x \in \mathbb {R}^{n} \mapsto \left( \frac{1}{2\pi i}\right) ^{n} \int _{{{\,\mathrm{\textrm{Log}}\,}}^{-1}(x)}\log |F(z)| \, \frac{dz}{z}. \end{aligned}$$

(10)

With a simple change of variables, we rewrite this function as

$$\begin{aligned} R_{F}: x\in \mathbb {R}^{n}\mapsto \int _{(\mathbb {R}/(2\pi \mathbb {Z}))^{n}}\log \left| F(e^{i\theta _1 + x_1}, \ldots , e^{i\theta _n+x_n})\right| d\lambda (\theta ) \end{aligned}$$

(11)

where $\lambda$ is the Lebesgue measure on $(\mathbb {R}/(2\pi \mathbb {Z}))^{n}$.

This function was introduced by Ronkin in Ronkin (2000), and it provides geometric information on the associated amœba $\mathcal {A}_F$. Three important properties of this function are listed hereafter:

• 1. The function $R_F$ is affine in the connected component (of $\mathbb {R}^n \setminus \mathcal A_F$) $E_\alpha \in \mathscr {E}_F$ with multiplicity $\alpha \in \Delta (F) \cap \mathbb {Z}^n$, provided, of course, that such component exists (Passare & Rullgård, 2004). More precisely,

  $$\begin{aligned} \forall x\in E_\alpha ,\quad R_F(x) = \rho _\alpha + \nu _{1}x_{1}+\cdots +\nu _{n}x_{n}. \end{aligned}$$

  (12)

  The vector $\nu =(\nu _{1}, \ldots , \nu _{n})$ belongs to $\Delta (F)\cap \mathbb {Z}^{n}$, it represents the multiplicity attached to a connected component $E_\alpha$, that is $\nu =\nu _{E_\alpha }$ and is given by

  $$\begin{aligned} \nu _{j} =\left( \dfrac{1}{2\pi i}\right) ^{n} \int _\mathrm{Log^{-1}(x)} z_{j}\dfrac{\partial _{j}F(z)}{F(z)}\frac{dz}{z}, \qquad 1\le j\le n. \end{aligned}$$

  (13)

  It is important to precise that in (13), x is an arbitrary point of $E_\alpha$. Moreover, the numbers $\nu _j$ are real (see (Ronkin, 2000; Lundqvist, 2015; Yger, 2012) for more details).

• 2. When $\alpha$ is a vertex of $\Delta (F)$ (and hence $E_\alpha$ exists), then, for all $x \in E_\alpha$, the integral

  $$\begin{aligned} a_\mu = \left( \dfrac{1}{2\pi i}\right) ^{n} \int _\mathrm{Log^{-1}(x)} \log \left| \frac{F(z)}{z^{\mu }}\right| \frac{dz}{z} \end{aligned}$$

  (14)

  is independent of x and we have

  $$\begin{aligned} a_\mu = \log |c_\mu | = \rho _\alpha \end{aligned}$$

  where $c_\mu$ is the coefficient of $z^\mu$ in the developed expression (8) for F.

• 3. The singular support of the distribution $\Delta ([R_F])$ (where $\Delta$ is the Laplace operator and $[R_F]$ means that $R_F$ is considered in the sense of distributions) is contained in the contour of $\mathcal A_F$ Ossete Ingoba (2019, Theorem 3.1).

Now if $\nu =\varvec{0} \in \mathbb {Z}^{n}$ is a vertex of $\Delta (F)$, then

$$\begin{aligned} a_\textbf{0}=R_{F}(x)=\rho _\textbf{0} = \log |c_\textbf{0}| \quad \forall x \in E_\textbf{0}. \end{aligned}$$

Assume that the origin $\varvec{0}$ of $\mathbb {R}^{n}$ belongs to the connected component $E_{\varvec{0}}$ of $\mathbb {R}^n \setminus \mathcal A_F$. Then the restriction of the Ronkin function in $E_{\varvec{0}}$ is a constant function. Therefore one has the following characterization:

Corollary 1

The polynomial F with $c_{\varvec{0}}= F(\varvec{0}) \ne 0$ has no zero in the closed unit polydisk $\overline{\mathbb {D}}^{n}$ if and only if $R_{F}(x)=\log |c_\textbf{0}|$ for all $x\in ]-\infty , 0]^{n}$.

5 Algorithmic considerations

5.1 Lopsided amœba

The characterization of $\mathscr {E}_F$ can be exploited to design a procedure to test the membership of $x \in \mathbb {R}^n$ to $\mathbb {R}^n \setminus \mathcal A_F$ and to identify the component $E_\nu$ to which it belongs, if any. One such procedure relies on the concept of lopsidedness approximation of $\mathcal A_F$, as introduced by Purbhoo (2008) and completed from the algorithmic point of view in Forsgård et al. (2019). We briefly recall the construction.

Observe that if $z \in \mathbb {T}^n$ satisfies $F(z) = \sum _{\alpha \in \textrm{Supp} F\subset \mathbb {Z}^n} c_\alpha z^\alpha = 0$ then the triangle inequality implies that $|c_\beta |\, |z^\beta | \le \sum _{\alpha \in \textrm{Supp} F, \alpha \ne \beta } |c_\alpha |\, |z^\alpha |$ for all $\beta \in \textrm{Supp} F$. The set $\mathcal {L}_z = \{|c_\alpha |\, e^{\langle \alpha , x_z\rangle }\,;\, \alpha \in \textrm{Supp} F\}$ where $x_z= {{\,\mathrm{\textrm{Log}}\,}}|z| = (\log |z_1|, \ldots , \log |z_n|)$ is said to be not lopsided. If, on the contrary, the condition $|c_\beta |\, e^{\langle \beta , x_z\rangle } > \sum _{\alpha \in \textrm{Supp} F, \alpha \ne \beta } |c_\alpha |\,e^{\langle \alpha , x_z\rangle }$ holds for some $\beta \in \textrm{Supp} F$ and for $x_z \in \mathbb {R}^n$, then we say that the set of strictly positive real numbers $\mathcal {L}_z$ is lopsided. In such situation, we will say that F is lopsided at the point $x_z \in \mathbb {R}^n$, with dominant exponent $\beta \in \mathbb {Z}^n$. The point $x_z$ thus clearly belongs to the complement of $\mathcal A_F$.

For any $N\in \mathbb {N}^*$ we denote by $F^{[N]}$ the cyclic resultant of F of order N, which is by definition the polynomial

$$\begin{aligned} F^{[N]}(z)=\prod _{k_{1}=0}^{N-1}\cdots \prod _{k_{n}=0}^{N-1}F(e^{2\pi i k_{1}/N}z_{1}, \ldots , e^{2\pi i k_{n}/N}z_{n}). \end{aligned}$$

(15)

Note that F and $F^{[N]}$ share the same amœba $\mathcal A_F$ for all $N\in \mathbb {N}^*$. Now, from K. Purbhoo’s observation in Purbhoo (2008, Theorem 1), we have

Theorem 5

- $(0, \ldots , 0) \in \textrm{Supp}\, F$ and $x=\varvec{0} \in E_{\varvec{0}}$ if, and only, if there exists $N_0 \in \mathbb {N}^*$, such that $F^{[N]}$ is lopsided at $\varvec{0}$ for all $N \ge N_0$, with dominant exponent $(0, \ldots , 0) \in \mathbb {Z}^n$.

Inspired from the Cooley-Tukey FFT algorithm (Cooley & Tukey, 1965), a fast iterative procedure to compute $F^{[2^k]}$ has been proposed in Forsgård (2019, §3). The resulting algorithm, which provides the position of a given point $x \in \mathbb {R}^n$ with respect to $\mathcal {A}_F$ and to the different components $E_\nu$, has been implemented in Singular/Sage (see (Forsgård et al., 2019) to access the code).

Note however that this algorithm does not escape the curse of dimensionality, like all the methods mentioned before. Indeed, in the computation of the cyclic resultants, parameters like the degree of $F^{[2^k]}$, the number of terms and the magnitudes of the coefficients all increase exponentially with k, as shown in Forsgård et al. (2019). This limits the practical utility of the method to systems with a number of variables not exceeding 3 or 4, like all the methods mentioned before.

5.2 Monte Carlo approach

To motivate the proposed Monte Carlo approach to BIBO stability let us reconsider the cyclic resultant in (15). Taking the logarithm of the module,

$$\begin{aligned} \frac{1}{N^n}\log \left| F^{[N]}(z)\right| =\frac{1}{N^n} \sum _{k_{1}=0}^{N-1}\cdots \sum _{k_{n}=0}^{N-1} \left| F(e^{2\pi i k_{1}/N}z_{1}, \ldots , e^{2\pi i k_{n}/N}z_{n})\right| \end{aligned}$$

(16)

we observe with Purbhoo (2008) that the right-hand side may be interpreted as a Riemann sum which converges pointwise to $R_F(x_z)$ provided the left-hand side is bounded. Now, as it is well known, the numerical computation of a multidimensional integral based on a regular multidimensional grid as in (16) has a reasonable complexity only for moderate dimension. The Monte Carlo numerical integration method does not suffer from such limitation. It is therefore the base of the algorithm we propose to test the BIBO stability of an n-rational filter with transfer function $H(z) = z^\gamma G(z)/F(z)$ as in (2), where we assume that G and F are coprime. For $j=1, \ldots , n$, let us define

$$\begin{aligned} \Psi _j(z) = z_{j}\dfrac{\partial _{j}F(z)}{F(z)}. \end{aligned}$$

The algorithm consists in two steps as described below:

Step1:

Monte Carlo integration: The first step is devoted to a direct approximation of the Ronkin function (11) and the orders $\nu _j, j= 1, \ldots , n$ (13), at the point $x \in \mathbb {R}^n$. We resort to the basic Monte Carlo (MC) method for these approximations. Given $K \in \mathbb {N}^*$, we consider sequences of random vectors ${\varvec{U}}= \left( {\varvec{u}}_k\right) _{k=1, \ldots , K}$ formed by independent and uniformly distributed (iid) samples in $[0, 1]^n$, that is ${\varvec{u}}_k = (u_{1,k}, \ldots , u_{n,k})$ where $\{u_{\ell ,k}\}$ are iid in [0, 1]. The K-point MC approximations, denoted by $\widehat{R}_{F, {\varvec{U}}}$ and $\widehat{\nu }_{j,{\varvec{U}}}, j=1, \ldots , n$ respectively, then read as:

$$\begin{aligned} R_F(x) \approx \widehat{R}_{F, {\varvec{U}}}(x)&:= \frac{1}{K} \sum _{k=1}^K \log \left| F(e^{i 2 \pi u_{1,k}+x_1}, \ldots , e^{i 2 \pi u_{n,k}+x_n})\right| \end{aligned}$$

(17)

$$\begin{aligned} \nu _j \approx \widehat{\nu }_{j,{\varvec{U}}}(x)&:= \Re \left\{ \frac{1}{K} \sum _{k=1}^K \Psi _j(e^{i 2 \pi u_{1,k}+x_1}, \ldots , e^{i 2 \pi u_{n,k}+x_n})\right\} . \end{aligned}$$

(18)

Remark 3

Needless to say, the sequences ${\varvec{U}}$ in $\widehat{R}_{F, {\varvec{U}}}(x)$ and $\widehat{\nu }_{j,{\varvec{U}}}(x), j=1, \ldots , n$ are of course independent.

Remark 4

In all the sequel, x will be the origin or a small perturbation around, obtained by a random selection from uniformly distributed points in the ball of $\mathbb {R}^n$ of radius $\delta = 0.01$, with center $\varvec{0}$. To ease the notation, we subsequently drop the argument x in $\widehat{R}_{F, {\varvec{U}}}(x)$ and $\widehat{\nu }_{j,{\varvec{U}}}(x)$.

Step2:

Hypothesis test: Note that $\widehat{R}_{F, {\varvec{U}}}$ and $\widehat{\nu }_{j,{\varvec{U}}}$ are random variables. As $K\rightarrow \infty$, they are expected to converge to

$$\begin{aligned} \widehat{R}_{F, {\varvec{U}}} \rightarrow \log |F(\varvec{0})| \, ; \quad \widehat{\nu }_{j,{\varvec{U}}}\rightarrow 0, \ \ j=1, \ldots , n \end{aligned}$$

if, and only if, the system is strongly BIBO stable. In all the sequel, we consider without loss of generality that F is monic, that is $F(\varvec{0}) = 1$ (if $F(\varvec{0}) = 0$ then the system is clearly unstable). Thus, $\widehat{R}_{F, {\varvec{U}}}$ will also be expected to converge to 0 in case of BIBO stability. The second step of the algorithm therefore amounts to devising a statistic based on these variables, completed by a hypothesis testing. The statistic should result to zero if, and only if, all variables are zero. If we denote by $\mathcal S$ the devised statistic, then the test reads as

$$\begin{aligned} H_0:\quad \mathcal {S}(\widehat{R}_{F, {\varvec{U}}}, \widehat{\nu }_{1,{\varvec{U}}}, \ldots , \widehat{\nu }_{n,{\varvec{U}}}) = 0\, \, a.s. \quad vs \quad H_A:\quad H_0 \text { is false}. \end{aligned}$$

(19)

Strong BIBO stability is concluded when $H_0$ is not rejected. The design of an appropriate statistic $\mathcal {S}$ is discussed after the illustrative examples of the next subsection.

In the following, we will say by abuse that an nD-polynomial F is BIBO stable or simply stable if it does not vanish in $\overline{\mathbb {D}}^n$, which amounts to saying that it is the denominator of a BIBO stable n-rational system.

5.3 Illustrative examples

We consider five examples quoted in the literature to illustrate the Monte Carlo approximations $\widehat{R}_{F, {\varvec{U}}}$ and $\widehat{\nu }_{j,{\varvec{U}}}$ of the Ronkin function at $\varvec{0}$ and the multiplicities given in (17) and (18), respectively. The examples are collected from the references indicated in the last column of Table 1 below. As indicated, the first 3 examples correspond to unstable filters and the two last to stable filters.

Table 1 Five examples treated in the literature

Observe that by Theorem 5, the stability property of the three examples $F_1$, $F_4$ and $F_5$ may be readily obtained:

• i) For the first one, we have $F_1(z_1, z_2) = \sum _\alpha c_\alpha z^\alpha$, with $c_{0,0}=1=c_{0,3}=c_{3,0}$, $c_{1,1}=-4$ and $c_\alpha =0$ elsewhere. Clearly, $F_1 = F_1^{[1]}$ is lopsided at $\varvec{0} = (0., 0.)$ [corresponding to $(|z_1|=1,|z_2|=1)$]. The dominant exponent is $\beta = (1,1)$ which implies that the origin $\varvec{0}$ belongs to the connected component $E_\beta$ wherein $1/F_1$ admits a convergent power series expansion. However, although the origin is outside the amœba, we conclude that $F_1$ is not BIBO stable since $\varvec{0}$ does not belong to $E_{\varvec{0}}$.

• ii) Like $F_1$, we note that $F_4 = F_4^{[1]}$ is lopsided at $\varvec{0}$, with dominant exponent $\beta =(0, 0, 0)$. The point $\varvec{0}$ then belongs to $E_{\varvec{0}}$. Since (0, 0, 0) is in the support of the filter ($F_4$ is monic), the necessary and sufficient conditions for strong BIBO stability are therefore met.

• iii) Likewise the BIBO stability of $F_5$ easily follows upon noting that each of its two factors is lopsided at $\varvec{0}$, with 0 as dominant exponent.

For each polynomial $F_i$, $i=1, \ldots , 5$, we compute $M=100$ sample realizations of $\widehat{R}_{F, {\varvec{U}}}$ and $\widehat{\nu }_{j,{\varvec{U}}}$, $j =1, \ldots , n$ as in (17) and (18), respectively. We use K-point MC integration with $K = 15000$. The resulting sequences¹ are displayed in the plots of Fig. 1 below, using the classical five-number summary boxplot diagram (showing the minimum, a (blue) box from the first to the third quartile, the median (red), the maximum and the outliers (red ’+’)).

Fig. 1

Boxplot of the approximation $\widehat{R}_{F, {\varvec{U}}}$ and $\widehat{\nu }_{j,{\varvec{U}}}$, $j =1, \ldots , n$

For the first three examples, $\widehat{R}_{F, {\varvec{U}}}$ is significantly different from 0 (see Fig. 1a). This is a sufficient condition to conclude to instability, in accordance with Table 1 indicating that the corresponding filters are unstable. An additional confirmation is provided in Fig. 1b which displays for each $F_i$, the sequence obtained by stacking the n corresponding sequences $\widehat{\nu }_{j,{\varvec{U}}}$, $j =1, \ldots , n$. Indeed, these sequences are also significantly different from 0 for $F_1$, $F_2$ and $F_3$, which also constitutes a sufficient condition for BIBO instability. Concerning $F_1$, we get $\widehat{\nu }_{j,{\varvec{U}}} = 1$ with a very low variance, showing to what extend the results of the stability analysis in the item i) above are retrieved, in particular $\varvec{0} \in E_{\beta =(1,1)}$. Note the contrast with the high dispersion of the corresponding sequence for $F_2$, suggesting that in this case, the origin is located in the amœba.

For $F_4$ and $F_5$, all sequences accumulate to 0, meaning that $\widehat{R}_{F, {\varvec{U}}} = 0$ a.e., and $\widehat{\nu }_{j,{\varvec{U}}} = 0$, a.e., $j =1, \ldots , n$. We then conclude that $F_4$ and $F_5$ are BIBO stable, in agreement with Table 1. Figures 1c and 1d present a tighter look at the sequences $\widehat{R}_{F, {\varvec{U}}}$ and $\widehat{\nu }_{j,{\varvec{U}}}$, $j =1, \ldots , n$ for $F_3$ and $F_5$ respectively. These plots illustrate the typical behavior of the different sequences when the filter is BIBO stable (how close to 0, in Fig. 1d) or unstable (how significantly different from 0, in Fig. 1c).

We close this subsection with the following two comments.

Recall that as the examples above have been taken from the literature, most of the methods mentioned so far are able to manage their BIBO stability analysis.

We also note that the corresponding approximated Ronkin function and exponents reveal very distinct values (very close to 0/very far from 0) depending on whether the filter is structurally BIBO stable or not. The clear-cut behaviors suggest that either the BIBO stability analysis of these polynomials is rather easy, reflecting a position far from the boundary of the stability domain, or the proposed method is very efficient. The latter alternative is investigated in the next section.

5.4 Performance of the MC approach

The objective of this subsection is to assess the performance of the proposed approach, combining Tropical geometry with Monte Carlo integration.

Related to the last two comments above, this section presents a set of experiments that allows one to 1) show that the proposed approach is not subject to the curse of dimensionality, unlike all the state-of-the-art methods and 2) investigate the sensitiveness of the BIBO stability test with respect to the closeness to the boundary of the stability domain.

To address these two points, it is first essential to be able to design nD-polynomials at will, with large n ($n = 4, 5, \ldots$), high degree, and with fully controlled BIBO stability properties.

5.4.1 Determinantal representation for stable nD-polynomials

A polynomial $G \in \mathbb {C}[x_1, \ldots , x_n]$ will be called $\Omega$-stable for some domain $\Omega \subset \mathbb {C}^n$, if G does not vanish in $\Omega$. Next we set the notation $\mathbb {C}^+ = \{s \in \mathbb {C}\,|\, \Im {s} > 0\}$ for the open upper half plane. The following result will be useful in the sequel (see (Borcea & Brändén, 2008) and (Wagner, 2011)).

Theorem 6

(Borcea and Brändén 2008, Proposition 2.4) Let $A_j$, $j=1, \ldots , n$ be n given positive semidefinite matrices, each of size $m\times m$. Let B be an $m\times m$ Hermitian matrix. Then the polynomial of n variables

$$\begin{aligned} P(s_1, \ldots , s_n) = \det (B + s_1 A_1 + \cdots + s_n A_n) \end{aligned}$$

(20)

has real coefficients and is either $(\mathbb {C}^+)^n$-stable or identically zero.

Let us make the following observations.

Lemma 7

Consider a $(\mathbb {C}^+)^n$-stable polynomial P obtained as in (20) of Theorem 6, with matrices B and $A_j$ of size m. Then we have

$$\begin{aligned} \deg _j P(s_1, \ldots , s_n)&= {{{\,\mathrm{\textrm{Rank}}\,}}}(A_j), \quad j = 1, \ldots , n\end{aligned}$$

(21)

$$\begin{aligned} \deg P(s_1, \ldots , s_n)&\leqslant m \end{aligned}$$

(22)

Proof

We first establish the equality (21). Let ${{\,\mathrm{\textrm{Rank}}\,}}(A_j) = \ell \leqslant m$ and consider the eigenvalue decomposition

$$\begin{aligned} A_j = Q \left[ \begin{array}{c|c} \Lambda &{}\\ \hline &{}\varvec{0} \end{array} \right] Q^* \end{aligned}$$

where $\Lambda$ is the diagonal matrix containing the $\ell$ (strictly) positive eigenvalues of $A_j$. Then, we may rewrite equation (20) as

$$\begin{aligned} P(s_1, \ldots , s_n) =\det \left[ \begin{array}{c|c} M_{11} + s_j \Lambda &{} M_{12}\\ \hline M_{21}&{}M_{22} \end{array} \right] \end{aligned}$$

where $M_{p,q}$ is the (p, q)-bloc submatrix of the matrix M given by

$$\begin{aligned} M = Q^* (B + \sum _{k=1,k\ne j}^n s_k A_k) Q. \end{aligned}$$

Now, we get

$$\begin{aligned} P(s_1, \ldots , s_n)&= \det (M_{22})\, \det (M_{11} - M_{12} M_{22}^{-1}M_{21} + s_j \Lambda )\\&= \det (M_{22})\, \det (\Lambda )\, \det (\Lambda ^{-1} [M_{11} - M_{12} M_{22}^{-1}M_{21}] + s_j \varvec{I}_\ell ) \end{aligned}$$

Hence, $P(s_1, \ldots , s_n) = \sum _{k=0}^\ell s_j^k p_k(s_1, \ldots , s_{j-1}, s_{j+1}, \ldots , s_n)$ reads as the characteristic polynomial of the $\ell \times \ell$-matrix $\Lambda ^{-1} [M_{11} - M_{12} M_{22}^{-1}M_{21}]$, multiplied by a polynomial which is independent of $s_j$. In particular, each $p_k$ above is a polynomial of the $n-1$ variables $s_q$, $q=1,\ldots , n$ and $q\ne j$.

The second part of the Lemma, that is the inequality (22), is straightforward. Indeed, the total degree of P cannot exceed the degree of the polynomial of one variable

$$\begin{aligned} q(s) = P(s, s, \ldots ,s) = \det (B + s \sum _j A_j). \end{aligned}$$

Now the degree of q(s) cannot obviously exceed the size of the matrix B. $\square$

To proceed, consider the Möbius map $s = \Phi (z) = i \frac{1+z}{1-z}$, which sends the open unit disc $\mathbb {D}$ (resp. unit circle $\partial \mathbb {D}$) to the open upper half plane $\mathbb {C}^+$ (resp. real line $\mathbb {R}$). Since $\Phi$ is a conformal map, it preserves (weak) stability. In other words, any $(\mathbb {C}^+)^n$-stable polynomial $P(s_1, \ldots , s_n)$, with $d_j = \deg _j P, j=1, \ldots , n$, is mapped by $\Phi (\cdot )$ to a polynomial

$$\begin{aligned} F(z_1, \ldots , z_n) = (1-z_1)^{d_1} \cdots (1-z_n)^{d_n} P(\Phi (z_1), \ldots , \Phi (z_n)) \end{aligned}$$

(23)

that is devoid of zero in $\mathbb {D}^n$ (Borcea & Brändén, 2008; Wagner, 2011). However, this mapping clearly induces at least one zero on the boundary of the unit polydisc, at the point $z_1 = z_2 = \cdots = z_n = 1$, unless $\alpha = (d_1, \ldots , d_n) \in \text {Supp } P$. Indeed, each monomial $c_{\alpha _1\cdots \alpha _n} s_1^{\alpha _1}\cdots s_n^{\alpha _n}$ of P is mapped to the corresponding monomial in F, given by

$$\begin{aligned} c_{\alpha _1\cdots \alpha _n} [i(1+z_1)]^{\alpha _1}\cdots [i(1+z_n)]^{\alpha _n} (1-z_1)^{d_1-\alpha _1} \cdots (1-z_n)^{d_n-\alpha _n}. \end{aligned}$$

Now this vanishes at $z_1= \cdots = z_n=1$ except when $d_j=\alpha _j$, for all $j=1,\ldots , n$.

As discussed above, the conversion from $(\mathbb {C}^+)^n$-stable to $\mathbb {D}^n$-stable polynomial may introduce some spurious zeros on the boundary of the unit polydisc. The presence of these zeros can be avoided by using a contractive determinantal representation for $\mathbb {D}^n$-stable polynomial (Grinshpan et al., 2013, 2016), as an alternative to Theorem 6 combined with the conformal mapping $\Phi (\cdot )$.

Given $r > 0$ and $F(z_1, \ldots , z_n) = \sum _{k \in \text {Supp } F \subset \mathbb {N}^n} a_{k_1\cdots k_n} z_1^{k_1}\cdots z_n^{k_n}$, we form the polynomial $F_r$ defined by

$$\begin{aligned} F_r(z_1, \ldots , z_n) = F(r z_1, \ldots ,r z_n) = \sum _{k \in \text {Supp } F \subset \mathbb {N}^n} r^{|k|} a_{k_1\cdots k_n} z_1^{k_1}\cdots z_n^{k_n} \end{aligned}$$

(24)

where $|k| = k_1+\cdots +k_n$. Clearly, to any zero, $z_0 \in \mathbb {C}^n$, of F corresponds a zero, $z'_0 = z_0/r$ of $F_r$. Starting from Theorem 6 and using Lemma 7, the procedure above shows how one can design an nD-polynomial $F_r$ with prescribed degrees $d_j$, $j=1, \ldots , n$, with completely controlled stability properties, depending on the choice of the parameter r. As the polynomial F, obtained from (23) and (20), is devoid of zero in the open unit polydisc $\mathbb {D}^n$, the associated polynomial $F_r$ will not vanish in the closed unit polydisc $\overline{\mathbb {D}}^n$ whenever $r < 1$. In particular, for $m < \sum _j d_j$ it comes that $\alpha = (d_1, \ldots , d_n) \notin \text {Supp } P$ and F admits a zero at the boundary point $z_1= \cdots =z_n= 1$ which is reflected in $F_r$ at the point $z'_1= \cdots = z'_n= 1/r$. The filter $F_r$ is thus strongly BIBO stable if, and only if, $r < 1$.

The next experiment gives an illustration of the immunity of the proposed approach to the curse of dimensionality. We use the construction above to design an nD-polynomial F, with $n = 5$ variables, with degrees $d_j = \deg _j F(z_1, \ldots , z_5) = j$, $j=1, \ldots , 5$. The matrices $A_j$ in (20) are of size $6\times 6$ and are simulated as

$$\begin{aligned} A_j = \sum _{\ell =1}^j \varvec{u}_\ell \varvec{u}_\ell ^* \end{aligned}$$

where the real and imaginary parts of the components of $\varvec{u}_\ell \in \mathbb {C}^6$ are sampled from a uniform distribution in $[-10, \, 10]$. The resulting polynomial F has a total degree of $d = m = 6$ and $m! = 720$ nonzero coefficients $a_{k_1\cdots k_5} \in \mathbb {C}$. It has no zero in the open unit polydisc but F vanishes at the boundary point $z_1=\cdots =z_5=1$ since $m < \sum _j d_j = 15$. Given r, we form $F_r$ from F and we compute $M=100$ samples of $\widehat{R}_{F_r, {\varvec{U}}}$ and of $\widehat{\nu }_{j,{\varvec{U}}}$, $j =1, \ldots , 5$, using K-point MC integration. The obtained sequences are all stacked together to form a unique sequence of size 6M. Figure 2 above displays the boxplot of this sequence for different values of r indicated on the abscissa axis.

Fig. 2

Boxplot of $\widehat{R}_{F_r, {\varvec{U}}}, \widehat{\nu }_{j,{\varvec{U}}}$, for different r, with $k = 50\,000$

It is remarkable how sensitive the proposed method is, with a high ability to discern strong structural stability ($r < 1$ top subplot) from instability ($r > 1$ bottom subplot, including weak structural stability $r=1$), even in borderline situations ($r=0.999$).

The results above have been obtained using $K=50\,000$ points for the MC integration. For each r, the Matlab computation time of the stacked sequence of the $6\times 100$ samples of $\widehat{R}_{F_r, {\varvec{U}}}$ and $\widehat{\nu }_{j,{\varvec{U}}}, j = 1, \ldots , 5$ took less than 42s. This computation time drops to less than 8s when the number of MC sample points is set to $K = 10\, 000$. The consequence of such complexity saving is just a small increase of the variance of the estimates, as shown in Fig. 3 below.

Fig. 3

Boxplot of $\widehat{R}_{F_r, {\varvec{U}}}, \widehat{\nu }_{j,{\varvec{U}}}$, for different r, with $K = 10\,000$

Note that the performance of the method, in terms of sensitivity and discernibility, does not degrade. Indeed, the mean and median of the sequences do not vary a lot: They are significantly different from 0 in case of instability ($r > 1$) and very close to zero when $F_r$ is strong structurally stable ($r < 1$) as shown in Table 2 above.

Table 2 Mean and Median of the estimates $\widehat{R}_{F_r, {\varvec{U}}}, \widehat{\nu }_{j,{\varvec{U}}}$

These experiment suggest that the number K of MC points is not a critical parameter.

5.4.2 Multiaffine polynomials

This section presents a setting in which the proposed method shows limitations, at least in its form described so far. These limitations are then definitely lifted by a simple patch.

Following (Wagner, 2011) and (Borcea & Brändén, 2009), we introduce for $n \in \mathbb {N}^*$ the linear transformation ${{\,\mathrm{\textrm{Pol}}\,}}_n : \mathbb {C}[z] \rightarrow \mathbb {C}[z_1, \ldots , z_n]$ which associates to each monomial $z^j \in \mathbb {C}[z]$, the elementary symmetric and homogeneous polynomials $e_j \in \mathbb {C}[z_1, \ldots , z_n]$ defined by $e_0(z_1, \ldots , z_n) = 1$ and

$$\begin{aligned} e_j(z_1, \ldots , z_n) = \left( {\begin{array}{c}n\\ j\end{array}}\right) ^{-1} \sum _{1 \leqslant i_1< \cdots < i_j \leqslant n} z_{i_1}\cdots z_{i_j}, \quad j=1, \ldots , n. \end{aligned}$$

Let f(z) be a univariate polynomial of degree n. The $n^{th}$-polarization of f is defined by the multiaffine polynomial (Wagner, 2011; Borcea & Brändén, 2009), $F(z_1, \ldots , z_n) = [{{\,\mathrm{\textrm{Pol}}\,}}_n f](z_1, \ldots , z_n)$ obtained as the image of f by the transformation ${{\,\mathrm{\textrm{Pol}}\,}}_n$. Then, we have

Theorem 8

(Borcea and Brändén 2009; Wagner 2011, Theorem 1.2, Lemma 4.2) Let $f(z) \in \mathbb {C}[z]$ be a polynomial of degree n. Then $F(z_1, \ldots , z_n) = [{{\,\mathrm{\textrm{Pol}}\,}}_n f](z_1, \ldots , z_n)$ is $\mathbb {D}^n$-BIBO stable if, and only if, f is $\mathbb {D}$-BIBO stable.

This theorem thus provides a procedure for designing multiaffine polynomials with known stability properties. We therefore use it in the next experiment.

We generate univariate polynomials f(z) of degree $n=6$, having $0 \leqslant \ell \leqslant 6$ zeros with a fixed modulus given by a parameter r, with phases uniformly distributed on $(0, 2\pi )$. The remaining $n-\ell$ zeros are chosen randomly, out of the unit disk. For each couple of such f, say $f_1, f_2$, we form the product of the two associated multiaffine polynomials $[{{\,\mathrm{\textrm{Pol}}\,}}_6f_i]$, $i=1,2$ which results to a polynomial of 6 variables and total degree 12. We subsequently denote this polynomial by $F_{r}(z_1, \ldots , z_6) = [{{\,\mathrm{\textrm{Pol}}\,}}_6 f_1]\cdot [{{\,\mathrm{\textrm{Pol}}\,}}_6 f_2]$ to make explicit the dependence on the parameter r which controls the stability. By Theorem 8, $F_r$ is strongly BIBO stable if, and only if, $r > 1$. Figure 4 shows the boxplot of the sequences $\{\widehat{R}_{F_r,{\varvec{U}}_m}\}, \{\widehat{\nu }_{j,{\varvec{U}}_m}\}, j=1,\ldots , 6; m=1,\ldots , 100$ for $r=0.98$.

Fig. 4

Multiaffine polynomials: boxplot of $\widehat{R}_{F_r, {\varvec{U}}}$ and $\widehat{\nu }_{j,{\varvec{U}}}$, $1 \leqslant j \leqslant 6$, for unstable $F_r$, $r=0.98$

Since $F_r$ is unstable in this case, one expects that the numerical values of all the sequences be significantly different from zeros. Now, this is not the behavior observed with $\ell =1$ unstable zero (left plot). With $\ell =2$ unstable zeros, the deviations from zero are still insignificant even if they are more accentuated (right plot).

We consider the next experiment to investigate this seeming limitation of the proposed method. For each given r, we compute the sample means

$$\begin{aligned} \overline{\widehat{R}_{F_r, {\varvec{U}}}} = \frac{1}{M} \sum _{m=1}^M \widehat{R}_{F_r, {\varvec{U}}_m} ; \quad \overline{\widehat{\nu }_{j,{\varvec{U}}}} = \frac{1}{M} \sum _{m=1}^M \widehat{\nu }_{j,{\varvec{U}}_m}, j=1, \ldots , 6. \end{aligned}$$

(25)

For this experiment, the statistic $\mathcal {S}$ is set as

$$\begin{aligned} \mathcal {S}(\widehat{R}_{F, {\varvec{U}}}, \widehat{\nu }_{1,{\varvec{U}}}, \ldots , \widehat{\nu }_{n,{\varvec{U}}}) = \max (|\overline{\widehat{R}_{F_r, {\varvec{U}}}}|, |\overline{\widehat{\nu }_{j,{\varvec{U}}}}|, j=1, \ldots , 6) \end{aligned}$$

and we validate the hypothesis $H_0$ ($F_r$ is BIBO stable) if $\mathcal {S}(\widehat{R}_{F, {\varvec{U}}}, \widehat{\nu }_{1,{\varvec{U}}}, \ldots , \widehat{\nu }_{n,{\varvec{U}}}) < \gamma$, where $\gamma$ is a given threshold. For each r, we repeat this experience 5000 times and compute the corresponding probability of error which is displayed in Fig. 5 above for different threshold $\gamma$.

Fig. 5

Probability of error

These results reveal that, in its current form, the proposed MC based method can be unreliable when the filter is in certain particular configuration and close to the boundary of the stability domain. Indeed, the probability of error is all the more greater as the filter approaches the stability limit while being unstable (see top plot of Fig. 5). Note however that this probability is less important as the number of unstable zeros of the associated univariate polynomial increases (see bottom plot of Fig. 5).

For a univariate polynomial f of degree n, we recall that by the Grace-Walsh-Szegö coincidence Theorem (GWST) (Walsh, 1964; Borcea & Brändén, 2009), one can associate to every point $(z_1, \ldots , z_n) \in \mathbb {D}^n$ a point $x \in \mathbb {D}$ such that

$$\begin{aligned}{}[{{\,\mathrm{\textrm{Pol}}\,}}_n f](z_1, \ldots , z_n) := F(z_1, \ldots , z_n) = F(x, \ldots , x) = f(x). \end{aligned}$$

Now, during the K-points MC computation of the Ronkin function $\widehat{R}_{F, {\varvec{U}}}$ (17), it may happen that the K sampled points $\varvec{\xi }_k = (\xi _{1,k}, \ldots , \xi _{n,k}), \text { where } \xi _{j,k} = e^{i 2\pi u_{j,k}}, k=1, \ldots , K$ are associated by the GWST to points $\zeta _k$ that fall outside some arc of the unit circle. If such situation occurs, then the computation of the Ronkin function and the exponents cannot be accurate. Recall that each exponent is the degree of the corresponding loop in (9).

A simple solution will then be to complete the sample set $\{e^{i 2\pi {\varvec{U}}}\}$ with points $\{\varvec{\xi } = (\xi , \ldots , \xi ) \in \mathbb {C}^n \ | \ |\xi | = 1\}$ that are sampled uniformly on the diagonal of the unit polycircle. Indeed, with this modification, the same experiment of Fig. 4 now produces sequences $\widehat{R}_{F_r, {\varvec{U}}}$ and $\widehat{\nu }_{j,{\varvec{U}}}$, $1 \leqslant j \leqslant 6$ with completely different behaviors are shown below.

Fig. 6

Multiaffine polynomials: boxplot of $\widehat{R}_{F_r, {\varvec{U}}}$ and $\widehat{\nu }_{j,{\varvec{U}}}$, $1 \leqslant j \leqslant 6$, for unstable $F_r$, $r=0.98$ - with samples on the diagonal of the polycircle

Repeating the experiment in Fig. 5 with samples on the diagonal of the unit polycircle, resulted in no error for all values of r, even for $r=0.999$. We observe that with this modification, the number K of MC points can be decreased very significantly without any impact on the accuracy of the test. In particular, the last experiment in Fig. 6 is carried with $K=2000$ instead of $K=10000$ in the previous case.

We observe that although the filter is unstable, the origin is located outside the amœba, namely in the component $E_\beta$, with $\beta = (2, 2, 2, 2, 2, 2)$.

5.5 IsStable algorithm

We now summarize all the preceding developments and present the final algorithm for testing the BIBO stability. As we will show, the test can be applied for multivariate polynomial of n variables for high values of n and for high degree. In fact the number of variables does not have any impact on the complexity of the method except on the evaluations of the polynomial at the sampled points.

To proceed, we first clarify the choice of the statistic $\mathcal {S}$, as announced at the end of section 5.2. The illustrative examples treated so far suggest to define the statistic $\mathcal {S}$ as the mean of the collected sequences $\{\widehat{R}_{F, {\varvec{U}}}\}$ and $\{(\widehat{\nu }_{1,{\varvec{U}}}, \ldots , \widehat{\nu }_{n,{\varvec{U}}})\}$:

$$\begin{aligned} \mathcal {S}(\widehat{R}_{F, {\varvec{U}}}, \widehat{\nu }_{1,{\varvec{U}}}, \ldots , \widehat{\nu }_{n,{\varvec{U}}}) = \frac{1}{2}\left[ {{\,\mathrm{\textsf {E}}\,}}(\widehat{R}_{F, {\varvec{U}}}) + \frac{1}{n}\sum _{j=1}^n {{\,\mathrm{\textsf {E}}\,}}(\widehat{\nu }_{j,{\varvec{U}}})\right] \end{aligned}$$

(26)

This amounts to considering a single random variable $\mathcal {R}_{F,U}$ defined by

$$\begin{aligned} \mathcal {R}_{F,U} = \widehat{R}_{F, {\varvec{U}}} + \frac{1}{n}\sum _{j=1}^n \widehat{\nu }_{j,{\varvec{U}}}. \end{aligned}$$

(27)

The test of BIBO stability then reduces to a classical test of zero mean for $\mathcal {R}_{F,U}$. The final algorithm can thus be described as follow, where K, L, M stand respectively for the number of MC integration points, the length of each sequence $\widehat{R}_{F, {\varvec{U}}}$, $\widehat{\nu }_{j,{\varvec{U}}}$, $j=1,\ldots , n$ and the number of trials:

The procedure of adding samples on the diagonal of the polycircle is equivalently replaced here by the $1D$-BIBO stability test of the diagonal slice of $F$, given by $f(z)$. It is clear that the stability of $f(z)$ is a necessary condition for $F$ to be stable.

Before closing this section, we present some last experiments to confirm the claim that the proposed algorithm does not stuck from the curse of dimensionality. How the algorithm is effective for testing the BIBO stability even in high dimension is illustrated through the example below. We consider the $nD$ polynomial $F(z_1, \ldots , z_n)$ with $n=10$ variables and of degree $\deg {F} = 14$,

$$\begin{aligned} F(z_1, \ldots , z_{10})&= c_{16} z_1^3 z_2^3 z_3^2 z_4^3 z_{10}^3 + c_{15} z_1^2 z_9^3 +c_{14} z_1 z_2 z_9 + c_{13}z_1 z_3 z_4 z_7 + c_{12} z_1 z_4 z_7\nonumber \\&\quad + c_{11} z_1 z_7^3 z_{10} + c_{10} z_1 + c_{9} z_2 z_3^2 z_6 z_8^2 + c_8 z_2 z_4 z_6 z_8 + c_7 z_2 z_5 z_6 +c_6 z_3 z_9^2 \nonumber \\&\quad + c_5 z_4 z_6^2 z_9^2 +c_4 z_5^3 z_8^3 + c_3 z_5^2 z_8 z_{10}+ c_2 z_5 z_{10}^2 + c_1 z_8 + c_0. \end{aligned}$$

(28)

where the coefficients $c_{k}, k=1, \ldots , 16$ are given by

$$\begin{aligned} c_{1}&= -0.4 + 0.8 i&c_{2}&=0.7-0.5i&c_{3}&= -0.1 + 0.7i&c_{4}&= -0.4+ 2.0i\\ c_{5}&= 0.6 + 1.1i&c_{6}&= -0.5 - 0.1i&c_{7}&= 0.3 - 0.7i&c_{8}&=-0.8+ 1.3i\\ c_{9}&=-1.4-0.1i&c_{10}&=0.9 - 0.2i&c_{11}&=0.6+2.4i&c_{12}&=0.2+0.9i\\ c_{13}&= -0.3 - 1.5i&c_{14}&=0.2 + 0.6i&c_{15}&=-1.3 - 1.3i&c_{16}&= 1.1 -1.6i \end{aligned}$$

The constant term is then selected such that $F$ vanishes at a given prescribed point $Z \in \mathbb {C}^{10}$. The points marked by ’$*$’ in Fig. 7 represent the components $Z_{j}, j=1,\ldots , 10$ of $Z$, for $c_{0}=-7.1616 - 6.3746i$. The unit circle is displayed in dashed line, as a reference.

Fig. 7

Unstable zero of $F(z_1, \ldots , z_{10})$ (’$*$’) and stable zeros of $f(z)$, (’$+$’)

For this choice of $c_0$, the resulting polynomial, noted by $F_{0}$, is clearly unstable since $|Z_j| < 1$ for all $j$. (The marks ’+’ represent the zeros of the diagonal slice $f_0(z) = F_0(z, \ldots , z)$, which is clearly stable). Henceforth, the coefficients $c_{k}, k=1, \ldots , 16$ are fixed as above and the constant term $c_{0}$ is allowed to vary in terms of a parameter $\tau > 0$ as

$$\begin{aligned} |c_0| = \tau \sum _{k=1}^{16} |c_k|. \end{aligned}$$

To the knowledge of the authors, there is no example in the literature with such a large $n$ on which a BIBO stability test has been successfully applied. The numerical values of the coefficients $c_{k}$, $k>0$, have been generated randomly and then rounded to a single significant digit for display and easy reproducibility purposes.

Starting from the unstable polynomial $F_{0}$, we increase progressively the module of the constant term. Equivalently, we increase the value of $\tau$, from $\tau _0 = 0.4743$, corresponding to $F_0$, up to some values of $\tau > 1$, corresponding to polynomials lopsided at $\textbf{0}$, hence BIBO stable. For each $\tau$, we compute the mean $\overline{\mathcal {R}}_{F}$ and the $p$-value of the associated t-test, as described in the algorithm above. Figure 8 below displays the computed values $\overline{\mathcal {R}}_{F,\ell }$ as a function of $\tau$ in the top subplot.

Fig. 8

IsStable algorithm on ten variables polynomial $F(z_1, \ldots , z_{10})$

The parameters used in this experiment are : $K=10^4$, $M=100$ and $L=30$. To show the added value of combining several trials as in line 11 of Algorithm 1, we first consider each trial separately with a t-test for zero mean, for each corresponding sequence $\{\mathcal {R}_{F,{\varvec{U}}_m}, m=1,\ldots , M\}$. The lower and upper hull of the $p$-values computed for the different $L$ sequences are displayed as a function of $\tau$ in the middle subplot, along with the median and the 10-quantile curves resulting from the $L$ trials. All individual tests clearly conclude that the first 4 filters, including $F_0$, are unstable (the corresponding $p$-values are equal to zero a.e.). Based on a confidence level of $\alpha = 0.05$, we observe that $90\%$ of the tests conclude with the stability of all the other polynomials except the fifth one. For the fifth polynomial, however, the null hypothesis is rejected (at $\alpha =5\%$), for some trials and accepted for others. As the median is closer to the lower hull than to the upper one, a voting procedure would likely lead to a rejection and, consequently, to the conclusion that the corresponding polynomial is not BIBO stable. These discussions show that the different trials need to be combined and this was the motivation of the loop at line 4 and 11 of Algorithm 1. With such combination, IsStable provides clear-cut answers as shown in the bottom subplot of Fig. 8. This graph displays the $p$-value resulting to the t-test for zero mean for the sequence $\{\overline{\mathcal {R}}_{F,\ell }, \ell =1, \ldots , L\}{}$.

6 Conclusion

The paper has proposed a tropical geometry approach to the question of Bounded-Input, Bounded-Output (BIBO) stability of multivariate $n$-rational systems. The notion of structural stability is shown to be equivalent to the membership of the origin of $\mathbb {R}^n$ to a specific open connected component of the complement of the amoeba associated with the denominator of the coprime transfer function of the system. Considering the boundary of this connected component, we have also introduced the notion of structural weak stability. This geometrical standpoint is then exploited to devise a numerical algorithm for testing BIBO stability. Extensive simulation examples are presented to asses the performance of the proposed algorithm. It is based on the method of classical Monte-Carlo integration and it shows an efficiency all the more surprising that it is conceptually simple. Regarding the computational complexity, the simulation study shows that the algorithm escapes the curse of dimensionality unlike the state-of-the-art methods which are practically effective only for a number of variables not exceeding 5.