Adaptive polynomial preconditioning for hermitian indefinite linear systems

This paper explores the use of polynomial preconditioned CG methods for hermitian indefinite linear systems,Ax=b. Polynomial preconditioning is attractive for several reasons. First, it is well-suited to vector and/or parallel architectures. It is also easy to employ, requiring only matrix-vector multiplication and vector addition. To obtain an optimum polynomial preconditioner we solve a minimax approximation problem. The preconditioning polynomial,C(), is optimum in that it minimizes a bound on the condition number of the preconditioned matrix,C(A)A. We also characterize the behavior of this minimax polynomial, which makes possible a thorough understanding of the associated CG methods. This characterization is also essential to the development of an adaptive procedure for dynamically determining the optimum polynomial preconditioner. Finally, we demonstrate the effectiveness of polynomial preconditioning in a variety of numerical experiments on a Cray X-MP/48. Our results suggest that high degree (20–50) polynomials are usually best.This research was supported in part by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Dept. of Energy, by Lawrence Livermore National Laboratory under contract W-7405-ENG-48.This research was supported in part by the Dept. of Energy and the National Science Foundation under grant DMS 8704169.This research was supported in part by U.S. Dept. of Energy grant DEFG02-87ER25026 and by National Science Foundation grant DMS 8703226.     

On hybrid iterative methods for nonsymmetric systems of linear equations

Summary. Hybrid methods for the solution of systems of linear equations consist of a first phase where some information about the associated coefficient matrix is acquired, and a second phase in which a polynomial iteration designed with respect to this information is used. Most of the hybrid algorithms proposed recently for the solution of nonsymmetric systems rely on the direct use of eigenvalue estimates constructed by the Arnoldi process in Phase I. We will show the limitations of this approach and propose an alternative, also based on the Arnoldi process, which approximates the field of values of the coefficient matrix and of its inverse in the Krylov subspace. We also report on numerical experiments comparing the resulting new method with other hybrid algorithms. Received May 27, 1993 / Revised version received November 14, 1994     

Generalized Lie derivations on skew elements of prime algebras with involution

We characterize generalized Lie derivations on skew elements of prime algebras A with involution, provided that A does not satisfy polynomial identities of low degree. The analogous result for matrix algebras is also described.     

Canonical Wiener–Hopf and spectral factorization of large-degree matrix polynomials

