The condition number of real Vandermonde, Krylov and positive definite Hankel matrices

Summary. We show that the Euclidean condition number of any positive definite Hankel matrix of order may be bounded from below by with , and that this bound may be improved at most by a factor . Similar estimates are given for the class of real Vandermonde matrices, the class of row-scaled real Vandermonde matrices, and the class of Krylov matrices with Hermitian argument. Improved bounds are derived for the case where the abscissae or eigenvalues are included in a given real interval. Our findings confirm that all such matrices – including for instance the famous Hilbert matrix – are ill-conditioned already for “moderate” order. As application, we describe implications of our results for the numerical condition of various tasks in Numerical Analysis such as polynomial and rational i nterpolation at real nodes, determination of real roots of polynomials, computation of coefficients of orthogonal polynomials, or the iterative solution of linear systems of equations. Received December 1, 1997 / Revised version received February 25, 1999 / Published online 16 March 2000     

Hankel matrices for system identification

The coefficients of a linear system, even if it is a part of a block-oriented nonlinear system, normally satisfy some linear algebraic equations via Hankel matrices composed of impulse responses or correlation functions. In order to determine or to estimate the coefficients of a linear system it is important to require the associated Hankel matrix be of row-full-rank. The paper first discusses the equivalent conditions for identifiability of the system. Then, it is shown that the row-full-rank of the Hankel matrix composed of impulse responses is equivalent to identifiability of the system. Finally, for the row-full-rank of the Hankel matrix composed of correlation functions, the necessary and sufficient conditions are presented, which appear slightly stronger than the identifiability condition. In comparison with existing results, here the minimum phase condition is no longer required for the case where the dimension of the system input and output is the same, though the paper does not make such a dimensional restriction.     

On the fast Lanczos method for computation of eigenvalues of Hankel matrices using multiprecision arithmetics

The use of the fast Fourier transform (FFT) accelerates Lanczos tridiagonalisation method for Hankel and Toeplitz matrices by reducing the complexity of matrix–vector multiplication. In multiprecision arithmetics, the FFT has overheads that make it less competitive compared with alternative methods when the accuracy is over 10000 decimal places. We studied two alternative Hankel matrix–vector multiplication methods based on multiprecision number decomposition and recursive Karatsuba‐like multiplication, respectively. The first method was uncompetitive because of huge precision losses, while the second turned out to be five to 14 times faster than FFT in the ranges of matrix sizes up to n = 8192 and working precision of b = 32768 bits we were interested in. We successfully applied our approach to eigenvalues calculations to studies of spectra of matrices that arise in research on Riemann zeta function. The recursive matrix–vector multiplication significantly outperformed both the FFT and the traditional multiplication in these studies. Copyright © 2016 John Wiley & Sons, Ltd.     

Solving Hankel matrix approximation problem using semidefinite programming

Positive semidefinite Hankel matrices arise in many important applications. Some of their properties may be lost due to rounding or truncation errors incurred during evaluation. The problem is to find the nearest matrix to a given matrix to retrieve these properties. The problem is converted into a semidefinite programming problem as well as a problem comprising a semidefined program and second-order cone problem. The duality and optimality conditions are obtained and the primal–dual algorithm is outlined. Explicit expressions for a diagonal preconditioned and crossover criteria have been presented. Computational results are presented. A possibility for further improvement is indicated.     

矩阵正定性的进一步推广

矩阵的正定性在很多领域中都有广泛的应用,其定义得到了一系列的推广.进一步推广了矩阵的正定性,给出了更广义的正定矩阵的定义,并得到了它的若干性质.     

Bell数的Hankel矩阵的一般表示

§ 1.　Introduction　　TheBellnumberBn countsthenumberofpartitionsofann set,withthefirstvaluesB0 =1 ,B1 =1 ,B2 =2 ,B3 =5 ,B4=1 5 ,B5=5 2 .ItsexponentialgeneratingfunctionisB(x) =∑n≥ 0Bnxnn ! =eex-1 ,(see [2 ]) .LetthegeneralhankelmatrixofBellnumberbe Bn(t) =Bt Bt+ 1 …Bn +tBt+ 1 Bt+ 2 …Bn+t+ 1…………Bn+t Bn+t+ 1 …B2n +t,(see [3]) .Recently ,AIGNER [1 ]obtaineddet Bn( 0 ) =det Bn( 1 ) =n ! ! ,wheren ! ! =∏nk =0 k ! .ThepurposeofthispaperistoprovideageneralrepersentationoftheH…     

