Let 𝑓1,…,𝑓𝑚 be univariate polynomials with rational coefficients and I:=⟨𝑓1,…,𝑓𝑚⟩⊂ℚ[𝑥] be the ideal they generate. Assume that we are given approximations {𝑧1,…,𝑧𝑘}⊂ℚ[𝑖] for the common roots {𝜉1,…,𝜉𝑘}=𝑉(I)⊆ℂ . In this study, we describe a symbolic-numeric algorithm to construct a rational matrix, called Hermite matrix, from the approximate roots {𝑧1,…,𝑧𝑘} and certify that this matrix is the true Hermite matrix corresponding to the roots V(I) . Applications of Hermite matrices include counting and locating real roots of the polynomials and certifying their existence.
more »
« less
Certified Hermite matrices from approximate roots
Let I = f1,..., fm ⊂ Q[x1,..., xn] be a zero dimensional radical
ideal defined by polynomials given with exact rational coefficients.
Assume that we are given approximations {z1,..., zk} ⊂ Cn for
the common roots {ξ1,..., ξk} = V (I) ⊆ Cn. In this paper we
show how to construct and certify the rational entries of Hermite
matrices for I from the approximate roots {z1,..., zk}. When I
is non-radical, we give methods to construct and certify Hermite
matrices for √
I from the approximate roots. Furthermore, we use
signatures of these Hermite matrices to give rational certificates
of non-negativity of a given polynomial over a (possibly positive
dimensional) real variety, as well as certificates that there is a real
root within an ε distance from a given point z ∈ Qn.
more »
« less
- Award ID(s):
- 1813340
- PAR ID:
- 10473728
- Publisher / Repository:
- Elsevier
- Date Published:
- Journal Name:
- Journal of Symbolic Computation
- Volume:
- 117
- Issue:
- C
- ISSN:
- 0747-7171
- Page Range / eLocation ID:
- 101 to 118
- Subject(s) / Keyword(s):
- Symbolic–numeric computation Polynomial systems Approximate roots Hermite matrices Certification
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract This paper solves the rational noncommutative analogue of Hilbert’s 17th problem: if a noncommutative rational function is positive semidefinite on all tuples of Hermitian matrices in its domain, then it is a sum of Hermitian squares of noncommutative rational functions. This result is a generalisation and culmination of earlier positivity certificates for noncommutative polynomials or rational functions without Hermitian singularities. More generally, a rational Positivstellensatz for free spectrahedra is given: a noncommutative rational function is positive semidefinite or undefined at every matricial solution of a linear matrix inequality $L\succeq 0$ if and only if it belongs to the rational quadratic module generated by L . The essential intermediate step toward this Positivstellensatz for functions with singularities is an extension theorem for invertible evaluations of linear matrix pencils.more » « less
-
Rothblum, Guy N ; Wee, Hoeteck (Ed.)The field of distributed certification is concerned with certifying properties of distributed networks, where the communication topology of the network is represented as an arbitrary graph; each node of the graph is a separate processor, with its own internal state. To certify that the network satisfies a given property, a prover assigns each node of the network a certificate, and the nodes then communicate with one another and decide whether to accept or reject. We require soundness and completeness: the property holds if and only if there exists an assignment of certificates to the nodes that causes all nodes to accept. Our goal is to minimize the length of the certificates, as well as the communication between the nodes of the network. Distributed certification has been extensively studied in the distributed computing community, but it has so far only been studied in the information-theoretic setting, where the prover and the network nodes are computationally unbounded. In this work we introduce and study computationally bounded distributed certification: we define locally verifiable distributed SNARGs (LVD-SNARGs), which are an analog of SNARGs for distributed networks, and are able to circumvent known hardness results for information-theoretic distributed certification by requiring both the prover and the verifier to be computationally efficient (namely, PPT algorithms). We give two LVD-SNARG constructions: the first allows us to succinctly certify any network property in P, using a global prover that can see the entire network; the second construction gives an efficient distributed prover, which succinctly certifies the execution of any efficient distributed algorithm. Our constructions rely on non-interactive batch arguments for NP (BARGs) and on RAM-SNARGs, which have recently been shown to be constructible from standard cryptographic assumptions.more » « less
-
more » « less
Abstract An $n \times n$ matrix with $\pm 1$ entries that acts on ${\mathbb {R}}^{n}$ as a scaled isometry is called Hadamard. Such matrices exist in some, but not all dimensions. Combining number-theoretic and probabilistic tools, we construct matrices with $\pm 1$ entries that act as approximate scaled isometries in ${\mathbb {R}}^{n}$ for all $n \in {\mathbb {N}}$. More precisely, the matrices we construct have condition numbers bounded by a constant independent of $n$.
Using this construction, we establish a phase transition for the probability that a random frame contains a Riesz basis. Namely, we show that a random frame in ${\mathbb {R}}^{n}$ formed by $N$ vectors with independent identically distributed coordinate having a nondegenerate symmetric distribution contains many Riesz bases with high probability provided that $N \ge \exp (Cn)$. On the other hand, we prove that if the entries are sub-Gaussian, then a random frame fails to contain a Riesz basis with probability close to $1$ whenever $N \le \exp (cn)$, where $c<C$ are constants depending on the distribution of the entries.
-
We generalize Hermite interpolation with error correction, which is the methodology for multiplicity algebraic error correction codes, to Hermite interpolation of a rational function over a field K from function and function derivative values. We present an interpolation algorithm that can locate and correct <= E errors at distinct arguments y in K where at least one of the values or values of a derivative is incorrect. The upper bound E for the number of such y is input. Our algorithm sufficiently oversamples the rational function to guarantee a unique interpolant. We sample (f/g)^(j)(y[i]) for 0 <= j <= L[i], 1 <= i <= n, y[i] distinct, where (f/g)^(j) is the j-th derivative of the rational function f/g, f, g in K[x], GCD(f,g)=1, g <= 0, and where N = (L[1]+1)+...+(L[n]+1) >= C + D + 1 + 2(L[1]+1) + ... + 2(L[E]+1) where C is an upper bound for deg(f) and D an upper bound for deg(g), which are input to our algorithm. The arguments y[i] can be poles, which is truly or falsely indicated by a function value infinity with the corresponding L[i]=0. Our results remain valid for fields K of characteristic >= 1 + max L[i]. Our algorithm has the same asymptotic arithmetic complexity as that for classical Hermite interpolation, namely soft-O(N). For polynomials, that is, g=1, and a uniform derivative profile L[1] = ... = L[n], our algorithm specializes to the univariate multiplicity code decoder that is based on the 1986 Welch-Berlekamp algorithm.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1016/j.jsc.2022.12.001
