Search

In this paper, we consider the generalized eigenvalue problem (GEP) for bidiagonalproduct (BP) pairs with sign regularity (SR), which include structured pairs associated with illconditioned matrices, such as Cauchy and Vandermonde matrices, that arise in many applications. A sufficient and necessary condition is provided for an SR-BP pair to be regular. For regular SR-BP pairs having both matrices singular, we establish sharp relative perturbation bounds to show that all the generalized eigenvalues including infinite and zero ones can be accurately determined by their BP representations. By operating on the BP representations, a new method is developed to accurately compute generalized eigenvalues of such a regular SR-BP pair. Our method first transforms the pair into an equivalent pair with a certain sign regularity. Then a technique is proposed to implicitly deflate all the infinite eigenvalues. After deflating infinite eigenvalues, finite eigenvalues are computed by reducing the deflated GEP into a standard eigenvalue problem. An attractive property of our method is that all the generalized eigenvalues are returned to high relative accuracy especially, all the infinite and zero eigenvalues are computed exactly. Error analysis and numerical experiments are performed to confirm the claimed high relative accuracy. [ABSTRACT FROM AUTHOR]

We propose a multi linear algebra framework to solve systems of polynomial equations with simple roots. We translate connections between univariate polynomial root-finding, eigenvalue decompositions, and harmonic retrieval to their higher-order counterparts: a canonical poly adicde-composition (CPD) that exploits shift in variance structures in the null space of the Macaulay matrix reveals the roots of the polynomial system. The new framework allows us to use numerical CPD algorithms for solving systems of polynomial equations. For the same degree of the Macaulay matrix a sin numerical polynomial algebra/polynomial numerical linear algebra, the CPD is interpreted as the joint eigenvalue decomposition of the multiplication tables. In our approach the degree can also belower . Affine roots and roots at infinity can be handled in the same way. With minor modifications,the technique can be used to estimate approximate roots of over constrained systems [ABSTRACT FROM AUTHOR]

Bernstein polynomials, long a staple of approximation theory and computational geometry, have also increasingly become of interest in finite element methods. Many fundamental problems in interpolation and approximation give rise to interesting linear algebra questions. When attempting to find a polynomial approximation of boundary or initial data, one encounters the Bernstein-Vander monde matrix, which is found to be highly ill conditioned. In [L. Allen and R. C.Kirby, SIAM J. Matrix Anal. Appl., 41 (2020), pp. 413-431], we used the relationship between mono-mial Bézout matrices and the inverse of Hankel matrices to obtain a decomposition of the inverse of the Bernstein mass matrix in terms of Hankel, Toeplitz, and diagonal matrices. In this paper, we use properties of the Bernstein-Bézout matrix to factor the inverse of the Bernstein--Vander monde a difference of products of Hankel, Toeplitz, and diagonal matrices. We also use the nonstandard matrix norm defined in [L. Allen and R. C. Kirby,SIAM J. Matrix Anal. Appl., 41 (2020), pp. 413-431] to study the conditioning of the Bernstein--Vander monde matrix, showing that the conditioning in this case is better than in the standard 2 norm. Additionally, we use properties of multivariate Bernstein polynomials to derive a block LU decomposition of the Bernstein--Vander monde matrix corresponding to equispaced nodes on the d-simplex. [ABSTRACT FROM AUTHOR]

We prove sharp lower bounds for the smallest singular value of a partial Fourier matrix with arbitrary "off the grid"" nodes (equivalently, a rectangular Vandermonde matrix with the nodes on the unit circle) in the case when some of the nodes are separated by less than the inverse bandwidth. The bound is polynomial in the reciprocal of the so-called superresolution factor, while the exponent is controlled by the maximal number of nodes which are clustered together. As a corollary, we obtain sharp minimax bounds for the problem of sparse superresolution on a grid under the partial clustering assumptions. [ABSTRACT FROM AUTHOR]

