Let G(s)=C(sI - A)-1B+D be a given system where entries of A,B,C,D are polynomials in a parameter k. Then H∞ norm || G(s) ||∞ of G(s) is a function of k, and [9] presents an algorithm to express 1/(||G(s) ||∞)2 as a root of a bivariate polynomial, assuming feedthrough term D to be zero. This paper extends the algorithm in two ways: The first extension is the form of the function to be expressed. The extended algorithm can treat, not only H∞ norm, but also functions that appear in the celebrated KYP Lemma. The other extension is the range of the frequency. While H∞ norm considers the supremum of the maximum singular value of G(i ω) for the infinite range 0 ≤ω ≤ ∞ of ω, the extended algorithm treats the norm for the finite frequency range ω ≤ ω ≤ ω- (ω, ω- ∈ R ∪ ∞). Those two extensions allow the algorithm to be applied to wider area of control problems. We give illustrative numerical examples where we apply the extended algorithm to the computation of the frequency-restricted norm, i.e., the supremum of the maximum singular value of G(i ω) (ω- ≤ ω ≤ ω-).

In [1], approximate eigenvalues and eigenvectors are defined and algorithms to compute them are described. However, the algorithms require a certain condition: the eigenvalues of M modulo S are all distinct, where M is a given matrix with polynomial entries and S is a maximal ideal generated by the indeterminate in M. In this paper, we deal with the construction of approximate eigenvalues and eigenvectors when the condition is not satisfied. In this case, powers of approximate eigenvalues and eigenvectors become, in general, fractions. In other words, approximate eigenvalues and eigenvectors are expressed in the form of Puiseux series. We focus on a matrix with univariate polynomial entries and give complete algorithms to compute the approximate eigenvalues and eigenvectors of the matrix.

Given the bivariate polynomial f(x,y), let φ(y) be a root of f(x,y) = 0 with respect to x, i.e. φ(y) is a function of y such that f(φ(y),y) = 0. If φ(y) is analytic at y = 0, then we have its power series expansion φ(y) = α0 + α1y + α2y2 + + αpyp + .(1)Let φ(p)(y) denote φ(y) truncated at yp, i.e. φ(p)(y) = α0 + α1y + α2y2 + + αpyp.(2) It is well-known that we can compute power series roots φ(p)(y) by Newton's method. In fact, given the initial value φ(0)(y) = α0 C, the following Newton's methodφ(k)(y) φ(k-1)(y) - (mod yk+1) (3) computes φ(k)(y) (1 k) in expression (2) efficiently (applying the above formula for k = 1,2,, we can compute the power series root φ(p)(y) of any degree p). The above formula (3) is referred to as "symbolic Newton's method" in this paper. From this formula (3), we can see that the numerical errors in the coefficients αs (s = 0,1,...,k - 1) directly affect the numerical error in the coefficient αk. This implies that the symbolic Newton's method is numerically unstable, i.e., a numerical error in the coefficient αk accumulates as the index k increases. Moreover, with the symbolic Newton's method, even if we need only one coefficient αk, we must compute all coefficients αs (s = 0,1,,k - 1). Thus, when we require only one high degree coefficient αk, the symbolic Newton's method is numerically unstable and inefficient. In this paper, given the integer k (> 0), we present a new algorithm to compute the coefficient αk of (1). The new algorithm is numerically stable and requires no computation of the coefficients other than αk itself.

In this paper, we give a new approach to the computation of primary decomposition and associated prime components of a zero-dimensional polynomial ideal (f1,f2,. . . ,fn), where fi are multivariate polynomials on Z (the ring of integer). Over the past several years, a considerable number of studies have been made on the computation of primary decomposition of a zero-dimensional polynomial ideal. Many algorithms to compute primary decomposition are proposed. Most of the algorithms recently proposed are based on Groebner basis. However, the computation of Groebner basis can be very expensive to perform. Some computations are even impossible because of the physical limitation of memory in a computer. On the other hand, recent advance in numerical methods such as homotopy method made access to the zeros of a polynomial system relatively easy. Hence, instead of Groebner basis, we use the zeros of a given ideal to compute primary decomposition and associated prime components. More specifically, given a zero-dimensional ideal, we use LLL reduction algorithm by Lenstra et al. to determine the integer coefficients of irreducible polynomials in the ideal. It is shown that primary decomposition and associated prime components of the ideal can be computed, provided the zeros of the ideal are computed with enough accuracy. A numerical experiment is given to show effectiveness of our algorithm.

Let M(y) be a matrix whose entries are polynomial in y, λ(y) and v(y) be a set of eigenvalue and eigenvector of M(y). Then, λ(y) and v(y) are algebraic functions of y, and λ(y) and v(y) have their power series expansionsλ(y) = β0 + β1 y + + βk yk + (βj C),(1) v(y) = γ0 + γ1 y + + γk yk + (γj Cn), (2)provided that y=0 is not a singular point of λ(y) or v(y). Several algorithms are already proposed to compute the above power series expansions using Newton's method (the algorithm in [4]) or the Hensel construction (the algorithm in[5],[12]). The algorithms proposed so far compute high degree coefficients βk and γk, using lower degree coefficients βj and γj (j=0,1,,k-1). Thus with floating point arithmetic, the numerical errors in the coefficients can accumulate as index k increases. This can cause serious deterioration of the numerical accuracy of high degree coefficients βk and γk, and we need to check the accuracy. In this paper, we assume that given matrix M(y) does not have multiple eigenvalues at y=0 (this implies that y=0 is not singular point of λ(y) or v(y)), and presents an algorithm to estimate the accuracy of the computed power series βi,γj in (1) and (2). The estimation process employs the idea in [9] which computes a coefficient of a power series with Cauchy's integral formula and numerical integrations. We present an efficient implementation of the algorithm that utilizes Newton's method. We also present a modification of Newton's method to speed up the procedure, introducing tuning parameter p. Numerical experiments of the paper indicates that we can enhance the performance of the algorithm by 1216%, choosing the optimal tuning parameter p.