We present a novel Newton method for canonical Wiener–Hopf and spectral factorization of matrix polynomials. The initial vector results from solving a block Toeplitz-like system, and the Jacobi matrix governing the Newton iteration has nice structural and numerical properties. The local quadratic convergence of the method is proved and was tested numerically. For scalar polynomials of degree 20000, a superfast version of the method implemented on a laptop typically reqired about half a minute to produce an initial vector and then performed the Newton iteration within one second. In the matrix case, the method worked reproachless on a laptop with 8 Gigabyte RAM if the degree of the polynomial times the squared matrix dimension did not exceed 20000. (© 2014 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Matrix orthogonal polynomials whose derivatives are also orthogonal

In this paper we prove some characterizations of the matrix orthogonal polynomials whose derivatives are also orthogonal, which generalize other known ones in the scalar case. In particular, we prove that the corresponding orthogonality matrix functional is characterized by a Pearson-type equation with two matrix polynomials of degree not greater than 2 and 1. The proofs are given for a general sequence of matrix orthogonal polynomials, not necessarily associated with a hermitian functional. We give several examples of non-diagonalizable positive definite weight matrices satisfying a Pearson-type equation, which show that the previous results are non-trivial even in the positive definite case.A detailed analysis is made for the class of matrix functionals which satisfy a Pearson-type equation whose polynomial of degree not greater than 2 is scalar. We characterize the Pearson-type equations of this kind that yield a sequence of matrix orthogonal polynomials, and we prove that these matrix orthogonal polynomials satisfy a second order differential equation even in the non-hermitian case. Finally, we prove and improve a conjecture of Durán and Grünbaum concerning the triviality of this class in the positive definite case, while some examples show the non-triviality for hermitian functionals which are not positive definite.     

一类不可约多项式的邻接矩阵

Dong和Pei在文[Construction for de Bruijn sequences with large stage,Des.Codes Cryptogr,2017,85(2):343-358]中利用F_2[x]的n次不可约多项式构造大级数de Bruijn序列.不可约多项式的邻接矩阵从理论上给出了这种方法能构造de Bruijn序列的数目.我们给出一类特殊不可约多项式的邻接矩阵,从理论上给出了用这类不可约多项式能够构造的de Bruijn序列的数目.     

Exploiting sparsity in linear and nonlinear matrix inequalities via positive semidefinite matrix completion

A basic framework for exploiting sparsity via positive semidefinite matrix completion is presented for an optimization problem with linear and nonlinear matrix inequalities. The sparsity, characterized with a chordal graph structure, can be detected in the variable matrix or in a linear or nonlinear matrix-inequality constraint of the problem. We classify the sparsity in two types, the domain-space sparsity (d-space sparsity) for the symmetric matrix variable in the objective and/or constraint functions of the problem, which is required to be positive semidefinite, and the range-space sparsity (r-space sparsity) for a linear or nonlinear matrix-inequality constraint of the problem. Four conversion methods are proposed in this framework: two for exploiting the d-space sparsity and the other two for exploiting the r-space sparsity. When applied to a polynomial semidefinite program (SDP), these conversion methods enhance the structured sparsity of the problem called the correlative sparsity. As a result, the resulting polynomial SDP can be solved more effectively by applying the sparse SDP relaxation. Preliminary numerical results on the conversion methods indicate their potential for improving the efficiency of solving various problems.     

Instability indices for matrix polynomials

There is a well-established instability index theory for linear and quadratic matrix polynomials for which the coefficient matrices are Hermitian and skew-Hermitian. This theory relates the number of negative directions for the matrix coefficients which are Hermitian to the total number of unstable eigenvalues for the polynomial. Herein we extend the theory to ?-even matrix polynomials of any finite degree. In particular, unlike previously known cases we show that the instability index depends upon the size of the matrices when the degree of the polynomial is greater than two. We also consider Hermitian matrix polynomials, and derive an index which counts the number of eigenvalues with nonpositive imaginary part. The results are refined if we consider the Hermitian matrix polynomial to be a perturbation of a ?-even polynomials; however, this refinement requires additional assumptions on the matrix coefficients.     

Hoffman polynomials of nonnegative irreducible matrices and strongly connected digraphs

For a nonnegative n × n matrix A, we find that there is a polynomial f(x)∈R[x] such that f(A) is a positive matrix of rank one if and only if A is irreducible. Furthermore, we show that the lowest degree such polynomial f(x) with tr f(A) = n is unique. Thus, generalizing the well-known definition of the Hoffman polynomial of a strongly connected regular digraph, for any irreducible nonnegative n × n matrix A, we are led to define its Hoffman polynomial to be the polynomial f(x) of minimum degree satisfying that f(A) is positive and has rank 1 and trace n. The Hoffman polynomial of a strongly connected digraph is defined to be the Hoffman polynomial of its adjacency matrix. We collect in this paper some basic results and open problems related to the concept of Hoffman polynomials.     

A note on the representation of positive polynomials with structured sparsity

We consider real polynomials in finitely many variables. Let the variables consist of finitely many blocks that are allowed to overlap in a certain way. Let the solution set of a finite system of polynomial inequalities be given, where each inequality involves only variables of one block. We investigate polynomials that are positive on such a set and sparse in the sense that each monomial involves only variables of one block. In particular, we derive a short and direct proof for Lasserre’s theorem on the existence of sums of squares certificates respecting the block structure. The motivation for the results can be found in the literature on numerical methods for global optimization of polynomials that exploit sparsity. The first and the third author were supported by the DFG grant “Barrieren”. The second author was supported by “Studienstiftung des deutschen Volkes”.     

Spectral factorization of Laurent polynomials

We analyse the performance of five numerical methods for factoring a Laurent polynomial, which is positive on the unit circle, as the modulus squared of a real algebraic polynomial. It is found that there is a wide disparity between the methods, and all but one of the methods are significantly influenced by the variation in magnitude of the coefficients of the Laurent polynomial, by the closeness of the zeros of this polynomial to the unit circle, and by the spacing of these zeros. This revised version was published online in August 2006 with corrections to the Cover Date.     

Using FFT-based techniques in polynomial and matrix computations: recent advances and applicatons

Computations with univariate polynomials, like the evaluation of product, quotient, remainder, greatest common divisor, etc, are closely related to linear algebra computations performed with structured matrices having the Toeplitz-like or the Hankel-like structures.

The discrete Fourier transform, and the FFT algorithms for its computation, constitute a powerful tool for the design and analysis of fast algorithms for solving problems involving polynomials and structured matrices.

We recall the main correlations between polynomial and matrix computations and present two recent results in this field: in particular, we show how Fourier methods can speed up the solution of a wide class of problems arising in queueing theory where certain Markov chains, defined by infinite block Toeplitz matrices in generalized Hessenberg form, must be solved. Moreover, we present a new method for the numerical factorization of polynomials based on a matrix generalization of Koenig's theorem. This method, that relies on the evaluation/interpolation technique at the Fourier points, reduces the problem of polynomial factorization to the computation of the LU decomposition of a banded Toeplitz matrix with its rows and columns suitably permuted. Numerical experiments that show the effectiveness of our algorithms are presented     

Extrema of a Real Polynomial

In this paper, we investigate critical point and extrema structure of a multivariate real polynomial. We classify critical surfaces of a real polynomial f into three classes: repeated, intersected and primal critical surfaces. These different critical surfaces are defined by some essential factors of f, where an essential factor of f means a polynomial factor of f–c ₀, for some constant c ₀. We show that the degree sum of repeated critical surfaces is at most d–1, where d is the degree of f. When a real polynomial f has only two variables, we give the minimum upper bound for the number of other isolated critical points even when there are nondegenerate critical curves, and the minimum upper bound of isolated local extrema even when there are saddle curves. We show that a normal polynomial has no odd degree essential factors, and all of its even degree essential factors are normal polynomials, up to a sign change. We show that if a normal quartic polynomial f has a normal quadratic essential factor, a global minimum of f can be either easily found, or located within the interior(s) of one or two ellipsoids. We also show that a normal quartic polynomial can have at most one local maximum.     

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).     

