<figure><img src="image_1.png" /></figure>

# $L^\infty$-norm computation for linear time-invariant systems depending on parameters

ALBAN QUADRAT and FABRICE ROUILLIER*, Sorbonne Université and Université de Paris, CNRS, IMJ-PRG, Inria Paris, France

GRACE YOUNES, Department of Sciences and Engineering, Sorbonne University Abu Dhabi and SUAD Research Institute, UAE

**Abstract.** This paper focuses on representing the $L^\infty$-norm of finite-dimensional linear time-invariant systems with parameter-dependent coefficients. Previous studies tackled the problem in a non-parametric scenario by simplifying it to finding the maximal $y$-projection of real solutions $(x, y)$ of a system of the form $\Sigma = \{P = 0, \partial P/\partial x = 0\}$, where $P \in \mathbb{Q}[x, y]$. To solve this problem, standard computer algebra methods were employed and analyzed.

In this paper, we address the parametric case where we aim to represent the maximal $y$-projection of real solutions of $\Sigma$ as a function of the given parameters. To accomplish this, we utilize cylindrical algebraic decomposition. This method allows us to determine the desired value as a function of the parameters within specific regions of parameter space.

CCS Concepts: • **Computing methodologies** → **Algebraic algorithms**.

Additional Key Words and Phrases: $L^\infty$-norm computation, polynomial systems, control theory

**Recommended Reference Format:**

Alban Quadrat, Fabrice Rouillier, and Grace Younes. 2024. $L^\infty$-norm computation for linear time-invariant systems depending on parameters. *Maple Trans.* 4, 1, Article 17129 (June 2024), 18 pages. https://doi.org/10.5206/mt.v4i1.17129

## 1 Introduction

In control theory, a key objective is to design a controller that stabilizes an unstable system, known as a plant, and then optimize the performance of the closed-loop system obtained by integrating the controller with the plant in a feedback loop. The concept of robustness, crucial in control theory, mathematically models uncertainties and errors inherent in the knowledge of physical systems. It plays a pivotal role in analyzing and designing control systems, enabling engineers to address uncertainties and disturbances effectively. By quantifying the worst-case effect of exogenous inputs (such as disturbances, noise, and parameter uncertainties) on error signals, the $L^\infty$-norm provides insights into the system's robustness with respect to modeling errors and its ability to handle unwanted signals. For more details, see [12, 20, 19] and the references therein.

Within the frequency domain approach to linear time-invariant systems, Zames shows [18] that the standard concept of stability corresponds to a system defined by a transfer matrix (which defines the dynamics between the inputs and the outputs of the system) whose entries belong to the Hardy algebra $H^\infty$ formed by the holomorphic functions in the right half complex plane which are bounded for the supremum norm. By the maximum modulus principle, it means that the

<footnote>Authors' addresses: Alban Quadrat, alban.quadrat@inria.fr; Fabrice Rouillier, fabrice.rouillier@inria.fr, Sorbonne Université and Université de Paris, CNRS, IMJ-PRG, Inria Paris, F-75005, Paris, France; Grace Younes, Department of Sciences and Engineering, Sorbonne University Abu Dhabi and SUAD Research Institute, Abu Dhabi, UAE, grace.younes@sorbonne.ae.</footnote>

<footnote>Permission to make digital or hard copies of all or part of this work for any use is granted without fee, provided that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. © 2024 Copyright held by the owner/author(s). Publication rights licensed to Maple Transactions, under Creative Commons CC-BY 4.0 License.</footnote>

<footnote>https://doi.org/10.5206/mt.v4i1.17129</footnote>
$H^\infty$-norm corresponds to the $L^\infty$-norm of the restriction of the transfer matrix to the imaginary axis $i\mathbb{R}$, i.e., the frequency axis. In the case of time-invariant finite-dimensional systems, i.e., systems defined by linear ordinary differential equations with constant coefficients, the coefficients of the corresponding transfer matrix are rational functions of a complex variable $s$. Zames’ approach was the starting point for the development of the so-called robust control theory or $H^\infty$-control theory (see [12, 20] and the references therein), a major achievement in control theory, which is nowadays commonly used by companies working in the area of control theory. In this approach, a property of a system is said to be robust if it is valid for all systems defined in a ball around the original system with a small radius for the $H^\infty$-norm.

The computation of the $H^\infty$-norm of finite-dimensional linear time-invariant systems, i.e., the $L^\infty$-norm of the restriction of a matrix with complex univariate rational function entries to the purely imaginary axis $i\mathbb{R}$, is thus a fundamental problem in robust control theory. Unfortunately and contrary to the $L^2$-norm (see, e.g., [20]), it is not possible to characterize this $L^\infty$-norm using simple closed-form expressions depending on the system coefficients. It is usually computed using numerical methods based on testing the existence of pure imaginary eigenvalues of Hamiltonian matrices and bisections (see [5, 4, 6, 20, 19]).

Previous studies [15, 3] explored the problem by reformulating it as finding the maximal $y$-projection of the real curve represented by the polynomial equation $P = 0$, where $P \in \mathbb{Q}[x, y]$. The computation involved identifying the maximal (largest possible) $y$-coordinate of the real solutions $(x, y)$ for the system of polynomial equations $\Sigma = \{P = 0, \partial P/\partial x = 0\}$. To solve this problem in a certified manner, standard computer algebra methods (such as Rational Univariate Representation (RUR), Sturm-Habicht sequences, and certified root isolation of univariate polynomials) were used. Finally, in [3], three different algorithms were proposed with their complexity analysis and implementation. In this paper, we investigate the computation of the $H_\infty$-norm of linear time-invariant systems of coefficients depending on constant parameters. Building on [3], we extend the methodology to handle parametric scenarios where $P$ belongs to $\mathbb{Q}[\alpha_1, \dots, \alpha_d][x, y]$. Here, $\alpha_1, \dots, \alpha_d$ represent the parameters under consideration. In this setting, the maximal $y$-projection of real solutions of $\Sigma$ can now be viewed as a semi-algebraic function of the given parameters. We show that it can be computed as part of a Cylindrical Algebraic Decomposition (CAD) of the parameter's space, adapted to polynomials computed with an ad-hoc projection strategy. It is important to note that symbolic methods for parametric optimization offer advantages over numerical approaches: they handle non-convex feasible regions without theoretical concerns and are not constrained by the size of parameter regions, even when unbounded or arbitrarily small. Additionally, symbolic methods partition the parameter space based on singularities, providing insight into the complexity of the solving process.

In Section 2, we will begin by outlining the problem at hand and then in Section 3 we will provide a concise overview of the research conducted in [3]. We then extend this work to scenarios involving parameters within the polynomial coefficients.

Please note that in this paper, our objective is to describe algorithms in terms of computable objects, irrespective of the specific algorithms used for computation. For instance, for historical reasons, we utilized the *CellDecomposition* from the *RootFinding[Parametric]* package in Maple, which is designed for solving parametric polynomial systems as described in [13]. This method predominantly employs techniques such as Gröbner bases, polynomial real root finding, and Cylindrical Algebraic Decomposition (CAD). However, we could also employ the * QuantifierElimination* package, newly introduced in Maple 2023. This package offers a fresh suite of routines for quantifier elimination over the reals, incorporating a new implementation of cylindrical algebraic decomposition. This approach allows us to independently focus on refining the general algorithm and optimizing its most critical sub-algorithms.
For example, we conducted tests using the newest approach for computing a RUR described in [10]. These tests have altered our previous observations discussed in [3] concerning the algorithms designed for the non-parametric cases, introduced in Section 3. Through this exploration, we have identified numerous optimizations and uncovered new packages that significantly improve computation times for a general implementation. These findings have the potential to contribute new insights, particularly in our examination of the practical limitations inherent in our methods.

## 2 Problem description

We first introduce a few standard notations and definitions. If $\mathbb{k}$ is a field and $P \in \mathbb{k}[x, y]$, then $L_{\mathbb{k}}\text{var}(P)$ is the leading coefficient of $P$ with respect to the variable $\text{var} \in \{x, y\}$ and $\text{deg}_{\text{var}}(P)$ the degree of $P$ in the variable $\text{var} \in \{x, y\}$. We also denote by $\text{deg}(P)$ the total degree of $P$. Moreover, let $\pi_x : \mathbb{R}^2 \to \mathbb{R}$ be the projection map from the real plane $\mathbb{R}^2$ onto the x-axis, i.e., $\pi_x(a, b) = a$ for all $(a, b) \in \mathbb{R}^2$. In this case, we say that $a$ is the x-projection of $(a, b)$. Similarly, for the y-projection, $\pi_y(a, b)$ yields the y-coordinate $b$. For $P, Q \in \mathbb{k}[x, y]$, let $\text{gcd}(P, Q)$ be the greatest common divisor of $P$ and $Q$, $I := \langle P, Q \rangle$ the ideal of $\mathbb{k}[x, y]$ generated by $P$ and $Q$, and $V_{\mathbb{k}}(I) := \{(x, y) \in \mathbb{k}^2 | \forall R \in I : R(x, y) = 0\}$ the affine algebraic set defined by $I$, where $\mathbb{k}$ is a field containing $\mathbb{k}$. Finally, let $\mathbb{C}_+ := \{s \in \mathbb{C} | \mathfrak{R}(s) > 0\}$ be the open right half-plane of $\mathbb{C}$.

