共查询到20条相似文献,搜索用时 921 毫秒
1.
Marc Hellmuth Wilfried Imrich Werner Klöckl Peter F. Stadler 《Mathematics in Computer Science》2009,2(4):653-682
The practical application of graph prime factorization algorithms is limited in practice by unavoidable noise in the data.
A first step towards error-tolerant “approximate” prime factorization, is the development of local approaches that cover the
graph by factorizable patches and then use this information to derive global factors. We present here a local, quasi-linear
algorithm for the prime factorization of “locally unrefined” graphs with respect to the strong product. To this end we introduce
the backbone
\mathbbB (G)\mathbb{B} (G) for a given graph G and show that the neighborhoods of the backbone vertices provide enough information to determine the global prime factors. 相似文献
2.
Two interior-point algorithms are proposed and analyzed, for the (local) solution of (possibly) indefinite quadratic programming
problems. They are of the Newton-KKT variety in that (much like in the case of primal-dual algorithms for linear programming)
search directions for the “primal” variables and the Karush-Kuhn-Tucker (KKT) multiplier estimates are components of the Newton
(or quasi-Newton) direction for the solution of the equalities in the first-order KKT conditions of optimality or a perturbed
version of these conditions. Our algorithms are adapted from previously proposed algorithms for convex quadratic programming
and general nonlinear programming. First, inspired by recent work by P. Tseng based on a “primal” affine-scaling algorithm
(à la Dikin) [J. of Global Optimization, 30 (2004), no. 2, 285–300], we consider a simple Newton-KKT affine-scaling algorithm. Then, a “barrier” version of the same algorithm is considered, which reduces to the affine-scaling version when the barrier parameter is set
to zero at every iteration, rather than to the prescribed value. Global and local quadratic convergence are proved under nondegeneracy
assumptions for both algorithms. Numerical results on randomly generated problems suggest that the proposed algorithms may
be of great practical interest.
The work of the first author was supported in part by the School of Computational Science of Florida State University through
a postdoctoral fellowship. Part of this work was done while this author was a Research Fellow with the Belgian National Fund
for Scientific Research (Aspirant du F.N.R.S.) at the University of Liège. The work of the second author was supported in
part by the National Science Foundation under Grants DMI9813057 and DMI-0422931 and by the US Department of Energy under Grant
DEFG0204ER25655. Any opinions, findings, and conclusions or recommendations expressed in this paper are those of the authors
and do not necessarily reflect the views of the National Science Foundation or those of the US Department of Energy. 相似文献
3.
V. A. Berezin 《Theoretical and Mathematical Physics》2012,170(1):71-82
We build a model in which the main global properties of classical and semiclassical black holes become local: these are the
event horizon, “no-hair,” temperature, and entropy. Our construction is based on the features of a quantum collapse, discovered
when studying some particular quantum black hole models. But our model is purely classical, and this allows using the Einstein
equations and classical (local) thermodynamics self-consistently and, in particular, solving the “puzzle of log 3.” 相似文献
4.
Alessio Moretti 《Logica Universalis》2009,3(1):19-57
Whereas geometrical oppositions (logical squares and hexagons) have been so far investigated in many fields of modal logic
(both abstract and applied), the oppositional geometrical side of “deontic logic” (the logic of “obligatory”, “forbidden”,
“permitted”, . . .) has rather been neglected. Besides the classical “deontic square” (the deontic counterpart of Aristotle’s
“logical square”), some interesting attempts have nevertheless been made to deepen the geometrical investigation of the deontic
oppositions: Kalinowski (La logique des normes, PUF, Paris, 1972) has proposed a “deontic hexagon” as being the geometrical
representation of standard deontic logic, whereas Joerden (jointly with Hruschka, in Archiv für Rechtsund Sozialphilosophie
73:1, 1987), McNamara (Mind 105:419, 1996) and Wessels (Die gute Samariterin. Zur Struktur der Supererogation, Walter de Gruyter,
Berlin, 2002) have proposed some new “deontic polygons” for dealing with conservative extensions of standard deontic logic
internalising the concept of “supererogation”. Since 2004 a new formal science of the geometrical oppositions inside logic
has appeared, that is “n-opposition theory”, or “NOT”, which relies on the notion of “logical bi-simplex of dimension m” (m = n − 1). This theory has received a complete mathematical foundation in 2008, and since then several extensions. In this paper,
by using it, we show that in standard deontic logic there are in fact many more oppositional deontic figures than Kalinowski’s
unique “hexagon of norms” (more ones, and more complex ones, geometrically speaking: “deontic squares”, “deontic hexagons”,
“deontic cubes”, . . ., “deontic tetraicosahedra”, . . .): the real geometry of the oppositions between deontic modalities
is composed by the aforementioned structures (squares, hexagons, cubes, . . ., tetraicosahedra and hyper-tetraicosahedra),
whose complete mathematical closure happens in fact to be a “deontic 5-dimensional hyper-tetraicosahedron” (an oppositional
very regular solid).
相似文献
5.
In this paper, we prove that any weak solution to the non-stationary Stokes system in 3D with right hand side -div f satisfying (1.4) below, belongs to C( ]0, T[; C
α (Ω)). The proof is based on Campanato-type inequalities and the existence of a local pressure introduced in Wolf [13].
Proc. Conference “Variational analysis and PDE’s”. Intern. Centre “E. Majorana”, Erice, July 5–14, 2006. 相似文献
6.
This paper deals with regular singular generalized q-hypergeometric equations with either “large” or “small” Galois groups. In particular, we consider the fundamental problem
of finding appropriate Galoisian substitutes for the usual notion of local monodromy. 相似文献
7.
J. Sakalauskaitė 《Lithuanian Mathematical Journal》2007,47(3):266-276
In this paper, we consider branching time temporal logic CT L with epistemic modalities for knowledge (belief) and with awareness operators. These logics involve the discrete-time linear
temporal logic operators “next” and “until” with the branching temporal logic operator “on all paths”. In addition, the temporal
logic of knowledge (belief) contains an indexed set of unary modal operators “agent i knows” (“agent i believes”). In a language of these logics, there are awareness operators. For these logics, we present sequent calculi with
a restricted cut rule. Thus, we get proof systems where proof-search becomes decidable. The soundness and completeness for
these calculi are proved.
Published in Lietuvos Matematikos Rinkinys, Vol. 47, No. 3, pp. 328–340, July–September, 2007. 相似文献
8.
The second order approach of local influence (see [15]) is developed and applied to Cox’s proportional hazards model, and
compared with Cook's local influence approach (see [6] and [13]) which was used in this model. To study local influence, we
perturb not only all cases simultaneously, but also cases individually to obtain “direction curvature” in directionl and “curvature” for single case. Some examples are used to illustrate these methods.
This work is supported by the Youth Science Foundation of Peking University and a research grant from State Educational Committee 相似文献
9.
The Generalized Riemann Problem (GRP) for a nonlinear hyperbolic system of m balance laws (or alternatively “quasi-conservative” laws) in one space dimension is now well-known and can be formulated
as follows: Given initial-data which are analytic on two sides of a discontinuity, determine the time evolution of the solution
at the discontinuity. In particular, the GRP numerical scheme (second-order high resolution) is based on an analytical evaluation
of the first time derivative. It turns out that this derivative depends only on the first-order spatial derivatives, hence
the initial data can be taken as piecewise linear. The analytical solution is readily obtained for a single equation (m = 1) and, more generally, if the system is endowed with a complete (coordinate) set of Riemann invariants. In this case it
can be “diagonalized” and reduced to the scalar case. However, most systems with m > 2 do not admit such a set of Riemann invariants. This paper introduces a generalization of this concept: weakly coupled
systems (WCS). Such systems have only “partial set” of Riemann invariants, but these sets are weakly coupled in a way which
enables a “diagonalized” treatment of the GRP. An important example of a WCS is the Euler system of compressible, nonisentropic
fluid flow (m = 3). The solution of the GRP discussed here is based on a careful analysis of rarefaction waves. A “propagation of singularities”
argument is applied to appropriate Riemann invariants across the rarefaction fan. It serves to “rotate” initial spatial slopes
into “time derivative”. In particular, the case of a “sonic point” is incorporated easily into the general treatment. A GRP
scheme based on this solution is derived, and several numerical examples are presented. Special attention is given to the
“acoustic approximation” of the analytical solution. It can be viewed as a proper linearization (different from the approach
of Roe) of the nonlinear system. The resulting numerical scheme is the simplest (second-order, high-resolution) generalization
of the Godunov scheme. 相似文献
10.
Representations of solutions of boundary value problems for simple domains in the Monte Carlo algorithms are widely distributed
[2]. In particular, widespread use is made of such a representation for the ball. It allows one to formally write an integral
equation of the second kind for the required function in an arbitrary domain with regular boundary. Moreover, with the involvement
of the joining conditions [1], one can picture a possible construction of a random process to “solve” the problem. However,
the “walk in spheres” process, which solves the first boundary value problem for the Poisson equation, results in ɛ-biased estimators, and so the introduction of a regularization parameter is required.
The authors investigate in detail the “walk in hemispheres” method, which has been proposed earlier by A. S. Sipin [10] without
full justification. The use of the Green’s function for the hemisphere makes it possible to obtain estimators for the first
and the third boundary value problems, as well as for the problem with discontinuous derivative; for a broad class of domains,
these estimators are shown to be unbiased. The algorithms proposed feature a high degree of parallelism. Results of solving
model problems are presented. 相似文献
11.
Aubrey Blecher Charlotte Brennan Toufik Mansour 《Central European Journal of Mathematics》2012,10(2):788-796
Compositions and partitions of positive integers are often studied in separate frameworks where partitions are given by q-series generating functions and compositions exhibiting specific patterns are designated by generating functions for these
patterns. Here, we view compositions as alternating sequences of weakly increasing and strictly decreasing partitions (i.e.
alternating blocks). We obtain generating functions for the number of such partitions in terms of the size of the composition,
the number of parts and the total number of “valleys” and “peaks”. From this, we find the total number of “peaks” and “valleys”
in the composition of n which have the mentioned pattern. We also obtain the generating function for compositions which split into just two partition
blocks. Finally, we obtain the two generating functions for compositions of n that start either with a weakly increasing partition or a strictly decreasing partition. 相似文献
12.
O. D. Frolkina 《Moscow University Mathematics Bulletin》2009,64(6):253-258
In 1998, Y. Benyamini published interesting results concerning interpolation of sequences using continuous functions ℝ → ℝ.
In particular, he proved that there exists a continuous function ℝ → ℝ which in some sense “interpolates” all sequences (x
n
)
n∈ℤ ∈ [0, 1]ℤ “simultaneously.” In 2005, M.R. Naulin and C. Uzcátegui unified and generalized Benyamini’s results. In this paper, the case
of topological spaces X and Y with an Abelian group acting on X is considered. A similar problem of “simultaneous interpolation” of all “generalized sequences” using continuous mappings
X → Y is posed. Further generalizations of Naulin-Uncátegui theorems, in particular, multidimensional analogues of Benyamini’s
results are obtained. 相似文献
13.
Maria E. Vares 《Bulletin of the Brazilian Mathematical Society》1981,12(2):33-55
Summary In this article we consider some problems on local growth of 2-parameter Lévy processes, i.e., processes with independent
and stationary increments, indexed by [0,+∞)×[0,+∞). The results are for the upper growth of these processes, at a fixed “time”z
0. 相似文献
14.
We study the R-controllability (the controllability within the attainability set) and the R-observability of time-varying linear differential-algebraic equations (DAE). We analyze DAE under assumptions guaranteeing
the existence of a structural form (which is called “equivalent”) with separated “differential” and “algebraic” subsystems.
We prove that the existence of this form guarantees the solvability of the corresponding conjugate system, and construct the
corresponding “equivalent form” for the conjugate DAE. We obtain conditions for the R-controllability and R-observability, in particular, in terms of controllability and observability matrices. We prove theorems that establish certain
connections between these properties. 相似文献
15.
C. Zălinescu 《Optimization Letters》2012,6(3):393-402
In their paper “Duality of linear conic problems” Shapiro and Nemirovski considered two possible properties (A) and (B) for
dual linear conic problems (P) and (D). The property (A) is “If either (P) or (D) is feasible, then there is no duality gap
between (P) and (D)”, while property (B) is “If both (P) and (D) are feasible, then there is no duality gap between (P) and
(D) and the optimal values val(P) and val(D) are finite”. They showed that (A) holds if and only if the cone K is polyhedral, and gave some partial results related to (B). Later Shapiro conjectured that (B) holds if and only if all
the nontrivial faces of the cone K are polyhedral. In this note we mainly prove that both the “if” and “only if” parts of this conjecture are not true by providing
examples of closed convex cone in
\mathbbR4{\mathbb{R}^{4}} for which the corresponding implications are not valid. Moreover, we give alternative proofs for the results related to (B)
established by Shapiro and Nemirovski. 相似文献
16.
Sonsoles Pérez 《Journal of Geometric Analysis》2001,11(3):491-507
In this work we present several theorems which imply the weak type 1 with respect to the Gaussian measure for the so-called
local part of certain operators associated with the Ornstein-Uhlenbeck semigroup. Particular cases of these operators are
the Riesz transforms of any order and the Littlewood-Paley square function. Also, we study general results based on the “size”
of the operator which ensure the strong type 1 <p < ∞of both the local and global parts. 相似文献
17.
Ahlswede Rudolf Khachatrian Levon H. Mauduit C. Sárközy A. 《Periodica Mathematica Hungarica》2003,46(2):107-118
In earlier papers finite pseudorandom binary sequences were studied, quantitative measures of pseudorandomness of them were
introduced and studied, and large families of “good” pseudorandom sequences were constructed. In certain applications (cryptography)
it is not enough to know that a family of “good” pseudorandom binary sequences is large, it is a more important property if
it has a “rich”, “complex” structure. Correspondingly, the notion of “f-complexity” of a family of binary sequences is introduced. It is shown that the family of “good” pseudorandom binary sequences
constructed earlier is also of high f-complexity. Finally, the cardinality of the smallest family achieving a prescibed f-complexity and multiplicity is estimated.
This revised version was published online in August 2006 with corrections to the Cover Date. 相似文献
18.
19.
It is well known that in the computation of Gr?bner bases arbitrarily small perturbations in the coefficients of polynomials
may lead to a completely different staircase, even if the solutions of the polynomial system change continuously. This phenomenon
is called artificial discontinuity in Kondratyev’s Ph.D. thesis. We show how such phenomenon may be detected and even “repaired” by using a new variable to
rename the leading term each time we detect a “problem”. We call such strategy the TSV (Term Substitutions with Variables)
strategy. For a zero-dimensional polynomial ideal, any monomial basis (containing 1) of the quotient ring can be found with
the TSV strategy. Hence we can use TSV strategy to relax term order while keeping the framework of Gr?bner basis method so
that we can use existing efficient algorithms (for instance the F
5 algorithm) to compute an approximate Gr?bner basis. Our main algorithms, named TSVn and TSVh, can be used to repair artificial
e{\epsilon}-discontinuities. Experiments show that these algorithms are effective for some nontrivial problems. 相似文献
20.
An ordered set-partition (or preferential arrangement) of n labeled elements represents a single “hierarchy” these are enumerated by the ordered Bell numbers. In this note we determine
the number of “hierarchical orderings” or “societies”, where the n elements are first partitioned into m ≤ n subsets and a hierarchy is specified for each subset. We also consider the unlabeled case, where the ordered Bell numbers
are replaced by the composition numbers. If there is only a single hierarchy, we show that the average rank of an element
is asymptotic to n/(4 log 2) in the labeled case and to n/4 in the unlabeled case.
This revised version was published online in September 2006 with corrections to the Cover Date. 相似文献