Strong convergence rates for backward Euler on a class of nonlinear jump-diffusion problems

We generalise the current theory of optimal strong convergence rates for implicit Euler-based methods by allowing for Poisson-driven jumps in a stochastic differential equation (SDE). More precisely, we show that under one-sided Lipschitz and polynomial growth conditions on the drift coefficient and global Lipschitz conditions on the diffusion and jump coefficients, three variants of backward Euler converge with strong order of one half. The analysis exploits a relation between the backward and explicit Euler methods.     

矩阵特征多项式的图论计算公式

给出了赋权有向图邻接矩阵特征多项式的图论计算公式,从而得到了一般矩阵特征多项式的图论计算方法,并且研究了赋权有向图邻接矩阵特征多项式和谱半径的一些性质．     

Sweeping algebraic curves for singular solutions

Many problems give rise to polynomial systems. These systems often have several parameters and we are interested to study how the solutions vary when we change the values for the parameters. Using predictor-corrector methods we track the solution paths. A point along a solution path is critical when the Jacobian matrix is rank deficient. The simplest case of quadratic turning points is well understood, but these methods no longer work for general types of singularities. In order not to miss any singular solutions along a path we propose to monitor the determinant of the Jacobian matrix. We examine the operation range of deflation and relate the effectiveness of deflation to the winding number. Computational experiments on systems coming from different application fields are presented.     

幂零--中心化方法

An nxn complex sign pattern(ray pattern) S is said to be spectrally arbitrary if for every monic nth degree polynomial f(λ) with coefficients from C,there is a complex matrix in the complex sign pattern class(ray pattern class) of S such that its characteristic polynomial is f(λ).We derive the Nilpotent-Centralizer methods for spectrally arbitrary complex sign patterns and ray patterns,respectively.We find that the Nilpotent-Centralizer methods for three kinds of patterns(sign pattern,complex sign pattern,ray pattern) are the same in form.     

Polynomial Reproduction in Subdivision

We study conditions on the matrix mask of a vector subdivision scheme ensuring that certain polynomial input vectors yield polynomial output again. The conditions are in terms of a recurrence formula for the vectors which determine the structure of polynomial input with this property. From this recurrence, we obtain an algorithm to determine polynomial input of maximal degree. The algorithm can be used in the design of masks to achieve a high order of polynomial reproduction.