**Definition 2.1** ([12, 20]). Let $RH_{\infty}$ be the $\mathbb{R}$-algebra of all the proper and stable rational functions with real coefficients, namely:

$$RH_{\infty} := \left\{ \frac{n}{d} \mid n, d \in \mathbb{R}[s], \text{gcd}(n, d) = 1, \text{deg}_{\mathbb{s}}(n) \le \text{deg}_{\mathbb{s}}(d), V_{\mathbb{C}}(\langle d \rangle) \cap \mathbb{C}_{+} = \emptyset \right\}.$$

An element $g$ of $RH_{\infty}$ is holomorphic and bounded on $\mathbb{C}_{+}$, i.e.,

$$\| g \|_{\infty} := \sup_{s \in \mathbb{C}_{+}} |g(s)| < +\infty.$$

$RH_{\infty}$ is a sub-algebra of the Hardy algebra $H_{\infty}(\mathbb{C}_{+})$ of bounded holomorphic functions on $\mathbb{C}_{+}$. The maximum modulus principle of complex analysis yields:

$$\forall g \in RH_{\infty}, \quad \| g \|_{\infty} = \sup_{\omega \in \mathbb{R}} |g(i \omega)|.$$

Note that this equality shows that the function $g_{i\mathbb{R}} : i\omega \in i\mathbb{R} \mapsto g(i\omega)$ belongs to the Lebesgue space $L_{\infty}(i\mathbb{R})$ or, more precisely, to the following $\mathbb{R}$-algebra

$$RL_{\infty} := \left\{ \frac{n(i \omega)}{d(i \omega)} \mid n, d \in \mathbb{R}[i \omega], \text{gcd}(n, d) = 1, \text{deg}_{\omega}(n) \le \text{deg}_{\omega}(d), V_{i\mathbb{R}}(\langle d \rangle) = \emptyset \right\},$$

i.e., the algebra of real rational functions on the imaginary axis $i\mathbb{R}$ which are proper and have no poles on $i\mathbb{R}$, or simply, the algebra of real rational functions with no poles on $i\mathbb{P}^1(\mathbb{R})$, where $\mathbb{P}^1(\mathbb{R}) := \mathbb{R} \cup \infty$.

We can extend the above $L_{\infty}$-norms defined on functions of $RH_{\infty}$ (resp., $RL_{\infty}$) to matrices as follows. Let $G \in RH_{\infty}^{u \times v}$ (resp., $G \in RL_{\infty}^{u \times v}$, $\mathbb{R}(s)^{u \times v}$), i.e., $G$ is a $u \times v$ matrix with entries in $RH_{\infty}$ (resp., $RL_{\infty}$, $\mathbb{R}(s)$) and let $\bar{\sigma}(\cdot)$ denote the largest singular value of a complex matrix. Then, we can define:

$$\| G \|_{\infty} := \sup_{s \in \mathbb{C}_{+}} \bar{\sigma}(G(s)).$$

If $G \in RH_{\infty}^{u \times v}$, then, as above, we have $\| G \|_{\infty} = \sup_{\omega \in \mathbb{R}} \bar{\sigma}(G(i\omega))$.

The conjugate $\tilde{G}$ of $G \in \mathbb{R}(s)^{u \times v}$ is defined by $\tilde{G}(s) := G^T(-s)$.

The next proposition gives a first characterization of $\| G \|_{\infty}$.
**PROPOSITION 2.2** ([15]). Let $\gamma > 0$, $G \in \mathbb{R}(s)^{u \times v}$ be such that $G|_{i \mathbb{R}} \in RL_{\infty}^{u \times v}$ and let us consider $\Phi_{\gamma}(s) = \gamma^2 I_v - \tilde{G}(s)G(s)$. Then, $\gamma > \|G\|_{\infty}$ if and only if $\gamma > \bar{\sigma}(G(i\infty))$ and $\det(\Phi_{\gamma}(i\omega)) \neq 0$ for all $\omega \in \mathbb{R}$.

Since $\det(\Phi_{\gamma}(i\omega))$ is a real rational function of $\omega$ and $\gamma$ (in fact a real rational function of $\omega^2$ and $\gamma^2$ by the parity of $\Phi_{\gamma}$), we can then write

$$ \det(\Phi_{\gamma}(i\omega)) = \frac{n(\omega, \gamma)}{d(\omega)}, \qquad (1) $$

where $n \in \mathbb{R}[\omega, \gamma]$ and $d \in \mathbb{R}[\omega]$ are coprime. To compute the maximal singular value of $G(i\omega)$, we have to compute the maximal real value $\gamma$ satisfying that a real value $\omega$ exists such that $\det(\Phi_{\gamma}(i\omega))$ vanishes.

Since $G$ has no poles on the imaginary axis, $d(\omega)$ does not vanish on $\mathbb{R}$. Hence, to compute the $L^{\infty}$-norm of $G$, it suffices to compute the maximal real value $\gamma$ such that there exists at least one real value $\omega$ for which $n(\omega, \gamma)$ vanishes. Hence, we are led to study the $\gamma$-extremal points (and thus, the critical points) of the following real plane algebraic curve:

$$ C := \{(\omega, \gamma) \in \mathbb{R}^2 \mid n(\omega, \gamma) = 0\}. \qquad (2) $$

**Definition 2.3.** Let $\gamma > 0$ and $G \in \mathbb{R}(s)^{u \times v}$ be such that $G|_{i \mathbb{R}} \in RL_{\infty}^{u \times v}$. The numerator $n \in \mathbb{R}[\omega, \gamma]$ of $\det(\gamma^2 I_v - G^T(-i\omega)G(i\omega)) = n/d$, where $d \in \mathbb{R}[\omega]$ and $\gcd(d, n) = 1$, is called the polynomial associated with the $L^{\infty}$-norm.

**PROPOSITION 2.4** ([15]). Let $G \in RL_{\infty}^{u \times v}$ and $n \in \mathbb{R}[\omega, \gamma]$ be the polynomial associated with the $L^{\infty}$-norm. We denote by $\tilde{n} \in \mathbb{R}[\omega, \gamma]$ the square free part of $n$. Then, we have:

$$ \| G \|_{\infty} = \max \left\{ \pi_{\gamma} \left( V_{\mathbb{R}} \left( \left( \bar{n}, \frac{\partial \bar{n}}{\partial \omega} \right) \right) \right) \cup V_{\mathbb{R}} \left( \langle Lc_{\omega}(\bar{n}) \rangle \right) \right\}. $$

**COROLLARY 2.5.** Let $G \in RL_{\infty}^{u \times v}$ and $n \in \mathbb{R}[\omega, \gamma]$ be the polynomial associated with the $L^{\infty}$-norm. Then, the real $\gamma$-projection $\pi_{\gamma}(V_{\mathbb{R}}(\langle n \rangle))$ of $V_{\mathbb{R}}(\langle n \rangle)$ is bounded by $\|G\|_{\infty}$.

According to Proposition 2.4, given $G \in RL_{\infty}^{u \times v}$, the problem of computing $\|G\|_{\infty}$ can be reduced to the computation of the maximal $\gamma$-projection of the real solutions of the following bivariate polynomial system:

$$ \Sigma := \left\{ \bar{n}(\omega, \gamma) = 0, \frac{\partial \bar{n}(\omega, \gamma)}{\partial \omega} = 0 \right\}. \qquad (3) $$

This amounts to finding the maximal positive real number $\gamma_*$ such that the plane algebraic curve $n(\omega, \gamma) = 0$ has points of the form $(\omega, \gamma_*)$ with $\omega$ being real numbers, i.e., such that $n(\omega, \gamma_*) = 0$ has at least one real root $\omega$. This study was done in [3, 15] for $n \in \mathbb{Q}[\omega, \gamma]$. In the upcoming section, we will provide a concise summary of this study before delving into our study of the problem where $n \in \mathbb{Q}[\alpha][\omega, \gamma]$, with $\alpha = \alpha_1, \dots, \alpha_d$ representing a set of real parameters.

### 3 Proposed methods in the non-parametric case

Without loss of generality, we will suppose that $n$ is squarefree in $\mathbb{Q}[\omega, \gamma]$. We also denote $x := \omega$, $y := \gamma$, and $P := n(\omega, \gamma)$.

Based on standard computer algebra methods and implementations, [3] developed methods for the study of the computation of the $L^{\infty}$-norm of finite-dimensional linear time-invariant systems. This problem is reduced to the computation of the maximal $y$-projection of the real solutions $(x, y)$ of the zero-dimensional system of two bivariate polynomial equations defined by:

$$ \Sigma = V_{\mathbb{R}}(\langle P, Q \rangle), \quad P \in \mathbb{Q}[x, y], \quad Q = \frac{\partial P}{\partial x}. \qquad (4) $$
Given coprime polynomials P and Q of degrees bounded by d and coefficient bitsize bounded by $\tau$, [3] proposes two approaches for the computation of the maximal y-projection of the real solutions of $\Sigma$. The first one uses a linear separating form and the second the real root counting of a univariate polynomial with algebraic coefficients. We briefly explain the functionality of both approaches before moving to the parametric case.

## 3.1 Separating linear form

The first approach is a direct bivariate solving with polynomials with rational coefficients. In this context, two methods were developed, namely the RUR method and the Root Separation method, requiring putting (4) in a local generic position, i.e., finding a separating linear form $y + ax$ that defines a shear of the coordinate system $(x, y)$, i.e., $(x, y) \mapsto (x, t - ax)$, so that no two distinct solutions of the sheared system defined by $\Sigma_a = \{P(x, t - ax) = 0, Q(x, t - ax) = 0\}$ are horizontally aligned. This approach has long been used in the computer algebra literature. For more details, see [1, 2] and the references therein.

