A Deterministic Algorithm for Approximating the Mixed Discriminant and Mixed Volume, and a Combinatorial Corollary

Abstract. We present a deterministic polynomial-time algorithm that computes the mixed discriminant of an n -tuple of positive semidefinite matrices to within an exponential multiplicative factor. To this end we extend the notion of doubly stochastic matrix scaling to a larger class of n -tuples of positive semidefinite matrices, and provide a polynomial-time algorithm for this scaling. As a corollary, we obtain a deterministic polynomial algorithm that computes the mixed volume of n convex bodies in R ⁿ to within an error which depends only on the dimension. This answers a question of Dyer, Gritzmann and Hufnagel. A ``side benefit' is a generalization of Rado's theorem on the existence of a linearly independent transversal.     

A fractional‐order Jacobi Tau method for a class of time‐fractional PDEs with variable coefficients

This paper presents a shifted fractional‐order Jacobi orthogonal function (SFJF) based on the definition of the classical Jacobi polynomial. A new fractional integral operational matrix of the SFJF is presented and derived. We propose the spectral Tau method, in conjunction with the operational matrices of the Riemann–Liouville fractional integral for SFJF and derivative for Jacobi polynomial, to solve a class of time‐fractional partial differential equations with variable coefficients. In this algorithm, the approximate solution is expanded by means of both SFJFs for temporal discretization and Jacobi polynomials for spatial discretization. The proposed tau scheme, both in temporal and spatial discretizations, successfully reduced such problem into a system of algebraic equations, which is far easier to be solved. Numerical results are provided to demonstrate the high accuracy and superiority of the proposed algorithm over existing ones. Copyright © 2015 John Wiley & Sons, Ltd.     

Complexity of solving parametric polynomial systems

In this paper, we present three algorithms: the first one solves zero-dimensional parametric homogeneous polynomial systems within single exponential time in the number n of unknowns; it decomposes the parameter space into a finite number of constructible sets and computes the finite number of solutions by parametric rational representations uniformly in each constructible set. The second algorithm factirizes absolutely multivariate parametic polynomials within single exponential time in n and in the upper bound d on the degree of the factorized polynomials. The third algorithm decomposes algebraic varieties defined by parametric polynomial systems of positive dimension into absolutely irreducible components uniformly in the values of the parameters. The complexity bound for this algorithm is double exponential in n. On the other hand, the lower bound on the complexity of the problem of resolution of parametric polynomial systems is double exponential in n. Bibliography: 72 titles.     

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.     

Semiscalar equivalence and the smith normal form of polynomial matrices

We give conditions under which a set of polynomial matrices over a finite field can be simultaneously reduced by means of semiscalar equivalent transformations to a special triangular form with invariant factors on the principal diagonals. We investigate multiplicative properties of the Smith normal form of polynomial matrices and in particular we identify a class of polynomial matrices for which the Smith normal form of the product matrix is equal to the product of the Smith normal forms of the factor matrices.Translated from Matematicheskie Metody i Fiziko-mekhanicheskie Polya, No. 26, pp. 13–16, 1987.     

Spectral factorization of non-symmetric polynomial matrices

The topic of the paper is spectral factorization of rectangular and possibly non-full-rank polynomial matrices. To each polynomial matrix we associate a matrix pencil by direct assignment of the coefficients. The associated matrix pencil has its finite generalized eigenvalues equal to the zeros of the polynomial matrix. The matrix dimensions of the pencil we obtain by solving an integer linear programming (ILP) minimization problem. Then by extracting a deflating subspace of the pencil we come to the required spectral factorization. We apply the algorithm to most general-case of inner–outer factorization, regardless continuous or discrete time case, and to finding the greatest common divisor of polynomial matrices.     

On the purely algebraic data‐sparse approximation of the inverse and the triangular factors of sparse matrices

