NDLI: Fast Computation of Minimal Interpolation Bases in Popov Form for Arbitrary Shifts

Please wait, while we are loading the content...

Compact Formulae in Sparse Elimination

Symbolic Computation of Parameter Integrals

Detecting Similarities of Rational Space Curves

Succinct Data Structures ... Potential for Symbolic Computation?

Symbolic Computation with Integro-Differential Operators

Solving Generic Nonarchimedean Semidefinite Programs Using Stochastic Game Algorithms

Symbolic Summation in Difference Rings and Applications

Formal Algorithmic Elimination for PDEs

Computing Limits of Real Multivariate Rational Functions

Infinitely Many Carmichael Numbers for a Modified Miller-Rabin Prime Test

Baby-Step Giant-Step Algorithms for the Symmetric Group

Computing the Lie Algebra of the Differential Galois Group of a Linear Differential System

Complexity Analysis of Root Clustering for a Complex Polynomial

A Superfast Randomized Algorithm to Decompose Binary Forms

Analysis of the Brun Gcd Algorithm

Guessing Linear Recurrence Relations of Sequence Tuplesand P-recursive Sequences with Linear Algebra

Determinantal Sets, Singularities and Application to Optimal Control in Medical Imagery

Computation of the Similarity Class of the p-Curvature

Fast Computation of the Nth Term of an Algebraic Series over a Finite Prime Field

Efficient Algorithms for Mixed Creative Telscoping

GBLA: Gröbner Basis Linear Algebra Package

Validating the Completeness of the Real Solution Set of a System of Polynomial Equations

On the Complexity of Solving Zero-Dimensional Polynomial Systems via Projection

Division and Slope Factorization of p-Adic Polynomials

Existence Problem of Telescopers: Beyond the Bivariate Case

Reduction-Based Creative Telescoping for Algebraic Functions

Critical Point Computations on Smooth Varieties: Degree and Complexity Bounds

Fast Fourier Orthogonalization

Linear Time Interactive Certificates for the Minimal Polynomial and the Determinant of a Sparse Matrix

Selecting Algorithms for Black Box Matrices: Checking For Matrix Properties That Can Simplify Computations

On the Bit Complexity of Solving Bilinear Polynomial Systems

Computing Small Certificates of Inconsistency of Quadratic Fewnomial Systems

Computer Assisted Proof for Apwenian Sequences

Bounds for Orders of Derivatives in Differential Elimination Algorithms

Numerical Sparsity Determination and Early Termination

Fast Polynomial Multiplication over $F_{2}_{60}$

A Factorization Algorithm for G-Algebras and Applications

A Fast Parallel Sparse Polynomial GCD Algorithm

New Bounds for Hypergeometric Creative Telescoping

Constructing Small Generating Sets for the Multiplicative Groups of Algebras over Finite Fields

Fast Computation of Minimal Interpolation Bases in Popov Form for Arbitrary Shifts

Computing Real Roots of Real Polynomials ... and now For Real!

Equivariant Gröbner Bases of Symmetric Toric Ideals

On p-Adic Differential Equations with Separation of Variables

Positive Root Isolation for Poly-Powers

Symbolic-Numeric Tools for Analytic Combinatorics in Several Variables

A Fast Algorithm for Computing the Truncated Resultant

Comprehensive Gröbner Systems in Rings of Differential Operators, Holonomic D-modules and B-functions

Solving Rank-Constrained Semidefinite Programs in Exact Arithmetic

Fast Computation of Shifted Popov Forms of Polynomial Matrices via Systems of Modular Polynomial Equations

Faster LLL-type Reduction of Lattice Bases

System of Partial Differential Equations for the Hypergeometric Function 1F1 of a Matrix Argument on Diagonal Regions

Computing with Quasiseparable Matrices

Algorithmic Operator Algebras via Normal Forms for Tensors

Algorithms for Simultaneous Padé Approximations

Contraction of Ore Ideals with Applications

Fast Computation of Minimal Interpolation Bases in Popov Form for Arbitrary Shifts

Content Provider	ACM Digital Library
Author	Jeannerod, Claude-Pierre Neiger, Vincent Schost, Éric Villard, Gilles
Abstract	We compute minimal bases of solutions for a general interpolation problem, which encompasses Hermite-Pade approximation and constrained multivariate interpolation, and has applications in coding theory and security. This problem asks to find univariate polynomial relations between m vectors of size σ; these relations should have small degree with respect to an input degree shift. For an arbitrary shift, we propose an algorithm for the computation of an interpolation basis in shifted Popov normal form with a cost of $O~(m^{ω-1}$ σ) field operations, where ω is the exponent of matrix multiplication and the notation O~(·) indicates that logarithmic terms are omitted. Earlier works, in the case of Hermite-Pade approximation and in the general interpolation case, compute non-normalized bases. Since for arbitrary shifts such bases may have size $Θ(m^{2}$ σ), the cost bound $O~(m^{ω-1}$ σ) was feasible only with restrictive assumptions on the shift that ensure small output sizes. The question of handling arbitrary shifts with the same complexity bound was left open. To obtain the target cost for any shift, we strengthen the properties of the output bases, and of those obtained during the course of the algorithm: all the bases are computed in shifted Popov form, whose size is always O(m σ). Then, we design a divide-and-conquer scheme. We recursively reduce the initial interpolation problem to sub-problems with more convenient shifts by first computing information on the degrees of the intermediate bases.
Starting Page	295
Ending Page	302
Page Count	8
File Format	PDF
ISBN	9781450343800
DOI	10.1145/2930889.2930928
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2016-07-20
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Order basis M-pade approximation Polynomial matrix Shifted popov form Hermite-pade approximation
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in