A Fast Algorithm for the Inversion of Quasiseparable Vandermonde-like Matrices

Sirani M. Perera, Grigory Bonik, Vadim OlshevskyarXiv 2014 · OpenReview

TL;DR

This paper introduces a novel, efficient $\mathcal{O}(n^2)$ algorithm for inverting a class of matrices called "quasiseparable Vandermonde-like matrices." By leveraging the concept of displacement structure and analyzing recurrence relations of associated polynomials, the authors provide a significant speedup over traditional methods for these important matrix structures.

What Problem Does This Paper Address?

The paper addresses the challenge of efficiently inverting Vandermonde-like matrices, which are generalizations of the classical Vandermonde matrix. While standard Gaussian elimination for inverting general matrices takes $\mathcal{O}(n^3)$ operations, structured matrices like Vandermonde matrices often admit faster algorithms. The authors focus on a specific subclass: quasiseparable, semiseparable, and well-free Vandermonde-like matrices. The core problem is to develop an inversion algorithm that maintains the efficiency gained from the matrix's structure, aiming for an $\mathcal{O}(n^2)$ complexity, which is a substantial improvement over the naive $\mathcal{O}(n^3)$ approach. This is crucial for applications where these matrices arise, such as solving systems of linear equations, polynomial interpolation, and Gaussian quadrature.

Methods

The paper's approach is multi-faceted, building upon the theory of displacement structures.

  • Fast Gaussian Elimination: They first present a fast Gaussian elimination algorithm for polynomial Vandermonde-like matrices, which serves as a foundational tool. This algorithm exploits the displacement structure to reduce the computational cost.
  • Displacement Operators: A key technique is the use of displacement operators. The authors define and analyze these operators for quasiseparable, semiseparable, and well-free polynomials. These operators capture the underlying structure of the matrices.
  • Recurrence Relations: The paper extensively uses recurrence relations for various types of polynomials (quasiseparable, semiseparable, well-free, and generalized associated polynomials). These relations are crucial for understanding the structure of the displacement operators and basis transformation matrices.
  • Basis Transformation Matrices: They derive recurrence relations for the columns of basis transformation matrices, which are essential for connecting different polynomial bases and ultimately for the inversion formula.
  • Inversion Formula: The core of the solution relies on a general inversion formula for Vandermonde-like matrices that utilizes displacement structure. By efficiently computing the components of this formula, particularly sums involving displacement operators and basis transformations, they achieve the $\mathcal{O}(n^2)$ complexity.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Unifying Power of Displacement Structure: The paper demonstrates how the concept of displacement structure provides a powerful framework to unify and generalize inversion algorithms for various types of Vandermonde-like matrices.
  • Recurrence Relations as Structural Keys: The recurrence relations of associated polynomials are identified as fundamental for characterizing the structure of displacement operators and basis transformation matrices, which are critical for efficient computation.
  • Bridging Polynomial Bases: The efficient computation of basis transformation matrices is a key enabler for the overall inversion algorithm, allowing the transition between different polynomial representations.
  • Achieving $\mathcal{O}(n^2)$ for Quasiseparable-like Matrices: The paper successfully extends the $\mathcal{O}(n^2)$ inversion complexity from simpler cases to a broader class of quasiseparable, semiseparable, and well-free Vandermonde-like matrices.

Key Results

The primary result is the development of an $\mathcal{O}(n^2)$ algorithm for inverting quasiseparable, semiseparable, and well-free Vandermonde-like matrices. This is achieved by:

  • Presenting a fast Gaussian elimination algorithm for polynomial Vandermonde-like matrices.
  • Deriving recurrence relations for generalized associated polynomials and basis transformation matrices, enabling $\mathcal{O}(n^2)$ computation of their entries.
  • Establishing the structure of displacement operators for these matrix classes.
  • Combining these elements into a unified inversion algorithm with an overall complexity of $\mathcal{O}(an^2)$, where 'a' is the displacement rank (typically small). For the specific cases discussed, this simplifies to $\mathcal{O}(n^2)$.

Limitations and Future Work

  • Displacement Rank 'a': While the algorithm achieves $\mathcal{O}(n^2)$ for the specific matrix classes, the general inversion formula has a complexity of $\mathcal{O}(an^3)$, which is only improved to $\mathcal{O}(an^2)$ when the specific structures are exploited. The paper focuses on cases where 'a' is small, implying that the efficiency is most pronounced for low-rank displacement matrices.
  • Generalization: The paper focuses on quasiseparable, semiseparable, and well-free Vandermonde-like matrices. Further research could explore extending these techniques to other classes of structured matrices or to more general forms of Vandermonde-like matrices.
  • Practical Implementation: While the theoretical complexity is established, the practical performance and numerical stability of the proposed algorithm in real-world applications would be a valuable area for future investigation.

Summary updated

Abstract

The results on Vandermonde-like matrices were introduced as a generalization of polynomial Vandermonde matrices, and the displacement structure of these matrices was used to derive an inversion formula. In this paper we first present a fast Gaussian elimination algorithm for the polynomial Vandermonde-like matrices. Later we use the said algorithm to derive fast inversion algorithms for quasiseparable, semiseparable and well-free Vandermonde-like matrices having $\mathcal{O}(n^2)$ complexity. To do so we identify structures of displacement operators in terms of generators and the recurrence relations(2-term and 3-term) between the columns of the basis transformation matrices for quasiseparable, semiseparable and well-free polynomials. Finally we present an $\mathcal{O}(n^2)$ algorithm to compute the inversion of quasiseparable Vandermonde-like matrices.
BibTeX
@misc{perera2014fast,
  author = {Sirani M. Perera and Grigory Bonik and Vadim Olshevsky},
  title = {{A Fast Algorithm for the Inversion of Quasiseparable Vandermonde-like Matrices}},
  year = {2014},
  eprint = {1401.1874},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1401.1874},
}
Figure