共查询到20条相似文献,搜索用时 31 毫秒
1.
We call a polynomial g(t1, . . . , tm,X ) over a field K generic for a group G if it has Galois group G as a polynomial inX , and if every Galois field extension N / L withK L and Gal(N / L) ≤ G arises as the splitting field of a suitable specializationg (λ1, . . . , λm, X) withλi L. We discuss how the rationality of the invariant field of a faithful linear representation leads to a generic polynomial which is often particularly simple and therefore useful. Then we consider various examples and applications in characteristic 0 and in positive characteristic. These include results on so-called vectorial polynomials and a generalization of an embedding criterion given by Abhyankar. We give recursive formulas for generic polynomials over a field of defining characteristic for the groups of upper unipotent and upper triangular matrices, and explicit formulae for generic polynomials for the groups GU2(q2) andGO3 (q). 相似文献
2.
A real n-dimensional homogeneous polynomial f(x) of degree m and a real constant c define an algebraic hypersurface S whose points satisfy f(x)=c. The polynomial f can be represented by Axm where A is a real mth order n-dimensional supersymmetric tensor. In this paper, we define rank, base index and eigenvalues for the polynomial f, the hypersurface S and the tensor A. The rank is a nonnegative integer r less than or equal to n. When r is less than n, A is singular, f can be converted into a homogeneous polynomial with r variables by an orthogonal transformation, and S is a cylinder hypersurface whose base is r-dimensional. The eigenvalues of f, A and S always exist. The eigenvectors associated with the zero eigenvalue are either recession vectors or degeneracy vectors of positive degree, or their sums. When c⁄=0, the eigenvalues with the same sign as c and their eigenvectors correspond to the characterization points of S, while a degeneracy vector generates an asymptotic ray for the base of S or its conjugate hypersurface. The base index is a nonnegative integer d less than m. If d=k, then there are nonzero degeneracy vectors of degree k−1, but no nonzero degeneracy vectors of degree k. A linear combination of a degeneracy vector of degree k and a degeneracy vector of degree j is a degeneracy vector of degree k+j−m if k+j≥m. Based upon these properties, we classify such algebraic hypersurfaces in the nonsingular case into ten classes. 相似文献
3.
《Journal of Symbolic Computation》2002,33(2):239-254
In this paper, we introduce “approximate solutions" to solve the following problem: given a polynomial F(x, y) over Q, where x represents an n -tuple of variables, can we find all the polynomials G(x) such that F(x, G(x)) is identically equal to a constant c in Q ? We have the following: let F(x, y) be a polynomial over Q and the degree of y in F(x, y) be n. Either there is a unique polynomial g(x) ∈ Q [ x ], with its constant term equal to 0, such that F(x, y) = ∑j = 0ncj(y − g(x))jfor some rational numbers cj, hence, F(x, g(x) + a) ∈ Q for all a ∈ Q, or there are at most t distinct polynomials g1(x),⋯ , gt(x), t ≤ n, such that F(x, gi(x)) ∈ Q for 1 ≤ i ≤ t. Suppose that F(x, y) is a polynomial of two variables. The polynomial g(x) for the first case, or g1(x),⋯ , gt(x) for the second case, are approximate solutions of F(x, y), respectively. There is also a polynomial time algorithm to find all of these approximate solutions. We then use Kronecker’s substitution to solve the case of F(x, y). 相似文献
4.
Under relative-degree-one and minimum-phase assumptions, it is well known that the class
of finite-dimensional, linear, single-input (u), single-output (y) systems (A,b,c) is universally stabilized by the feedback strategy u = Λ(λ)y, λ = y2, where Λ is a function of Nussbaum type (the terminology “universal stabilization” being used in the sense of rendering /s(0/s) a global attractor for each member of the underlying class whilst assuring boundedness of the function λ(·)). A natural generalization of this result to a class
k of nonlinear control systems (a,b,c), with positively homogeneous (of degree k 1) drift vector field a, is described. Specifically, under the relative-degree-one (cb ≠ 0) and minimum-phase hypotheses (the latter being interpreted as that of asymptotic stability of the equilibrium of the “zero dynamics”), it is shown that the strategy u = Λ(λ)/vby/vbk−1y,
assures
k-universal stabilization. More generally, the strategy u = Λ(λ)exp(/vby/vb)y,
assures
-universal stabilization, where
= k 1
k. 相似文献
5.
Let be an imaginary quadratic number field with ring of integers Zk and let k(α) be the cubic extension of k generated by the polynomial ft(x)=x3−(t−1)x2−(t+2)x−1 with tZk. In the present paper we characterize all elements γZk[α] with norms satisfying |Nk(α)/k|≤|2t+1| for |t|≥14. This generalizes a corresponding result by Lemmermeyer and Pethő for Shanks’ cubic fields over the rationals. 相似文献
6.
Shih Ping Tung 《Information and Computation》1999,149(2):99
LetRbe a Hilbertian domain and letKbe its fraction field. Letψ(x1, …, xn, y) be a quantifier free arithmetical formula overR. We may also takeψ(x1, …, xn, y) to be an arithmetical formula overK[x1, …, xn] and write it asψ(y). In this paper we show that ifRhas enough non-units and x1…xn y ψ(x1, …, xn, y), called an n sentence, is true inR, then y ψ(y) is true inK[x1, …, xn]. Also, ifR=K[T], whereKis an infinite integral domain andx1…xn y ψ(x1, …, xn, y)is true inR, then y ψ(y) is true inR[x1, …, xn]. These results are applied to find the upper and lower bounds of the time complexities of various decision problems on diophantine equations with parameters and arithmetical sentences. Some of the results are: 1. The decision problem of sentences and diophantine equations with parameters over the ring of integers of a global field are co-NP-complete. 2. The decision problem of sentences over the ring of integers of a global field is NP-complete. 3. LetKbe an infinite domain, the time complexities of the decision problems of equations with parameters and sentences over the polynomial ringK[t] are polynomial time reducible to factoring polynomials overK. 4. The decision problem of sentences over all algebraic integer rings is in P. 5. The decision problem of sentences over all integral domains with characteristic 0 is in P. 6. The time complexity of the decision problem of sentences over all integral domains is polynomial time reducible to factoring integers overZand factoring polynomials over finite fields. 相似文献
7.
The analytic structure of Rational Interpolants (R.I.) f
(z) built from randomly perturbed data is explored; the interpolation nodes x
j
, j = 1,...,M, are real points where the function f reaches these prescribed data
. It is assumed that the data
are randomly perturbed values of a rational function (n)
(m) (m / n is the degree of the numerator/denominator). Much attention is paid to the R.I. familyf
(n+1)
(m–1), in the small stochasticity régime. The main result is that the additional zero and pole are located nearby the root of the same random polynomial, called the Froissart Polynomial (F.P.). With gaussian hypothesis on the noise, the random real root of F.P. is distributed according to a Cauchy-Lorentz law, with parameters such that the integrated probability over the interpolation interval x
1, x
M
is always larger than 1/2; in two cases studied in detail, it reaches 2/3 in one case and almost 3/4 in the other. For the families f
(n+k)
(m+k), numerical explorations point to similar phenomena; inspection shows that, in the mean, the localization occurs in the complex and/or real vicinity of the interpolation interval. 相似文献
8.
If { Pn(x;q)}nis a family of polynomials belonging to the q -Hahn tableau then each polynomial of this family can be written as Pn(x;q) = ∑m = 0nDm(n)m(x) where m(x) stands for (x;q)mor xm. In this paper we solve the corresponding inversion problem, i.e. we find the explicit expression for the coefficients Im(n) in the expansion n(x) = ∑m = 0nIm(n)Pm(x;q). 相似文献
9.
10.
P. W. Eloe 《Computers & Mathematics with Applications》1998,36(10-12)
The concept of concavity is generalized to discrete functions, u, satisfying the nth-order difference inequality, (−1)n−kΔnu(m) ≥ 0, M = 0, 1,..., N and the homogeneous boundary conditions, u(0) = … = u(k−1) = 0, u(N + k + 1) = … = u(N + n) = 0 for some k “1, …, n − 1”. A piecewise polynomial is constructed which bounds u below. The piecewise polynomial is employed to obtain a positive lower bound on u(m) for m = k, …, N + k, where the lower bound is proportional to the supremum of u. An analogous bound is obtained for a related Green's function. 相似文献
11.
P. N. Denisenko 《Cybernetics and Systems Analysis》2011,47(3):466-480
An algebraic algorithm is developed for computing an algebraic polynomial y
n
of order n ∈ N in computer algebra systems. This polynomial is the optimal approximation of the solution y = y(x), x ∈ [a,b], to a system of linear differential equations with polynomial coefficients and initial conditions at a regular singular
zero point of this equation in a space C[ a,b ]k C_{\left[ {a,b} \right]}^k . 相似文献
12.
Inapproximability of the Tutte polynomial 总被引:2,自引:0,他引:2
The Tutte polynomial of a graph G is a two-variable polynomial T(G;x,y) that encodes many interesting properties of the graph. We study the complexity of the following problem, for rationals x and y: take as input a graph G, and output a value which is a good approximation to T(G;x,y). Jaeger et al. have completely mapped the complexity of exactly computing the Tutte polynomial. They have shown that this is #P-hard, except along the hyperbola (x-1)(y-1)=1 and at four special points. We are interested in determining for which points (x,y) there is a fully polynomial randomised approximation scheme (FPRAS) for T(G;x,y). Under the assumption RP≠NP, we prove that there is no FPRAS at (x,y) if (x,y) is in one of the half-planes x<-1 or y<-1 (excluding the easy-to-compute cases mentioned above). Two exceptions to this result are the half-line x<-1,y=1 (which is still open) and the portion of the hyperbola (x-1)(y-1)=2 corresponding to y<-1 which we show to be equivalent in difficulty to approximately counting perfect matchings. We give further intractability results for (x,y) in the vicinity of the origin. A corollary of our results is that, under the assumption RP≠NP, there is no FPRAS at the point (x,y)=(0,1-λ) when λ>2 is a positive integer. Thus, there is no FPRAS for counting nowhere-zero λ flows for λ>2. This is an interesting consequence of our work since the corresponding decision problem is in P for example for λ=6. Although our main concern is to distinguish regions of the Tutte plane that admit an FPRAS from those that do not, we also note that the latter regions exhibit different levels of intractability. At certain points (x,y), for example the integer points on the x-axis, or any point in the positive quadrant, there is a randomised approximation scheme for T(G;x,y) that runs in polynomial time using an oracle for an NP predicate. On the other hand, we identify a region of points (x,y) at which even approximating T(G;x,y) is as hard as #P. 相似文献
13.
A two-dimensional arrayA={a[i, j]} is calledtotally monotone if, for alli
1i
2 andj
1j
2,a[i
1,j
1]a[i
1,j
2] impliesa[i
2,j
1]a[i
2,j
2]. Totally monotone arrays were introduced in 1987 by Aggarwal, Klawe, Moran, Shor, and Wilber, who showed that several problems in computational geometry and VLSI river routing could be reduced to the problem of finding a maximum entry in each row of a totally monotone array. In this paper we consider several selection and sorting problems involving totally monotone arrays and give a number of applications of solutions for these problems. In particular, we obtain the following results for anm × n totally monotone arrayA:
An earlier version of this paper appeared inProceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms, pages 494–502, January 1990. Portions of the paper also appeared in Dina Kravets' S.M. thesis [Kr]. The work of D. Kravets was supported in part by the Air Force under Contract OSR-86-0076, the Defense Advanced Research Projects Agency under Contract N00014-89-J-1988, and the Army under Contract DAAL-03-86-K-0171. J. K. Park's work was supported in part by the Defense Advanced Research Projects Agency under Contract N00014-87-K-0825, the Office of Naval Research under Contract N00014-86-K-0593, and an NSF Graduate Fellowship. 相似文献
1. | Thek largest (ork smallest) entries in each row ofA can be computed inO(k(m + n)) time. This result allows us to determine thek farthest (ork nearest) neighbors of each vertex of a convexn-gon inO(kn) time. |
2. | Provided the transpose ofA is also totally monotone, thek largest (ork smallest) entries overall inA can be computed inO(m + n + k lg(mn/k)) time. This result allows us to find thek farthest (ork nearest) pairs of vertices from a convexn-gon inO(n + k lg(n 2/k)) time. |
3. | The rows ofA can be sorted inO(mn) time whenm n and inO(mn(1 + lg(n/m))) time whenm <>. This result allows us to solve the of (S) on the number of combinations of row permutations possible for a totally monotone array would imply an (lgS) lower bound on the time necessary to sort the array's rows in a linear decision tree model.) |
4. | In Subsection 4.2 we applied our algorithm for sorting the rows of a totally monotone array to the neighbor-ranking problem for the vertices of a convex polygonP. We then extended this technique to arbitrary point sets. It remains open whether our two selection algorithms for totally monotone arrays, which we also applied to the vertices of a convex polygon, can likewise be applied to arbitrary point sets. |
14.
We consider the multivariate interlace polynomial introduced by Courcelle (Electron. J. Comb. 15(1), 2008), which generalizes several interlace polynomials defined by Arratia, Bollobás, and Sorkin (J. Comb. Theory Ser. B 92(2):199–233,
2004) and by Aigner and van der Holst (Linear Algebra Appl., 2004). We present an algorithm to evaluate the multivariate interlace polynomial of a graph with n vertices given a tree decomposition of the graph of width k. The best previously known result (Courcelle, Electron. J. Comb. 15(1), 2008) employs a general logical framework and leads to an algorithm with running time f(k)⋅n, where f(k) is doubly exponential in k. Analyzing the GF(2)-rank of adjacency matrices in the context of tree decompositions, we give a faster and more direct algorithm. Our algorithm
uses 23k2+O(k)·n2^{3k^{2}+O(k)}\cdot n arithmetic operations and can be efficiently implemented in parallel. 相似文献
15.
H. Hermes 《Systems & Control Letters》1987,8(4)
Let X1,…, Xk be real analytic vector fields on an n-dimensional manifold M, k < n, which are linearly independent at a point p ε M and which, together with their Lie products at p, span the tangent space TMp. Then X1,…, Xk form a local basis for a real analytic k-dimensional distribution x→Dk(x)=span{X1(x),…,Xk(x)}. We study the question of when Dk admits a basis which generates a nilpotent, or solvable (or finite dimensional) Lie algebra. If this is the case the study of affine control systems, or partial differential operators, described via X1,…, Xk can often be greatly simplified. 相似文献
16.
A graph G of order n (≥2) is said to be panconnected if for each pair (x,y) of vertices of G there exists an xy-path of length ℓ for each ℓ such that d
G
(x,y)≤ℓ≤n−1, where d
G
(x,y) denotes the length of a shortest xy-path in G. In this paper, we consider the panconnectivity of Cartesian product graphs. As a consequence of our results, we prove that
the n-dimensional generalized hypercube Q
n
(k
1,k
2,…,k
n
) is panconnected if and only if k
i
≥3 (i=1,…,n), which generalizes a result of Hsieh et al. that the 3-ary n-cube
Q3nQ^{3}_{n}
is panconnected. 相似文献
17.
Plant template generation is the key step in applying quantitative feedback theory (QFT) to design robust control for uncertain systems. In this paper we propose a technique for generating plant templates for a class of linear systems with an uncertain time delay and affine parameter perturbations in coefficients. The main contribution lies in presenting a necessary and sufficient condition for the zero inclusion of the value set f(T,Q)={f(τ,q): τT[τ−,τ+], qQ∏k=0m−1[qk−,qk+]}, where f(τ,q)=g(q)+h(q)e−jτω*, g(q) and h(q) are both complex-valued affine functions of the m-dimensional real vector q, and ω* is a fixed frequency. Based on this condition, an efficient algorithm which involves, in the worst case, evaluation of m algebraic inequalities and solution of m2m−1 one-variable quadratic equations, is developed for testing the zero inclusion of the value set f(T,Q). This zero-inclusion test algorithm allows one to utilize a pivoting procedure to generate the outer boundary of a plant template with a prescribed accuracy or resolution. The proposed template generation technique has a linear computational complexity in resolution and is, therefore, more efficient than the parameter gridding and interval methods. A numerical example illustrating the proposed technique and its computational superiority over the interval method is included. 相似文献
18.
19.
Rhonda Righter 《Systems & Control Letters》1988,10(4)
We consider a sequencing problem in which there are n jobs to be processed nonpreemptively on m nonidentical processors. The processing time of the j-th processor is exponentially distributed with rate μj, where μ1μ2μm. Job i incurs a holding cost at rate ci per unit time while still in the system, where c1c2cn. We show that to minimize total expected holding costs (weighted flowtime), it is optimal to take the fastest (lowest indexed) available processor, say processor j, and assign job k to it if k>(Σij−1μi)/μj−j k−1. After each assignment the jobs are renumbered (so that job k+1 becomes job k, etc.), and the procedure is repeated with the next fastest available processor, etc. Note that the policy does not depend on the values of the holding costs ci. This result is a generalization of the result of Agrawala et al. (1984) for minimizing expected flowtime, i.e., minimizing total holding cost when the holding costs of all the jobs are the same. We give a simpler proof of the more general result. 相似文献
20.
Letk be an infinite and perfect field,x
1, ...,x
n
indeterminates overk and letf
1, ...,f
s
be polynomials ink[x
1, ...,x
n
] of degree bounded by a given numberd, which satisfiesdn. We prove an effective affine Nullstellensatz of the following particular form:For arbitrary given parametersd, s, n there exists a probabilistic (randomized) arithmetic network overk of sizes
O(1)
d
O(n)
and depthO(n
4log2
sd) solving the following task: 相似文献