Symbolic-numeric sparse interpolation of multivariate polynomials

DOI10.1016/J.JSC.2008.11.003zbMath1167.65003OpenAlexW1977375620MaRDI QIDQ5902083

Wen-Shin Lee, George Labahn, Mark W. Giesbrecht

Publication date: 11 June 2009

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jsc.2008.11.003

zbMATH Keywords

algorithmsstabilitynumerical exampleseigenvalueserror analysismultivariate interpolationconditioningmultivariate polynomialssparse interpolationsensitivity generalizedsymbolic-numeric computing

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Numerical interpolation (65D05) Kinematics of deformation (74A05) Multidimensional problems (41A63)

Related Items (27)

Numerical reconstruction of convex polytopes from directional moments ⋮ Polynomial-exponential decomposition from moments ⋮ A new algorithm for sparse interpolation of multivariate polynomials ⋮ Faster sparse multivariate polynomial interpolation of straight-line programs ⋮ An extended Prony's interpolation scheme on an equispaced grid ⋮ Reconstruction of sparse Legendre and Gegenbauer expansions ⋮ Prony's method in several variables: symbolic solutions by universal interpolation ⋮ On the numerical condition of a generalized Hankel eigenvalue problem ⋮ On rational functions without Froissart doublets ⋮ SLRA Interpolation for Approximate GCD of Several Multivariate Polynomials ⋮ Obtaining exact interpolation multivariate polynomial by approximation ⋮ Faint and clustered components in exponential analysis ⋮ Border basis relaxation for polynomial optimization ⋮ Sparse interpolation of multivariate rational functions ⋮ Optimizing \(n\)-variate \((n+k)\)-nomials for small \(k\) ⋮ Sparse polynomial interpolation in Chebyshev bases ⋮ Fast ESPRIT algorithms based on partial singular value decompositions ⋮ Deterministic sparse FFT for \(M\)-sparse vectors ⋮ A fast parallel sparse polynomial GCD algorithm ⋮ Prony's method in several variables ⋮ Sparse polynomial interpolation: sparse recovery, super-resolution, or Prony? ⋮ Regularization and Matrix Computation in Numerical Polynomial Algebra ⋮ Approximate factorization of multivariate polynomials using singular value decomposition ⋮ Sparse Polynomial Interpolation by Variable Shift in the Presence of Noise and Outliers in the Evaluations ⋮ A Symbolic Approach to Compute a Null-Space Basis in the Projection Method ⋮ Sparse interpolation in terms of multivariate Chebyshev polynomials ⋮ Accurate solution of near-colliding Prony systems via decimation and homotopy continuation

Uses Software

• FOXBOX
• mctoolbox

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Numerical factorization of multivariate complex polynomials
• On the numerical condition of a generalized Hankel eigenvalue problem
• Interpolating polynomials from their values
• Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators
• Lower bounds for the condition number of Vandermonde matrices
• Norm estimates for inverses of Vandermonde matrices
• The condition number of real Vandermonde, Krylov and positive definite Hankel matrices
• On the history of multivariate polynomial interpolation
• Multivariate Hermite interpolation by algebraic polynomials: A survey
• Early termination in sparse interpolation algorithms
• Pseudospectra of matrix polynomials that are expressed in alternative bases
• Numerical Decomposition of the Solution Sets of Polynomial Systems into Irreducible Components
• A Weakly Stable Algorithm for Padé Approximants and the Inversion of Hankel Matrices
• Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields
• A Stable Numerical Method for Inverting Shape from Moments
• Approximate factorization of multivariate polynomials via differential equations
• Accuracy and Stability of Numerical Algorithms
• Randomized Interpolation and Approximation of Sparse Polynomials
• Conditioning of Rectangular Vandermonde Matrices with Nodes in the Unit Disk
• Symbolic-numeric sparse interpolation of multivariate polynomials
• Vandermonde matrices on the circle: Spectral properties and conditioning

This page was built for publication: Symbolic-numeric sparse interpolation of multivariate polynomials