Polynomials with respect to a general basis. I. Theory

As n × n Hessenberg matrix A is defined whose characteristic polynomial is relative to an arbitrary basis. This generalizes the companion, colleague, and comrade matrices when the bases are, respectively, power, Chebyshev, and orthogonal, so the term “confederate” matrix is suggested. Some properties of A are derived, including an algorithm for computing powers of A. A scheme is given for inverting the transformation matrix between the arbitrary and power bases. A Vandermonde-type matrix associated with A and a block confederate matrix are defined.     

A recursive algorithm for constructing complicated Dixon matrices

Whether the determinant of the Dixon matrix equals zero or not is used for determining if a system of n + 1 polynomial equations in n variables has a common root, and is a very efficient quantifier elimination approach too. But for a complicated polynomial system, it is not easy to construct the Dixon matrix. In this paper, a recursive algorithm to construct the Dixon matrix is proposed by which some problems that cannot be tackled by other methods can be solved on the same computer platform. A dynamic programming algorithm based on the recursive formula is developed and compared for speed and efficiency to the recursive algorithm.     

To Solving Multiparameter Problems of Algebra. 5. The ∇V-q Factorization Algorithm and its Applications

The algorithm of ∇V-factorization, suggested earlier for decomposing one- and two-parameter polynomial matrices of full row rank into a product of two matrices (a regular one, whose spectrum coincides with the finite regular spectrum of the original matrix, and a matrix of full row rank, whose singular spectrum coincides with the singular spectrum of the original matrix, whereas the regular spectrum is empty), is extended to the case of q-parameter (q ≥ 1) polynomial matrices. The algorithm of ∇V-q factorization is described, and its justification and properties for matrices with arbitrary number of parameters are presented. Applications of the algorithm to computing irreducible factorizations of q-parameter matrices, to determining a free basis of the null-space of polynomial solutions of a matrix, and to finding matrix divisors corresponding to divisors of its characteristic polynomial are considered. Bibliogrhaphy: 4 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 309, 2004, pp. 144–153.     

An algorithm for computing powers of a Hessenberg matrix and its applications

A simple algorithm for computing the first n powers of an n×n Hessenberg matrix with unit codiagonal or for evaluating a polynomial of degree ?n in such a matrix is proposed in this paper. Several applications of the algorithm are mentioned, including the solution of Lyapunov matrix equations associated with stability problems.     

The matrix equation XA=ATX and an associated algorithm for solving the inertia and stability problems

We develop a constructive procedure for generating nonsingular solutions of the matrix equation XA=A^TX and establish an interesting relationship between a given solution X of the above equation and the associated matrix polynomial p(A). The latter is then used to develop an algorithm for computing the inertia of a matrix. The algorithm is more efficient than the other common procedures.     

A fully polynomial approximation algorithm for the 0–1 knapsack problem

A fully polynomial ?-approximation algorithm is developed for the 0–1 knapsack problem. The algorithm uses results of Lawler and Ibarra and Kim. A pseudo-polynomial dynamic programming algorithm is first suggested which solves the problem in O(nb log n) time and O(b) space.     

Interpolation algorithm of Leverrier–Faddev type for polynomial matrices

We investigated an interpolation algorithm for computing outer inverses of a given polynomial matrix, based on the Leverrier–Faddeev method. This algorithm is a continuation of the finite algorithm for computing generalized inverses of a given polynomial matrix, introduced in [11]. Also, a method for estimating the degrees of polynomial matrices arising from the Leverrier–Faddeev algorithm is given as the improvement of the interpolation algorithm. Based on similar idea, we introduced methods for computing rank and index of polynomial matrix. All algorithms are implemented in the symbolic programming language MATHEMATICA , and tested on several different classes of test examples.     

QD algorithms and algebraic eigenvalue problems