This paper presents an efficient algorithm for computing the characteristic polynomial of a matrix, which utilizes Cayley-Hamilton's theorem. The algorithm requires no condition on input matrix and can be performed only with basic matrix operations except only one computation of inverse of constant matrix. Though the algorithm can be applied to a constant matrix, it is the most effective when applied to a matrix with polynomial entries. Computational tests are given to compare the algorithm with conventional ones.

Suppose that we need to design a controller for the system x(t) = A x(t) + B u, u = -K x(t), y(t) = C x(t), where matrices A, B and C are given and K is the matrix to to determine. It is required to determine K so that y(t) should not exceed prescribed value (i.e., the peak of output y(t) is limited). This kind of specification, in general, difficult to satisfy, since the peak ymax of y(t) (we define ymax to be max0 t |y(t)|) is a non-trivial function of design parameter K, which can not be expressed explicitly generally. Therefore, a controller design with such specifications often requires try and error process. In this paper, we approximate ymax in the form of formal power series and give an efficient algorithm to compute the series. We also give a design example of a control system as an application of the algorithm.

In recent years, algorithms based on Computer Algebra ([1]-[3]) have been introduced into a range of control design problems because of the capacity to handle unknown parameters as indeterminates. This feature of algorithms in Computer Algebra reduces the costs of computer simulation and the trial and error process involved, enabling us to design and analyze systems more theoretically with the behavior of given parameters. In this paper, we apply Computer Algebra algorithms to H∞ control theory, representing one of the most successful achievements in post-modern control theory. More specifically, we consider the H∞ norm minimization problem using a state feedback controller. This problem can be formulated as follows: Suppose that we are given a plant described by the linear differential equation = Ax + B1w + B2u, z = Cx + Du, where A,B1,B2,C,D are matrices whose entries are polynomial in an unknown parameter k. We apply a state feedback controller u = -F x to the plant, where F is a design parameter, and obtain the system = (A - B2F)x + B1w, z =(C - DF)x. Our task is to compute the minimum H∞ norm of the transfer function G(s)(=(C - DF)(sI - A + B2F)-1B1) from w to z achieved using a static feedback controller u = -Fx, where F is a constant matrix. In the H∞ control theory, it is only possible to check if there is a controller such that ||G(s)||∞ < γ is satisfied for a given number γ, where ||G(s)||∞ denotes the H∞ norm of the transfer function G(s). Thus, a typical procedure to solve the H∞ optimal problem would involve a bisection method, which cannot be applied to plants with parameters. In this paper, we present a new method of solving the H∞ norm minimization problem that can be applied to plants with parameters. This method utilizes QE (Quantifier Elimination) and a variable elimination technique in Computer Algebra, and expresses the minimum of the H∞ norm as a root of a bivariate polynomial. We also present a numerical example to illustrate each step of the algorithm.

H∞ optimal control is one of the most successful achievements in the post modern control theory. In the H∞ optimal control, we design a controller that minimizes the H∞ norm of a given system. Although the algorithms to solve the problem have already been reported, they focus on numerical systems (systems without any unknown parameters) and, can not be applied for parametric systems (systems with unknown parameters). Given a parametric system, this paper presents an algorithm to compute the optimal H∞ norm of the system achieved by an output feedback controller. The optimal H∞ norm is expressed as , where φ(k) denotes a root of a bivariate polynomial. A numerical example is given to show the effectiveness of the algorithm.

In Ref.[5], the author defines "approximate eigenvalues" and "approximate eigenvectors," which are, in short, Taylor series expansions of eigenvalues and eigenvectors of a polynomial matrix. In this paper, an efficient algorithm to compute the approximate eigenvalues and eigenvectors is presented. The algorithm performs the computations with an arbitrary degree of convergence.

This paper presents an efficient algorithm to compute the characteristic polynomial of a polynomial matrix. We impose the following condition on given polynomial matrix M. Let M0 be the constant part of M, i. e. M0 M ( mod (y,,z)), where y,,z are indeterminates in M. Then, all eigenvalues of M0 must be distinct. In this case, the minimal polynomial of M and the characteristic polynomial of M agree, i. e. the characteristic polynomial f(x,y,,z) | x E M | is the minimal degree (w. r. t. x) polynomial satisfying f(M,y,,z) 0. We use this fact to compute f(x,y,,z). More concretely, we determine the coefficients of f(x,y,,z) little by little with basic matrix operations, which makes the algorithm quite efficient. Numerical experiments are given to compare the algorithm with conventional ones.