共查询到20条相似文献,搜索用时 13 毫秒
1.
HereR andN denote respectively the real numbers and the nonnegative integers. Also 0 <n εN, ands(x) =x
1+...+x
n when x = (x
1,...,x
n) εR
n. Adiagonal function of dimensionn is a mapf onN
n (or any larger set) that takesN
n bijectively ontoN and, for all x, y inN
n, hasf(x) <f(y) whenevers(x) <s(y). We show that diagonalpolynomials f of dimensionn all have total degreen and have the same terms of that degree, so that the lower-degree terms characterize any suchf. We call two polynomialsequivalent if relabeling variables makes them identical. Then, up to equivalence, dimension two admits just one diagonal polynomial,
and dimension three admits just two. 相似文献
2.
Maurice Jansen 《Theory of Computing Systems》2011,49(2):343-354
The determinantal complexity of a polynomial f(x
1,x
2,…,x
n
) is the minimum m such that f=det
m
(L(x
1,x
2,…,x
n
)), where L(x
1,x
2,…,x
n
) is a matrix whose entries are affine forms in the x
i
s over some field $\mbox {$\mbox {. 相似文献
3.
HereN = {0, 1, 2, ...}, while a functionf onN
m or a larger domain is apacking function if its restrictionf|N
m is a bijection ontoN. (Packing functions generalize Cantor's [1]pairing polynomials, and yield multidimensional-array storage schemes.) We call two functionsequivalent if permuting arguments makes them equal. Alsos(x) =x
1 + ... +x
m when x = (x
1,...,x
m); and such anf is adiagonal mapping iff(x) <f(y) whenever x, y εN
m ands(x) <s(y). Lew [7] composed Skolem's [14], [15] diagonal packing polynomials (essentially one for eachm) to constructc(m) inequivalent nondiagonal packing polynomials on eachN
m. For eachm > 1 we now construct 2m−2 inequivalent diagonal packing polynomials. Then, extending the tree arguments of the prior work, we obtaind(m) inequivalent nondiagonal packing polynomials, whered(m)/c(m) → ∞ asm → ∞. Among these we count the polynomials of extremal degree. 相似文献
4.
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. 相似文献
5.
Conclusion In the optimization problem [f
0(x)│hi(x)<-0,i=1,…,l] relaxation of the functionf
0(x)+Nh+(x) does not produce, as we know [6, 7], αk=1 in Newton's method with the auxiliary problem (5), (6), whereF(x)=f
0′(x). For this reason, Newton type methods based on relaxation off
0(x)+Nh+(x) are not superlinearly convergent (so-called Maratos effect). The results of this article indicate that if (F(x)=f
0′(x), then replacement of the initial optimization problem with a larger equivalent problem (7) eliminates the Maratos effect
in the proposed quasi-Newton method. This result is mainly of theoretical interest, because Newton type optimization methods
in the space of the variablesx ∈R
n are less complex. However to the best of our knowledge, the difficulties with nonlocal convergence arising in these methods
(choice of parameters, etc.) have not been fully resolved [10, 11]. The discussion of these difficulties and comparison with
the proposed method fall outside the scope of the present article, which focuses on solution of variational inequalities (1),
(2) for the general caseF′(x)≠F′
T(x).
Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 78–91, November–December, 1994. 相似文献
6.
It is proved that the system of word equations x
i
1=y
i
1
y
i
2…y
i
n
, i=1, 2,…, ⌈n/2⌉ +1, has only cyclic solutions. Some sharpenings concerning the cases n=5, 7 and n≥9 are derived as well as results concerning the general system of equations x
i
1
x
i
2…x
i
m
=y
i
1
y
i
2…y
i
n
, i=1, 2,… . Applications to test sets of certain bounded languages are considered.
Received: 18 May 1995/2 January 1996 相似文献
7.
L. Rocha 《Computing》1997,59(3):187-207
LetG be a compact set in ℝ
d
d≥1,M=G×G andϕ:M →G a map inC
3(M). Suppose thatϕ has a fixed pointξ, i.e.ϕ(ξ, ξ)=ξ. We investigate the rate of convergence of the iterationx
n+2=φ(x
n+1,x
n) withx
0,x
1∈G andx
n→ξ. Iff
n=Q‖x
n−ξ‖ with a suitable norm and a constantQ depending onξ, an exact representation forf
n is derived. The error terms satisfyf
2m+1≍(ƒ2m)γ,f
2m+2≍(ƒ2m+1)2γ,m≥0, with 1<gg<2, andγ=γ(x
1,x
0). According to our main result we have limn→∞{‖x
n+2‖/(‖x
n‖)2}=Q, 0<Q<∞.
This paper constitutes an extension of a part of the author’s doctoral thesis realized under the direction of Prof. E. Wirsing
and Prof. A. Peyerimhoff, University of Ulm (Germany). 相似文献
8.
The optimal least-squares filtering of a diffusion x(t) from its noisy measurements {y(τ); 0 τ t} is given by the conditional mean E[x(t)|y(τ); 0 τ t]. When x(t) satisfies the stochastic diffusion equation dx(t) = f(x(t)) dt + dw(t) and y(t) = ∫0tx(s) ds + b(t), where f(·) is a global solution of the Riccati equation /xf(x) + f(x)2 = f(x)2 = αx2 + βx + γ, for some
, and w(·), b(·) are independent Brownian motions, Benes gave an explicit formula for computing the conditional mean. This paper extends Benes results to measurements y(t) = ∫0tx(s) ds + ∫0t dx(s) + b(t) (and its multidimensional version) without imposing additional conditions on f(·). Analogous results are also derived for the optimal least-squares smoothed estimate E[x(s)|y(τ); 0 τ t], s < t. The methodology relies on Girsanov's measure transformations, gauge transformations, function space integrations, Lie algebras, and the Duncan-Mortensen-Zakai equation. 相似文献
9.
We consider a nonlinear discrete-time system of the form Σ: x(t+1)=f(x(t), u(t)), y(t) =h(x(t)), where x ε RN, u ε Rm, y ε Rq and f and h are analytic. Necessary and sufficient conditions for local input-output linearizability are given. We show that these conditions are also sufficient for a formal solution to the global input-output linearization problem. Finally, we show that zeros at infinity of ε can be obtained by the structure algorithm for locally input-output linearizable systems. 相似文献
10.
Fork functionsf
1, ...f
k, ak-tuple (x
1, ...x
k) such thatf
1(x
1)=...=f
k(x
k) is called a claw off
1, ...,f
k. In this paper, we construct a new quantum claw-finding algorithm for three functions that is efficient when the numberM of intermediate solutions is small. The known quantum claw-finding algorithm for three functions requiresO(N
7/8 logN) queries to find a claw, but our algorithm requiresO(N
3/4 logN) queries ifM ≤ √N andO(N
7/12
M
1/3 logN) queries otherwise. Thus, our algorithm is more efficient ifM≤N
7/8.
Kazuo Iwama, Ph.D.: Professor of Informatics, Kyoto University, Kyoto 606-8501, Japan. Received BE, ME, and Ph.D. degrees in Electrical Engineering
from Kyoto University in 1978, 1980 and 1985, respectively. His research interests include algorithms, complexity theory and
quantum computation. Editorial board of Information Processing Letters and Parallel Computing. Council Member of European
Association for Theoretical Computer Science (EATCS).
Akinori Kawachi: Received B.Eng. and M.Info. from Kyoto University in 2000 and 2002, respectively. His research interests are quantum computation
and distributed computation. 相似文献
11.
A point (x*,λ*) is called apitchfork bifurcation point of multiplicityp≥1 of the nonlinear systemF(x, λ)=0,F:ℝn×ℝ1→ℝn, if rank∂
xF(x*, λ*)=n−1, and if the Ljapunov-Schmidt reduced equation has the normal formg(ξ, μ)=±ξ
2+
p±μξ=0. It is shown that such points satisfy a minimally extended systemG(y)=0,G:ℝ
n+2→ℝn+2 the dimensionn+2 of which is independent ofp. For solving this system, a two-stage Newton-type method is proposed. Some numerical tests show the influence of the starting
point and of the bordering vectors used in the definition of the extended system on the behavior of the iteration. 相似文献
12.
Tadeusz Banek 《Systems & Control Letters》1988,11(4)
Under some regularity assumptions and the following generalization of the well-known Bene
condition [1]:
, where F(t,z) = g−2(t)∫f(t,z)dz, Ft, Fz, Fzz, are partial derivatives of F, we obtain explicit formulas for the unnormalized conditional density qt(z, x) α Pxt ε dz| ys, 0 st, where diffusion xt on R1 solves x0 = x, dxt = [β(t) + α(t)xt + f(t, xt] dt + g(t) dw1, and observation yt = ∫oth(s)xs ds + ∫ot(s) dw2t, with w = (w1, w2) a two-dimensional Wiener process. 相似文献
Full-size image
13.
LetG andH be graphs with |V(G)≤ |V(H)|. Iff:V(G) →V(H) is a one-to-one map, we letdilation(f) be the maximum of dist
H
(f
x),f(y)) over all edgesxy inG where dist
H
denotes distance inH. The construction of maps fromG toH of small dilation is motivated by the problem of designing small slowdown simulations onH of algorithms that were originally designed for the networkG.
LetS(n), thestar network of dimension n, be the graph whose vertices are the elements of the symmetric group of degreen, two verticesx andy being adjacent ifx o (1,i) =y for somei. That is,xy is an edge ifx andy are related by a transposition involving some fixed symbol (which we take to be 1). Also letP(n), thepancake network of dimension n, be the graph whose vertices are the elements of the symmetric group of degreen, two verticesx andy being adjacent if one can be obtained from the other by reversing some prefix. That is,xy is an edge ifx andy are related byx o (1,i(2,i-1) ⋯ ([i/2], [i/2]) =y. The star network (introduced in [AHK]) has nice symmetry properties, and its degree and diameter are sublogarithmic as functions
of the number of vertices, making it compare favorably with the hypercube network. These advantages ofS(n) motivate the study of how well it can simulate other parallel computation networks, in particular, the hypercube.
The concern of this paper is to construct low dilation maps of hypercube networks into star or pancake networks. Typically
in such problems, there is a tradeoff between keeping the dilationsmall and simulating alarge hypercube. Our main result shows that at the cost ofO (1) dilation asn→ ∞, one can embed a hypercube of near optimum dimension into the star or pancake networksS(n) orP(n).
More precisely, lettingQ (d) be the hypercube of dimensiond, our main theorem is stated below. For simplicity, we state it only in the special case when the star network dimension is
a power of 2. A more general result (applying to star networks of arbitrary dimension) is obtained by a simple interpolation.
This author's research was done during the Spring Semester 1991, as a visiting professor in the Department of Mathematics
and Statistics at Miami University. 相似文献
14.
Prof. Dr. H. Esser 《Computing》1975,14(4):367-369
It is shown that the following modification of the Steffensen procedurex n+1=x n ?k s (x n )f(x n ) (f[x n ,x n ?f(x n )])?1 (n=0,1,...) withk s (x)=(1?z s (x))?1,z s (x)=f(x) 2f[x?f(x),x,x+f(x)]×(f[x,x?f(x)])?2 is quadratically convergent to the root of the equation \(f(x) = (x - \bar x)^p g(x) = 0(p > 0,g(\bar x) \ne 0)\) . Furthermore \(\mathop {\lim }\limits_{n \to \infty } k_s (x_n ) = p\) holds. 相似文献
15.
16.
V. I. Levin 《Cybernetics and Systems Analysis》2012,48(2):304-312
The problem of synthesis of a dynamic process in some prescribed form at the output of a logical (n,1)-port device is formulated for a given dependence b = f(a
1,…, a
n
) of switching the output signal on moments a
1,…, a
n
of switching input signals, where f is a continuous-logic function. A regular procedure is proposed to solve the problem
by constructing an (n,1)-port device that implements the required dependence f. Solutions for all possible typical cases and a solution algorithm for the general case are given. 相似文献
17.
There are two main fuzzy system methodologies for translating expert rules into a logical formula: In Mamdani's methodology, we get a DNF formula (disjunction of conjunctions), and in a methodology which uses logical implications, we get, in effect, a CNF formula (conjunction of disjunctions). For both methodologies, universal approximation results have been proven which produce, for each approximated function f(x), two different approximating relations RDNF(x, y) and RCNF(x, y). Since, in fuzzy logic, there is a known relation FCNF(x) ≤ FDNF(x) between CNF and DNF forms of a propositional formula F, it is reasonable to expect that we would be able to prove the existence of approximations for which a similar relation RCNF(x, y) ≤ RDNF(x, y) holds. Such existence is proved in our paper. © 2002 Wiley Periodicals, Inc. 相似文献
18.
P. Baratella 《Calcolo》1977,14(3):237-242
In this paper we study the remainder term of a quadrature formula of the form $$\int\limits_{ - 1}^1 {f(x)dx = A_n \left[ {f( - 1) + f(1)} \right] + C_n \sum\limits_{i = 1}^n {f(x_{n,i} ) + R_n \left[ f \right],} } $$ , withx x,i ∈-1,1, andR n [f]=0 whenf(x) is a polynomial of degree ≤n+3 ifn is even, or ≤n+2 ifn is odd. Such a formula exists only forn=1(1)11. It is shown that, iff(x)∈ C(h+1) [-1,1], (h=n+3 orn+2), thenR n [f]=f h+1 (τ)·± n . The values α n are given. 相似文献
19.
Embedding of Cycles in Twisted Cubes with Edge-Pancyclic 总被引:1,自引:0,他引:1
In this paper, we study the embedding of cycles in twisted cubes. It has been proven in the literature that, for any integer
l, 4≤l≤2
n
, a cycle of length l can be embedded with dilation 1 in an n-dimensional twisted cube, n≥3. We obtain a stronger result of embedding of cycles with edge-pancyclic. We prove that, for any integer l, 4≤l≤2
n
, and a given edge (x,y) in an n-dimensional twisted cube, n≥3, a cycle C of length l can be embedded with dilation 1 in the n-dimensional twisted cube such that (x,y) is in C in the twisted cube. Based on the proof of the edge-pancyclicity of twisted cubes, we further provide an O(llog l+n
2+nl) algorithm to find a cycle C of length l that contains (u,v) in TQ
n
for any (u,v)∈E(TQ
n
) and any integer l with 4≤l≤2
n
. 相似文献
20.
The problem of finding approximate solutions for a subclass of multicovering problems denoted byILP(k, b) is considered. The problem involves findingx∈{0,1}
n
that minimizes ∑
j
x
j
subject to the constraintAx≥b, whereA is a 0–1m×n matrix with at mostk ones per row,b is an integer vector, andb is the smallest entry inb. This subclass includes, for example, the Bounded Set Cover problem whenb=1, and the Vertex Cover problem whenk=2 andb=1.
An approximation ratio ofk−b+1 is achievable by known deterministic algorithms. A new randomized approximation algorithm is presented, with an approximation
ratio of (k−b+1)(1−(c/m)1/(k−b+1)) for a small constantc>0. The analysis of this algorithm relies on the use of a new bound on the sum of independent Bernoulli random variables,
that is of interest in its own right.
The first author was supported in part by a Walter and Elise Haas Career Development Award and by a grant from the Israeli
Science Foundation. This work was done white the third author was at the Department of Applied Mathematics and Computer Science,
The Weizmann Institute, Rehovot 76100, Israel. 相似文献