A sketch of the standard QD algorithm is followed by the derivation of two similar algorithms for the calculation of all the eigenvalues of the matrix A from the sequence {A^rg₀}. The existence of one of the methods is stablished and bounds for the results are given when A is totally positive. The paper concludes by showing the close connection between the QD algorithm for the calculation of the zeros of a polynomial and the method of treppeniteration for the calculation of the eigenvalues of its companion matrix.     

The eigenstructure of an arbitrary polynomial matrix: computational aspects

We give a new numerical method to compute the eigenstructure—i.e. the zero structure, the polar structure, and the left and right null space structure—of a polynomial matrix P(λ). These structural elements are of fundamental importance in several systems and control problems involving polynomial matrices. The approach is more general than previous numerical methods because it can be applied to an arbitrary m × n polynomial matrix P(λ) with normal rank r smaller than m and/or n. The algorithm is then shown to compute the structure of the left and right null spaces of P(λ) as well. The speed and accuracy of this new approach are also discussed.     

Strongly polynomial algorithm for a class of combinatorial LCPs

We show that an LCP with positive definite coefficient matrix can be solved in time polynomially bounded by the size of the numbers in the coefficient matrix. As a special case, we have a strongly polynomial algorithm for the problem of fitting the best convex curve to a given set of points in R².     

Detecting rigid convexity of bivariate polynomials

Given a polynomial x∈Rⁿ?p(x) in n=2 variables, a symbolic-numerical algorithm is first described for detecting whether the connected component of the plane sublevel set P={x:p(x)?0} containing the origin is rigidly convex, or equivalently, whether it has a linear matrix inequality (LMI) representation, or equivalently, if polynomial p(x) is hyperbolic with respect to the origin. The problem boils down to checking whether a univariate polynomial matrix is positive semidefinite, an optimization problem that can be solved with eigenvalue decomposition. When the variety C={x:p(x)=0} is an algebraic curve of genus zero, a second algorithm based on Bézoutians is proposed to detect whether P has an LMI representation and to build such a representation from a rational parametrization of C. Finally, some extensions to positive genus curves and to the case n>2 are mentioned.     

To solving multiparameter problems of algebra. 7. The PG-q factorization method and its applications

The paper continues the development of rank-factorization methods for solving certain algebraic problems for multi-parameter polynomial matrices and introduces a new rank factorization of a q-parameter polynomial m × n matrix F of full row rank (called the PG-q factorization) of the form F = PG, where is the greatest left divisor of F; Δ _i ^(k) i is a regular (q-k)-parameter polynomial matrix the characteristic polynomial of which is a primitive polynomial over the ring of polynomials in q-k-1 variables, and G is a q-parameter polynomial matrix of rank m. The PG-q algorithm is suggested, and its applications to solving some problems of algebra are presented. Bibliography: 6 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 323, 2005, pp. 150–163.     

To solving multiparameter problems of algebra. 8. The <Emphasis Type="Italic">RP-q</Emphasis> method and its applications

A new method (the RP-q method) for factorizing scalar polynomials in q variables and q-parameter polynomial matrices (q ≥ 1) of full rank is suggested. Applications of the algorithm to solving systems of nonlinear algebraic equations and some spectral problems for a q-parameter polynomial matrix F (such as separation of the eigenspectrum and mixed spectrum of F, computation of bases with prescribed spectral properties of the null-space of polynomial solutions of F, and computation of the hereditary polynomials of F) are considered. Bibliography: 10 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 334, 2006, pp. 149–164.     

DFT calculation for the {2}-inverse of a polynomial matrix with prescribed image and kernel

In this paper, we first give the finite algorithm for generalized inverse of a matrix A over an integral domain, and, based on it and the discrete Fourier transform, present an algorithm for calculating {2}-inverses of a polynomial matrix with prescribed image and kernel. And the algorithm is implemented in the Mathematica programming language and expands the algorithms in [13].     

Generalized GIPSCAL re-revisited: a fast convergent algorithm with acceleration by the minimal polynomial extrapolation