In [1, 2], it was demonstrated that a separating linear form $y + ax$, where $a \in \{0, \dots, 2d^4\}$, can be computed. Subsequently, as explained in [1], a Rational Univariate Representation (RUR) for the sheared system $\Sigma_a$ can be employed to compute isolating boxes for its real solutions. This approach can be directly applied to the polynomial system associated with the $L^∞$-norm computation problem. We then select the maximal y-projection of the real solutions of the system. This value is represented by its isolating interval with respect to the univariate polynomial embodying the y-projection of the system solutions, i.e., the so-called resultant polynomial Res($P, Q, x$). In this case, up to a sign, the resultant polynomial is the discriminant of $P \in \mathbb{Q}[y][x]$ multiplied by $L_c(x)(P)$. This resultant polynomial embodies the y-projection of the critical and singular points of the real curve $P = 0$, along with the y-values at which the real curve $P = 0$ forms a horizontal asymptote along the x-axis. The complexity analysis shows that this algorithm performs $\tilde{O}_B(d_y d_x^3 (d_y^2 + d_x d_x + d_x \tau))$ bit operations in the worst case, where $\tau$ is the maximal coefficient bitsize of P and Q, and $d_v = \max(\deg_o(P), \deg_o(Q))$ with $v \in \{x, y\}$.

Alternatively, it is possible to localize the maximal y-projection of the real solutions of $\Sigma$ by only applying a linear separating form on the system $\Sigma$, i.e., without computing isolating boxes for the whole system solutions. The linear separating form $t = y + sx$ proposed in [7] preserves the order of the solutions of the sheared system

$$ \Sigma_s = V_R(\langle P(x, t - s x), Q(x, t - s x) \rangle) $$

with respect to the y-projection of the solutions of the original system $\Sigma$. In other words, with this linear separating form $t = y + sx$, we have:

$$ t_1 = y_1 + s x_1 < t_2 = y_2 + s x_2 \implies y_1 \le y_2. $$

Thus, the projection of the solutions of $\Sigma_s$ onto the new separating axis $t$ could be done so that we could simply choose the y-projection corresponding to the maximal t-projection of the real solutions of $\Sigma_s$. The drawback of this method is in the growth of the size of the coefficients of $\Sigma_s$ due to the large size of $s$. The complexity analysis shows that the last algorithm performs, in the worst case, $\tilde{O}_B(d_x^3 d_y^4 \tau (d_x^2 + d_x d_y + d_y^2))$ bit operations.

## 3.2 Real roots counting

The second approach, employed in the third proposed method, involves solving a univariate polynomial equation with algebraic coefficients. This method identified the maximal y-projection of the system real solutions – denoted by $\bar{y}$ – by first isolating the real roots of the univariate resultant polynomial Res($P, \frac{\partial P}{\partial x}, x$) and then verifying the existence of at least one real root of the greatest
common divisor $\gcd(P(x, \bar{y}), \frac{\partial P}{\partial y}(x, \bar{y})) \in \mathbb{R}[x]$ of $P(x, \bar{y})$ and $\frac{\partial P}{\partial x}(x, \bar{y})$. But the polynomial $P$ – corresponding to our modeled problem – defines a plane real algebraic curve bounded in the $y$-direction by the value that we are aiming at computing. Thus, a resulting key point is that the number of real roots of $\gcd(P(x, \bar{y}), \frac{\partial P}{\partial x}(x, \bar{y}))$ is equal to the number of real roots of $P(x, \bar{y})$. Hence, we could simply compute the *Sturm-Habicht sequence* [14] of $P(x, \bar{y})$ for counting the number of its real roots without any consequent overhead. Since the $\gcd$ polynomial has a larger size than the polynomial $P$, this key point leads to a better complexity in the worst case. We also mention that the *Sturm-Habicht sequence* corresponding to $P(x, \bar{y}) \in \mathbb{R}[x]$ is a *signed subresultant sequence* of the polynomials $P(x, \bar{y}) \in \mathbb{R}[x]$ and its derivative with respect to $x$. Being already computed to obtain $\text{Res}(P, \frac{\partial P}{\partial x}, x)$, the practical and theoretical complexities are mainly carried by the complexity of evaluating the leading coefficients with respect to $x$ of the subresultant polynomials (the so-called *the principal subresultant coefficients*) over the real value $\bar{y}$. The complexity analysis showed that this algorithm performs $\tilde{O}_B(d_x^4 d_y^2 (d_y + \tau))$ bit operations in the worst case and $\tilde{O}_B(d_x^4 d_y^2 \tau)$ when the plane curve $P(x, y) = 0$ has no real isolated singular points.

After implementing the three approaches in Maple, the real roots counting approach was shown to perform better than its counterpart in terms of practical computational efficiency (see [3]). However, as already mentioned in the introduction, we recently conducted tests with the newest approach for computing a RUR described in [10], which have altered this observation. Therefore, future experiments will focus on optimizing the performance of these approaches by exploring alternative sub-algorithms.

# 4 Parametric case

## 4.1 Background

Let us consider the *basic semi-algebraic set* defined by

$$S = \{x \in \mathbb{R}^n \mid p_1(x) = 0, \dots, p_s(x) = 0, q_1(x) > 0, \dots, q_t(x) > 0\},$$

where $p_i, q_j$ are polynomials with rational coefficients. Moreover, let

$$[U, X] := [u_1, \dots, u_d, x_{d+1}, \dots, x_n]$$

be the set of unknowns, while $U = [u_1, \dots, u_d]$ is the set of parameters and $X = [x_{d+1}, \dots, x_n]$ the set of the variables. We denote by $\Pi_U : \mathbb{C}^n \to \mathbb{C}^d$ the canonical projection onto the parameter space $(u_1, \dots, u_d, x_{d+1}, \dots, x_n) \mapsto (u_1, \dots, u_d)$. Finally, for any set $\mathcal{V} \subset \mathbb{C}^n$, we will denote by $\bar{\mathcal{V}}$ the $\mathbb{C}$-Zariski closure of $\mathcal{V}$, namely, the smallest affine algebraic set containing $\mathcal{V}$.

In this section, we only consider systems that are so-called *well-behaved systems*. They are systems that contain as many equations as variables, are generically zero-dimensional, i.e., for almost all complex parameter values, at most finitely many complex solutions exist, and *generically radical*, i.e., for almost all complex parameter values, there are no solutions of multiplicity greater than 1 (in particular, the input equations are square-free).

In applications, questions that often arise concern the structure of the solution space in terms of the parameters such as, e.g., determining the parameter values for which real solutions exist or, more generally, determining the parameter values for which the system has a given number of real solutions.

To solve a well-behaved system $S$, it is significant to choose a finite number of representative “good” parameter values that cover all possible cases.

A method was proposed by D. Lazard and F. Rouillier in [16] based on the concept of *discriminant variety*. This method can be outlined as follows. First, the set of solutions of the system $S$ is projected onto the parameter space. Then, the topological closure $\bar{S}$ of the resulting projection, which will usually be equal to the whole parameter space $\mathbb{R}^d$, is divided into two parts: a *discriminant variety* $W$
and its complement $\bar{S} \setminus W$. A discriminant variety $W$ of the system can be understood as the set of "bad" parameter values leading to non-generic solutions of the system, for instance, infinitely many solutions, solutions at infinity, or solutions of multiplicity greater than 1. It is a generalization of the well-known discriminant of a univariate polynomial.

The complement $\bar{S} \setminus W$ of $W$ can be expressed as a finite disjoint union of connected open sets, usually called cells, such that a specific behavior of the system does not change when the parameters vary within the same cell.

Describing the connected open cells can be done using the so-called *Cylindrical Algebraic Composition* or CAD for short [11]. It is a well-known concept in computational real algebraic geometry, first proposed by G. E. Collins [8]. It allows one to obtain a practical description of the connected components of the complement of the discriminant variety. For a well-behaved system, the discriminant variety is of dimension less than $d$, and it characterizes the boundaries between these cells. Hence, the number of solutions of the system only changes on the boundary or when crossing a boundary. We are interested in open cells of maximal dimension (the complement of the discriminant variety), which are the easiest to compute since they do not require algebraic number computations.

For each open cell in the parameter space, we can choose a sample point, evaluate the original system at the sample point, and then solve the resulting non-parametric system. In this way, we can, for instance, determine the number of real solutions of the system that are constant for parameter values chosen in the same open cell.

**Example 4.1.** Consider the following semi-algebraic system

$$C = \{ax^2 + b - 1 = 0, bz + y = 0, cz + y = 0, c > 0\},$$

where $\{x_1 = x, x_2 = y, x_3 = z\}$ (resp., $\{u_1 = a, u_2 = b, u_3 = c\}$) is the set of variables (resp., set of parameters). Then, a discriminant variety is defined by:

$$\mathcal{D} = \{(a, b, c) \mid a = 0 \text{ or } b = 1 \text{ or } b = c \text{ or } c = 0\}.$$

