A matrix triangularization algorithm for the polynomial point interpolation method

A novel matrix triangularization algorithm (MTA) is proposed to overcome the singularity problem in the point interpolation method (PIM) using the polynomial basis, and to ensure stable and reliable construction of PIM shape functions. The present algorithm is validated using several examples, and implemented in the local point interpolation method (LPIM) that is a truly meshfree method based on a local weak form. Numerical examples demonstrate that LPIM using the present MTA are very easy to implement, and very robust for solving problems of computational mechanics. It is shown that PIM with the present MTA is very effective in constructing shape functions. Most importantly, PIM shape functions possess Kronecker delta function properties. Parameters that influence the performance of them are studied in detail. The convergence and efficiency of them are thoroughly investigated.     

Fast triangularization of a symmetric tridiagonal matrix

A simple linear systolic array is presented for triangularizing a symmetric tridiagonal matrix by Gaussian Elimination using nearest neighbor pivoting. The array consists of three cells requiring an area bounded by four simple inner product cells. The design can compute the elimination in time 2_n + k₁ for the simple point case and using an implicit 2*2 block structuring of data produces an almost eliminated form in time n + k₂. The implicit result can be fully eliminated by only a constant number of extra operations independent of the matrix order (n), where k, and k2 are constants.     

Systolic architectures for polynomial and polynomial matrix manipulations

Manipulations of polynomials and polynomial matrices, basic to the polynomial equation approach to control system design, are dissected in a manner suitable for repeatable, rhythmic solution. These solutions are then implemented on systolic arrays. An introduction to a systematic design and analysis procedure for systolic arrays, along with an example, concludes the paper.     

A numerical elimination method for polynomial computations

A numerical elimination method is presented in this paper for floating-point computation in polynomial algebra. The method is designed to calculate one or more polynomials in an elimination ideal by a sequence of matrix rank/kernel computation. The method is reliable in numerical computation with verifiable stability and a sensitivity measurement. Computational experiment shows that the method possesses significant advantages over classical resultant computation in numerical stability and in producing eliminant polynomials with lower degrees and fewer extraneous factors. The elimination algorithm combined with an approximate GCD finder appears to be effective in solving polynomial systems for positive dimensional solutions.     

An algorithm for polynomial matrix factor extraction

An algorithm is described for extracting a polynomial matrix factor featuring any subset of the zeros of a given non-singular polynomial matrix. It is assumed that the zeros to be extracted are given as input data. Complex or repeated zeros are allowed. The algorithm is based on interpolation and relies upon numerically reliable subroutines only. It makes use of a procedure that computes the generalized characteristic vectors of a polynomial matrix at a given point. The extracted factor is provided in column- and row-reduced Popov form. Applications of the algorithm include polynomial matrix interpolation, plus/minus factorization, column- and row-reduction, or computation of the Smith form of a polynomial matrix. The numerical routines described in this paper are implemented in the new release 2.0 of the Polynomial Toolbox for MATLAB.     

Subdivision methods for solving polynomial equations

This paper presents a new algorithm for solving a system of polynomials, in a domain of Rⁿ${\mathbb{R}}^n$. It can be seen as an improvement of the Interval Projected Polyhedron algorithm proposed by Sherbrooke and Patrikalakis [Sherbrooke, E.C., Patrikalakis, N.M., 1993. Computation of the solutions of nonlinear polynomial systems. Comput. Aided Geom. Design 10 (5), 379–405]. It uses a powerful reduction strategy based on univariate root finder using Bernstein basis representation and Descarte’s rule  . We analyse the behavior of the method, from a theoretical point of view, shows that for simple roots, it has a local quadratic convergence speed and gives new bounds for the complexity of approximating real roots in a box of Rⁿ${\mathbb{R}}^n$. The improvement of our approach, compared with classical subdivision methods, is illustrated on geometric modeling applications such as computing intersection points of implicit curves, self-intersection points of rational curves, and on the classical parallel robot benchmark problem.     

Validating numerical semidefinite programming solvers for polynomial invariants

Semidefinite programming (SDP) solvers are increasingly used as primitives in many program verification tasks to synthesize and verify polynomial invariants for a variety of systems including programs, hybrid systems and stochastic models. On one hand, they provide a tractable alternative to reasoning about semi-algebraic constraints. However, the results are often unreliable due to “numerical issues” that include a large number of reasons such as floating-point errors, ill-conditioned problems, failure of strict feasibility, and more generally, the specifics of the algorithms used to solve SDPs. These issues influence whether the final numerical results are trustworthy or not. In this paper, we briefly survey the emerging use of SDP solvers in the static analysis community. We report on the perils of using SDP solvers for common invariant synthesis tasks, characterizing the common failures that can lead to unreliable answers. Next, we demonstrate existing tools for guaranteed semidefinite programming that often prove inadequate to our needs. Finally, we present a solution for verified semidefinite programming that can be used to check the reliability of the solution output by the solver and a padding procedure that can check the presence of a feasible nearby solution to the one output by the solver. We report on some successful preliminary experiments involving our padding procedure.     

Asymptotically fast polynomial matrix algorithms for multivariable systems

