ML p(r)ior | Linear Time Interactive Certificates for the Minimal Polynomial and the Determinant of a Sparse Matrix

Linear Time Interactive Certificates for the Minimal Polynomial and the Determinant of a Sparse Matrix

2016-02-02
1602.00810 | cs.SC
Certificates to a linear algebra computation are additional data structures for each output, which can be used by a-possibly randomized- verification algorithm that proves the correctness of each output. In this paper, we give an algorithm that compute a certificate for the minimal polynomial of sparse or structured n x n matrices over an abstract field, of sufficiently large cardinality, whose Monte Carlo verification complexity requires a single matrix-vector multiplication and a linear number of extra field operations. We also propose a novel preconditioner that ensures irreducibility of the characteristic polynomial of the preconditioned matrix. This preconditioner takes linear time to be applied and uses only two random entries. We then combine these two techniques to give algorithms that compute certificates for the determinant, and thus for the characteristic polynomial, whose Monte Carlo verification complexity is therefore also linear.

Highlights - Most important sentences from the article

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 Highlights - Most important sentences from the article 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 Highlights - Most important sentences from the article 2018-10-25 1810.11068 | math.NT We present a probabilistic Las Vegas algorithm for computing the local zeta function of a genus-$g$… show more Highlights - Most important sentences from the article 2017-12-02 1712.00669 | cs.CG We present a novel randomized algorithm to factor polynomials over a finite field$\F_q$of odd char… show more Highlights - Most important sentences from the article 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 Highlights - Most important sentences from the article 2015-11-11 1511.03730 | cs.CC In this paper we present a deterministic polynomial time algorithm for testing if a symbolic matrix … show more Highlights - Most important sentences from the article 2018-06-29 1806.11293 | cs.SC In an emerging computing paradigm, computational capabilities, from processing power to storage capa… show more Highlights - Most important sentences from the article 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

Highlights - Most important sentences from the article

2014-04-17
1404.5525 | cs.NA

In this paper, we study iterative methods on the coefficients of the rational univariate representat… show more

Highlights - Most important sentences from the article

2012-08-17
1208.3639 | cs.CC

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

Highlights - Most important sentences from the article

2012-10-04
1210.1451 | cs.CC

The multivariate resultant is a fundamental tool of computational algebraic geometry. It can in part… show more

Highlights - Most important sentences from the article

2013-11-22
1311.5694 | cs.SC

We present a deterministic polynomial-time algorithm which computes the multilinear factors of multi… show more

Highlights - Most important sentences from the article

2016-04-29
1604.08944 | cs.SC

Given a zero-dimensional polynomial system consisting of n integer polynomials in n variables, we pr… show more

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

2016-02-29
1602.09037 | cs.DS

We show in this paper that the Gentry-Szydlo algorithm for cyclotomic orders, previously revisited b… show more

Highlights - Most important sentences from the article

2012-01-27
1201.5810 | cs.SC

Sparse (or toric) elimination exploits the structure of polynomials by measuring their complexity in… show more

Highlights - Most important sentences from the article