In fact, the case $a = 0$ corresponds to a vanishing leading coefficient of the first equation, which can be interpreted as “solution at $\infty$”. If $b = 1$, then the first equation has a real root $x = 0$ of multiplicity 2. If $b = c$, the second and third equations of $C$ coincide, and therefore the system $C$ becomes underdetermined and has infinitely many solutions. Finally, the case $c = 0$ corresponds to a boundary case for the inequality $c > 0$. Thus, for every choice of the parameter values outside the discriminant variety $\mathcal{D}$, the system $C$ has finitely many solutions, all of multiplicity 1.

Getting back to our problem, let $n(\omega, \gamma)$ be the polynomial associated with the $L^\infty$-norm for $G$ (see Definition 2.3). Note that $n$ belongs to $\mathbb{Q}[\alpha][\omega, \gamma]$, where $\alpha = \alpha_1, \dots, \alpha_d$ represents a set of real parameters (i.e., $X = [\omega, \gamma]$ and $U = [\alpha]$). By considering the following two sets

$$\Sigma = \{ (\omega, \gamma, \alpha) \in \mathbb{R}^{2+d} \mid n(\omega, \gamma, \alpha) = 0, \frac{\partial n}{\partial \omega}(\omega, \gamma, \alpha) = 0 \}, \\ \Sigma_{\infty} = \{ (\gamma, \alpha) \in \mathbb{R}^{1+d} \mid \text{Lc}_{\omega}(n) = 0 \},$$

then, for $\alpha \in \mathbb{R}^d$, the $L^\infty$-norm of the transfer matrix $G$ is given by

$$\|G\|_{\infty} = \max(\pi_{\gamma}(\Sigma), \pi_{\gamma}(\Sigma_{\infty})).$$

This implies that the norm we are aiming to compute (namely, the maximal $\gamma$ projection of the real solutions of $\Sigma$ and $\Sigma_{\infty}$) is a function of the parameters, and thus, is influenced by the parameters $\alpha$.
**Problem Statement:**

Let G be a transfer matrix and let $n \in \mathbb{Q}[\alpha][\omega, \gamma]$ be the polynomial associated with the $L^\infty$-norm, where $\alpha = \{\alpha_1, \dots, \alpha_d\}$ represents a set of real parameters. Then, for every parameter value $\alpha$, we aim to compute

$$ \|G\|_{\infty} = \max \left\{ \pi_{\gamma} \left( V_{\mathbb{R}^2} \left( \left\langle n, \frac{\partial n}{\partial \omega} \right\rangle \right) \right) \cup V_{\mathbb{R}} \left( \langle Lc_{\omega}(n) \rangle \right) \right\}. $$

This involves determining the maximum $\gamma$ projection of the real solutions of the sets $\Sigma$ and $\Sigma_\infty$ as functions of the parameters $\alpha$.

## 4.2 Illustrative example

Before introducing the proposed algorithm for representing this norm in terms of the parameters, consider the transfer function derived from an application to a gyro-stabilized sight model, as discussed in [17]. Notably, the transfer function in this model relies on a specific set of parameters. In Proposition 4.2, we will compute its $L^\infty$-norm as a function of these parameters through a step-by-step proof. Employing computer algebra tools, including resultant polynomials and intricate properties related to root multiplicity, we will demonstrate the process.

**PROPOSITION 4.2.** Let $\omega_0, \omega_1 \in \mathbb{R}_{>0}, \omega_0 \neq \omega_1, 0 < \xi \le 1$, and:

$$ G = \frac{\left(\frac{s}{\omega_0}\right)^2 + 2\xi\left(\frac{s}{\omega_0}\right) + 1}{\left(\frac{s}{\omega_1}\right)^2 + 2\xi\left(\frac{s}{\omega_1}\right) + 1}. \qquad (5) $$

Set $r = \omega_1/\omega_0$, $\mu = 4\xi^2(\xi - 1)(\xi + 1)$, and let $\delta$ be the maximal real root of:

$$ M = \mu\gamma^4 + ((r^2 - 1)^2 - 2\mu r^2)\gamma^2 + \mu r^4 \in \mathbb{R}[\gamma]. $$

Then, the $L^\infty$-norm of G is given by:

$$ \| G \|_{\infty} = \begin{cases} \max\{1, r^2\}, & \text{if } \xi \ge \frac{1}{\sqrt{2}}, \\ \delta, & \text{if } \xi < \frac{1}{\sqrt{2}}. \end{cases} \qquad (6) $$

To establish Proposition 4.2, we introduce two essential lemmas that will facilitate our proof.

**LEMMA 4.3.** Let us consider $\xi$, $\omega_0$, $\omega_1 \in \mathbb{R}_{>0}$, $\omega_0 \neq \omega_1$, $0 < \xi < 1$, $r = \omega_1/\omega_0$, and $\mu = 4\xi^2(\xi - 1)(\xi + 1)$. Then, the following polynomial

$$ M_1 = \mu X^2 + ((r^2 - 1)^2 - 2\mu r^2)X + \mu r^4 \in \mathbb{R}[X] $$

has two positive real roots $X_1$ and $X_2$ such that $0 < X_1 < 1 < X_2$ and $X_2 > r^4$.

**PROOF.** A discriminant of $M_1$ is $\Delta = (r+1)^2(r-1)^2((r^2-1)^2 - 4\mu r^2)$. Since $0 < \xi \le 1$, we get $\mu \le 0$, and thus, $\Delta > 0$, which shows that $M_1$ has two distinct real solutions, denoted by $X_1$ and $X_2$ with the assumption that $X_1 < X_2$. Moreover, we have

$$ X_1 X_2 = r^4 > 0, \quad X_1 + X_2 = \frac{(r^2 - 1)^2 - 2\mu r^2}{-\mu} > 0, $$

which yields $X_1 > 0$ and $X_2 = r^4/X_1 > 0$. Now, if we let $x := X - 1$, then we get $M_1(X) = M_1(x+1) = m(x)$, where:

$$ m(x) = \mu x^2 + (r^2 - 1)(8\xi^2(1 - \xi^2) + r^2 - 1)x + (2\xi^2 - 1)^2(r - 1)^2(r + 1)^2. $$
Clearly, the two roots of $m$ are $X_1 - 1$ and $X_2 - 1$, and we have

$$ (X_1 - 1)(X_2 - 1) = \frac{(2\xi^2 - 1)^2 (r - 1)^2 (r + 1)^2}{\mu} < 0, $$

which shows that $X_1 < 1$ and $X_2 > 1$ since $X_1 < X_2$. Finally, $X_1 < 1$ yields $X_2 = r^4/X_1 > r^4$, which proves the result. ■

**LEMMA 4.4.** Let $\omega_0$, $\omega_1 \in \mathbb{R}_{>0}$, $\omega_0 \neq \omega_1$, $0 < \xi < 1$, $\xi \neq 1/\sqrt{2}$, $r = \omega_1/\omega_0$, and $\beta = 2\xi^2 - 1$. Then, the following polynomial

$$ L = \beta Y^2 + \omega_0^2 (r^2 + 1) Y + \beta r^2 \omega_0^4 \in \mathbb{R}[Y] $$

has two positive real roots if and only if $0 < \xi < 1/\sqrt{2}$.

**PROOF.** A discriminant of $L$ is $\delta = \omega_0^4 (r^2 + 2\beta r + 1) (r^2 - 2\beta r + 1)$. We have

$$ \beta^2 - 1 = 4 \xi^2 (\xi + 1) (\xi - 1) < 0, $$

and thus, the discriminant $4(\beta^2 - 1)$ of the two polynomials $r^2 + 2\beta r + 1$ and $r^2 - 2\beta r + 1$ is negative, which yields $\delta > 0$ and thus, $L$ has two distinct real roots. The product of these roots is $r^2 \omega_0^4 > 0$ and their sum is $\omega_0^2 (r^2 + 1)/(-\beta)$. Since $\beta < 0$ if and only if $0 < \xi < 1/\sqrt{2}$, we obtain that the sum is positive if and only if $0 < \xi < 1/\sqrt{2}$, which then implies that $L$ has two positive real roots only when $0 < \xi < 1/\sqrt{2}$. ■

We can now proceed with the proof of Proposition 4.2 by leveraging Lemmas 4.3 and 4.4.

**PROOF OF PROPOSITION 4.2.** Set $\alpha = \{r, \omega_0, \xi\}$. Let $N$ and $D$ be two polynomials such that:

$$ G(-i\omega)G(i\omega) = \frac{N(\omega)}{D(\omega)}. $$

Let $n(\gamma, \omega) = D(\omega)\gamma^2 - N(\omega)$ be the polynomial associated with the $L^\infty$-norm and consider:

$$ \Sigma = \left\{ (\omega, \gamma, \alpha) \in \mathbb{R}^{2+3} \mid n(\omega, \gamma) = 0, \frac{\partial n}{\partial \omega}(\omega, \gamma) = 0 \right\}, \\ \Sigma_{\infty} = \left\{ (\gamma, \alpha) \in \mathbb{R}^{1+3} \mid \text{Lc}_{\omega}(n) = 0 \right\}. $$

We compute $n$ and we obtain

$$ n = (\gamma^2 - r^4)\omega^4 + 2r^2\omega_0^2\beta(\gamma^2 - r^2)\omega^2 + r^4\omega_0^4(\gamma^2 - 1), $$

where $\beta = 2\xi^2 - 1$. The resultant $R$ of $n(\omega, \gamma)$ and $q = \frac{\partial n}{\partial \omega}(\omega, \gamma)$ with respect to $\omega$ is then given by

