اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدInterpolation by decomposable univariate polynomials
201
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
The usual univariate interpolation problem of finding a monic polynomial f of degree n that interpolates n given values is well understood. This paper studies a variant where f is required to be composite, say, a composition of two polynomials of degrees d and e, respectively, with de=n, and therefore d+e-1 given values. Some special cases are easy to solve, and for the general case, we construct a homotopy between it and a special case. We compute a geometric solution of the algebraic curve presenting this homotopy, and this also provides an answer to the interpolation task. The computing time is polynomial in the geometric data, like the degree, of this curve. A consequence is that for almost all inputs, a decomposable interpolation polynomial exists.
قيم البحث
اقرأ أيضاً
We estimate the density of tubes around the algebraic variety of decomposable univariate polynomials over the real and the complex numbers.
A univariate trace polynomial is a polynomial in a variable x and formal trace symbols Tr(x^j). Such an expression can be naturally evaluated on matrices, where the trace symbols are evaluated as normalized traces. This paper addresses global and con
strained positivity of univariate trace polynomials on symmetric matrices of all finite sizes. A tracial analog of Artins solution to Hilberts 17th problem is given: a positive semidefinite univariate trace polynomial is a quotient of sums of products of squares and traces of squares of trace polynomials.
Amendola et al. proposed a method for solving systems of polynomial equations lying in a family which exploits a recursive decomposition into smaller systems. A family of systems admits such a decomposition if and only if the corresponding Galois gro
up is imprimitive. When the Galois group is imprimitive we consider the problem of computing an explicit decomposition. A consequence of Esterovs classification of sparse polynomial systems with imprimitive Galois groups is that this decomposition is obtained by inspection. This leads to a recursive algorithm to solve decomposable sparse systems, which we present and give evidence for its efficiency.
The Macaulay2 package DecomposableSparseSystems implements methods for studying and numerically solving decomposable sparse polynomial systems. We describe the structure of decomposable sparse systems and explain how the methods in this package may be used to exploit this structure, with examples.
Given a black box function to evaluate an unknown rational polynomial f in Q[x] at points modulo a prime p, we exhibit algorithms to compute the representation of the polynomial in the sparsest shifted power basis. That is, we determine the sparsity
t, the shift s (a rational), the exponents 0 <= e1 < e2 < ... < et, and the coefficients c1,...,ct in Q{0} such that f(x) = c1(x-s)^e1+c2(x-s)^e2+...+ct(x-s)^et. The computed sparsity t is absolutely minimal over any shifted power basis. The novelty of our algorithm is that the complexity is polynomial in the (sparse) representation size, and in particular is logarithmic in deg(f). Our method combines previous celebrated results on sparse interpolation and computing sparsest shifts, and provides a way to handle polynomials with extremely high degree which are, in some sense, sparse in information.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