The approximation of the inverse and the factors of the LU decomposition of general sparse matrices by hierarchical matrices is investigated. In this first approach, we present and motivate a new matrix partitioning algorithm which is based on the matrix graph by proving logarithmic‐linear complexity of the approximant in the case of bounded condition numbers. In contrast to the usual partitioning, the new algorithm allows to treat general grids if the origin of the sparse matrix is the finite element discretization of differential operators. Numerical examples indicate that the restriction to bounded condition numbers has only technical reasons. Copyright © 2010 John Wiley & Sons, Ltd.     

Computing the Invariant Polynomials of a Polynomial Matrix. I

An algorithm for computing the invariant polynomials and the canonical triangular (trapezoidal) matrix for a polynomial matrix of full column rank is suggested. The algorithm is based on the Δ W-1 rank-factorization method for solving algebraic problems for polynomial matrices, previously suggested by the author. Bibliography: 3 titles.     

求首尾和r-循环矩阵的极小多项式的算法

研究了域上首尾和r-循环矩阵，利用多项式环的理想的Groebner基的算法给出了任意域上首尾和r-循环矩阵的极小多项式和公共极小多项式的一种算法.同时给出了这类矩阵逆矩阵的一种求法。     

On the complexity of computing the handicap of a sufficient matrix

The class of sufficient matrices is important in the study of the linear complementarity problem (LCP)—some interior point methods (IPM’s) for LCP’s with sufficient data matrices have complexity polynomial in the bit size of the matrix and its handicap.In this paper we show that the handicap of a sufficient matrix may be exponential in its bit size, implying that the known complexity bounds of interior point methods are not polynomial in the input size of the LCP problem. We also introduce a semidefinite programming based heuristic, that provides a finite upper bond on the handicap, for the sub-class of P{\mathcal{P}} -matrices (where all principal minors are positive).     

An implicit QR algorithm for symmetric semiseparable matrices

The QR algorithm is one of the classical methods to compute the eigendecomposition of a matrix. If it is applied on a dense n × n matrix, this algorithm requires O(n³) operations per iteration step. To reduce this complexity for a symmetric matrix to O(n), the original matrix is first reduced to tridiagonal form using orthogonal similarity transformations. In the report (Report TW360, May 2003) a reduction from a symmetric matrix into a similar semiseparable one is described. In this paper a QR algorithm to compute the eigenvalues of semiseparable matrices is designed where each iteration step requires O(n) operations. Hence, combined with the reduction to semiseparable form, the eigenvalues of symmetric matrices can be computed via intermediate semiseparable matrices, instead of tridiagonal ones. The eigenvectors of the intermediate semiseparable matrix will be computed by applying inverse iteration to this matrix. This will be achieved by using an O(n) system solver, for semiseparable matrices. A combination of the previous steps leads to an algorithm for computing the eigenvalue decompositions of semiseparable matrices. Combined with the reduction of a symmetric matrix towards semiseparable form, this algorithm can also be used to calculate the eigenvalue decomposition of symmetric matrices. The presented algorithm has the same order of complexity as the tridiagonal approach, but has larger lower order terms. Numerical experiments illustrate the complexity and the numerical accuracy of the proposed method. Copyright © 2005 John Wiley & Sons, Ltd.     

On the Toeplitz embedding of an arbitrary matrix

It has been shown by Delosme and Morf that an arbitrary block matrix can be embedded into a block Toeplitz matrix; the dimension of this embedding depends on the complexity of the matrix structure compared to the block Toeplitz structure. Due to the special form of the embedding matrix, the algebra of matrix polynomials relative to block Toeplitz matrices can be interpreted directly in terms of the original matrix and therefore can be extended to arbitrary matrices. In fact, these polynomials turn out to provide an appropriate framework for the recently proposed generalized Levinson algorithm solving the general matrix inversion problem.     

The shifted number system for fast linear algebra on integer matrices

The shifted number system is presented: a method for detecting and avoiding error producing carries during approximate computations with truncated expansions of rational numbers. Using the shifted number system the high-order lifting and integrality certification techniques of Storjohann 2003 for polynomial matrices are extended to the integer case. Las Vegas reductions to integer matrix multiplication are given for some problems involving integer matrices: the determinant and a solution of a linear system can be computed with about the same number of bit operations as required to multiply together two matrices having the same dimension and size of entries as the input matrix. The algorithms are space efficient.     