Generalized GIPSCAL, like DEDICOM, is a model for the analysis of square asymmetric tables. It is a special case of DEDICOM, but unlike DEDICOM, it ensures the nonnegative definiteness (nnd) of the model matrix, thereby allowing a spatial representation of the asymmetric relationships among ??objects??. A fast convergent algorithm was developed for GIPSCAL with acceleration by the minimal polynomial extrapolation. The proposed algorithm was compared with Trendafilov??s algorithm in computational speed. The basic algorithm has been adapted to various extensions of GIPSCAL, including off-diagonal DEDICOM/GIPSCAL, and three-way GIPSCAL.     

To solving problems of algebra for two-parameter matrices. III

The paper continues the series of papers devoted to surveying and developing methods for solving algebraic problems for two-parameter polynomial and rational matrices of general form. It considers linearization methods, which allow one to reduce the problem of solving an equation F(λ, μ)x = 0 with a polynomial two-parameter matrix F(λ, μ) to solving an equation of the form D(λ, μ)y = 0, where D(λ, μ) = A(μ)-λB(μ) is a pencil of polynomial matrices. Consistent pencils and their application to solving spectral problems for the matrix F(λ, μ) are discussed. The notion of reducing subspace is generalized to the case of a pencil of polynomial matrices. An algorithm for transforming a general pencil of polynomial matrices to a quasitriangular pencil is suggested. For a pencil with multiple eigenvalues, algorithms for computing the Jordan chains of vectors are developed. Bibliography: 8 titles. Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 359, 2008, pp. 166–207.     

Solution of systems of general-form nonilinear algebraic equations. Methods and algorithms. IV

This paper considers the solution of a system of m nonlinear equations in q>02 variables (SNAE-q). A method for finding all of the finite zero-dimensional roots of a given SNAE-q, which extends the method suggested previously for q=2 and q=3 to the case q≥2, is developed and theoretically justified. This method is based on the algorithm of the ΔW-q factorization of a polynomial q-parameter matrix and on the algorithm of relative factorization of a scalar polynomial in q variables. Bibliography: 7 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 248, 1998, pp. 124–146. Translated by V. N. Kublanovskaya.     

A bisection method for measuring the distance of a quadratic matrix polynomial to the quadratic matrix polynomials that are singular on the unit circle

The computation of the distance of a quadratic matrix polynomial to the quadratic matrix polynomials that are singular on the unit circle is investigated. The emphasis is placed on backward stable methods that transform the computation of the distance to a palindromic eigenvalue problem for which structure-preserving eigensolvers can be utilized in conjunction with a bisection algorithm. Reliability of the suggested methods is guaranteed by a novel error analysis.     

Congenial matrices

For a given polynomial in the usual power form, its associated companion matrix can be applied to investigate qualitative properties, such as the location of the roots of the polynomial relative to regions of the complex plane, or to determine the greatest common divisor of a set of polynomials. If the polynomial is in “generalized” form, i.e. expressed relative to an orthogonal basis, then an analogue to the companion matrix has been termed the comrade form. This followed a special case when the basis is Chebyshev, for which the term colleague matrix had been introduced. When a yet more general basis is used, the corresponding matrix has been named confederate. These constitute the class of congenial matrices, which allow polynomials to be studied relative to an appropriate basis. Block-partitioned forms relate to polynomial matrices.     

Polynomial least squares fitting in the Bernstein basis

The problem of polynomial least squares fitting in which the usual monomial basis is replaced by the Bernstein basis is considered. The coefficient matrix of the overdetermined system to be solved in the least squares sense is then a rectangular Bernstein-Vandermonde matrix. In order to use the method based on the QR decomposition of A, the first stage consists of computing the bidiagonal decomposition of the coefficient matrix A. Starting from that bidiagonal decomposition, an algorithm for obtaining the QR decomposition of A is the applied. Finally, a triangular system is solved by using the bidiagonal decomposition of the R-factor of A. Some numerical experiments showing the behavior of this approach are included.