A note on 3D orthogonal drawings with direction constrained edges

The recent interest in three-dimensional graph drawing has been motivating studies on how to extend two-dimensional techniques to higher dimensions. A common 2D approach for computing an orthogonal drawing separates the task of defining the shape of the drawing from the task of computing its coordinates. First results towards finding a three-dimensional counterpart of this approach are presented by G. Di Battista, et al. [Graph Drawing (Proc. GD'00), Lecture Notes in Comput. Sci., vol. 1984, Springer, Berlin, 2001; Theoret. Comput. Sci. 289 (2002) 897], where characterizations of orthogonal representations of paths and cycles are studied. In this paper we show that the characterization for cycles given by G. Di Battista, et al. [Theoret. Comput. Sci. 289 (2002) 897] does not immediately extend to even seemingly simple graphs.     

A New Mapped Weighted Essentially Non-oscillatory Scheme

The weighted essentially non-oscillatory (WENO) methods are a popular high-order spatial discretization for hyperbolic partial differential equations. Recently Henrick et al. (J. Comput. Phys. 207:542–567, 2005) noted that the fifth-order WENO method by Jiang and Shu (J. Comput. Phys. 126:202–228, 1996) is only third-order accurate near critical points of the smooth regions in general. Using a simple mapping function to the original weights in Jiang and Shu (J. Comput. Phys. 126:202–228, 1996), Henrick et al. developed a mapped WENO method to achieve the optimal order of accuracy near critical points. In this paper we study the mapped WENO scheme and find that, when it is used for solving the problems with discontinuities, the mapping function in Henrick et al. (J. Comput. Phys. 207:542–567, 2005) may amplify the effect from the non-smooth stencils and thus cause a potential loss of accuracy near discontinuities. This effect may be difficult to be observed for the fifth-order WENO method unless a long time simulation is desired. However, if the mapping function is applied to seventh-order WENO methods (Balsara and Shu in J. Comput. Phys. 160:405–452, 2000), the error can increase much faster so that it can be observed with a moderate output time. In this paper a new mapping function is proposed to overcome this potential loss of accuracy.     

Code OK1—Simulation of multi-beam irradiation on a spherical target in heavy ion fusion

Code OK1 is a fast and precise three-dimensional computer program designed for simulations of heavy ion beam (HIB) irradiation on a direct-driven spherical fuel pellet in heavy ion fusion (HIF). OK1 provides computational capabilities of a three-dimensional energy deposition profile on a spherical fuel pellet and the HIB irradiation non-uniformity evaluation, which are valuables for optimizations of the beam parameters and the fuel pellet structure, as well for further HIF experiment design. The code is open and complete, and can be easily modified or adapted for users' purposes in this field.

Program summary

Title of program: OK1Catalogue identifier: ADSTProgram summary URL:http://cpc.cs.qub.ac.uk/summaries/ADSTProgram obtainable from: CPC Program Library, Queen's University of Belfast, N. IrelandComputer: PC (Pentium 4, ∼1 GHz or more recommended)Operating system: Windows or UNIXProgram language used: C++Memory required to execute with typical data: 911 MBNo. of bits in a word: 32No. of processors used: 1 CPUHas the code been vectorized or parallelized: NoNo. of bytes in distributed program, including test data: 16 557Distribution format: tar gzip fileKeywords: Heavy ion beam, inertial confinement fusion, energy deposition, fuel pelletNature of physical problem: Nuclear fusion energy may have attractive features as one of our human energy resources. In this paper we focus on heavy ion inertial confinement fusion (HIF). Due to a favorable energy deposition behavior of heavy ions in matter [J.J. Barnard et al., UCRL-LR-108095, 1991; C. Deutsch et al., J. Plasma Fusion Res. 77 (2001) 33; T. Someya et al., Fusion Sci. Tech. (2003), submitted] it is expected that heavy ion beam (HIB) would be one of energy driver candidates to operate a future inertial confinement fusion power plant. For a successful fuel ignition and fusion energy release, a stringent requirement is imposed on the HIB irradiation non-uniformity, which should be less than a few percent [T. Someya et al., Fusion Sci. Tech. (2003), submitted; M.H. Emery et al., Phys. Rev. Lett. 48 (1982) 253; S. Kawata et al., J. Phys. Soc. Jpn. 53 (1984) 3416]. In order to meet this requirement we need to evaluate the non-uniformity of a realistic HIB irradiation and energy deposition pattern. The HIB irradiation and non-uniformity evaluations are sophisticated and difficult to calculate analytically. Based on our code one can numerically obtain a three-dimensional profile of energy deposition and evaluate the HIB irradiation non-uniformity onto a spherical target for a specific HIB parameter value set in HIF.Method of solution: OK1 code is based on the stopping power of ions in matter [J.J. Barnard et al., UCRL-LR-108095, 1991; C. Deutsch et al., J. Plasma Fusion Res. 77 (2001) 33; T. Someya et al., Fusion Sci. Tech. (2003), submitted; M.H. Emery et al., Phys. Rev. Lett. 48 (1982) 253; S. Kawata et al., J. Phys. Soc. Jpn. 53 (1984) 3416; T. Mehlhorn, SAND80-0038, 1980; H.H. Andersen, J.F. Ziegler, Pergamon Press, 1977, p. 3]. The code simulates a multi-beam irradiation, obtains the 3D energy deposition profile of the fuel pellet and evaluates the deposition non-uniformity.Restrictions on the complexity of the problem: NoTypical running time: The execution time depends on the number of beams in the simulated irradiation and its characteristics (beam radius on the pellet surface, beam subdivision, projectile particle energy and so on). In almost of the practical running tests performed, the typical running time for one beam deposition is less than 2 s on a PC with a CPU of Pentium 4, 2.2 GHz (e.g., in Test 2 when the number of beams is 600, the running time is about 18 minutes).Unusual features of the program: No     

Computer Assisted Proofs of Bifurcating Solutions for Nonlinear Heat Convection Problems

In previous works (Nakao et al., Reliab. Comput., 9(5):359–372, 2003; Watanabe et al., J. Math. Fluid Mech., 6(1):1–20, 2004), the authors considered the numerical verification method of solutions for two-dimensional heat convection problems known as Rayleigh-Bénard problem. In the present paper, to make the arguments self-contained, we first summarize these results including the basic formulation of the problem with numerical examples. Next, we will give a method to verify the bifurcation point itself, which should be an important information to clarify the global bifurcation structure, and show a numerical example. Finally, an extension to the three dimensional case will be described.     

A program for generating configuration state lists in many-electron atoms

This program written in FORTRAN is aimed at generating configuration state list of the set of complex atomic configurations. The program generates a list of configuration states obtained by taking into account many additional constraints of different types for minimizing the orders of matrices, as proposed in [Bogdanovich et al., Comput. Phys. Comm. 143 (2002) 174]. The generated list file complies with the requirements of codes [Hibbert et al., Comput. Phys. Comm. 64 (1991) 455; Fischer et al., Comput. Phys. Comm. 64 (1991) 486] and other related programs.

Program summary

Title of program: ATOTERMCatalogue identifier: ADTMProgram summary URL:http://cpc.cs.qub.ac.uk/summaries/ADTMProgram obtainable from: CPC Program Library, Queen's University of Belfast, N. IrelandLicensing provisions: NoneComputers: Any computer with a FORTRAN 77 compilerOperating systems under which the program has been tested: LinuxProgramming language used: FORTRAN 77Memory required to execute with typical data: 2 MBNo. of lines in distributed program, including text data, etc.: 2368No. of bytes in distributed program, including test data, etc.: 15 446Distribution format: tar gzip fileKeywords: Complex atom, configuration interaction, configuration state, LS-couplingNature of physical problem: Generating the list of configuration states with taking into account multiple additional constraints of different types.Method of solution: Building the configuration state list for the set of the given configurations with further selection of necessary configuration states by applying a set of restrictions on each configuration.Restrictions onto the complexity of the problem: For atomic configurations containing any electron shells with l?3; momenta of the electron shells with l>3 and N?2 is restricted by L_max=6. The number of the active shells can not exceed seven.Unusual features of the program: Possibility to select configuration states.Typical running time: Seconds to minutes. Depends on the size of the problem: of the order of a few seconds for simple configurations to minutes for a large set of very complex admixed configurations with f-electron shells.     

Stochastic kinetic Monte Carlo algorithms for long-range Hamiltonians

We present a higher order kinetic Monte Carlo methodology suitable to model the evolution of systems in which the transition rates are non-trivial to calculate or in which Monte Carlo moves are likely to be non-productive flicker events. The second order residence time algorithm first introduced by Athènes et al. [Phil. Mag. A 76 (1997) 565] is rederived from the n-fold way algorithm of Bortz et al. [J. Comput. Phys. 17 (1975) 10] as a fully stochastic algorithm. The second order algorithm can be dynamically called when necessary to eliminate unproductive flickering between a metastable state and its neighbours. An algorithm combining elements of the first order and second order methods is shown to be more efficient, in terms of the number of rate calculations, than the first order or second order methods alone while remaining statistically identical. This efficiency is of prime importance when dealing with computationally expensive rate functions such as those arising from long-range Hamiltonians. Our algorithm has been developed for use when considering simulations of vacancy diffusion under the influence of elastic stress fields. We demonstrate the improved efficiency of the method over that of the n-fold way in simulations of vacancy diffusion in alloys. Our algorithm is seen to be an order of magnitude more efficient than the n-fold way in these simulations. We show that when magnesium is added to an Al-2at.%Cu alloy, this has the effect of trapping vacancies. When trapping occurs, we see that our algorithm performs thousands of events for each rate calculation performed.     

Application of efficient composite methods for computing with certainty periodic orbits in molecular systems

Recently, we have proposed a technique for the computation of periodic orbits in molecular systems, based on the characteristic bisection method [Vrahatis et al., Comput. Phys. Commun. 138 (2001) 53]. The main advantage of the characteristic bisection method is that it converges with certainty within a given starting rectangular region. In this paper we further improve this technique by applying, on a surface of section of a Poincaré map, an iterative scheme based on the composition of the characteristic bisection method with other more rapid root-finding methods such as Newton's or Broyden's methods. Thus, the composite schemes compute rapidly with certainty periodic orbits of molecular systems. By applying these methods to the LiNC/LiCN molecular system we obtain promising results. We have reproduced previous results using considerable less CPU time. Also, we have located and computed new asymmetric families of periodic orbits.     

Local abstraction–refinement for the <Emphasis Type="Italic">μ</Emphasis>-calculus

A key technique for the verification of programs is counterexample-guided abstraction–refinement (CEGAR). Grumberg et al. (LNCS, vol 3385, pp. 233–249. Springer, Berlin, 2005; Inf Comput 205(8):1130–1148, 2007) developed a CEGAR-based algorithm for the modal μ-calculus. There, every abstract state is split in a refinement step. In this paper, the work of Grumberg et al. is generalized by presenting a new CEGAR-based algorithm for the μ-calculus. It is based on a more expressive abstract model and applies refinement only locally (at a single abstract state), i.e., the lazy abstraction technique for safety properties is adapted to the μ-calculus. Furthermore, it separates refinement determination from the (3-valued based) model checking. Three different heuristics for refinement determination are presented and illustrated.     

Sharpening Occam's razor

We provide a new representation-independent formulation of Occam's razor theorem, based on Kolmogorov complexity. This new formulation allows us to: (i) obtain better sample complexity than both length-based [Blumer et al., Inform. Process. Lett. 24 (1987) 377-380] and VC-based [Blumer et al., J. ACM 35 (1989) 929-965] versions of Occam's razor theorem, in many applications; and (ii) achieve a sharper reverse of Occam's razor theorem than that of Board and Pitt [STOC, 1999, pp. 54-63]. Specifically, we weaken the assumptions made by Board and Pitt [STOC, 1999, pp. 54-63] and extend the reverse to superpolynomial running times.     

The stationary phase auxiliary field Monte Carlo method: a new strategy for reducing the sign problem of auxiliary field methodologies

In this paper we focus on a new computational procedure, which permits an efficient calculation within the classical auxiliary field methodology. As has been previously reported, the method suffers from a sign problem, typically encountered in methodologies based on a field-theoretical approach. To ameliorate its statistical convergence, the efforts have so far exclusively been concentrated on the development of efficient analytical integral transformation techniques, such as the method of Gaussian equivalent representation of Efimov et al. In the present work we reformulate the classical auxiliary field methodology according to the concepts of the stationary phase Monte Carlo method of Doll et al., a numerical strategy originally developed for the simulation with real-time path integrals. The procedure, which is here employed for the first time for auxiliary field computation, utilizes an importance sampling strategy, to identify the regions of configuration space that contribute most strongly to the functional integral averages. Its efficiency is here compared to the method of Gaussian equivalent representation.     

Efficient image restoration of virtual machines with reference count based rewriting and caching

Virtual machine (VM) image backups have duplicate data blocks distributed in different physical addresses, which occupy a large amount of storage space in a cloud computing platform (Choo et al.,  [1] and González-Manzano et al.,  [2]). Deduplication is a widely used technology to reduce the redundant data in a VM backup process. However, deduplication always causes the fragmentation of data blocks, which seriously affects the VM restoration performance. Current approaches often rewrite data blocks to accelerate image restoration, but rewriting could cause significant performance overhead because of frequent I/O operations. To address this issue, we have found that the reference count is a key to the fragmentation degree from a series of experiments. Thus, we propose a reference count based rewriting method to defragment VM image backups, and a caching method based on the distribution of rewritten data blocks to restore VM images. Compared with existing studies, our approach has no interfere to the deduplication process, needs no extra storage, and efficiently improves the performance of VM image restoration. We have implemented a prototype to evaluate our approach in our real cloud computing platform OnceCloud. Experimental results show that our approach can reduce about 57% of the dispersion degree of data blocks, and accelerate about 51% of the image restoration of virtual machines.     

Optimal placements of replicas in a ring network with majority voting protocol

In a distributed database system, data replicas are placed at different locations to achieve high data availability in the presence of link failures. With a majority voting protocol, a location survives for read/write operations if and only if it is accessible to more than half of the replicas. The problem is to find out the optimal placements for a given number of data replicas in a ring network. When the number of replicas is odd, it was conjectured by Hu et al. [X.-D. Hu, X.-H. Jia, D.-Z. Du, D.-Y. Li, H.-J. Huang, Placement of data replicas for optimal data availability in ring networks, J. Parallel Distrib. Comput., 61 (2001) 1412–1424] that every uniform placement is optimal, which is proved by Shekhar and Wu later. However, when the number of replicas is even, it was pointed out by Hu et al. that uniform placements are not optimal and the optimal placement problem may be very complicated. In this paper, we study the optimal placement problem in a ring network with majority voting protocol and an even number of replicas, and give a complete characterization of optimal placements when the number of replicas is not too large compared with the number of locations.     

Improved on-line broadcast scheduling with deadlines

We study an on-line broadcast scheduling problem in which requests have deadlines, and the objective is to maximize the weighted throughput, i.e., the weighted total length of the satisfied requests. For the case where all requested pages have the same length, we present an online deterministic algorithm named BAR and prove that it is 4.56-competitive. This improves the previous algorithm of (Kim, J.-H., Chwa, K.-Y. in Theor. Comput. Sci. 325(3):479–488, 2004) which is shown to be 5-competitive by (Chan, W.-T., et al. in Lecture Notes in Computer Science, vol. 3106, pp. 210–218, 2004). In the case that pages may have different lengths, we give a ( )-competitive algorithm where Δ is the ratio of maximum to minimum page lengths. This improves the (4Δ+3)-competitive algorithm of (Chan, W.-T., et al. in Lecture Notes in Computer Science, vol. 3106, pp. 210–218, 2004). We also prove an almost matching lower bound of Ω(Δ/log Δ). Furthermore, for small values of Δ we give better lower bounds. The work described in this paper was fully supported by grants from the Research Grants Council of the Hong Kong SAR, China [CityU 1198/03E, HKU 7142/03E, HKU 5172/03E], an NSF Grant of China [No. 10371094], and a Nuffield Foundation Grant of UK [NAL/01004/G].     

A note on double splittings of different monotone matrices

Comparison theorems between the spectral radii of different matrices are a useful tool for judging the efficiency of preconditioners. For single splittings of different monotone matrices, Elsner et al. (Linear Algebra Appl. 363:65–80, 2003) gave out comparison theorems for spectral radii. For double splittings, some convergence and comparison theorems of a monotone matrix are presented by Shen et al. (Comput. Math. Appl. 51:1751–1760, 2006). In this note we give the comparison theorem for the spectral radii of matrices arising from double splittings of different monotone matrices.     

An algorithmic framework for network reconstruction

Models of biological systems and phenomena are of high scientific interest and practical relevance, but not always easy to obtain due to their inherent complexity. To gain the required insight, experimental data are provided and need to be interpreted in terms of models that explain the observed phenomena. In systems biology the framework of Petri nets is often used to describe models for the regulatory mechanisms of biological systems. The aim of this paper is to provide, based on results in Marwan et al. (2008) [1] and Durzinsky et al. (2008) [2], an algorithmic framework for the challenging task of generating all possible Petri nets fitting the given experimental data.     

A Dynamic Penalty or Projection Method for Incompressible Fluids

In a previous work (Angot et al. in J. Comput. Appl. Math. 226:228–245, 2009), some penalty–projection methods have been tested for the numerical analysis of the Navier-Stokes equations. The purpose of this study is to introduce a variant of the penalty–projection method which allows us to compute the solutions faster than by using the previous solver. This new variant combines dynamically and alternatively a penalty procedure and a projection procedure according to the size of the divergence of the velocity. In other words, this study aims to prove that it is possible to project the intermediate velocity, computed by the first step of the penalty–projection method, only if its divergence is larger than a specified threshold. Theoretical estimates for the new method are given, which are in accordance with the numerical results provided.     

Invariant Signatures of Closed Planar Curves

We prove that any subset of ℝ² parametrized by a C ¹ periodic function and its derivative is the Euclidean invariant signature of a closed planar curve. This solves a problem posed by Calabi et al. (Int. J. Comput. Vis. 26:107–135, 1998). Based on the proof of this result, we then develop some cautionary examples concerning the application of signature curves for object recognition and symmetry detection as proposed by Calabi et al.