The complexity of minimizing the number of shape matrices subject to minimal beam-on time in multileaf collimator field decomposition with bounded fluence

The use of multileaf collimators (MLCs) is a modern way to realize intensity modulated fields in radiotherapy. An important step in the treatment planning is the shape matrix decomposition: the desired fluence distribution, given by an integer matrix, has to be decomposed into a small number shape matrices, i.e. (0,1)-matrices corresponding to the field shapes that can be delivered by the MLC used. The two main objectives are to minimize the total irradiation time, and the number of shape matrices. Assuming that the entries of the fluence matrix are bounded by a constant, we prove that a shape matrix decomposition with minimal number of shape matrices under the condition that the total irradiation time is minimal, can be determined in time polynomial in the matrix dimensions. The results of our algorithm are compared with Engel’s [K. Engel, A new algorithm for optimal multileaf collimator field segmentation, Discrete Appl. Math. 152 (1-3) (2005) 35-51.] heuristic for the reduction of the number of shape matrices.     

求鳞状循环因子矩阵的极小多项式的算法

提出了任意域上鳞状循环因子矩阵 ,利用多项式环的理想的Go bner基的算法给出了任意域上鳞状循环因子矩阵的极小多项式和公共极小多项式的一种算法 .同时给出了这类矩阵逆矩阵的一种求法 .在有理数域或模素数剩余类域上 ,这一算法可由代数系统软件Co CoA4 .0实现 .数值例子说明了算法的有效性     

Using Gauss-Jordan elimination to compute the index,generalized nullspaces,and Drazin inverse

We develop and analyze a new algorithm that computes bases for the null spaces of all powers of a given matrix, as well as its index. The algorithm uses row operations and “shuffling” steps in which rows of pairs of matrices are interchanged. In particular, the new algorithm may be viewed as an extension of the classic Gauss-Jordan elimination method for inverting a nonsingular matrix. It is also shown that the Drazin inverse has a simple representation in terms of the output of the algorithm and the original matrix.     

A polynomial algorithm for minimum quadratic cost flow problems

Network flow problems with quadratic separable costs appear in a number of important applications such as; approximating input-output matrices in economy; projecting and forecasting traffic matrices in telecommunication networks; solving nondifferentiable cost flow problems by subgradient algorithms. It is shown that the scaling technique introduced by Edmonds and Karp (1972) in the case of linear cost flows for deriving a polynomial complexity bound for the out-of-kilter method, may be extended to quadratic cost flows and leads to a polynomial algorithm for this class of problems. The method may be applied to the solution of singly constrained quadratic programs and thus provides an alternative approach to the polynomial algorithm suggested by Helgason, Kennington and Lall (1980).     

Minimal polynomial systems for parametric matrices

In this article, we study the minimal polynomials of parametric matrices. Using the concept of (comprehensive) Gröbner systems for parametric ideals, we introduce the notion of a minimal polynomial system for a parametric matrix, i.e. we decompose the space of parameters into a finite set of cells and for each cell we give the corresponding minimal polynomial of the matrix. We also present an algorithm for computing a minimal polynomial system for a given parametric matrix.     

An algorithm for numerical determination of the structure of a general matrix

An algorithm, proposed by V. N. Kublanovskaya, for solving the complete eigenvalue problem of a degenerate (that is defective and/or derogatory) matrix, is studied theoretically and numerically. It uses successiveQR-factorizations to determine annihilated subspaces.An adaptation of the algorithm is developed which, applied to a matrix with a very ill-conditioned eigenproblem, computes a degenerate matrix. The difference between these matrices is small, measured in the spectral norm. The degenerate matrix will appear in a standard form, whose eigenvalues and principal vectors can be computed in a numerically stable manner.Numerical examples are given.