PaperlayerView exact revision on arXiv

Source-linked AI summary

How Bad Are Vandermonde Matrices?

Victor Y. Pan

arXiv:1504.02118v3math.NAcs.NA

TL;DR

The paper addresses the limited formal support for empirical reports that Vandermonde matrices with complex knots are often badly conditioned. It combines singular-value arguments with Vandermonde–Cauchy transformations, inversion formulas, and low-rank approximation to prove exponential lower bounds, with poor conditioning also shown for quasi-cyclic knots and half-size DFT blocks.

  • Problem

    Formal exponential condition-number results had been established for real-knot Vandermonde matrices, while poor conditioning for complex-knot matrices was largely an empirical observation.

    Source: §1 · p. 1

  • Method

    The authors combine the Ekkart–Young theorem, Vandermonde–Cauchy transformations, Cauchy and Vandermonde inversion formulas, and low-rank approximation.

    Source: §1 · p. 2, §10 · p. 12

  • Results

    Condition numbers grow exponentially unless knots are roughly equally spaced on or near the unit circle; quasi-cyclic Vandermonde matrices and half-size leading DFT blocks are also badly ill-conditioned.

    Source: §1 · p. 2, §10 · p. 12

  • Takeaways & Limitations

    The results narrow the well-conditioned exceptions to Vandermonde matrices whose knots are roughly equally spaced on or about the unit circle.

    Source: §1 · p. 2, §10 · p. 11

    The low-rank Cauchy-matrix bounds are developed under geometric partition assumptions on the knots, including a division between knots inside and outside a specified disc.

    Source: §7 · p. 9

Abstract

from arXiv · show

The work on the estimation of the condition numbers of Vandermonde matrices, motivated by applications to interpolation and quadrature, can be traced back at least to the 1970s. Empirical study has shown consistently that Vandermonde matrices tend to be badly ill-conditioned, with a narrow class of notable exceptions, such as the matrices of the discrete Fourier transform (hereafter referred to as DFT). So far formal support for this empirical observation, however, 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 $C(0,1)=\{x:\,|x|=1\}$. The matrices of DFT are perfectly conditioned, being 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 block of a large DFT matrix is badly ill-conditioned. (This result was motivated by an application to pre-conditioning of an input matrix for Gaussian elimination with no pivoting.) 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.

1 Introduction

The paper addresses the gap between empirical reports of poor conditioning in complex-knot Vandermonde matrices and formal bounds previously established for real knots. It develops lower bounds and applies them to general knot sets and important special cases.

1 Introduction

  • Formal results extend beyond real knots the evidence that large Vandermonde matrices are badly conditioned unless their knots are roughly equally spaced on or about the unit circle.Earlier exponential-growth results covered real knots, while the broader empirical observation lacked formal support.Source: §1 · pp. 1–2
  • Quasi-cyclic knots and half-size leading blocks of large DFT matrices yield badly ill-conditioned Vandermonde matrices, although the full DFT matrix is unitary up to scaling.The quasi-cyclic case had previously been supported empirically, and the DFT-block result was motivated by preconditioning for Gaussian elimination without pivoting.Source: §1 · p. 2
  • The authors prove exponential condition-number growth for broad classes of Vandermonde matrices using a Vandermonde–Cauchy link and a new formula for Cauchy-matrix inverses.They also derive alternative exponential lower bounds using low-rank approximation of large Cauchy submatrices.Source: §1 · pp. 2–3
  • The analysis first uses the Ekkart–Young theorem for narrower classes, then develops broader bounds through Vandermonde–Cauchy transformations and low-rank approximation.The paper also presents an inverse formula for Cauchy matrices and extends bounds on their inverse norms and condition numbers to Vandermonde matrices.Source: §1 · pp. 2–3

2 Some Definitions and Auxiliary Results

This section supplies singular-value and matrix-norm definitions, along with approximation and interlacing facts used in later conditioning arguments.

2 Some Definitions and Auxiliary Results

  • For a full-rank square matrix, the condition number is the product of its spectral norm and the spectral norm of its inverse.The spectral norm equals the largest singular value; the condition number is also expressed as the ratio of the largest to smallest singular values.Source: §2 · p. 3
  • The Ekkart–Young theorem identifies the jth singular value with the distance to the closest matrix approximation of rank at most j−1.This connects singular values to low-rank approximation.Source: §2 · p. 3
  • Appending k rows or columns to a matrix cannot increase its jth singular value above the corresponding jth-plus-k singular value of the enlarged matrix.The stated relation is σ_j(A) ≥ σ_(j+k)(B).Source: §2 · p. 3

3 The Condition of Vandermonde Matrices: Simple Bounds

The section uses rank-deficient perturbations and the Ekkart–Young theorem to obtain simple exponential lower bounds and initial restrictions on well-conditioned Vandermonde knot sets.

