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

**2016-02-01**

1602.00651 | cs.SC

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.

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

# Related Articles

**2019-03-08**

1903.03278 | cs.SC

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

**2019-05-12**

1905.04614 | cs.SC

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

**2019-01-27**

1901.09423 | cs.CC

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

**2018-01-14**

1801.04553 | cs.SC

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

**2018-08-07**

1808.02575 | math.AC

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

**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

**2019-01-03**

1901.00904 | cs.SC

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

**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

**2018-03-21**

1803.07974 | math.AG

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

**2017-12-12**

1712.04177 | cs.SC

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

**2017-10-30**

1710.11253 | cs.DS

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

**2012-08-17**

1208.3639 | cs.CC

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

**2016-01-06**

1601.01067 | cs.SC

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

**2018-07-02**

1807.00645 | cs.SC

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

**2012-03-30**

1203.6705 | cs.DS

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

**2013-12-27**

1312.7279 | cs.NA

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