ML p(r)ior | Fast Computation of Shifted Popov Forms of Polynomial Matrices via Systems of Modular Polynomial Equations

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.
PDF

Highlights - Most important sentences from the article

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

Related Articles

2019-05-10

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

Highlights - Most important sentences from the article

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

2018-10-30

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

Highlights - Most important sentences from the article

2018-06-15

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

2016-10-27
1610.08671 | math.RA

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

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

2016-08-09
1608.02674 | cs.DC

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

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article