$$ R = 256 \omega_0^{12} r^{12} (\gamma^2 - 1) (\gamma^2 - r^4)^2 M^2, $$

where $M = \mu\gamma^4 + ((r^2 - 1)^2 - 2\mu r^2)\gamma^2 + \mu r^4$, i.e., $M(\gamma) = M_1(\gamma^2)$ with $M_1$ defined in Lemma 4.3. By assumptions on the parameters, $M_1(X)$ has two positive real solutions, $X_1$ and $X_2$, and thus, $M$ has the four real roots $\pm\sqrt{X_1}$, $\pm\sqrt{X_2}$. Thus, based on the properties of the resultant polynomial, we have:

$$ \| G \|_{\infty} = \max \left\{ \left\{ 1, r^2, \sqrt{X_1}, \sqrt{X_2} \right\} \cap \pi_{\gamma}(\Sigma) \cup \pi_{\gamma}(\Sigma_{\infty}) \right\}. $$

(1) For $\gamma = r^2$: $\text{Lc}_{\omega}(n) = (\gamma^2 - r^4) = 0$, i.e, $r^2 \in \pi_{\gamma}(\Sigma_{\infty})$.
(2) For $\gamma = 1$, we get:

$$n(\omega, 1) = -(r^2 - 1) \omega^2 f_1, \quad q(\omega, 1) = -4(r^2 - 1) \omega f_2,$$

where

$$f_1 := (r^2 + 1) \omega^2 + 2 r^2 \omega_0^2 (2 \xi^2 - 1), \quad f_2 := (r^2 + 1) \omega^2 + r^2 \omega_0^2 (2 \xi^2 - 1).$$

Here, Res($f_1, f_2, \omega$) = $(\omega_0^2 r^2 (2 \xi^2 - 1) (r^2 + 1))^2$. If $\xi = 1/\sqrt{2}$, we obtain that $f_1 = f_2 = (r^2 + 1)\omega^2$ which clearly proves that $(\omega, \gamma) = (0, 1) \in \Sigma$. If $\xi \neq 1/\sqrt{2}$, then Res($f_1, f_2, \omega) \neq 0$, which implies that $\text{gcd}(n(\omega, 1), q(\omega, 1)) = (r^2 - 1)\omega$. This, in turn, proves again that $(\omega, \gamma) = (0, 1) \in \Sigma$.

(3) For $\gamma$ real root of $M$: the point is to verify that $\gamma \in \pi_{\gamma}(\Sigma)$. For doing so, we start by computing $F = \text{Res}(n(\omega, \gamma), \frac{\partial n}{\partial \omega}(\omega, \gamma), \gamma)$. Using the properties of resultants, we recall that $\pi_{\omega}(\Sigma) \subset V_{\mathbb{R}}(F)$, where $F$ is defined by $F = c \omega^2 F_1^2$ with $F_1 = \beta \omega^4 + \omega_0^2 (r^2 + 1) \omega^2 + r^2 \omega_0^4 \beta$ and $c = 16 \omega_0^4 r^8 (r^2 - 1)^2$. We have seen that:

$$\pi_{\omega} \left( V_{\mathbb{R}} \left( \langle n(\omega, \pm 1), \frac{\partial n}{\partial \omega}(\omega, \pm 1) \rangle \right) \right) = \{0\}.$$

Taking into consideration the power and degree of the factor $\omega$ in $F$ and the power and degree of the factor $\gamma^2 - 1$ in $R$, and the properties of the resultant concerning root multiplicity (see [9, Chapter 4]), we can say that:

$$(\omega, \gamma) \in \Sigma, \quad \gamma = \pm 1 \iff \omega = 0.$$

With this being said, let $L \in \mathbb{R}[Y]$ be the polynomial obtained after substituting $Y$ for $\omega^2$ in $F_1$.

Based on Lemma 4.4, $L$ has two positive real roots if and only if $\xi < \frac{\sqrt{2}}{2}$. Thus we can conclude two cases:

* For $\xi < \frac{\sqrt{2}}{2}$, $F_1 \in \mathbb{R}[\omega]$ has four real roots. Thus, we have:

$$\forall \gamma_i \in V_{\mathbb{R}}(M), \exists \omega_{i,j} \in V_{\mathbb{R}}(F_1) : (\omega_{i,j}, \gamma_i) \in \Sigma.$$

Consequently, based on Lemma 4.3 where we proved that

$$X_1 < 1 < X_2, \quad X_2 > r^4,$$

we can say that $\delta = \sqrt{X_2} > r^2$, and we conclude that $\|G\|_{\infty} = \delta$.

* For $\xi > \frac{\sqrt{2}}{2}$, $F_1$ has no real roots in $\omega$. In this case, none of the real roots of $M$ is a good candidate, and we conclude that:

$$\|G\|_{\infty} = \max\{1, r^2\}.$$

(4) For $\xi = \frac{\sqrt{2}}{2}$, $M = c(\gamma^2 - 1)(\gamma^2 - r^4)$, where $c \in \mathbb{R}$. In this case, we have:

$$\|G\|_{\infty} = \max\{1, r^2\}.$$

(5) Similarly, for $\xi = 1$, $M = c\gamma(\gamma^2 - 1)(\gamma^2 - r^4)$, where $c \in \mathbb{R}$. Then, we have:

$$\|G\|_{\infty} = \max\{1, r^2\}.$$

h

It is important to emphasize that deriving this representation manually, especially in the presence of parameters, can be a daunting task due to its inherent complexities. Therefore, we will proceed to introduce an algorithm specifically designed to compute the $L^{\infty}$-norm in the parametric case. After stating this proposed algorithm, we will apply it once more to the aforementioned example, verifying its efficacy by obtaining the same result.
## 4.3 Proposed algorithm

To establish the context, one method for achieving this parameter space decomposition and norm representation is by employing a CAD of $\mathbb{R}^{d+2}$ adapted to $\{n(\omega, \gamma, \alpha) = 0, \frac{\partial n}{\partial \omega}(\omega, \gamma, \alpha) = 0\}$ and a semi-algebraic set $S_p$ containing the inequalities satisfied by the parameters. But it may yield a very huge result, difficult to analyze in practice, with lots of cells we are not interested in. We are just interested in the cells where the curves representing the $\gamma$-projection of the system solutions, when they exist, are continuous and do not intersect.

Below, we state Algorithm 1, where non_parametric corresponds to one of the proposed methods in Section 3 and indexᵢ denotes the index of the output of non_parametric in the sorted list of the real roots of $R = \text{Res}(n, \frac{\partial n}{\partial \omega}, \omega)$.

This algorithm uses a CAD to study $R = \text{Res}(n, \frac{\partial n}{\partial \omega}, \omega)$. This resultant polynomial depends on the set of parameters $\alpha$. Within this context, the discriminant variety simplifies to the discriminant of this resultant polynomial. The cells derived in the parameter space, post-CAD application, represent regions where the roots $\gamma$ of the resultant exhibit non-variant behavior. Notably, within each cell, these roots do not intersect, ensuring their distinct positions relative to one another. By selecting a sample point within a cell, we can determine the “maximal” $\gamma$, which is a parameterized expression depending on $\alpha$.

**Algorithm 1** Parametric case

**Input:** A well-behaved polynomial system $\Sigma = \{n(\omega, \gamma) = 0, \frac{\partial n}{\partial \omega}(\omega, \gamma) = 0\}$, where $n \in \mathbb{Q}[\alpha][\omega, \gamma]$, and a semi-algebraic set $S_p$ (for parameters conditions).

**Output:** A list of pairs $[C_i, \text{index}_i]$ as in Theorem 4.5.

(1) Compute $R = \text{Res}(n, \frac{\partial n}{\partial \omega}, \omega)$.

(2) Compute a discriminant variety $R_2$ of $\{R = 0, S_p\}$ with respect to $\pi_\alpha$.

(3) Using a CAD, compute the partition $\{C_1, \dots, C_l\}$ of $C = \mathbb{R}^d \setminus R_2$, along with sample points $\text{sample}_i \in C_i$.

(4) Apply non_parametric on subs(sampleᵢ, °) and get indexᵢ.

(5) return $\{[C_i, \text{index}_i], i = 1, \dots, l\}$.

**THEOREM 4.5.** Given a well-behaved system $\Sigma = \{n(\omega, \gamma) = 0, \frac{\partial n}{\partial \omega}(\omega, \gamma) = 0\}$, where $n \in \mathbb{Q}[\alpha][\omega, \gamma]$, $\alpha = (\alpha_1, \dots, \alpha_d)$, and a semi-algebraic set $S_p$ verified by a set of parameters $\alpha$, Algorithm 1 outputs a set of pairs $[C_i, \text{index}_i]$, where the $C_i$s are disjoint parameter cells in the parameter space and, for all $\alpha \in C_i$, indexᵢ denotes the index of

$$ \gamma_{\max} = \max \left\{ \pi_{\gamma} \left( V_{\mathbb{R}^2} \left( \left\langle n, \frac{\partial n}{\partial \omega} \right\rangle \right) \right) \cup V_{\mathbb{R}} \left( \langle \text{Lc}_{\omega}(n) \rangle \right) \right\} $$

in the sorted list of the real roots of $R = \text{Res}(n, \frac{\partial n}{\partial \omega}, \omega)$.

Finally, if $n$ is the polynomial associated with the $L^\infty$-norm for $G$, then we have $\|G\|_\infty = \gamma_{\max}$.