On sensitivity of central solutions in semidefinite programming

In this paper we study the properties of the analytic central path of a semidefinite programming problem under perturbation of the right hand side of the constraints, including the limiting behavior when the central optimal solution, namely the analytic center of the optimal set, is approached. Our analysis assumes the primal-dual Slater condition and the strict complementarity condition. Our findings are as follows. First, on the negative side, if we view the central optimal solution as a function of the right hand side of the constraints, then this function is not continuous in general, whereas in the linear programming case this function is known to be Lipschitz continuous. On the positive side, compared with the previous conclusion we obtain a (seemingly) paradoxical result: on the central path any directional derivative with respect to the right hand side of the constraints is bounded, and even converges as the central optimal solution is approached. This phenomenon is possible due to the lack of a uniform bound on the derivatives with respect to the right hand side parameters. All these results are based on the strict complementarity assumption. Concerning this last property we give an example. In that example the set of right hand side parameters for which the strict complementarity condition holds is neither open nor closed. This is remarkable since a similar set for which the primal-dual Slater condition holds is always open. Received: April 2, 1998 / Accepted: January 16, 2001?Published online March 22, 2001     

A small note on the scaling of symmetric positive definite semiseparable matrices

In this paper we will adapt a known method for diagonal scaling of symmetric positive definite tridiagonal matrices towards the semiseparable case. Based on the fact that a symmetric, positive definite tridiagonal matrix satisfies property A, one can easily construct a diagonal matrix such that has the lowest condition number over all matrices , for any choice of diagonal matrix . Knowing that semiseparable matrices are the inverses of tridiagonal matrices, one can derive similar properties for semiseparable matrices. Here, we will construct the optimal diagonal scaling of a semiseparable matrix, based on a new inversion formula for semiseparable matrices. Some numerical experiments are performed. In a first experiment we compare the condition numbers of the semiseparable matrices before and after the scaling. In a second numerical experiment we compare the scalability of matrices coming from the reduction to semiseparable form and matrices coming from the reduction to tridiagonal form. *The research was partially supported by the Research Council K.U. Leuven, project OT/00/16 (SLAP: Structured Linear Algebra Package), by the Fund for Scientific Research–Flanders (Belgium), projects G.0078.01 (SMA: Structured Matrices and their Applications), G.0176.02 (ANCILA: Asymptotic aNalysis of the Convergence behavior of Iterative methods in numerical Linear Algebra), G.0184.02 (CORFU: Constructive study of Orthogonal Functions) and G.0455.0 (RHPH: Riemann–Hilbert problems, random matrices and Padé–Hermite approximation), and by the Belgian Programme on Interuniversity Poles of Attraction, initiated by the Belgian State, Prime Minister's Office for Science, Technology and Culture, project IUAP V-22 (Dynamical Systems and Control: Computation, Identification & Modelling). The scientific responsibility rests with the authors. The second author participates in the SCCM program, Gates 2B, Stanford University, CA, USA and is also partially supported by the NSF. The first author visited the second one with a grant by the Fund for Scientific Research–Flanders (Belgium).     

Relatively prime polynomials and nonsingular Hankel matrices over finite fields

The probability for two monic polynomials of a positive degree n with coefficients in the finite field Fq to be relatively prime turns out to be identical with the probability for an n×n Hankel matrix over Fq to be nonsingular. Motivated by this, we give an explicit map from pairs of coprime polynomials to nonsingular Hankel matrices that explains this connection. A basic tool used here is the classical notion of Bezoutian of two polynomials. Moreover, we give simpler and direct proofs of the general formulae for the number of m-tuples of relatively prime polynomials over Fq of given degrees and for the number of n×n Hankel matrices over Fq of a given rank.     

Optimization over structured subsets of positive semidefinite matrices via column generation