Vandermonde matrices arise frequently in computational mathematics in problems that require polynomial approximation, differentiation, or integration. These matrices are defined by a set of n distinct nodes x1, x2, . . ., xn and a monomial basis. A difficulty with Vandermonde matrices is that they typically are quite ill-conditioned when the nodes are real and n is not very small. The ill-conditioning often can be reduced significantly by using a basis of orthonormal polynomials p0, p1, . . ., pn-1, with deg(pj) = j. This was first observed by Gautschi. The matrices so obtained are commonly referred to as Vandermonde-like and are of the form Vn,n = [pi-1(xj)]n i,j=1 2 Rn×n. Gautschi analyzed optimally conditioned and optimally scaled square Vandermonde and Vandermonde-like matrices with real nodes. We extend Gautschi's analysis to rectangular Vandermonde-like matrices with real nodes, as well as to Vandermonde-like matrices with nodes on the unit circle in the complex plane. Additionally, we investigate existence and uniqueness of optimally conditioned Vandermonde-like matrices. Finally, we discuss properties of rectangular Vandermonde and Vandermonde-like matrices VN,n of order N × n, N 6= n, with Chebyshev nodes or with equidistant nodes on the unit circle in the complex plane, and show that the condition number of these matrices can be bounded independently of the number of nodes. [ABSTRACT FROM AUTHOR]

Estimation of the condition numbers of Vandermonde matrices, motivated by applications to interpolation and quadrature, can be traced back to at least the 1970s. Empirical study has consistently shown that Vandermonde matrices tend to be badly ill-conditioned, with a narrow class of exceptions, such as the matrices of the discrete Fourier transform (hereafter we use the acronym DFT). So far, however, formal support for this empirical observation has been limited to the matrices defined by the real set of knots. We prove that, more generally, any Vandermonde matrix of a large size is badly ill-conditioned unless its knots are more or less equally spaced on or about the circle {x : |x| = 1}. The matrices of the DFT are unitary up to scaling and therefore perfectly conditioned. They are defined by a cyclic sequence of knots, equally spaced on that circle, but we prove that even a slight modification of the knots into the so-called quasi-cyclic sequence on this circle defines badly ill-conditioned Vandermonde matrices. Likewise, we prove that the half-size leading (that is, northwestern) block of a large DFT matrix is badly ill-conditioned. (This result was motivated by an application to preconditioning of an input matrix for Gaussian elimination with no pivoting and for block Gaussian elimination.) Our analysis involves the Ekkart{Young theorem, the Vandermonde-to-Cauchy transformation of matrix structure, our new inversion formula for a Cauchy matrix, and low-rank approximation of its large submatrices. [ABSTRACT FROM AUTHOR]

A fast O(n2) algorithm is derived for solving linear systems where the coefficient matrix is a polynomial-Vandermonde matrix VR(x) = [rj-1(xi)] with polynomials {rk(x)} defined by a Hessenberg matrix with quasiseparable structure. The result generalizes the well-known Björck- Pereyra algorithm for classical Vandermonde systems involving monomials. It also generalizes the algorithms of Reichel-Opfer for VR(x) involving Chebyshev polynomials of Higham for VR(x) involving real orthogonal polynomials, and a recent algorithm of the authors for VR(x) involving Szegö polynomials. The new algorithm applies to a fairly general new class of (H, k)-quasiseparable polynomials (Hessenberg, order k quasiseparable) that includes (along with the above mentioned classes of real orthogonal and Szegö polynomials) several other important classes of polynomials, e.g., defined by banded Hessenberg matrices. Numerical experiments are presented that coincide with previous experiences with Björck-Pereyra-type algorithms giving better forward error than Gaussian elimination, and this accuracy is consistent with the so-called Chan-Foulser conditioning of the system. [ABSTRACT FROM AUTHOR]

Let WN = WN(z1,z2,…,zn) be a rectangular Vandermonde matrix of order n×N, N ≥ n, with distinct nodes zj in the unit disk and zjk-1 as its (j,k) entry. Matrices of this type often arise in frequency estimation and system identification problems. In this paper, the conditioning of WN is analyzed and bounds for the spectral condition numberk2(WN) are derived. The bounds depend on n, N, and the separation of the nodes. By analyzing the behavior of the bounds as functions of N, we conclude that these matrices may become well conditioned, provided the nodes are close to the unit circle but not extremely close to each other and provided the number of columns of WN is large enough. The asymptotic behavior of both the conditioning itself and the bounds is analyzed and the theoretical results arising from this analysis verified by numerical examples. [ABSTRACT FROM AUTHOR]