**PROOF.** In the first step, we compute a discriminant variety $R$ of $\{n(\omega, \gamma, \alpha) = 0\}$ with respect to $\pi_{(\alpha, \gamma)}$, where $n(\omega, \gamma, \alpha)$ is seen as a univariate polynomial in $\omega$. We recall that this discriminant variety is the set of parameter values leading to non-generic solutions of the system, for example, infinitely many solutions, solutions at infinity, or solutions of multiplicity greater than 1. It is simply the resultant polynomial of the polynomial $n(\omega, \gamma)$ and its derivative with respect to the main variable $\omega$, i.e., $R = \text{Res}(n, \frac{\partial n}{\partial \omega}, \omega) \in \mathbb{Q}[\alpha][\gamma]$. In this case, $R = 0$ is a sub-variety of $\mathbb{R}^{d+1}$ and the complement of $R = 0, \mathbb{R}^{d+1} \setminus \{R = 0\}$, can be expressed as a finite disjoint union of cells – which
are connected open sets – such that the number of the system real solutions $\omega$ does not change when the parameters vary within the same cell.

In the second step, we consider the variable $\gamma$ as the main variable in the polynomial $R \in \mathbb{Q}[\alpha][\gamma]$ since it is the polynomial embodying the $\gamma$-projection of the system $\{n(\omega, \gamma) = 0, \frac{\partial n}{\partial \omega}(\omega, \gamma) = 0\}$. In this case, the $\gamma$-projection of the system solutions is considered as a real function of $\alpha$ such that the position of the curves representing $\gamma(\alpha) = 0$ changes after each intersection of at least two of these curves in $\mathbb{R}^d$. To locate the maximal value $\gamma$ over a given cell, we decompose $\mathbb{R}^d$ into cells where no changes in the position of the curves $\gamma(\alpha)$ occur. For doing so, we can naturally propose to eliminate from the parameter space the set of “bad” parameter values leading to non-generic solutions of $R = 0$. This set corresponds to a discriminant variety of $\{(\alpha, \gamma) \in \mathbb{R}^{d+1} | R = 0\} \cup S_p$ with respect to $\pi_\alpha$, denoted by $R_2$. We recall that $R_2$ is simply the curve of the discriminant of $R$ with respect to the variable $\gamma$, multiplied by the leading coefficient of $R$ with respect to $\gamma$, that is $\mathrm{Res}(R, \frac{\partial R}{\partial \gamma}, \gamma) \in \mathbb{Q}[\alpha]$, up to some curves related to the inequalities of $S_p$.

In the third step, using a CAD, we can decompose $C = \mathbb{R}^d \setminus R_2$ into connected cells, above each cell, the variable $\gamma$ is a real-valued function depending continuously on the parameters $\alpha$, whose graphs are disjoint. Now, let $\{C_1, \dots, C_l\}$ be the partition of $C$ and let $\mathrm{sample}_i$ be a sample point in $C_i$.

By substituting $\mathrm{sample}_i$ for $\alpha$ in $\Sigma$, we obtain a zero-dimensional polynomial system $\Sigma_i = \{n_i = 0, \frac{\partial n_i}{\partial \omega} = 0\}$ of polynomials in $\mathbb{Q}[\omega, \gamma]$. Consequently, by applying nonParametric in the fourth step, we obtain the isolating interval of the maximal real root of $\mathrm{Res}(n_i, \frac{\partial n_i}{\partial \omega}, \omega)$ corresponding to a real point $(\omega, \gamma)$ on the real curve $n_i = 0$.

We assume that $\mathrm{index}_i$ represents the index of $\gamma_{\max}$ from within the sorted list of the real roots of $R$, for all $\alpha \in C_i$. Indeed, over a cell $C_i$, the real roots $\gamma$ of $R$ are represented as real-valued functions depending continuously on the parameters, whose graphs are disjoint. This assures that for every parameter value in $C_i$, the relative positions of the functions $\gamma$ remain consistent. Therefore, for each $\alpha \in C_i$, $\mathrm{index}_i$ consistently denotes the index of $\gamma_{\max}$ in the sorted list of real roots of $R$. As a result, Algorithm 1 outputs a set of pairs $[C_i, \mathrm{index}_i]$, where the $C_i$'s are disjoint parameter cells and $\mathrm{index}_i$ indicates the index of $\gamma_{\max}$ in the sorted list of the real roots of $R = \mathrm{Res}(n, \frac{\partial n}{\partial \omega}, \omega)$ over a cell $C_i$.

**Example 4.6.** Let us consider the following simple example of transfer function

$$G(s) = \frac{as + 1}{bs + 1},$$

where $a, b \in \mathbb{R} > 0$. See Example 2 on page 17 of [12]. The polynomial associated with the $L^\infty$-norm $n \in \mathbb{Q}[a, b][\omega, \gamma]$ of $G$ (see Definition 2.3) is given by:

$$n = (-b^2 \gamma^2 + a^2) \omega^2 - \gamma^2 + 1.$$

Applying Algorithm 1 to $\Sigma = \{n(\omega, \gamma) = 0, \frac{\partial n}{\partial \omega}(\omega, \gamma) = 0\}$ and $S_p = \{a > 0, b > 0\}$, we obtain $\{[C_1, 4], [C_2, 4]\}$ (7)

where the cells $C_1$ and $C_2$ are respectively defined by:

$$C_1 = \{0 < a < b\}, \quad C_2 = \{b > 0\} \cap \{a > b\} = \{a > b > 0\}.$$

Here, $R = \mathrm{Res}(n, \frac{\partial n}{\partial \omega}, \omega) = -4(\gamma - 1)(\gamma + 1)(b\gamma - a)^2(b\gamma + a)^2 \in \mathbb{Q}[a, b][\gamma]$. Therefore, for all $a, b \in C_1$, the real roots of $R$ are ordered as:

$$\{-1, -\frac{a}{b}, \frac{a}{b}, 1\}.$$
Thus, according to (7), Theorem 4.5 yields $||G||_{∞} = γ_{max} = 1$ for all $a, b ∈ C_1$. Moreover, for all $a, b ∈ C_2$, the real roots of R are ordered as:

$$ \{-\frac{a}{b}, -1, 1, \frac{a}{b}\}. $$

Thus, according to (7), Theorem 4.5 yields $||G||_{∞} = γ_{max} = \frac{a}{b}$ for all $a, b ∈ C_2$. We find again the result obtained in [12].

**Example 4.7.** Let us consider the following transfer function

$$ G(s) = \frac{\omega_n^2}{s^2 + 2 \xi \omega_n s + \omega_n^2}, $$

where $ξ > 0$ and $ω_n > 0$ ([19]). The polynomial associated with the L$^{∞}$-norm $n ∈ Q[ω_n, ξ][ω, γ]$ is given by:

$$ n = \omega^4 \gamma^2 + 4 \left( \xi^2 - \frac{1}{2} \right) \omega_n^2 \omega^2 \gamma^2 + \omega_n^4 (\gamma^2 - 1). $$

Algorithm 1, applied to the polynomial system $Σ = \{n(ω, γ) = 0, \frac{∂n}{∂ω}(ω, γ) = 0\}$ and $S_p = \{ω_n > 0, ξ > 0\}$, returns $\{[C_1, 5], [C_2, 4], [C_3, 3]\}$, where the cells $C_1, C_2$, and $C_3$ are respectively defined by:

$$ (1) C_1 = \{ω_n > 0\} \cap \{0 < ξ < \frac{1}{\sqrt{2}}\}, $$

$$ (2) C_2 = \{ω_n > 0\} \cap \{\frac{1}{\sqrt{2}} < ξ < 1\}, $$

$$ (3) C_3 = \{ω_n > 0\} \cap \{ξ > 1\}. $$

Here, $R = \text{Res}(n, \frac{∂n}{∂ω}, ω) = ω_n γ (γ^2 - 1) (4ξ^2 (ξ^2 - 1) γ^2 + 1) ∈ Q[ω_n, ξ][γ]$. Therefore, we obtain the following results:

(1) Over the cell $C_1$, the real roots of R are ordered as follows:

$$ \{-\frac{1}{2\sqrt{\xi^2(1-\xi^2)}}, -1, 0, 1, \frac{1}{2\sqrt{\xi^2(1-\xi^2)}}\}. $$

By Theorem 4.5, we obtain that $||G||_{∞} = γ_{max} = \frac{1}{2\sqrt{ξ^2(1-ξ^2)}}$ for all $ω_n, ξ ∈ C_1$.

(2) Over the cell $C_2$, the real roots of R are ordered as follows:

$$ \{-\frac{1}{2\sqrt{\xi^2(1-\xi^2)}}, -1, 0, 1, \frac{1}{2\sqrt{\xi^2(1-\xi^2)}}\}. $$

By Theorem 4.5, we obtain that $||G||_{∞} = γ_{max} = 1$ for all $ω_n, ξ ∈ C_2$. This indicates that over the cell $C_2$, the maximal real root of R, the one of index 5, is a real $γ$ coordinate of a non-real solution $(ω, γ)$ of $Σ$.

(3) Over the cell $C_3$, the real roots of R are ordered as $\{-1, 0, 1\}$. Theorem 4.5 then yields $||G||_{∞} = γ_{max} = 1$ for all $ω_n, ξ ∈ C_3$.