We develop algorithms to construct inner approximations of the cone of positive semidefinite matrices via linear programming and second order cone programming. Starting with an initial linear algebraic approximation suggested recently by Ahmadi and Majumdar, we describe an iterative process through which our approximation is improved at every step. This is done using ideas from column generation in large-scale linear programming. We then apply these techniques to approximate the sum of squares cone in a nonconvex polynomial optimization setting, and the copositive cone for a discrete optimization problem.     

广义正定矩阵的行列式不等式

研究了广义正定矩阵的行列式理论，给出了一些新的结果，推广了Ky Fan、Openheim、Minkowski、Ostrowski-Taussky等著名行列式不等式，削弱了华罗庚不等式的条件．     

Strengthened semidefinite programming bounds for codes

We give a hierarchy of semidefinite upper bounds for the maximum size A(n,d) of a binary code of word length n and minimum distance at least d. At any fixed stage in the hierarchy, the bound can be computed (to an arbitrary precision) in time polynomial in n; this is based on a result of de Klerk et al. (Math Program, 2006) about the regular ∗-representation for matrix ∗-algebras. The Delsarte bound for A(n,d) is the first bound in the hierarchy, and the new bound of Schrijver (IEEE Trans. Inform. Theory 51:2859–2866, 2005) is located between the first and second bounds in the hierarchy. While computing the second bound involves a semidefinite program with O(n ⁷) variables and thus seems out of reach for interesting values of n, Schrijver’s bound can be computed via a semidefinite program of size O(n ³), a result which uses the explicit block-diagonalization of the Terwilliger algebra. We propose two strengthenings of Schrijver’s bound with the same computational complexity. Supported by the Netherlands Organisation for Scientific Research grant NWO 639.032.203.     

New upper bounds for kissing numbers from semidefinite programming

Recently A. Schrijver derived new upper bounds for binary codes using semidefinite programming. In this paper we adapt this approach to codes on the unit sphere and we compute new upper bounds for the kissing number in several dimensions. In particular our computations give the (known) values for the cases .

     

Numerical experiments on the condition number of the interpolation matrices for radial basis functions

Through numerical experiments, we examine the condition numbers of the interpolation matrix for many species of radial basis functions (RBFs), mostly on uniform grids. For most RBF species that give infinite order accuracy when interpolating smooth f(x)—Gaussians, sech's and Inverse Quadratics—the condition number κ(α,N) rapidly asymptotes to a limit κasymp(α) that is independent of N and depends only on α, the inverse width relative to the grid spacing. Multiquadrics are an exception in that the condition number for fixed α grows as N². For all four, there is growth proportional to an exponential of 1/α (1/α² for Gaussians). For splines and thin-plate splines, which contain no width parameter, the condition numbers grows asymptotically as a power of N—a large power as the order of the RBF increases. Random grids typically increase the condition number (for fixed RBF width) by orders of magnitude. The quasi-random, low discrepancy Halton grid may, however, have a lower condition number than a uniform grid of the same size.     

正定二次规划的一个对偶算法

给出了一个正定二次规划的对偶算法．算法把原问题分解为一系列子问题,在保持原问题的Wolfe对偶可行的前提下,通过迭代计算,由这一系列子问题的最优解向原问题的最优解逼近．同时给出了算法的有限收敛性．     

Sufficient conditions for the convergent splittings of non-Hermitian positive definite matrices

We present sufficient conditions for the convergent splitting of a non-Hermitian positive definite matrix. These results are applicable to identify the convergence of iterative methods for solving large sparse system of linear equations.     

复半正定矩阵的奇异值不等式

用Mn表示所有复矩阵组成的集合.对于A∈Mn,σ(A)=(σ1(A),…,σn(A)),其中σ1(A)≥…≥σn(A)是矩阵A的奇异值.本文给出证明:对于任意实数α,A,B∈Mn为半正定矩阵,优化不等式σ(A-|α|B) wlogσ(A+αB)成立,改进和推广了文[5]的结果.     

Lower bounds for the condition number of a real confluent Vandermonde matrix

Lower bounds on the condition number of a real confluent Vandermonde matrix are established in terms of the dimension , or and the largest absolute value among all nodes that define the confluent Vandermonde matrix and the interval that contains the nodes. In particular, it is proved that for any modest (the largest multiplicity of distinct nodes), behaves no smaller than , or than if all nodes are nonnegative. It is not clear whether those bounds are asymptotically sharp for modest .