NDLI: Sparse polynomial interpolation and Berlekamp/Massey algorithms that correct outlier errors in input values

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

A-hypergeometric functions: computational aspects

Complexity of deciding connectivity in real algebraic sets: recent results and future research directions

Asymptotic spectrum and matrix multiplication

Upper bounds on real roots and lower bounds for the permanent

Elements of computer-algebraic analysis

Algebraic statistics

On valuations of meromorphic solutions of arbitrary-order linear difference systems with polynomial coefficients

Computing Puiseux series for algebraic surfaces

The M4RIE library for dense linear algebra over small fields with even characteristic

A root isolation algorithm for sparse univariate polynomials

Computing closed form solutions of integrable connections

Solving linear ordinary differential systems in hyperexponential extensions

Relaxed p-adic Hensel lifting for algebraic systems

Solving polynomial systems over finite fields: improved analysis of the hybrid approach

A polynomial time algorithm for computing the HNF of a module over the integers of a number field

Parallel sparse polynomial multiplication on modern hardware architectures

Compositions and collisions at degree $p^{2}$

Fast computation of common left multiples of linear ordinary differential operators

Power series solutions of singular (q)-differential equations

On the complexity of solving initial value problems

Order-degree curves for hypergeometric creative telescoping

Telescopers for rational and algebraic functions via residues

Sparse polynomial interpolation and Berlekamp/Massey algorithms that correct outlier errors in input values

Fast computation of Smith forms of sparse matrices over local rings

On the complexity of solving a bivariate polynomial system

Critical points and Gröbner bases: the unmixed case

Solving polynomial systems globally invariant under an action of the symmetric group and application to the equilibria of N vortices in the plane

Twisting q-holonomic sequences by complex roots of unity

Improving the accuracy of linear programming solvers with iterative refinement

Certificates of impossibility of Hilbert-Artin representations of a given degree for definite polynomials and functions

Practical Gröbner basis computation

On the complexity of multivariate blockwise polynomial multiplication

Rational invariants of scalings from Hermite normal forms

Zeilberger's holonomic ansatz for Pfaffians

Algorithms for the universal decomposition algebra

An efficient implementation of the algorithm computing the Borel-fixed points of a Hilbert scheme

Computing real solutions of polynomial systems via low-rank moment matrix completion

Small homogeneous quandles

Border basis representation of a general quotient algebra

An algorithm to compute the differential equations for the logarithm of a polynomial

Deterministic unimodularity certification

Programming before theorizing, a case study

When Newton meets Descartes: a simple and fast algorithm to isolate the real roots of a polynomial

Effective de Rham cohomology: the hypersurface case

Construction of 2-closed M-representations

Near optimal tree size bounds on a simple real root isolation algorithm

An efficient programming model for memory-intensive recursive algorithms using parallel disks

Solving polynomial systems over semialgebraic sets represented by cylindrical algebraic formulas

Univariate real root isolation in multiple extension fields

A signature-based algorithm for computing Gröbner bases in solvable polynomial algebras

Factorization of differential operators with ordinary differential polynomial coefficients

Computing minimal nullspace bases

Sparse polynomial interpolation and Berlekamp/Massey algorithms that correct outlier errors in input values

Content Provider	ACM Digital Library
Author	Comer, Matthew T. Kaltofen, Erich L. Pernet, Clément
Abstract	We propose algorithms performing sparse interpolation with errors, based on Prony's--Ben-Or's & Tiwari's algorithm, using a Berlekamp/Massey algorithm with early termination. First, we present an algorithm that can recover a t-sparse polynomial f from a sequence of values, where some of the values are wrong, spoiled by either random or misleading errors. Our algorithm requires bounds T ≥ t and E ≥ e, where e is the number of evaluation errors. It interpolates $f(ω^{i})$ for i = 1,., 2T(E + 1), where ω is a field element at which each non-zero term evaluates distinctly. We also investigate the problem of recovering the minimal linear generator from a sequence of field elements that are linearly generated, but where again e ≤ E elements are erroneous. We show that there exist sequences of < 2t(2e + 1) elements, such that two distinct generators of length t satisfy the linear recurrence up to e faults, at least if the field has characteristic ≠ 2. Uniqueness can be proven (for any field characteristic) for length ≥ 2t(2e + 1) of the sequence with e errors. Finally, we present the Majority Rule Berlekamp/Massey algorithm, which can recover the unique minimal linear generator of degree t when given bounds T ≥ t and E ≥ e and the initial sequence segment of 2T(2E + 1) elements. Our algorithm also corrects the sequence segment. The Majority Rule algorithm yields a unique sparse interpolant for the first problem. The algorithms are applied to sparse interpolation algorithms with numeric noise, into which we now can bring outlier errors in the values.
Starting Page	138
Ending Page	145
Page Count	8
File Format	PDF
ISBN	9781450312691
DOI	10.1145/2442829.2442852
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2012-07-22
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Fault tolerance Polynomial recovery Linearly generated sequences
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