3 The Condition of Vandermonde Matrices: Simple Bounds

  • The condition number grows exponentially in n when a knot lies outside the unit circle, or exponentially in k when at least k knots lie sufficiently inside it.The stated inside-disc condition is 1/|s_i| ≥ ν > 1 for the relevant knots.Source: §3 · pp. 3–4
  • The proof applies Ekkart–Young by perturbing the Vandermonde matrix into a rank-deficient matrix, first by zeroing a column and then by zeroing selected entries in its first rows.The resulting perturbation norms yield the exponential bounds for the outside-knot and multiple-inside-knot cases.Source: §3 · p. 4
  • These bounds imply that large well-conditioned Vandermonde matrices require knots to lie in or near the unit disc and mostly on or near its boundary circle.The section presents these as initial restrictions before deriving stronger ones later.Source: §3 · p. 4

4 The Condition Estimates via the Inversion Formulae

This section links Vandermonde and Cauchy inverses to derive condition-number bounds, then interprets those bounds as restrictions on knot distributions.

4 The Condition Estimates via the Inversion Formulae

  • A Vandermonde–Cauchy transformation and an inverse formula for Cauchy matrices provide representations used to estimate Vandermonde condition numbers.The formula extends to minors because square submatrices of a nonsingular Cauchy matrix retain Cauchy structure.Source: §4 · pp. 4–5
  • Theorem 4.1 gives a lower bound for κ(V_s) using a unit-modulus parameter f chosen so that fω_j differs from every knot s_i.The theorem's setup makes the associated Cauchy matrix well-defined and nonsingular.Source: §4 · p. 5
  • The bounds suggest that a large Vandermonde matrix is badly conditioned when its knots are sparse across a thick neighborhood of a long unit-circle arc.The section interprets this as requiring well-conditioned knot sets to be roughly equally spaced on or about the unit circle.Source: §4 · pp. 5–6
  • The section seeks broader formal restrictions by tracking polynomial-coefficient growth as knots depart from an even distribution and applying low-rank approximation to Cauchy matrices.For a fixed knot set, the polynomial coefficients can be computed in O(n log^2(n)) arithmetic operations and used to bound the condition number.Source: §4 · p. 6

5 The Case of the Quasi-Cyclic Sequence of Knots

The quasi-cyclic sequence preserves the DFT knots initially but adds further knots as the sequence grows. The paper formally shows that these matrices become exponentially ill-conditioned, unlike the perfectly conditioned DFT matrices.

5 The Case of the Quasi-Cyclic Sequence of Knots

  • The DFT is perfectly conditioned when its knots are equally spaced on the unit circle, but even a minor deviation can make the matrix ill-conditioned.The quasi-cyclic sequence is the section’s example of such a deviation.Source: §5 · p. 6
  • The quasi-cyclic construction starts with the DFT knots for n = 2^k and extends them recursively as n increases.The added knots follow a specified sequence of fractions; the text describes adding successive roots in counter-clockwise order.Source: §5 · p. 6
  • For quasi-cyclic knots on the unit circle with n = 3q and q = 2^k−1 (k ≥ 4), log(κ(Vs)) grows at least proportionally to 2^k, so κ(Vs) grows exponentially in n.Source: §5 · p. 6
  • At n = 48, successive refinements raise the lower bound on κ(Vq) to 71,174.The initial bound is 1,773.6; the passage reports intermediate refinements to 15,417, 27,598, and 38,453.Source: §5 · p. 7
  • The section contrasts quasi-cyclic knots with van der Corput sequences, which Gautschi reports yield well-conditioned matrices for all sizes and are evenly distributed on the circle.The van der Corput construction also reorders quasi-cyclic knots in a zigzag manner.Source: §5 · p. 7

6 Numerical Instability of Gaussian Elimination with No Pivoting for the Matrices of Discrete Fourier Transform

The section studies Gaussian elimination with no pivoting (GENP) on DFT matrices, where leading blocks can be ill-conditioned despite the full DFT matrix being unitary. It also identifies knot orderings and block behavior relevant to numerical stability.

6 Numerical Instability of Gaussian Elimination with No Pivoting for the Matrices of Discrete Fourier Transform

  • Pivoting burdens matrix computations, while GENP encounters numerical problems when leading blocks are singular or ill-conditioned.The cited concerns about pivoting include comparisons, bookkeeping, locality, parallelization, and communication overhead.Source: §6 · pp. 7–8
  • For a DFT matrix, all k × k blocks are badly ill-conditioned when k or n − k is large, despite the full matrix being unitary.The half-size leading block has an exponential lower bound on its condition number.Source: §6 · p. 8
  • Gaussian random circulant multipliers support numerically stable GENP on the DFT matrix only with probability near 0, according to the cited results combined with the block-conditioning result.This contrasts with their reported performance in extensive tests on other matrix classes.Source: §6 · p. 8
  • Reordering DFT rows according to a van der Corput sequence makes all leading blocks well-conditioned.The section also states that leading blocks in the van der Corput sequence remain in that sequence, supporting stable GENP.Source: §6 · p. 8

7 Low-Rank Approximation of Cauchy and CV Matrices

This section develops lower bounds for Cauchy and CV matrices using separated knot sets and submatrix estimates. It then connects those bounds to inverse norms and condition numbers of Vandermonde matrices whose knots depart substantially from even spacing on the circle.

