The Accurate and Efficient Solution of a Totally Positive Generalized Vandermonde Linear System
Abstract
Vandermonde, Cauchy, and Cauchy--Vandermonde totally positive linear systems can be solved extremely accurately in O(n 2 time using Björck--Pereyra-type methods. We prove that Björck--Pereyra-type methods exist not only for the above linear systems but also for any totally positive linear system as long as the initial minors (i.e., contiguous minors that include the first row or column) can be computed accurately. Using this result we design a new O(n 2 Björck--Pereyra-type method for solving generalized Vandermonde systems of equations by using a new algorithm for computing the Schur function. We present explicit formulas for the entries of the bidiagonal decomposition, the LDU decomposition, and the inverse of a totally positive generalized Vandermonde matrix, as well as algorithms for computing these entries to high relative accuracy.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Cites
Gantmacher, F. R. (1984) · UCLA - Biblioteca de Ciencias y Tecnologia Felix Morales Bueno · Cited by 8,520 · see citing works
Symmetric Functions and Hall Polynomials
MacDonald, I. G. (1995) · doi:10.1093/oso/9780198534891.001.0001 · Cited by 7,797 · see citing works
Applied Numerical Linear Algebra
Demmel, J. (1997) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611971446 · Cited by 3,437 · see citing works
Self-citationMathematica. A system for doing mathematics by computer
Wolfram, S. (1988) · Virtual Defense Library (Ministerio de Defensa) · Cited by 2,813 · see citing works
Applied numerical linear algebra
Demmel, J. W. (1998) · Choice Reviews Online · doi:10.5860/choice.35-3919 · Cited by 2,212 · see citing works
Self-citationOscillation Matrices and Kernels and Small Vibrations of Mechanical Systems
Gantmacher, F. R., & Крейн, M. Г. (2002) · American Mathematical Society eBooks · doi:10.1090/chel/345 · Cited by 486 · see citing works
Oettli, W., & Prager, W. (1964) · Numerische Mathematik · doi:10.1007/bf01386090 · Cited by 408 · see citing works
Solution 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
Double Bruhat cells and total positivity
Fomin, S., & Zelevinsky, A. V. (1999) · Journal of the American Mathematical Society · doi:10.1090/s0894-0347-99-00295-7 · Cited by 357 · see citing works
Parametrizations of Canonical Bases and Totally Positive Matrices
Berenstein, A., Fomin, S., & Zelevinsky, A. V. (1996) · Advances in Mathematics · doi:10.1006/aima.1996.0057 · Cited by 314 · see citing works
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
Total positivity and Neville elimination
Gasca, M., & Peña, J. M. (1992) · Linear Algebra and its Applications · doi:10.1016/0024-3795(92)90226-z · Cited by 236 · see citing works
Total Positivity: Tests and Parametrizations
Fomin, S., & Zelevinsky, A. V. (2000) · The Mathematical Intelligencer · doi:10.1007/bf03024444 · Cited by 202 · see citing works
Accurate Eigenvalues and SVDs of Totally Nonnegative Matrices
Koev, P. (2005) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/s0895479803438225 · Cited by 162 · see citing works
Self-citationOn Factorizations of Totally Positive Matrices
Gasca, M., & Peña, J. M. (1996) · Springer eBooks · doi:10.1007/978-94-015-8674-0_7 · Cited by 150 · see citing works
A matricial description of Neville elimination with applications to total positivity
Gasca, M., & Peña, J. M. (1994) · Linear Algebra and its Applications · doi:10.1016/0024-3795(94)90183-x · Cited by 118 · see citing works
Backward error analysis for totally positive linear systems
de Boor, C., & Pinkus, A. M. (1976) · Numerische Mathematik · doi:10.1007/bf01399609 · Cited by 109 · 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
Bidiagonal Factorizations of Totally Nonnegative Matrices
Fallat, S. (2001) · American Mathematical Monthly · doi:10.1080/00029890.2001.11919801 · 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
Explicit factorization of the Vandermonde matrix
Oruç, H., & Phillips, G. M. (2000) · Linear Algebra and its Applications · doi:10.1016/s0024-3795(00)00124-5 · Cited by 57 · see citing works
Factorizations of Cauchy-Vandermonde matrices
Martínez, J., & Peña, J. M. (1998) · Linear Algebra and its Applications · doi:10.1016/s0024-3795(98)10073-3 · Cited by 39 · see citing works
A 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
Bidiagonal Factorizations of Totally Nonnegative Matrices
Fallat, S. (2001) · American Mathematical Monthly · doi:10.2307/2695613 · Cited by 38 · see citing works
Backward error analysis of Neville elimination
Alonso, P., Gasca, M., & Peña, J. M. (1997) · Applied Numerical Mathematics · doi:10.1016/s0168-9274(96)00051-7 · Cited by 34 · see citing works
Accurate and efficient evaluation of Schur and Jack functions
Demmel, J. W., & Koev, P. (2005) · Mathematics of Computation · doi:10.1090/s0025-5718-05-01780-1 · Cited by 28 · see citing works
Self-citationFast algorithms of Björck-Pereyra type for solving Cauchy-Vandermonde linear systems
Martínez, J., & Peña, J. M. (1998) · Applied Numerical Mathematics · doi:10.1016/s0168-9274(97)00102-5 · Cited by 26 · see citing works
Scaled pivoting in Gauss and Neville elimination for totally positive systems
Gasca, M., & Peña, J. M. (1993) · Applied Numerical Mathematics · doi:10.1016/0168-9274(93)90093-7 · Cited by 20 · see citing works
Numerical treatment of a generalized Vandermonde system of equations
de Vel, H. V. (1977) · Linear Algebra and its Applications · doi:10.1016/0024-3795(77)90035-0 · Cited by 18 · see citing works
Algorithm 167: calculation of confluent divided differences
Kahan, W., & Farkas, I. (1963) · Communications of the ACM · doi:10.1145/366349.366444 · Cited by 10 · see citing works
Accurate and efficient computations with structured matrices
Koev, P., & Demmel, J. W. (2002) · Cited by 3 · see citing works
Self-citation
Flagged first, then by citations
Cited by
Sorted by citations
A fast bjorck-pereyra-type algorithm for solving hessenberg-quasiseparable-vandermonde systems
Bella, T., Eidelman, Y., Gohberg, I., Koltracht, I., & Olshevsky, V. (2009) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/060676635 · Cited by 14 · see citing works
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
- Authors
- Demmel, J., & Koev, P.
- Affiliations
- University of California, Berkeley (US)
- Venue
- SIAM Journal on Matrix Analysis and Applications
- Published
- 2005-01
- Volume
- 27
- Issue
- 1
- Pages
- 142-152
- ISSN
- 0895-4798 (ISSN-L)
- 1095-7162
- OpenAlex
- W1988043369
- Cited by
- 154
- References
- 31
- Citations by year
- 2026: 9 · 2025: 13 · 2024: 16 · 2023: 11 · 2022: 8 · 2021: 11 · 2020: 6 · 2019: 6 · 2018: 7 · 2017: 5 · 2016: 7 · 2015: 8 · 2014: 3 · 2013: 7 · 2012: 6
- FWCI
- 6.05
- 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 › Numerical Methods and Algorithms
- Keywords
- totally positive matrices, Cauchy matrix, matrix inversion, LDU decomposition, high relative accuracy, minors
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