We present the asymtotically fastest known algorithms for some basic problems on univariate polynomial matrices: rank; nullspace; determinant; generic inverse reduced form (Giorgi et al. 2003, Storjohann 2003 Storjohann, A. 2003. “High-order lifting and integrality certification”. In J. Symb. Comp. Edited by: Giusti, M and Pardo, LM. Vol. 36, 613–648. Nice, France, 3, , USA Special issue International Symposium on Symbolic and Algebraic Computation (ISSAC’2002). Guest editors: [Google Scholar], Jeannerod and Villard 2005 Jeannerod, C-P and Villard, G. 2005. Essentially optimal computation of the inverse of generic polynomial matrices. J. Comp., 21: 72–86.  [Google Scholar], Storjohann and Villard 2005 Storjohann, A and Villard, G. July 2005. “Computing the rank and a small nullspace basis of a polynomial matrix”. In Proc. International Symposium on Symbolic and Algebraic Computation, 309–316. Beijing, China: ACM Press.  [Google Scholar]). We show that they essentially can be reduced to two computer algebra techniques, minimal basis computations and matrix fraction expansion/reconstruction, and to polynomial matrix multiplication. Such reductions eventually imply that all these problems can be solved in about the same amount of time as polynomial matrix multiplication. The algorithms are deterministic, or randomized with certified output in a Las Vegas fashion.     

Evaluation of a matrix polynomial

A simple method is proposed to reduce the computational requirements for evaluation of matrix polynomials. An example is given indicating its use in evaluating e^Aarising in the solution of linear differential equations.     

Reliable stabilization via factorization methods

Reliable stabilization of multicontroller systems composed of one plant and two controllers are considered. The main objective is to propose a reliability design when controllers use independent inputs and outputs of the plant. The assumption of independence is crucial if one wants to increase the chance that at least one of the controllers survives the sensor and actuator failures, which otherwise could disable both controllers and result in a system breakdown     

Hermite matrix in Lagrange basis for scaling static output feedback polynomial matrix inequalities

Using Hermite's formulation of polynomial stability conditions, static output feedback (SOF) controller design can be formulated as a polynomial matrix inequality (PMI), a (generally nonconvex) nonlinear semidefinite programming problem that can be solved (locally) with PENNON, an implementation of a penalty and augmented Lagrangian method. Typically, Hermite SOF PMI problems are badly scaled and experiments reveal that this has a negative impact on the overall performance of the solver. In this note we recall the algebraic interpretation of Hermite's quadratic form as a particular Bézoutian and we use results on polynomial interpolation to express the Hermite PMI in a Lagrange polynomial basis, as an alternative to the conventional power basis. Numerical experiments on benchmark problem instances show the improvement brought by the approach, in terms of problem scaling, number of iterations and convergence behaviour of PENNON.     

Stability of the second-order matrix polynomial

This note summarizes some existing stability and instability conditions of the second-order matrix polynomial which arises in the formulation of classical mechanics, aerodynamics, and robotic systems. Also, some sufficient conditions for stability or instability of the second-order matrix polynomial are newly developed via the relevant linear matrix equation obtained from the Lyapunov theory.     

On multivariate polynomial matrix factorization problems

This paper studies the multivariate polynomial matrix factorization problems which have applications to multidimensional systems theory and signal processing. We first extract an algorithm from Pommaret's proof of the Lin-Bose conjecture. Then we simplify our algorithm, and prove a theorem which gives a sufficient and necessary condition for a multivariate polynomial matrix to have an minor left prime (MLP) factorization. Examples are given to illustrate the effectiveness of this algorithm. Our results hold for any coefficient field and thus have a wide range of applications. This work was supported by grants from the Research Grants Council of Hong Kong (Project CUHK4185/01E) and 973 projects(G1999035802 and 2004CB318004)     

A new method for computing a column reduced polynomial matrix

A new algorithm is presented for computing a column reduced form of a given full column rank polynomial matrix. The method is based on reformulating the problem as a problem of constructing a minimal polynomial basis for the right nullspace of a polynomial matrix closely related to the original one. The latter problem can easily be solved in a numerically reliable way. Three examples illustrating the method are included.     

Heuristic regularization methods for numerical differentiation

In this paper, we use smoothing splines to deal with numerical differentiation. Some heuristic methods for choosing regularization parameters are proposed, including the $L$-curve method and the de Boor method. Numerical experiments are performed to illustrate the efficiency of these methods in comparison with other procedures.     

Genetic programming for iterative numerical methods

Genetic Programming and Evolvable Machines - We introduce GPLS (Genetic Programming for Linear Systems) as a GP system that finds mathematical expressions defining an iteration matrix. Stationary...     

Decentralized control of linear dynamical systems via polynomial matrix methods I: Two interconnected scalar systems

The problem of the decentralized control of a linear interconnected dynamical system is considered. This is done by defining the problems of the decentralized controllability and of the decentralized observability, which are solved for a system consisting of two interconnected scalar systems. The solution is determined using the theory of the linear dynamical systems in the differential operator representation (Wolovich 1974), and provides, besides structural results, a systematic method for the decentralized control of these systems.     

Nonnegative matrix factorization in polynomial feature space

Plenty of methods have been proposed in order to discover latent variables (features) in data sets. Such approaches include the principal component analysis (PCA), independent component analysis (ICA), factor analysis (FA), etc., to mention only a few. A recently investigated approach to decompose a data set with a given dimensionality into a lower dimensional space is the so-called nonnegative matrix factorization (NMF). Its only requirement is that both decomposition factors are nonnegative. To approximate the original data, the minimization of the NMF objective function is performed in the Euclidean space, where the difference between the original data and the factors can be minimized by employing L(2)-norm. In this paper, we propose a generalization of the NMF algorithm by translating the objective function into a Hilbert space (also called feature space) under nonnegativity constraints. With the help of kernel functions, we developed an approach that allows high-order dependencies between the basis images while keeping the nonnegativity constraints on both basis images and coefficients. Two practical applications, namely, facial expression and face recognition, show the potential of the proposed approach.