ML p(r)ior | Fast Computation of Minimal Interpolation Bases in Popov Form for Arbitrary Shifts

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

2016-02-01
We compute minimal bases of solutions for a general interpolation problem, which encompasses Hermite-Pad\'e 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 $\sigma$; 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 $\mathcal{O}\tilde{~}(m^{\omega-1} \sigma)$ field operations, where $\omega$ is the exponent of matrix multiplication and the notation $\mathcal{O}\tilde{~}(\cdot)$ indicates that logarithmic terms are omitted. Earlier works, in the case of Hermite-Pad\'e approximation and in the general interpolation case, compute non-normalized bases. Since for arbitrary shifts such bases may have size $\Theta(m^2 \sigma)$, the cost bound $\mathcal{O}\tilde{~}(m^{\omega-1} \sigma)$ 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 $\mathcal{O}(m \sigma)$. 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.
PDF

Highlights - Most important sentences from the article

Login to like/save this paper, take notes and configure your recommendations

Related Articles

2019-03-08

It is well known that for any finite Galois extension field $K/F$, with Galois group $G = \mathrm{Ga… show more
PDF

Highlights - Most important sentences from the article

2019-05-12

Following recent work by van der Hoeven and Lecerf (ISSAC 2017), we discuss the complexity of linear… show more
PDF

Highlights - Most important sentences from the article

2019-01-27
1901.09423 | cs.CC

This paper presents a deterministic, strongly polynomial time algorithm for computing the matrix ran… show more
PDF

Highlights - Most important sentences from the article

2018-01-14

In this article, we design fast algorithms for the computation of approximant bases in shifted Popov… show more
PDF

Highlights - Most important sentences from the article

2018-08-07

We compute minimal solutions of the rational interpolation problem in terms of different notions of … show more
PDF

Highlights - Most important sentences from the article

2019-01-08
1901.02536 | cs.DS

For any finite group $G$, we give an arithmetic algorithm to compute generalized Discrete Fourier Tr… show more
PDF

Highlights - Most important sentences from the article

2019-01-03
1901.00904 | cs.SC

Volker Strassen first suggested an algorithm to multiply matrices with worst case running time less … show more
PDF

Highlights - Most important sentences from the article

2018-03-17
1803.06521 | cs.LG

We introduce the problem of learning mixtures of $k$ subcubes over $\{0,1\}^n$, which contains many … show more
PDF

Highlights - Most important sentences from the article

2018-03-21

We consider the problem of finding the isolated common roots of a set of polynomial functions defini… show more
PDF

Highlights - Most important sentences from the article

2017-12-12

Consider a zero-dimensional ideal $I$ in $\mathbb{K}[X_1,\dots,X_n]$. Inspired by Faug\`ere and Mou'… show more
PDF

Highlights - Most important sentences from the article

2017-10-30

We study the $\ell_0$-Low Rank Approximation Problem, where the goal is, given an $m \times n$ matri… show more
PDF

Highlights - Most important sentences from the article

2012-08-17

We show that linear differential operators with polynomial coefficients over a field of characterist… show more
PDF

Highlights - Most important sentences from the article

2016-01-06

In this paper, a polynomial-time algorithm is given to compute the generalized Hermite normal form f… show more
PDF

Highlights - Most important sentences from the article

2018-07-02
1807.00645 | cs.SC

This paper presents new fast algorithms for Hermite interpolation and evaluation over finite fields … show more
PDF

Highlights - Most important sentences from the article

2012-03-30

We consider the problem of computing the rank of an m x n matrix A over a field. We present a random… show more
PDF

Highlights - Most important sentences from the article

2013-12-27

Structured Low-Rank Approximation is a problem arising in a wide range of applications in Numerical … show more
PDF

Highlights - Most important sentences from the article