Local Algorithms for the Prime Factorization of Strong Product Graphs

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.     

Newton-KKT interior-point methods for indefinite quadratic programming

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.     

Classical analogue of a quantum Schwarzschild black hole: “Standard model” and beyond

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.”     

The Geometry of Standard Deontic Logic

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).      

On the interior regularity of weak solutions to the non-stationary Stokes system

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.     

Generalized basic hypergeometric equations

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.     

Sequent calculi for branching time temporal logics of knowledge and beliefwith awareness: Completeness and decidability

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.     

Assessment of local influence on Cox’s proportional hazards model

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     

Hyperbolic balance laws: Riemann invariants and the generalized Riemann problem

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.     

The “walk in hemispheres” process and its applications to solving boundary value problems

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.     

Cantor set and interpolation

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.     

Compositions of n as alternating sequences of weakly increasing and strictly decreasing partitions

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.     

Some results on local growth of two-parameter Lévy processes

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 ₀.     

The <Emphasis Type="Italic">R</Emphasis>-observability and <Emphasis Type="Italic">R</Emphasis>-controllability of linear differential-algebraic systems

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.     

On duality gap in linear conic problems

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 \mathbbR⁴{\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.     

The local part and the strong type for operators related to the Gaussian measure

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.     

Pivoting in Extended Rings for Computing Approximate Gr?bner Bases

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 ₅ 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.     

A complexity measure for families of binary sequences

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.     

The Number of Hierarchical Orderings

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.