Finally, in Figure 1a, we illustrate the results by plotting the real roots of the resultant polynomial R as functions of the parameter $ξ$ for $ω_n = 1$. Then, in Figure 1b, we illustrate the surface $n = 0$, where $ω_n = 1, ξ > 0$, and $γ > 0$.
<figure><img src="image_2.png" /><figcaption>(a) The curves defined by $\gamma \in \mathbb{Q}[\xi]$ corresponding to $R \in \mathbb{Q}[\xi][\gamma]$ for $\omega_n = 1$.</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>(b) 3D plot of the surface $n = 0$ for $\omega_n = 1$, $\xi > 0$, and $\gamma > 0$.</figcaption></figure>

<caption>Fig. 1. Example 4.7. (a) Plot of the real roots of the resultant polynomial $R$ as functions of $\xi$ for $\omega_n = 1$. (b) 3D plot of the surface defined by $n = 0$ for $\omega_n = 1$, $\xi > 0$, and $\gamma > 0$.</caption>

**Example 4.8.** Consider again the transfer function $G$ studied in Proposition 4.2, i.e., (5) and let $n \in \mathbb{Q}[\omega_0, r, \xi][\omega, \gamma]$ be the polynomial associated with the $L^\infty$-norm. Applying Algorithm 1 to the system $\Sigma = \{n(\omega, \gamma) = 0, \frac{\partial n}{\partial \omega}(\omega, \gamma) = 0\}$ and $S_p = \{\omega_0 > 0, r > 0, r \neq 1, 0 < \xi \leq 1\}$, we obtain:
$$ \{[C_1, 8], [C_2, 8], [C_3, 7], [C_4, 7]\} $$

To elaborate, let $R = \text{Res}(n, \frac{\partial n}{\partial \omega}, \omega) \in \mathbb{Q}[\omega_0, r, \xi][\gamma]$, where $n$ and $R$ are computed in the proof of Proposition 4.2. After conducting the required computations, as in Algorithm 1, we obtain the parameter space partition $\{C_1, C_2, C_3, C_4\}$, where

$$ C_1 = \{0 < \xi < \frac{\sqrt{2}}{2}\} \cap \{0 < r < 1\} \cap \{\omega_0 > 0\}, $$

$$ C_2 = \{0 < \xi < \frac{\sqrt{2}}{2}\} \cap \{r > 1\} \cap \{\omega_0 > 0\}, $$

$$ C_3 = \{\frac{\sqrt{2}}{2} < \xi < 1\} \cap \{0 < r < 1\} \cap \{\omega_0 > 0\}, $$

$$ C_4 = \{\frac{\sqrt{2}}{2} < \xi < 1\} \cap \{r > 1\} \cap \{\omega_0 > 0\}, $$

and the sample points

$$ \text{sample}_1 = \left[ \xi = \frac{25476206690102465}{72057594037927936}, r = \frac{1}{2}, \omega_0 = 1 \right], $$

$$ \text{sample}_2 = \left[ \xi = \frac{25476206690102465}{72057594037927936}, r = 2, \omega_0 = 1 \right], $$

$$ \text{sample}_3 = \left[ \xi = \frac{30752501854533959}{36028797018963968}, r = \frac{1}{2}, \omega_0 = 1 \right], $$
$$ \text{sample}_4 = \left[ \xi = \frac{30752501854533959}{36028797018963968}, r = 2, \omega_0 = 1 \right]. $$

By substituting sample$_1$ for $\alpha$ in $n(\omega, \gamma)$, we obtain

$$ n_1(\omega, \gamma) = \left(\gamma - \frac{1}{4}\right) \left(\gamma + \frac{1}{4}\right) \omega^4 + (a\gamma^2 + b)\omega^2 + \frac{1}{16}(\gamma - 1)(\gamma + 1), $$

where:

$$ a = -\frac{1947111321950592219128255965533823}{5192296858534827628530496329220096}, $$

$$ b = \frac{1947111321950592219128255965533823}{20769187434139310514121985316880384}. $$

Then, by using one of the proposed methods described in Section 3, we obtain the following isolating interval for $\gamma_{\max}$ (as defined in Theorem 4.5),

$$ \left[ \frac{6100687164736347533}{4611686018427387904}, \frac{24402748658945394263}{18446744073709551616} \right], $$

which is the isolating interval of the element of index 8 in the sorted list of the real roots of $\text{Res}(n_1, \frac{\partial n_1}{\partial \omega}, \omega) \in \mathbb{Q}[\gamma]$. This indicates that the output list contains the element $[C_1, 8]$. To match this result with what we have obtained in Proposition 4.2, we can see that the real roots of $R$ are ordered as

$$ \{-\sqrt{X_2}, -1, -r^2, -\sqrt{X_1}, \sqrt{X_1}, r^2, 1, \sqrt{X_2}\}, $$

for all $\omega_0, r, \xi \in C_1$ and the element of index 8 is indeed the $L^\infty$-norm of $G$ as proven in Proposition 4.2.

Similarly, $n_2$ is the polynomial obtained after substituting sample$_2$ for $\alpha$ in $n$. In this case, $\gamma_{\max}$ is of isolating interval

$$ \left[ \frac{6100687164736347533}{1152921504606846976}, \frac{24402748658945394263}{4611686018427387904} \right], $$

which is the isolating interval of the element of index 8 in the sorted list of the real roots of $\text{Res}(n_2, \frac{\partial n_2}{\partial \omega}, \omega) \in \mathbb{Q}[\gamma]$. This indicates that the output list contains the element $[C_2, 8]$. With the notations of Proposition 4.2, the real roots of $R$ are ordered as

$$ \{-\sqrt{X_2}, -r^2, -1, -\sqrt{X_1}, \sqrt{X_1}, 1, r^2, \sqrt{X_2}\}, $$

for all $\omega_0, r, \xi \in C_2$. This shows that the result $[C_2, 8]$ aligns with Proposition 4.2.

Following the same approach, $n_3$ is the polynomial obtained after substituting sample$_3$ for $\alpha$ in $n$. In this case, $\gamma_{\max}$ is of isolating interval $[1, 1]$, which is the isolating interval of the element of index 7 in the sorted list of the real roots of $\text{Res}(n_3, \frac{\partial n_3}{\partial \omega}, \omega)$. This indicates that the output list contains the element $[C_3, 7]$. Moreover, we can verify that this result aligns with the result of Proposition 4.2 where the real roots of $R$ are ordered as

$$ \{-\sqrt{X_2}, -1, -r^2, -\sqrt{X_1}, \sqrt{X_1}, r^2, 1, \sqrt{X_2}\}, $$

for all $\omega_0, r, \xi \in C_3$.

Finally, $n_4$ is the polynomial obtained after substituting sample$_4$ for $\alpha$ in $n$. In this case, $\gamma_{\max}$ is of isolating interval $[4, 4]$ which is the isolating interval of the element of index 7 in the sorted list of the real roots of $\text{Res}(n_4, \frac{\partial n_4}{\partial \omega}, \omega)$. This indicates that the output contains the element $[C_4, 7]$. Indeed, the real roots of $R$ are ordered as

$$ \{-\sqrt{X_2}, -r^2, -1, -\sqrt{X_1}, \sqrt{X_1}, 1, r^2, \sqrt{X_2}\}, $$
for all $\omega_0, r, \xi \in C_4$ which aligns with the result of Proposition 4.2.

In Figure 2, we illustrate the above results by plotting the real roots of the resultant polynomial $R$ as functions of the parameter $\xi$, where we fix numerical values for $r$ and $\omega_0$. To facilitate visualization and for a clearer illustration, we fix the values of $r$ and $\omega_0$ as follows: $r = 2$ for Figure 2a and $r = 0.5$ for Figure 2b. Additionally, we set $\omega_0 = 1$.

In the resulting plots, the real roots of the resultant polynomial $R$, which represent $\gamma$ as a function of $\xi$, demonstrate how the functions behave with respect to $\xi$. For instance, when $0 < \xi < \frac{\sqrt{2}}{2}$ (the yellow region), $\gamma_{max}$ (as defined in Theorem 4.5) corresponds to the curve with the highest index, specifically the curve with index 8, indicating the maximal real root of $R$. Conversely, when $\frac{\sqrt{2}}{2} < \xi < 1$ (the blue region), $\gamma_{max}$ is represented by the curve with index 7. This curve corresponds to $\gamma = r^2$ when $r > 1$ and $\gamma = 1$ when $r < 1$. This observation underscores that the real root of $R$ with index 8, which corresponds to the maximal real root, represents a real $\gamma$ coordinate of a non-real solution of $\Sigma = \{n(\omega, \gamma) = 0, \frac{\partial n}{\partial \omega}(\omega, \gamma) = 0\}$ when $\frac{\sqrt{2}}{2} < \xi < 1$.

<figure><img src="image_4.png" /><figcaption>(a) The real roots of $R$ for $r = 2$ and $\omega_0 = 1$ as a function of $\xi$.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>(b) The real roots of $R$ for $r = 0.5$ and $\omega_0 = 1$ as a function of $\xi$.</figcaption></figure>

<caption>Fig. 2. Real roots $\gamma \in \mathbb{Q}[\xi]$ of $R \in \mathbb{Q}[\xi][\gamma]$ in Example 4.8 with fixed numerical values of $r$ and $\omega_0$.</caption>

While no complexity computation has been conducted for Algorithm 1, it is worthwhile mentioning that, using Cylindrical Algebraic Decomposition, the bit complexity of the algorithm is doubly exponential.

