Artificial time integration

Many recent algorithmic approaches involve the construction of a differential equation model for computational purposes, typically by introducing an artificial time variable. The actual computational model involves a discretization of the now time-dependent differential system, usually employing forward Euler. The resulting dynamics of such an algorithm is then a discrete dynamics, and it is expected to be “close enough” to the dynamics of the continuous system (which is typically easier to analyze) provided that small – hence many – time steps, or iterations, are taken. Indeed, recent papers in inverse problems and image processing routinely report results requiring thousands of iterations to converge. This makes one wonder if and how the computational modeling process can be improved to better reflect the actual properties sought. In this article we elaborate on several problem instances that illustrate the above observations. Algorithms may often lend themselves to a dual interpretation, in terms of a simply discretized differential equation with artificial time and in terms of a simple optimization algorithm; such a dual interpretation can be advantageous. We show how a broader computational modeling approach may possibly lead to algorithms with improved efficiency. AMS subject classification (2000)  65L05, 65M32, 65N21, 65N22, 65D18     

Parametric and Non Homogeneous Semi-Markov Process for HIV Control

In AIDS control, physicians have a growing need to use pragmatically useful and interpretable tools in their daily medical taking care of patients. Semi-Markov process seems to be well adapted to model the evolution of HIV-1 infected patients. In this study, we introduce and define a non homogeneous semi-Markov (NHSM) model in continuous time. Then the problem of finding the equations that describe the biological evolution of patient is studied and the interval transition probabilities are computed. A parametric approach is used and the maximum likelihood estimators of the process are given. A Monte Carlo algorithm is presented for realizing non homogeneous semi-Markov trajectories. As results, interval transition probabilities are computed for distinct times and follow-up has an impact on the evolution of patients.      

Speedup estimates for some variants of the parallel implementations of the branch-and-bound method

The efficiency of parallel implementations of the branch-and-bound method in discrete optimization problems is considered. A theoretical analysis and comparison of two parallel implementations of this method is performed. A mathematical model of the computation process is constructed and used to obtain estimates of the maximum possible speedup. Examples of problems in which none of these two parallel implementations can speed up the computations are considered.     

On existence and stability in the theory of swelling porous elastic soils

The aim of this paper is to introduce a new functional in thestudy of swelling porous elastic soils saturated by a fluid.This new functional is a useful tool; it allows us to provethe existence of solutions in the case of a compressible fluid.We also prove the stability of solutions and the exponentialdecay in the case of an incompressible fluid. We study as wellthe continuous dependence with respect to the initial time.     

CONSTRUCTION OF SOME KIESSWETTER-LIKE FUNCTIONS-THE CONTINUOUS BUT NON-DIFFERENTIABLE FUNCTION DEFINED BY QUINARY DECIMAL

In this paper, we construct some continuous but non-differentiable functions defined by quinary decimal, that are Kiesswetter-like functions. We discuss their properties, then investigate the Hausdorff dimensions of graphs of these functions and give a detailed proof.     

Approximating schedules for dynamic process graphs efficiently

A model for parallel and distributed programs, the dynamic process graph (DPG), is investigated under graph-theoretic and complexity aspects. Such graphs embed constructors for parallel programs, synchronization mechanisms as well as conditional branches. They are capable of representing all possible executions of a parallel or distributed program in a very compact way. The size of this representation can be as small as logarithmic with respect to the size of any execution of the program.

In a preceding paper [A. Jakoby, et al., Scheduling dynamic graphs, in: Proc. 16th Symposium on Theoretical Aspects in Computer Science STACS'99, LNCS, vol. 1563, Springer, 1999, pp. 383–392] we have analysed the expressive power of the general model and various variants of it. We have considered the scheduling problem for DPGs given enough parallelism taking into account communication delays between processors when exchanging data. Given a DPG the question arises whether it can be executed (that means whether the corresponding parallel program has been specified correctly), and what is its minimum schedule length.

In this paper we study a subclass of dynamic process graphs called -output DPGs, which are appropriate in many situations, and investigate their expressive power. In a previous paper we have shown that the problem to determine the minimum schedule length is still intractable for this subclass, namely this problem is -complete as is the general case. Here we will investigate structural properties of the executions of such graphs. A natural graph-theoretic conjecture that executions must always split into components that are isomorphic to subgraphs turns out to be wrong. We are able to prove a weaker property. This implies a quadratic upper bound on the schedule length that may be necessary in the worst case, in contrast to the general case, where the optimal schedule length may be exponential with respect to the size of the representing DPG. Making this bound constructive, we obtain an approximation to a -complete problem. Computing such a schedule and then executing the program can be done on a parallel machine in polynomial time in a highly distributive fashion.     

The Asymmetric Avalanche Process

An asymmetric stochastic process describing the avalanche dynamics on a ring is proposed. A general kinetic equation which incorporates the exclusion and avalanche processes is considered. The Bethe ansatz method is used to calculate the generating function for the total distance covered by all particles. It gives the average velocity of particles which exhibits a phase transition from an intermittent to continuous flow. We calculated also higher cumulants and the large deviation function for the particle flow. The latter has the universal form obtained earlier for the asymmetric exclusion process and conjectured to be common for all models of the Kardar–Parisi–Zhang universality class.     

酵母蛋白质网络的动力学性质

蛋白质-蛋白质、蛋白质-DNA相互作用网络决定了细胞中各种关键功能的执行．基于芽殖酵母(budding yeast saccharomyces cerevisiae)的蛋白质-蛋白质相互作用网络数据和相关的实验文献，我们建立了调控细胞周期和生命周期(cell cycle and life cycle)的蛋白质网络，并利用离散模型研究了该网络的动力学性质，研究表明：细胞周期网络的动力学性质具有很强的稳定性，约94％的蛋白质初态将演化到对应于生物学G1基态的稳定态，使其成为惟一的全局吸引点；同时，绝大多数的初态的演化路径都通过由G1激发态到G1基态的细胞周期演化路径，使细胞周期路径成为全局性的“吸引”路径。     

Liminf results on the increments of an (N,d)-Gaussian process

We establish some liminf theorems on the increments of a (N,d)-Gaussian process with the usual Euclidean norm, via estimating upper bounds of large deviation probabilities on the suprema of the (N,d)-Gaussian process. This revised version was published online in June 2006 with corrections to the Cover Date.