Displacement structure approach to polynomial Vandermonde and related matrices
Open accessAbstract
We introduce a new class of what we call polynomial Vandermonde-like matrices. This class generalizes the polynomial Vandermonde matrices studied earlier by various authors, who derived explicit inversion formulas and fast algorithms for inversion and for solving the associated linear systems. A displacement-structure approach allows us to carry over all these results to the wider class of polynomial Vandermonde-like matrices.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Cites
Golub, G. (2012) · doi:10.56021/9781421407944 · Cited by 34,505 · see citing works
Über Potenzreihen, die im Innern des Einheitskreises beschränkt sind.
Schur, J. (1917) · Journal für die reine und angewandte Mathematik (Crelles Journal) · doi:10.1515/crll.1917.147.205 · Cited by 1,041 · see citing works
The theory of matrices : with applications
Lancaster, P., & Tismenetsky, M. (1985) · Cited by 792 · see citing works
Convolution equations and projection methods for their solution
Gohberg, I., & Feldman, I. (2005) · Translations of mathematical monographs · doi:10.1090/mmono/041 · Cited by 703 · see citing works
Algebraic Methods for Toeplitz-like Matrices and Operators
Heinig, G., & Rost, K. (1984) · Operator theory · doi:10.1007/978-3-0348-6241-7 · Cited by 588 · see citing works
Displacement ranks of matrices and linear equations
Kailath, T., Kung, S., & Morf, M. (1979) · Journal of Mathematical Analysis and Applications · doi:10.1016/0022-247x(79)90124-0 · Cited by 500 · see citing works
Self-citationDisplacement Structure: Theory and Applications
Kailath, T., & Sayed, A. H. (1995) · SIAM Review · doi:10.1137/1037082 · Cited by 436 · see citing works
Self-citationSolution of Vandermonde systems of equations
Björck, Ȧ., & Pereyra, V. (1970) · Mathematics of Computation · doi:10.1090/s0025-5718-1970-0290541-1 · Cited by 398 · see citing works
Fast Gaussian Elimination with Partial Pivoting for Matrices with Displacement Structure
Gohbert, I., Kailath, T., & Olshevsky, V. (1995) · Mathematics of Computation · doi:10.2307/2153371 · Cited by 192 · see citing works
Self-citationDoubling algorithms for Toeplitz and related equations
Morf, M. (2005) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.1980.1171074 · Cited by 159 · see citing works
On certain determinants whose elements are orthogonal polynomials
Karlin, S., & Szegő, G. (1960) · Journal d Analyse Mathématique · doi:10.1007/bf02786848 · Cited by 159 · see citing works
Lower bounds for the condition number of Vandermonde matrices
Gautschi, W., & Inglese, G. (1987) · Numerische Mathematik · doi:10.1007/bf01398878 · Cited by 148 · see citing works
Tyrtyshnikov, E. E. (1994) · Numerische Mathematik · doi:10.1007/s002110050027 · Cited by 142 · see citing works
Fast Gaussian elimination with partial pivoting for matrices with displacement structure
Gohberg, I., Kailath, T., & Olshevsky, V. (1995) · Mathematics of Computation · doi:10.1090/s0025-5718-1995-1312096-x · Cited by 136 · see citing works
Self-citationMixed, Componentwise, and Structured Condition Numbers
Gohberg, I., & Koltracht, I. (1993) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/0614049 · Cited by 130 · see citing works
Complexity of multiplication with vectors for structured matrices
Gohberg, I., & Olshevsky, V. (1994) · Linear Algebra and its Applications · doi:10.1016/0024-3795(94)90189-9 · Cited by 127 · see citing works
Self-citationLandau, H. J. (1987) · Proceedings of symposia in applied mathematics · doi:10.1090/psapm/037 · Cited by 103 · see citing works
Fast algorithms with preprocessing for matrix-vector multiplication problems
Gohberg, I., & Olshevsky, V. (1994) · Journal of Complexity · doi:10.1006/jcom.1994.1021 · Cited by 90 · see citing works
Self-citationInversion of Generalized Cauchy Matrices and other Classes of Structured Matrices
Heinig, G. (1995) · The IMA volumes in mathematics and its applications · doi:10.1007/978-1-4612-4228-4_5 · Cited by 86 · see citing works
Efficient solution of linear systems of equations with recursive structure
Gohberg, I., Kailath, T., & Koltracht, I. (1986) · Linear Algebra and its Applications · doi:10.1016/0024-3795(86)90279-x · Cited by 80 · see citing works
Self-citationFast Solution of Vandermonde-Like Systems Involving Orthogonal Polynomials
Higham, N. J. (1988) · IMA Journal of Numerical Analysis · doi:10.1093/imanum/8.4.473 · Cited by 78 · 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
Associated Polynomials and Uniform Methods for the Solution of Linear Problems
Traub, J. F. (1966) · SIAM Review · doi:10.1137/1008061 · Cited by 76 · see citing works
The condition of Vandermonde-like matrices involving orthogonal polynomials
Gautschi, W. (1983) · Linear Algebra and its Applications · doi:10.1016/0024-3795(83)80020-2 · Cited by 64 · see citing works
A companion matrix analogue for orthogonal polynomials
Barnett, S. M. (1975) · Linear Algebra and its Applications · doi:10.1016/0024-3795(75)90041-5 · Cited by 62 · see citing works
Linear complexity parallel algorithms for linear systems of equations with recursive structure
Gohberg, I., Kailath, T., Koltracht, I., et al. (1987) · Linear Algebra and its Applications · doi:10.1016/0024-3795(87)90113-3 · Cited by 59 · see citing works
Self-citationReichel, L., & Opfer, G. (1991) · Mathematics of Computation · doi:10.1090/s0025-5718-1991-1094957-9 · Cited by 55 · see citing works
The Fast Generalized Parker–Traub Algorithm for Inversion of Vandermonde and Related Matrices
Gohberg, I., & Olshevsky, V. (1997) · Journal of Complexity · doi:10.1006/jcom.1997.0442 · Cited by 51 · see citing works
Self-citationSignal processing applications of some moment problems
Kailath, T. (1987) · Proceedings of symposia in applied mathematics · doi:10.1090/psapm/037/921085 · Cited by 50 · see citing works
Self-citationFast state space algorithms for matrix Nehari and Nehari-Takagi interpolation problems
Gohberg, I., & Olshevsky, V. (1994) · Integral Equations and Operator Theory · doi:10.1007/bf01194749 · Cited by 47 · see citing works
Self-citationFast inversion of Chebyshev--Vandermonde matrices
Gohberg, I., & Olshevsky, V. (1994) · Numerische Mathematik · doi:10.1007/s002110050018 · Cited by 47 · see citing works
Self-citationFast inversion of vandermonde-like matrices involving orthogonal polynomials
Calvetti, D., & Reichel, L. (1993) · BIT Numerical Mathematics · doi:10.1007/bf01990529 · Cited by 46 · see citing works
Fast inversion algorithms of Toeplitz-plus-Hankel matrices
Heinig, G., Jankowski, P., & Rost, K. (1988) · Numerische Mathematik · doi:10.1007/bf01395817 · Cited by 43 · see citing works
Displacement structure approach to Chebyshev-Vandermonde and related matrices
Kailath, T., & Olshevsky, V. (1995) · Integral Equations and Operator Theory · doi:10.1007/bf01195490 · Cited by 38 · see citing works
Self-citationDisplacement structure for Hankel, Vandermonde, and related (derived) matrices
Chun, J., & Kailath, T. (1991) · Linear Algebra and its Applications · doi:10.1016/0024-3795(91)90364-3 · Cited by 36 · 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
Efficient algorithm for Toeplitz plus Hankel matrices
Gohberg, I., & Koltracht, I. (1989) · Integral Equations and Operator Theory · doi:10.1007/bf01199761 · Cited by 35 · see citing works
Inverses of Vandermonde matrices
Parker, F. D. (1964) · The American Mathematical Monthly · doi:10.2307/2313246 · Cited by 35 · see citing works
Inverses of generalized Vandermonde matrices
Verde‐Star, L. (1988) · Journal of Mathematical Analysis and Applications · doi:10.1016/0022-247x(88)90210-7 · Cited by 31 · see citing works
Fast algorithms for generalized displacement structures
Sayed, A. H., & Kailath, T. (1991) · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · Cited by 22 · see citing works
Self-citation(1982) · Birkhäuser Boston eBooks · doi:10.1007/978-1-4612-5785-1 · Cited by 18 · see citing works
Fast triangular factorization of the sum of quasi-Toeplitz and quasi-Hankel matrices
Sayed, A. H., Lev-Ari, H., & Kailath, T. (1993) · Linear Algebra and its Applications · doi:10.1016/0024-3795(93)90510-u · Cited by 13 · see citing works
Self-citation[60–8] On Certain Determinants Whose Elements are Orthogonal Polynomials
Karlin, S., & Szegő, G. (1982) · Birkhäuser Boston eBooks · doi:10.1007/978-1-4612-5785-1_40 · Cited by 13 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
Predictor-feedback prescribed-time stabilization of LTI systems with input delay
Espitia, N., & Perruquetti, W. (2022) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2021.3093527 · Cited by 63 · see citing works
Perera, S. M., Madanayake, A., & Cintra, R. J. (2020) · IEEE Access · doi:10.1109/access.2020.2970342 · Cited by 18 · see citing works
Bella, 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-citationA 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
“…such as the computation of Vandermonde structured matrices by a vector, inverse Vandermonde structured matrices (leading to inversion formulas or inversion algorithms), or the solution of the linear systems associated with Vandermonde structured matrices as the coefficient matrices as in [37–47].”
MethodA 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
- Kailath, T., & Olshevsky, V.
- Affiliations
- Stanford University (US)
- Corresponding author
- Kailath, Thomas
- Olshevsky, Vadim
- Venue
- Linear Algebra and its Applications
- Publisher
- Elsevier BV
- Published
- 1997-08
- Volume
- 261
- Issue
- 1-3
- Pages
- 49-90
- ISSN
- 0024-3795 (ISSN-L)
- OpenAlex
- W2021962862
- Cited by
- 50
- References
- 43
- Citations by year
- 2025: 2 · 2024: 1 · 2023: 1 · 2022: 1 · 2021: 2 · 2020: 1 · 2017: 2 · 2016: 1 · 2014: 2 · 2013: 5 · 2012: 1
- FWCI
- 5.06
- Type
- journal article
- Language
- en
- Open access
- hybrid
- doi.org
- Licence
- Locations
- Linear Algebra and its Applications (publishedVersion, cc-by-nc-nd)
- Linear Algebra and its Applications (publishedVersion)
- Funders
- National Science Foundation
- Army Research Office
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Matrix Theory and Algorithms
- Physical Sciences › Mathematics › Applied Mathematics › Mathematical functions and polynomials
- Physical Sciences › Mathematics › Discrete Mathematics and Combinatorics › Advanced Combinatorial Mathematics
- Keywords
- displacement structure, matrix inversion, fast algorithms, linear systems
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