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

**2016-02-01**

1602.00710 | cs.SC

We give a Las Vegas algorithm which computes the shifted Popov form of an $m
\times m$ nonsingular polynomial matrix of degree $d$ in expected
$\widetilde{\mathcal{O}}(m^\omega d)$ field operations, where $\omega$ is the
exponent of matrix multiplication and $\widetilde{\mathcal{O}}(\cdot)$
indicates that logarithmic factors are omitted. This is the first algorithm in
$\widetilde{\mathcal{O}}(m^\omega d)$ for shifted row reduction with arbitrary
shifts.
Using partial linearization, we reduce the problem to the case $d \le \lceil
\sigma/m \rceil$ where $\sigma$ is the generic determinant bound, with $\sigma
/ m$ bounded from above by both the average row degree and the average column
degree of the matrix. The cost above becomes $\widetilde{\mathcal{O}}(m^\omega
\lceil \sigma/m \rceil)$, improving upon the cost of the fastest previously
known algorithm for row reduction, which is deterministic.
Our algorithm first builds a system of modular equations whose solution set
is the row space of the input matrix, and then finds the basis in shifted Popov
form of this set. We give a deterministic algorithm for this second step
supporting arbitrary moduli in $\widetilde{\mathcal{O}}(m^{\omega-1} \sigma)$
field operations, where $m$ is the number of unknowns and $\sigma$ is the sum
of the degrees of the moduli. This extends previous results with the same cost
bound in the specific cases of order basis computation and M-Pad\'e
approximation, in which the moduli are products of known linear factors.

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

# Related Articles

**2019-05-10**

1905.04356 | cs.SC

Complexity bounds for many problems on matrices with univariate polynomial
entries have been improve… show more

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

**2018-10-30**

1810.12588 | cs.SC

Symmetric tensor decomposition is an important problem with applications in
several areas for exampl… show more

**2018-06-15**

1806.05834 | math.NT

We propose a Las Vegas probabilistic algorithm to compute the zeta function
of a genus-3 hyperellipt… 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

**2016-10-27**

1610.08671 | math.RA

We propose a randomized polynomial time algorithm for computing nontrivial
zeros of quadratic forms … 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

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

**2016-08-09**

1608.02674 | cs.DC

Censor-Hillel et al. [PODC'15] recently showed how to efficiently implement
centralized algebraic al… show more

**2018-02-07**

1802.02270 | cs.SC

We present new algorithms to detect and correct errors in the product of two
matrices, or the invers… show more