7 Low-Rank Approximation of Cauchy and CV Matrices

  • Under mild assumptions, the inverse norm of a CV matrix has an exponential lower bound, extended from a submatrix estimate to the full matrix.The inverse norm is the reciprocal of the smallest singular value.Source: §7 · p. 8
  • The resulting bounds apply to the inverse norm and condition number of a Vandermonde matrix when its knots deviate substantially from an evenly spaced distribution on the unit circle.The section obtains the Vandermonde conclusion by combining the CV bound with an earlier result.Source: §7 · pp. 8–9
  • The section uses the notion of two knot sets being (η, c)-separated and applies a Cauchy-matrix theorem to such sets.Its construction places one set outside a disc centered at c and the target knots within distance r of c.Source: §7 · pp. 8–9
  • The method selects a short arc of equally spaced target knots and partitions the other knots by whether they lie inside or outside a surrounding disc.The outside set is separated from the target knots, enabling application of a Cauchy submatrix bound.Source: §7 · p. 9

8 A Typical Large Vandermonde Matrix is Badly Ill-conditioned

The section turns the bounds into a condition for when large Vandermonde matrices must be badly ill-conditioned. The bounds grow exponentially unless the knot set has a near-even distribution around the unit circle.

8 A Typical Large Vandermonde Matrix is Badly Ill-conditioned

  • The condition number grows exponentially in n unless, for every specified arc and scale, the knot count near its center matches or nearly matches the count in the arc.The stated consequence applies when the arc contains a number of target knots of order n; the text identifies this distribution property with knots being more or less evenly spaced on or about the unit circle.Source: §8 · p. 9

9 Numerical Tests

The numerical tests broadly agree with the estimates, while observed condition numbers can grow faster than their lower bounds. Tests cover several knot configurations, leading blocks of DFT matrices, and GENP residuals.

9 Numerical Tests

  • With one knot moved beyond the roots of unity, the condition number rose quickly as the knot magnitude or matrix size increased.The comparison case with the knot at the corresponding root of unity has condition number 1.Source: §9 · p. 10
  • Table 9.2 compares condition numbers for knots combining roots of unity with k scaled roots and reports a lower estimate for each configuration.The scaled roots use ρ = 3/4 or 1/2.Source: §9 · p. 10, Table 9.2 · p. 10
  • Table 9.1 reports condition numbers for matrices with one absolutely large knot, while Table 9.2 covers matrices with k absolutely small knots.The numerical tests were run in MATLAB R2014a using IEEE standard double precision.Source: Table 9.1 · p. 10, Table 9.2 · p. 10, §9 · p. 10
  • Table 9.3 compares condition numbers for quasi-cyclic knot sequences with lower bounds calculated from equations (5.5) and (5.3).The tested matrices are 3q × 3q, with q = 2k.Source: §9 · p. 10, Table 9.3 · p. 11
  • The lower bounds grew very fast, but the condition numbers grew even faster in the tested cases.The comparisons included bounds from equations (5.5) and (5.3) and from Theorem 6.1.Source: §9 · p. 11
  • The tests also report condition numbers for leading blocks of DFT matrices and relative residual norms from GENP applied to DFT systems.For the residual tests, 100 systems were solved at each listed size from n = 64 to 1024, and residual norms grew quickly with n.Source: §9 · p. 11, Table 9.4 · p. 11, Table 9.5 · p. 11

10 Conclusions

The conclusions give formal support for the tendency of large Vandermonde matrices to be badly conditioned, except when their knots are roughly equally spaced on or near the unit circle. The authors derive bounds through Cauchy-matrix techniques and outline extensions to structured and polynomial Vandermonde matrices.

10 Conclusions

  • The results support exponential growth of the condition number unless knots are more or less equally spaced on or near the unit circle.The conclusion frames this as formal support for the observed ill-conditioning of matrices with complex knots.Source: §10 · pp. 11–12
  • The auxiliary inversion formulae for Cauchy and Vandermonde matrices are noted as potentially useful independently of the main results.Source: §10 · p. 11
  • The proof develops lower bounds through a Vandermonde–Cauchy transformation, Cauchy and Vandermonde inversion formulae, and low-rank approximation.The Ekkart–Young theorem first yields geometric restrictions on knot locations.Source: §10 · p. 12
  • The test results are reported to accord rather well with the estimates, and the authors suggest varying parameters in equation (4.4) to narrow the remaining gap.Source: §10 · p. 12
  • The estimates also apply to transposed Vandermonde matrices and extend to smallest-singular-value bounds for Vandermonde-like and Cauchy-like matrices.The stated structured classes include sums of diagonal-scaled factor-circulant matrices for bounded positive integer d.Source: §10 · p. 12
  • Extending the estimates to polynomial Vandermonde matrices is identified as a research challenge, with knot selection proposed as a key step toward a Cauchy-matrix reduction.The proposed route also requires extending the estimates to a new subclass of Cauchy matrices.Source: §10 · p. 12
Loading 1504.02118v3…