*Example 4.9.* In this example, we examine the servo-control of a mechanical axis with inertia $J$. The system, controlled by a motor with resistance $R_m$, inductance $L$, and electrical constant $k_e$, measures speed using a gyrometer. The system's transfer function $G$ includes $M$, the transfer function of a mechanical mode with resonance pulsation $\omega_d$ and anti-resonance $\omega_n$:
$$M(s) = \frac{1 + 2 \xi_n \frac{s}{\omega_n} + \left(\frac{s}{\omega_n}\right)^2}{1 + 2 \xi_d \frac{s}{\omega_d} + \left(\frac{s}{\omega_d}\right)^2}$$

We focus on computing the L$^{∞}$-norm of M from this servo-control example, as it is practically valuable. In this case, the parameter set is given by {$ω_n, ξ_n, ω_d, ξ_d$} ⊂ ℝ>0, and the polynomial associated with the L$^{∞}$-norm $n ∈ ℝ[ω_n, ξ_n, ω_d, ξ_d][ω, γ]$ is given by

$$n = a_2 ω^4 + a_1 ω^2 + a_0,$$

where $a_2 = ω_n^4 γ^2 - ω_d^4$, $a_1 = 4 ω_n^4 (ξ_d^2 - \frac{1}{2}) ω_d^2 γ^2 + (2 - 4 ξ_n^2) ω_n^2 ω_d^4$, and finally $a_0 = (γ^2 - 1) ω_n^4 ω_d^4$.

Algorithm 1, applied to $Σ = \{n_1(ω, γ) = 0, \frac{∂n_1}{∂ω}(ω, γ) = 0\}$ and $S_ρ = \{ω_n > 0, ξ_n > 0, ω_d > 0, ξ_d > 0\}$, returns

$$\{[C_i, \text{index}_i] | i \in \{1, 2, \dots, 52\}\}.$$

If we now consider the matrix M(s)/s, then the polynomial associated with the L$^{∞}$-norm $n ∈ ℝ[ω_n, ξ_n, ω_d, ξ_d][ω, γ]$ is given by

$$n = a_3 ω^6 + a_2 ω^4 + a_1 ω^2 + a_0,$$

where $a_3 = -γ^2 ω_n^4$, $a_2 = ω_d^2 (ω_d^2 - 4 ω_n^4 (ξ_d^2 - \frac{1}{2}) γ^2)$, $a_1 = ω_n^2 ω_d^4 ((4 ξ_n^2 - 2) - ω_n^2 γ^2)$, and $a_0 = ω_d^4 ω_n^4$. Algorithm 1, applied to $Σ = \{n_2(ω, γ) = 0, \frac{∂n_2}{∂ω}(ω, γ) = 0\}$ and $S_ρ = \{ω_n > 0, ξ_n > 0, ω_d > 0, ξ_d > 0\}$, returns

$$\{[C_i, \text{index}_i] | i \in \{1, 2, \dots, 920\}\}.$$

This example illustrates that the number of cells can quickly become large even for a low-order system with only a few parameters.

# 5 Conclusion

Future work will focus on expanding the capabilities of our approach to tackle higher-dimensional systems and further advancing our understanding in this field. For instance, the problem of determining sharp inequalities for the L$^{∞}$-norm of the product of two matrices will be investigated. Recall that L$^{∞}$-norm is sub-multiplicative, namely, we have $||G_1 G_2||_∞ ≤ ||G_1||_∞ ||G_2||_∞$ for all matrices $G_1 ∈ RH_∞^{p×q}$ and $G_2 ∈ RH_∞^{q×r}$. This inequality is used in control theory to obtain bounds on the L$^{∞}$-norm of transfer matrices which can be written as products (see, e.g., [17]). But this inequality is usually conservative. Hence, using algebraic methods for curves, we would like to study the L$^{∞}$-norm of $G_1 G_2$ in terms of the norms of $G_1$ and $G_2$, at least for classes of structured matrices $G_1$ and $G_2$ (e.g., block-diagonal or block-triangular matrices, invertible matrices, i.e., elements of the general linear group of $RH_∞$ of degree p, namely, $GL_p(RH_∞^{p×q}) = \{U ∈ RH_∞^{p×q} | ∃V ∈ RH_∞^{p×q}: U V = I_p\}$ and of some of its subgroups (e.g., transvections, elementary matrices)). Any progress in this direction can have an impact on robust control. Extensions of the results proposed in [3] and in this paper will be investigated for the classes of differential time-delay systems, which, in the frequency domain, are defined by quasipolynomials, namely, polynomials in s and $e^{-τ_i s}$ where $τ_i > 0$. Finally, the symbolic-numeric results on the characterization of the L$^{∞}$-norm for finite-dimensional linear time-invariant systems will also be used to revisit problems of robust control (e.g., the standard problem) [20, 19].
References

[1] Bouzidi, Y., Lazard, S., Moroz, G., Pouget, M., Rouillier, F., Sagraloff, M.: Solving bivariate systems using rational univariate representations. Journal of Complexity 37, 34–75 (2016). https://doi.org/10.1016/j.jco.2016.07.002

[2] Bouzidi, Y., Lazard, S., Pouget, M., Rouillier, F.: Separating linear forms and rational univariate representations of bivariate systems. Journal of Symbolic Computation 68, 84–119 (2015). https://doi.org/10.1016/j.jsc.2014.08.009

[3] Bouzidi, Y., Quadrat, A., Rouillier, F., Younes, G.: Computation of the $L_\infty$-norm of finite-dimensional linear systems. Communications in Computer and Information Science 1414, 119–136 (Aug 2021). https://doi.org/10.1007/978-3-030-81698-8_9, https://inria.hal.science/hal-03328685

[4] Boyd, S., Balakrishnan, V.: A regularity result for the singular values of a transfer matrix and a quadratically convergent algorithm for computing its $L_\infty$-norm. Systems and Control Letters 15(1), 1–7 (1990). https://doi.org/10.1016/0167-6911(90)90037-u

[5] Boyd, S., Balakrishnan, V., Kabamba, P.: A bisection method for computing the $H_\infty$ norm of a transfer matrix and related problems. Math. Control, Signals, and Systems 2, 207–220 (1989). https://doi.org/10.1007/bf02551385

[6] Chen, C., Moreno Maza, M., Xie, Y.: A fast algorithm to compute the $H_\infty$-norm of a transfer function matrix. Systems and Control Letters 14(4), 287–293 (1990). https://doi.org/10.1016/0167-6911(90)90049-z

[7] Cheng, J.S., Gao, X.S., Li, J.: Root isolation for bivariate polynomial systems with local generic position method. In: Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation. pp. 103–110. ACM (2009). https://doi.org/10.1145/1576702.1576719

[8] Collins, G.E.: Quantifier elimination for real closed fields by cylindrical algebraic decomposition. In: Automatic theory and formal languages, pp. 134–183. Springer (1975). https://doi.org/10.1007/3-540-07407-4_17

[9] Cox, D.A., Little, J., O'Shea, D.: Using algebraic geometry, Graduate Texts in Mathematics, vol. 185. Springer Science & Business Media (2005). https://doi.org/10.1007/978-1-4757-6911-1

[10] Demin, A., Rouillier, F., Ruiz, J.: Reading rational univariate representations on lexicographic groebner bases. arXiv preprint arXiv:2402.07141 (2024). https://doi.org/10.48550/arXiv.2402.07141

[11] Dolzmann, A., Sturm, T., Weispfenning, V.: Real quantifier elimination in practice. In: Algorithmic algebra and number theory, pp. 221–247. Springer (1999). https://doi.org/10.1007/978-3-642-59932-3_11

[12] Doyle, J.C., Francis, B.A., Tannenbaum, A.R.: Feedback control theory. Courier Corporation (2013)

[13] Gerhard, J., Jeffrey, D.J., Moroz, G.: A package for solving parametric polynomial systems. ACM Communications in Computer Algebra 43(3/4), 61–72 (2010). https://doi.org/10.1145/1823931.1823933

[14] González-Vega, L., Recio, T., Lombardi, H., Roy, M.F.: Sturm-Habicht sequences, determinants and real roots of univariate polynomials. In: Quantifier Elimination and Cylindrical Algebraic Decomposition, pp. 300–316. Springer (1998). https://doi.org/10.1007/978-3-7091-9459-1_14

[15] Kanno, M., Smith, M.C.: Validated numerical computation of the $L_\infty$-norm for linear dynamical systems. Journal of Symbolic Computation 41(6), 697–707 (2006). https://doi.org/10.1016/j.jsc.2005.11.005

[16] Lazard, D., Rouillier, F.: Solving parametric polynomial systems. Journal of Symbolic Computation 42(6), 636–667 (2007). https://doi.org/10.1016/j.jsc.2007.01.007

[17] Rance, G.: Commande H∞ paramétrique et application aux viseurs gyrostabilisés. Theses, Université Paris Saclay (COmUE) (Jul 2018), https://theses.hal.science/tel-01904086

[18] Zames, G.: Feedback and optimal sensitivity: Model reference transformations, multiplicative seminorms, and approximate inverses. IEEE Transactions on Automatic Control 26(2), 301–320 (1981). https://doi.org/10.1109/TAC.1981.1102603

[19] Zhou, K., Doyle, J.C.: Essentials of robust control. Prentice Hall, Upper Saddle River, NJ (1998)

[20] Zhou, K., Doyle, J.C., Glover, K.: Robust and Optimal Control. Prentice Hall (1996)