A fast bjorck-pereyra-type algorithm for solving hessenberg-quasiseparable-vandermonde systems
Abstract
A fast $\mathcal{O}(n^2)$ algorithm is derived for solving linear systems where the coefficient matrix is a polynomial-Vandermonde matrix $V_R(x)=\left[r_{j-1}(x_i)\right]$ with polynomials $\{r_k(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 $V_R(x)$ involving Chebyshev polynomials of Higham for $V_R(x)$ involving real orthogonal polynomials, and a recent algorithm of the authors for $V_R(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.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Cites
Solution of Vandermonde Systems of Equations
Björck, Å., & Pereyra, V. L. (1970) · Mathematics of Computation · doi:10.2307/2004623 · Cited by 248 · see citing works
On a new class of structured matrices
Eidelman, Y., & Gohberg, I. (1999) · Integral Equations and Operator Theory · doi:10.1007/bf01300581 · Cited by 197 · see citing works
Self-citationThe Accurate and Efficient Solution of a Totally Positive Generalized Vandermonde Linear System
Demmel, J., & Koev, P. (2005) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/s0895479804440335 · Cited by 154 · see citing works
Newton interpolation at Leja points
Reichel, L. (1990) · BIT Numerical Mathematics · doi:10.1007/bf02017352 · Cited by 129 · see citing works
Gragg, W. B. (1993) · Journal of Computational and Applied Mathematics · doi:10.1016/0377-0427(93)90294-l · Cited by 125 · see citing works
A fast and accurate algorithm for solving Bernstein–Vandermonde linear systems
Marco, A., & ́nez, J.-J. M. (2007) · Linear Algebra and its Applications · doi:10.1016/j.laa.2006.11.020 · Cited by 99 · see citing works
Error analysis of the Bj�rck-Pereyra algorithms for solving Vandermonde systems
Higham, N. J. (1987) · Numerische Mathematik · doi:10.1007/bf01408579 · Cited by 89 · see citing works
Effectively Well-Conditioned Linear Systems
Chan, T. F.-C., & Foulser, D. E. (1988) · SIAM Journal on Scientific and Statistical Computing · doi:10.1137/0909067 · Cited by 82 · see citing works
Stability Analysis of Algorithms for Solving Confluent Vandermonde-Like Systems
Higham, N. J. (1990) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/0611002 · Cited by 77 · see citing works
A modification of the Dewilde–van der Veen method for inversion of finite structured matrices
Eidelman, Y., & Gohberg, I. (2002) · Linear Algebra and its Applications · doi:10.1016/s0024-3795(01)00363-9 · Cited by 71 · see citing works
Self-citationThe block decomposition of a vandermonde matrix and its applications
Tang, W.-P., & Golub, G. H. (1981) · BIT Numerical Mathematics · doi:10.1007/bf01932847 · Cited by 58 · see citing works
Reichel, L., & Opfer, G. (1991) · Mathematics of Computation · doi:10.1090/s0025-5718-1991-1094957-9 · Cited by 55 · see citing works
Fast inversion of Chebyshev--Vandermonde matrices
Gohberg, I., & Olshevsky, V. (1994) · Numerische Mathematik · doi:10.1007/s002110050018 · Cited by 47 · see citing works
Self-citationA fast parallel Björck–Pereyra-type algorithm for solving Cauchy linear equations
Boros, T., Kailath, T., & Olshevsky, V. (1999) · Linear Algebra and its Applications · doi:10.1016/s0024-3795(99)00115-9 · Cited by 39 · see citing works
Self-citationPolynomials with respect to a general basis. I. Theory
Maroulas, J., & Barnett, S. M. (1979) · Journal of Mathematical Analysis and Applications · doi:10.1016/0022-247x(79)90282-8 · Cited by 36 · see citing works
Linear complexity inversion algorithms for a class of structured matrices
Eidelman, Y., & Gohberg, I. (1999) · Integral Equations and Operator Theory · doi:10.1007/bf01225526 · Cited by 27 · see citing works
Self-citationEigenstructure of order-one-quasiseparable matrices. Three-term and two-term recurrence relations
Eidelman, Y., Gohberg, I., & Olshevsky, V. (2005) · Linear Algebra and its Applications · doi:10.1016/j.laa.2005.02.039 · Cited by 22 · see citing works
Self-citationOlshevsky, V. (1998) · Linear Algebra and its Applications · doi:10.1016/s0024-3795(98)10099-x · Cited by 18 · see citing works
Self-citationBella, T., Eidelman, Y., Gohberg, I., Koltracht, I., & Olshevsky, V. (2007) · Linear Algebra and its Applications · doi:10.1016/j.laa.2006.08.032 · Cited by 17 · see citing works
Self-citationDisplacement-structure approach to polynomial Vandermonde and related matrices
Kailath, T. (1997) · Linear Algebra and its Applications · doi:10.1016/s0024-3795(97)80061-4 · Cited by 4 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
A Fast DVM Algorithm for Wideband Time-Delay Multi-Beam Beamformers
Perera, S. M., Lingsch, L., Madanayake, A., Mandal, S., & Mastronardi, N. (2022) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2022.3231182 · Cited by 11 · see citing works
Thiran Filters for Wideband DSP-Based Multi-Beam True Time Delay RF Sensing Applications
Perera, S. M., Rathnasekara, G., & Madanayake, A. (2024) · Sensors · doi:10.3390/s24020576 · Cited by 5 · see citing works
A Fast Algorithm to Solve Delay Vandermonde Systems in Phased-Array Digital Receivers
Perera, S. M., Madanayake, A., Ogle, A., Silverio, D., & Huang, J. Q. (2021) · IEEE Transactions on Aerospace and Electronic Systems · doi:10.1109/taes.2021.3086356 · Cited by 5 · see citing works
- Authors
- Bella, T., Eidelman, Y., Gohberg, I., Koltracht, I., & Olshevsky, V.
- Affiliations
- University of Connecticut (US)
- Venue
- SIAM Journal on Matrix Analysis and Applications
- Published
- 2009-01
- Volume
- 31
- Issue
- 2
- Pages
- 790-815
- ISSN
- 0895-4798 (ISSN-L)
- 1095-7162
- OpenAlex
- W2068374637
- Cited by
- 14
- References
- 20
- Citations by year
- 2024: 1 · 2023: 3 · 2022: 1 · 2021: 1 · 2016: 2 · 2015: 1 · 2013: 1
- FWCI
- 0.98
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- SIAM Journal on Matrix Analysis and Applications (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Matrix Theory and Algorithms
- Physical Sciences › Mathematics › Applied Mathematics › Mathematical functions and polynomials
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Polynomial and algebraic computation
- Keywords
- Vandermonde systems, linear system solvers, Chebyshev polynomials, Szegő polynomials, forward error analysis, O(n^2) algorithm
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
