Tree Series Transformations that Respect Copying

We consider tree series transducers which were introduced in [EFV], and define the tree-to-tree series transformations computed by them in two different ways. One of the definitions is based on the

Communication—Processor Tradeoffs in a Limited Resources PRAM

   Abstract. We consider a simple restriction of the PRAM model (called PPRAM), where the input is arbitrarily partitioned between a fixed set of p processors and the shared memory is restricted to m cells. This model allows for investigation of the tradeoffs/ bottlenecks with respect to the communication bandwidth (modeled by the shared memory size m ) and the number of processors p . The model is quite simple and allows the design of optimal algorithms without losing the effect of communication bottlenecks. We have focused on the PPRAM complexity of problems that have

The Quantum Black-Box Complexity of Majority

   Abstract. We describe a quantum black-box network computing the majority of N bits with zero-sided error ɛ using only

Computing the Maximum Degree of Minors in Matrix Pencils via Combinatorial Relaxation

   Abstract. This paper presents a new algorithm for computing the maximum degree δ _k (A) of a minor of order k in a matrix pencil A(s) . The problem is of practical significance in the field of numerical analysis and systems control. The algorithm adopts a general framework of ``combinatorial relaxation' due to Murota. It first solves the weighted bipartite matching problem to obtain an estimate

FIESTA 2: Parallelizeable multiloop numerical calculations

The program FIESTA has been completely rewritten. Now it can be used not only as a tool to evaluate Feynman integrals numerically, but also to expand Feynman integrals automatically in limits of momenta and masses with the use of sector decompositions and Mellin–Barnes representations. Other important improvements to the code are complete parallelization (even to multiple computers), high-precision arithmetics (allowing to calculate integrals which were undoable before), new integrators, Speer sectors as a strategy, the possibility to evaluate more general parametric integrals.

Program summary

Program title:FIESTA 2Catalogue identifier: AECP_v2_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AECP_v2_0.htmlProgram obtainable from: CPC Program Library, Queen's University, Belfast, N. IrelandLicensing provisions: GNU GPL version 2No. of lines in distributed program, including test data, etc.: 39 783No. of bytes in distributed program, including test data, etc.: 6 154 515Distribution format: tar.gzProgramming language: Wolfram Mathematica 6.0 (or higher) and CComputer: From a desktop PC to a supercomputerOperating system: Unix, Linux, Windows, Mac OS XHas the code been vectorised or parallelized?: Yes, the code has been parallelized for use on multi-kernel computers as well as clusters via Mathlink over the TCP/IP protocol. The program can work successfully with a single processor, however, it is ready to work in a parallel environment and the use of multi-kernel processor and multi-processor computers significantly speeds up the calculation; on clusters the calculation speed can be improved even further.RAM: Depends on the complexity of the problemClassification: 4.4, 4.12, 5, 6.5Catalogue identifier of previous version: AECP_v1_0Journal reference of previous version: Comput. Phys. Comm. 180 (2009) 735External routines: QLink [1], Cuba library [2], MPFR [3]Does the new version supersede the previous version?: YesNature of problem: The sector decomposition approach to evaluating Feynman integrals falls apart into the sector decomposition itself, where one has to minimize the number of sectors; the pole resolution and epsilon expansion; and the numerical integration of the resulting expression.Solution method: The sector decomposition is based on a new strategy as well as on classical strategies such as Speer sectors. The sector decomposition, pole resolution and epsilon-expansion are performed in Wolfram Mathematica 6.0 or, preferably, 7.0 (enabling parallelization) [4]. The data is stored on hard disk via a special program, QLink [1]. The expression for integration is passed to the C-part of the code, that parses the string and performs the integration by one of the algorithms in the Cuba library package [2]. This part of the evaluation is perfectly parallelized on multi-kernel computers.Reasons for new version:

• 1. 

  The first version of FIESTA had problems related to numerical instability, so for some classes of integrals it could not produce a result.

• 2. 

  The sector decomposition method can be applied not only for integral calculation.

Summary of revisions:

• 1. 

  New integrator library is used.

• 2. 

  New methods to deal with numerical instability (MPFR library).

• 3. 

  Parallelization in Mathematica.

• 4. 

  Parallelization on multiple computers via TCP-IP.

• 5. 

  New sector decomposition strategy (Speer sectors).

• 6. 

  Possibility of using FIESTA to for integral expansion.

• 7. 

  Possibility of using FIESTA to discover poles in d.

• 8. 

  New negative terms resolution strategies.

Restrictions: The complexity of the problem is mostly restricted by CPU time required to perform the evaluation of the integralRunning time: Depends on the complexity of the problemReferences:

• [1] 

  http://qlink08.sourceforge.net, open source.

• [2] 

  http://www.feynarts.de/cuba/, open source.

• [3] 

  http://www.mpfr.org/, open source.

• [4] 

  http://www.wolfram.com/products/mathematica/index.html.

     

Competitive Analysis of the LRFU Paging Algorithm

   Abstract. We present a competitive analysis of the LRFU paging algorithm, a hybrid of the LRU (Least Recently Used) and LFU (Least Frequently Used) paging algorithms. We show that the competitive ratio of LRFU is k +

How to market yourself as an ISSO

• 1. 

  1. Prior to being interviewed for TCI's ISSO position, learn all you can about TCI.

• 2. 

  2. Read articles about how to prepare and dress for interviews.

• 3. 

  3. Prepare answers for the typical questions you will probably be asked and practice the interview process so your answers come across naturally, and not as memorized, rehearsed answers.

• 4. 

  4. Develop an ISSO portfolio to be used during the interview.

• 5. 

  5. During the interview, refer the interviewers to the portfolio.

• 6. 

  6. During the interview, use “we” and “our” as if you already worked at TCI.

     

Preconditioned iterative methods for the numerical solution of Fredholm equations of the second kind

In this paper, we consider the numerical solution of Fredholm integral equations of the second kind:

XtalOpt version r7: An open-source evolutionary algorithm for crystal structure prediction

A new version of XtalOpt, a user-friendly GPL-licensed evolutionary algorithm for crystal structure prediction, is available for download from the CPC library or the XtalOpt website, http://xtalopt.openmolecules.net. The new version now supports four external geometry optimization codes (VASP, GULP, PWSCF, and CASTEP), as well as three queuing systems: PBS, SGE, SLURM, and “Local”. The local queuing system allows the geometry optimizations to be performed on the user?s workstation if an external computational cluster is unavailable. Support for the Windows operating system has been added, and a Windows installer is provided. Numerous bugfixes and feature enhancements have been made in the new release as well.

New version program summary

Program title:XtalOptCatalogue identifier: AEGX_v2_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AEGX_v2_0.htmlProgram obtainable from: CPC Program Library, Queen?s University, Belfast, N. IrelandLicensing provisions: GPL v2.1 or later [1]No. of lines in distributed program, including test data, etc.: 125 383No. of bytes in distributed program, including test data, etc.: 11 607 415Distribution format: tar.gzProgramming language: C++Computer: PCs, workstations, or clustersOperating system: Linux, MS WindowsClassification: 7.7External routines: Qt [2], Open Babel [3], Avogadro [4], and one of: VASP [5], PWSCF [6], GULP [7], CASTEP [8]Catalogue identifier of previous version: AEGX_v1_0Journal reference of previous version: Comput. Phys. Comm. 182 (2011) 372Does the new version supersede the previous version?: YesNature of problem: Predicting the crystal structure of a system from its stoichiometry alone remains a grand challenge in computational materials science, chemistry, and physics.Solution method: Evolutionary algorithms are stochastic search techniques which use concepts from biological evolution in order to locate the global minimum of a crystalline structure on its potential energy surface. Our evolutionary algorithm, XtalOpt, is freely available for use and collaboration under the GNU Public License. See the original publication on XtalOpt?s implementation [11] for more information on the method.Reasons for new version: Since XtalOpt?s initial release in June 2010, support for additional optimizers, queuing systems, and an operating system has been added. XtalOpt can now use VASP, GULP, PWSCF, or CASTEP to perform local geometry optimizations. The queue submission code has been rewritten, and now supports running any of the above codes on ssh-accessible computer clusters that use the Portable Batch System (PBS), Sun Grid Engine (SGE), or SLURM queuing systems for managing the optimization jobs. Alternatively, geometry optimizations may be performed on the user?s workstation using the new internal “Local” queuing system if high performance computing resources are unavailable. XtalOpt has been built and tested on the Microsoft Windows operating system (XP or later) in addition to Linux, and a Windows installer is provided. The installer includes a development version of Avogadro that contains expanded crystallography support [12] that is not available in the mainline Avogadro releases. Other notable new developments include:

• • 

  LIBSSH [10] is distributed with the XtalOpt sources and used for communication with the remote clusters, eliminating the previous requirement to set up public-key authentication;

• • 

  Plotting enthalpy (or energy) vs. structure number in the plot tab will trace out the history of the most stable structure as the search progresses A read-only mode has been added to allow inspection of previous searches through the user interface without connecting to a cluster or submitting new jobs;

• • 

  The tutorial [13] has been rewritten to reflect the changes to the interface and the newly supported codes. Expanded sections on optimizations schemes and save/resume have been added;

• • 

  The included version of SPGLIB has been updated. An option has been added to set the Cartesian tolerance of the space group detection. A new option has been added to the Progress table?s right-click menu that copies the selected structure?s POSCAR formatted representation to the clipboard;

• • 

  Numerous other small bugfixes/enhancements.

Summary of revisions: See “Reasons for new version” above.Running time: User dependent. The program runs until stopped by the user.References:

•  [1] 

  http://www.gnu.org/licenses/gpl.html.

•  [2] 

  http://www.trolltech.com/.

•  [3] 

  http://openbabel.org/.

•  [4] 

  http://avogadro.openmolecules.net.

•  [5] 

  http://cms.mpi.univie.ac.at/vasp.

•  [6] 

  http://www.quantum-espresso.org.

•  [7] 

  https://www.ivec.org/gulp.

•  [8] 

  http://www.castep.org.

•  [9] 

  http://spglib.sourceforge.net.

• [10] 

  http://www.libssh.org.

• [11] 

  D. Lonie, E. Zurek, Comp. Phys. Comm. 182 (2011) 372–387, doi:10.1016/j.cpc.2010.07.048.

• [12] 

  http://davidlonie.blogspot.com/2011/03/new-avogadro-crystallography-extension.html.

• [13] 

  http://xtalopt.openmolecules.net/globalsearch/docs/tut-xo.html.

     

Preface: Volume 65, Issue 1

This volume contains the Proceedings of the Fifth Workshop on Coalgebraic Methods in Computer Science (CMCS'2002). The Workshop was held in Grenoble, France on April 6--7 2002, as satellite event to ETAPS'2002.Over the last few years it has become clear that a great variety of state-based dynamical systems, like transition systems, automata, process calculi and class-based systems can be captured uniformly as coalgebras. The aim of the CMCS workshops is to bring together researchers with a common interest in the theory and application of coalgebras. The five CMCS volumes demonstrate that coalgebra is developing into a field of its own, presenting a deep mathematical foundation and a growing field of applications and interactions with various other fields, such as modal logic, category theory, dynamical systems, control systems, object-oriented and concurrent programming, formal systems specifications, algebra, analysis, combinatorics, and set theory.The papers in this volume were reviewed by the program committee:

Jiri Adamek	(Department of Computer Science, Technical University of Braunschweig)
Alexandru Baltag	(Department of Computer Science, Oxford University)
H. Peter Gumm	(Department of Mathematics and Computer Science, University of Marburg)
Jesse Hughes	(Department of Computer Science, University of Nijmegen)
Bart Jacobs	(Department of Computer Science, University of Nijmegen)
Alexander Kurz	(Department of Software Technology, CWI)
Marina Lenisa	(Department of Mathematics and Computer Science, University of Udine)
Ugo Montanari	(Department of Computer Science, University of Pisa)
Larry Moss	(Department of Mathematics, Indiana University)
Ataru T. Nakagawa	(SRA Key Technology Laboratory, Tokyo)
John Power	(Department of Computer Science, The University of Edinburgh)
Horst Reichel	(Institute of Theoretical Computer Science, Dresden University of Technology)
Jan Rutten	(Department of Software Technology, CWI)

Full-size table

Several outside reviewers also assisted. CMCS received 20 submissions and accepted 15 of them. In addition, there were two invited speakers: Jose Meseguer and Luigi Santocanale. Their papers appear in this volume along with the 15 submitted contributions. We are grateful to everyone who sent us papers, and we regret that the length of the conference did not allow more papers to be presented.We thank the organizers of ETAPS'2002 for their help and encouragement. Special thanks to Rachid Echahed for his constant help with the organization of the workshop, and also to Mike Mislove for his work as a Managing Editor of the ENTCS series. Their efforts have been crucial for the success of CMCS'2002.September 1, 2002 Lawrence S. Moss     

GeodesicViewer – A tool for exploring geodesics in the theory of relativity

The GeodesicViewer realizes exocentric two- and three-dimensional illustrations of lightlike and timelike geodesics in the general theory of relativity. By means of an intuitive graphical user interface, all parameters of a spacetime as well as the initial conditions of the geodesics can be modified interactively.

New version program summary

Program title: GeodesicViewerCatalogue identifier: AEFP_v2_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AEFP_v2_0.htmlProgram obtainable from: CPC Program Library, Queen?s University, Belfast, N. IrelandLicensing provisions: Standard CPC licence, http://cpc.cs.qub.ac.uk/licence/licence.htmlNo. of lines in distributed program, including test data, etc.: 76 202No. of bytes in distributed program, including test data, etc.: 1 722 290Distribution format: tar.gzProgramming language: C++, OpenGLComputer: All platforms with a C++ compiler, Qt, OpenGLOperating system: Linux, Mac OS X, WindowsRAM: 24 MBytesClassification: 1.5External routines:

• • 

  Motion4D (included in the package)

• • 

  Gnu Scientific Library (GSL) (http://www.gnu.org/software/gsl/)

• • 

  Qt (http://qt.nokia.com/downloads)

• • 

  OpenGL (http://www.opengl.org/)

Catalogue identifier of previous version: AEFP_v1_0Journal reference of previous version: Comput. Phys. Comm. 181 (2010) 413Does the new version supersede the previous version?: YesNature of problem: Illustrate geodesics in four-dimensional Lorentzian spacetimes.Solution method: Integration of ordinary differential equations. 3D-Rendering via OpenGL.Reasons for new version: The main reason for the new version was to visualize the parallel transport of the Sachs legs and to show the influence of curved spacetime on a bundle of light rays as is realized in the new version of the Motion4D library (http://cpc.cs.qub.ac.uk/summaries/AEEX_v3_0.html).Summary of revisions:

• • 

  By choosing the new geodesic type “lightlike_sachs”, the parallel transport of the Sachs basis and the integration of the Jacobi equation can be visualized.

• • 

  The 2D representation via Qwt was replaced by an OpenGL 2D implementation to speed up the visualization.

• • 

  Viewing parameters can now be stored in a configuration file (.cfg).

• • 

  Several new objects can be used in 3D and 2D representation.

• • 

  Several predefined local tetrads can be choosen.

• • 

  There are some minor modifications: new mouse control (rotate on sphere); line smoothing; current last point in coordinates is shown; mutual-coordinate representation extended; current cursor position in 2D; colors for 2D view.

Running time: Interactive. The examples given take milliseconds.     

Quantum Complexities of Ordered Searching, Sorting, and Element Distinctness

   Abstract. We consider the quantum complexities of the following three problems: searching an ordered list, sorting an un-ordered list, and deciding whether the numbers in a list are all distinct. Letting N be the number of elements in the input list, we prove a lower bound of (1/π )(ln(N )-1) accesses to the list elements for ordered searching, a lower bound of Ω(N logN ) binary comparisons for sorting, and a lower bound of

Preface: Volume 68, Issue 6

INFINITY 2002, the 4th International Workshop on Verification of Infinite-State Systems, was held as a satellite workshop of CONCUR 2002 (the 13th International Conference on Concurrency Theory) in Brno, Czech Republic, on August 24, 2002. The aim of the workshop is to provide a forum for researchers interested in the development of mathematical techniques for the analysis and verification of systems with infinitely many states. The topics of INFINITY 2002 included the following: techniques for modeling and analysis of infinite-state systems, equivalence-checking and model-checking with infinite-state systems, parameterized systems, calculi for mobility and security, finite-state abstractions of infinite-state systems.The volume consists of six contributed papers selected by the INFINITY 2002 programme committee. The papers were reviewed by the program committee consisting, besides editors, of

Parosh Abdulla	(Uppsala (SE))
Julian Bradfield	(Edinburgh (UK))
Didier Caucal	(Irisa (F))
Hubert Comon	(LSV Cachan (F))
Giorgio Delzanno	(Genova (I))
Yoram Hirshfeld	(Tel-Aviv (Israel))
Denis Lugiez	(Marseille (F))
Bernhard Steffen	(Dortmund (D))
P.S. Thiagarajan	(Chennai (India))
Moshe Vardi	(Rice (USA))

Full-size table

The programme of INFINITY 2002 was further enriched by an invited talk given by Colin Stirling, and by four short presentations of work in progress.This volume will be published as volume 68(6) in the series Electronic Notes in Theoretical Computer Science (ENTCS). This series is published electronically through the facilities of Elsevier Science B.V. and its auspices. The volumes in the ENTCS series can be accessed at the URL http://www.elsevier.nl/locate/entcsWe are very grateful to the CONCUR 2002 Organizing Committee for arranging all local affairs, and to Michael Mislove, the managing editor of ENTCS, for providing the opportunity to publish the INFINITY 2002 proceedings in the ENTCS series.December 9, 2002 Antonin Kucera, Richard Mayr     

Max- and Min-Neighborhood Monopolies

   Abstract. Given a graph G=(V,E) and a set of vertices M

XtalOpt: An open-source evolutionary algorithm for crystal structure prediction

The implementation and testing of XtalOpt, an evolutionary algorithm for crystal structure prediction, is outlined. We present our new periodic displacement (ripple) operator which is ideally suited to extended systems. It is demonstrated that hybrid operators, which combine two pure operators, reduce the number of duplicate structures in the search. This allows for better exploration of the potential energy surface of the system in question, while simultaneously zooming in on the most promising regions. A continuous workflow, which makes better use of computational resources as compared to traditional generation based algorithms, is employed. Various parameters in XtalOpt are optimized using a novel benchmarking scheme. XtalOpt is available under the GNU Public License, has been interfaced with various codes commonly used to study extended systems, and has an easy to use, intuitive graphical interface.

Program summary

Program title:XtalOptCatalogue identifier: AEGX_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AEGX_v1_0.htmlProgram obtainable from: CPC Program Library, Queen's University, Belfast, N. IrelandLicensing provisions: GPL v2.1 or later [1]No. of lines in distributed program, including test data, etc.: 36 849No. of bytes in distributed program, including test data, etc.: 1 149 399Distribution format: tar.gzProgramming language: C++Computer: PCs, workstations, or clustersOperating system: LinuxClassification: 7.7External routines: QT [2], OpenBabel [3], AVOGADRO [4], SPGLIB [8] and one of: VASP [5], PWSCF [6], GULP [7].Nature of problem: Predicting the crystal structure of a system from its stoichiometry alone remains a grand challenge in computational materials science, chemistry, and physics.Solution method: Evolutionary algorithms are stochastic search techniques which use concepts from biological evolution in order to locate the global minimum on their potential energy surface. Our evolutionary algorithm, XtalOpt, is freely available to the scientific community for use and collaboration under the GNU Public License.Running time: User dependent. The program runs until stopped by the user.References:

• [1] 

  http://www.gnu.org/licenses/gpl.html.

• [2] 

  http://www.trolltech.com/.

• [3] 

  http://openbabel.org/.

• [4] 

  http://avogadro.openmolecules.net.

• [5] 

  http://cms.mpi.univie.ac.at/vasp.

• [6] 

  http://www.quantum-espresso.org.

• [7] 

  https://www.ivec.org/gulp.

• [8] 

  http://spglib.sourceforge.net.

     

Motion4D-library extended

The new version of the Motion4D-library now also includes the integration of a Sachs basis and the Jacobi equation to determine gravitational lensing of pointlike sources for arbitrary spacetimes.

New version program summary

Program title: Motion4D-libraryCatalogue identifier: AEEX_v3_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AEEX_v3_0.htmlProgram obtainable from: CPC Program Library, Queen?s University, Belfast, N. IrelandLicensing provisions: Standard CPC licence, http://cpc.cs.qub.ac.uk/licence/licence.htmlNo. of lines in distributed program, including test data, etc.: 219 441No. of bytes in distributed program, including test data, etc.: 6 968 223Distribution format: tar.gzProgramming language: C++Computer: All platforms with a C++ compilerOperating system: Linux, WindowsRAM: 61 MbytesClassification: 1.5External routines: Gnu Scientic Library (GSL) (http://www.gnu.org/software/gsl/)Catalogue identifier of previous version: AEEX_v2_0Journal reference of previous version: Comput. Phys. Comm. 181 (2010) 703Does the new version supersede the previous version?: YesNature of problem: Solve geodesic equation, parallel and Fermi-Walker transport in four-dimensional Lorentzian spacetimes. Determine gravitational lensing by integration of Jacobi equation and parallel transport of Sachs basis.Solution method: Integration of ordinary differential equations.Reasons for new version: The main novelty of the current version is the extension to integrate the Jacobi equation and the parallel transport of the Sachs basis along null geodesics. In combination, the change of the cross section of a light bundle and thus the gravitational lensing effect of a spacetime can be determined. Furthermore, we have implemented several new metrics.Summary of revisions: The main novelty of the current version is the integration of the Jacobi equation and the parallel transport of the Sachs basis along null geodesics. The corresponding set of equations read(1)(2)(3) where (1) is the geodesic equation, (2) represents the parallel transport of the two Sachs basis vectors s1,2, and (3) is the Jacobi equation for the two Jacobi fields Y1,2.The initial directions of the Sachs basis vectors are defined perpendicular to the initial direction of the light ray, see also Fig. 1,(4a)(4b)A congruence of null geodesics with central null geodesic γ which starts at the observer O with an infinitesimal circular cross section is defined by the above mentioned two Jacobi fields with initial conditions and . The cross section of this congruence along γ is described by the Jacobian . However, to determine the gravitational lensing of a pointlike source S that is connected to the observer via γ, we need the reverse Jacobian JS→O. Fortunately, the reverse Jacobian is just the negative transpose of the original Jacobian JO→S,(5)J:=JS→O=−T(JO→S). The Jacobian J transforms the circular shape of the congruence into an ellipse whose shape parameters (M_±: major/minor axis, ψ: angle of major axis, ε: ellipticity) read(6a)(6b)ψ=arctan2(J₂₁cosζ₊+J₂₂sinζ₊,J₁₁cosζ₊+J₁₂sinζ₊),(6c) with(7) and the parameters α=J₁₁J₁₂+J₂₁J₂₂, . The magnification factor is given by(8) These shape parameters can be easily visualized in the new version of the GeodesicViewer, see Ref. [1]. A detailed discussion of gravitational lensing can be found, for example, in Schneider et al. [2].In the following, a list of newly implemented metrics is given:

• • 

  BertottiKasner: see Rindler [3].

• • 

  BesselGravWaveCart: gravitational Bessel wave from Kramer [4].

• • 

  DeSitterUniv, DeSitterUnivConf: de Sitter universe in Cartesian and conformal coordinates.

• • 

  Ernst: Black hole in a magnetic universe by Ernst [5].

• • 

  ExtremeReissnerNordstromDihole: see Chandrasekhar [6].

• • 

  HalilsoyWave: see Ref. [7].

• • 

  JaNeWi: Janis–Newman–Winicour metric, see Ref. [8].

• • 

  MinkowskiConformal: Minkowski metric in conformally rescaled coordinates.

• • 

  PTD_AI, PTD_AII, PTD_AIII, PTD_BI, PTD_BII, PTD_BIII, PTD_C Petrov-Type D – Levi-Civita spacetimes, see Ref. [7].

• • 

  PainleveGullstrand: Schwarzschild metric in Painlevé–Gullstrand coordinates, see Ref. [9].

• • 

  PlaneGravWave: Plane gravitational wave, see Ref. [10].

• • 

  SchwarzschildIsotropic: Schwarzschild metric in isotropic coordinates, see Ref. [11].

• • 

  SchwarzschildTortoise: Schwarzschild metric in tortoise coordinates, see Ref. [11].

• • 

  Sultana-Dyer: A black hole in the Einstein–de Sitter universe by Sultana and Dyer [12].

• • 

  TaubNUT: see Ref. [13].

The Christoffel symbols and the natural local tetrads of these new metrics are given in the Catalogue of Spacetimes, Ref. [14].To study the behavior of geodesics, it is often useful to determine an effective potential like in classical mechanics. For several metrics, we followed the Euler–Lagrangian approach as described by Rindler [10] and implemented an effective potential for a specific situation. As an example, consider the Lagrangian for timelike geodesics in the ?=π/2 hypersurface in the Schwarzschild spacetime with α=1−2m/r. The Euler–Lagrangian equations lead to the energy balance equation with the effective potential V(r)=(r−2m)(r²+h²)/r³ and the constants of motion and . The constants of motion for a timelike geodesic that starts at (r=10m,φ=0) with initial direction ξ=π/4 with respect to the black hole direction and with initial velocity β=0.7 read k≈1.252 and h≈6.931. Then, from the energy balance equation we immediately obtain the radius of closest approach rmin≈5.927.Beside a standard Runge–Kutta fourth-order integrator and the integrators of the Gnu Scientific Library (GSL), we also implemented a standard Bulirsch–Stoer integrator.Running time: The test runs provided with the distribution require only a few seconds to run.References:

• [1] 

  T. Müller, New version announcement to the GeodesicViewer, http://cpc.cs.qub.ac.uk/summaries/AEFP_v2_0.html.

• [2] 

  P. Schneider, J. Ehlers, E. E. Falco, Gravitational Lenses, Springer, 1992.

• [3] 

  W. Rindler, Phys. Lett. A 245 (1998) 363.

• [4] 

  D. Kramer, Ann. Phys. 9 (2000) 331.

• [5] 

  F.J. Ernst, J. Math. Phys. 17 (1976) 54.

• [6] 

  S. Chandrasekhar, Proc. R. Soc. Lond. A 421 (1989) 227.

• [7] 

  H. Stephani, D. Kramer, M. MacCallum, C. Hoenselaers, E. Herlt, Exact Solutions of the Einstein Field Equations, Cambridge University Press, 2009.

• [8] 

  A.I. Janis, E.T. Newman, J. Winicour, Phys. Rev. Lett. 20 (1968) 878.

• [9] 

  K. Martel, E. Poisson, Am. J. Phys. 69 (2001) 476.

• [10] 

  W. Rindler, Relativity – Special, General, and Cosmology, Oxford University Press, Oxford, 2007.

• [11] 

  C.W. Misner, K.S. Thorne, J.A. Wheeler, Gravitation, W.H. Freeman, 1973.

• [12] 

  J. Sultana, C.C. Dyer, Gen. Relativ. Gravit. 37 (2005) 1349.

• [13] 

  D. Bini, C. Cherubini, Robert T. Jantzen, Class. Quantum Grav. 19 (2002) 5481.

• [14] 

  T. Muller, F. Grave, arXiv:0904.4184 [gr-qc].

     

The Construction of Discretely Conservative Finite Volume Schemes that Also Globally Conserve Energy or Entropy

This work revisits an idea that dates back to the early days of scientific computing, the energy method for stability analysis. It is shown that if the scalar non-linear conservation law

Preface: Volume 23, Issue 2

This volume contains the proceedings of the First International Workshop on Symbolic Model Checking (SMC'99), held in Trento, Italy, on July 6, 1999, as part of the Second Federated Logic Conference (FLoC'99).Symbolic model checking is a formal technique for the verification of finite-state concurrent systems. Symbolic model checkers (e.g. SMV, VIS) have been used to verify industrial systems, ranging from hardware to communication protocols to safety critical plants and procedures. Symbolic model checking is the core technique for several industrial verification tools, and is applied in technology transfer projects. The aim of the SMC'99 workshop is to bring together active developers and users of symbolic model checkers, compare state of the art model checking techniques (e.g. compositional reasoning, abstraction, partitioning), discuss experimental results and experience reports, and promising directions for future research.Nine contributions (out of twenty-two submissions) were selected for presentation by the program committee. The workshop program is completed by two keynote invited lectures, given by Ken McMillan (Cadence Labs, USA) on Compositional Reasoning and Abstraction, and Fabio Somenzi (University of Colorado, USA) on Symbolic State ExplorationThanks are due to a number of people who helped to organize and plan the workshop. Among this group are the Program Committee members:

Adnan Aziz	(University of Texas at Austin, USA)
Armin Biere	(Verysys)
Sergio Campos	(Federal University of Minas Gerais, Brazil)
Alessandro Cimatti	(IRST, Italy)
Edmund Clarke	(Carnegie Mellon University, USA)
Danny Geist	(IBM Haifa, Israel)
Fausto Giunchiglia	(IRST, Italy)
Orna Grumberg	(Technion, Israel)
Markus Kaltenbach	(Siemens, Germany)
Carl Pixley	(Motorola, USA)

Full-size table

The following people helped in the evaluation of the submissions: Yael Abarbanel-Vinov, Neta Aizenbud-Reshef, Shoham Ben-David, Doron Bustan, Jorge Cuellar, David Deharbe, Cindy Eisner, Ranan Fraer, Edelweis Garcez, Leonid Gluhovsky, Marcelo Glusman, Jae-Young Jang, Shmuel Katz, Sharon Keidar, Monika Maidl, Robi Malik, Anamaria Martins Moreira, Shiri Moran, Peter Päppinghaus, Marco Roveri, Peter Warkentin, Karen Yorav, Jun Yuan, Yunshan Zhu.We would like to thank IBM Haifa Research Laboratory for the financial support to SMC'99. Carola Dori, Morena Carli, Marco Roveri and Adolfo Villafiorita helped in several matters related to the local organization. Finally, we are grateful to Michael Mislove for his constat support during the preparation of this electronic volume.Alessandro Cimatti and Orna Grumberg, Guest Editors     

Preface: Volume 65, Issue 6

This volume contains the Proceedings of the First Workshop on the Theory and Practice of Timed Systems (TPTS'2002). The Workshop was held in Grenoble, France on April 6 and 7, 2002, as satellite event to ETAPS'2002.The study of time-dependent behavior is treated currently under different titles by different communities. Classical problems of manufacturing scheduling, for example, are considered as part of operation research and industrial engineering. Similar but different scheduling problems are encountered in the research on real-time operating systems. People who are interested in semantics, verification or performance analysis are working on models such as timed automata, timed Petri nets or max-plus algebra. Electrical engineers have to consider propagation delays in their circuits and designer of embedded controllers have to take into account the time it takes for the controller to compute its reaction after sampling the environment. The unifying theme underlying all these apparently different domains is that they treat systems whose behavior depends upon combinations of logical and temporal constraints, i.e. constraints on the distance between the occurrences of two events.The workshop goal is to promote the study of fundamental and practical aspects of timed systems. The three major axes of interest are listed below: Foundations and semantics: contributions to a better theoretical foundations for timed systems and timed formal languages as well as a comparison between different models used by different communities (timed automata, timed Petri nets, max-plus algebra, etc.).Algorithms and tools: new algorithms and data-structures for analyzing timed systems and resolving temporal constraints. are needed in order to push timing technology into the real world.Applications: adaptation and specialization of timing technology to the modeling and analysis of certain types of application domains in which timing plays an important role (real-time software, hardware circuits and problems of scheduling in manufacturing or telecommunication).The papers in this volume were reviewed by the program committee consisting of

Rajeev Alur	(U. Penn, Philadelphia)
Eugene Asarin	(Verimag, Grenoble)
Ahmed Bouajjani	(LIAFA, Paris)
Jordi Cortadella	(U. Catalunya, Barcelona)
Sebastian Engell	(U. of Dortmund)
Tom Henzinger	(U. California, Berkeley)
Bengt Jonsson	(U. of Uppsala)
Kim Larsen	(U. of Aalborg)
Insup Lee	(U. Penn, Philadelphia)
Oded Maler	(Verimag, Grenoble)
Chris Myers	(U. Utah, Salt Lake City)
Peter Niebert	(U. Provence, Marseille)
Antoine Petit	(ENS, Cachan)
Paul Petterson	(U. of Uppsala)
Amir Pnueli	(Weizmann Institute, Rehovot)
Alex Rabinovich	(U. of Tel-Aviv)
Jean-Francois Raskin	(Free University, Brussels)
Karem Sakallah	(U. Michigan, Ann Arbor)
Ken Stevens	(Intel, Hillsboro)
Wang Yi	(U. of Uppsala)
Sergio Yovine	(Verimag, Grenoble)

Full-size table

This volume will be published as volume 65, issue 6 in the series Electronic Notes in Theoretical Computer Science (ENTCS). This series is published electronically through the facilities of Elsevier Science B.V. and its auspices. The volumes in the ENTCS series can be accessed at the URLMarch 18, 2002 Eugene Asarin, Oded Maler, Sergio Yovine     

Continuous-time quantum Monte Carlo impurity solvers

Continuous-time quantum Monte Carlo impurity solvers are algorithms that sample the partition function of an impurity model using diagrammatic Monte Carlo techniques. The present paper describes codes that implement the interaction expansion algorithm originally developed by Rubtsov, Savkin, and Lichtenstein, as well as the hybridization expansion method developed by Werner, Millis, Troyer, et al. These impurity solvers are part of the ALPS-DMFT application package and are accompanied by an implementation of dynamical mean-field self-consistency equations for (single orbital single site) dynamical mean-field problems with arbitrary densities of states.

Program summary

Program title: dmftCatalogue identifier: AEIL_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AEIL_v1_0.htmlProgram obtainable from: CPC Program Library, Queen's University, Belfast, N. IrelandLicensing provisions: ALPS LIBRARY LICENSE version 1.1No. of lines in distributed program, including test data, etc.: 899 806No. of bytes in distributed program, including test data, etc.: 32 153 916Distribution format: tar.gzProgramming language: C++Operating system: The ALPS libraries have been tested on the following platforms and compilers:

• • 

  Linux with GNU Compiler Collection (g++ version 3.1 and higher), and Intel C++ Compiler (icc version 7.0 and higher)

• • 

  MacOS X with GNU Compiler (g++ Apple-version 3.1, 3.3 and 4.0)

• • 

  IBM AIX with Visual Age C++ (xlC version 6.0) and GNU (g++ version 3.1 and higher) compilers

• • 

  Compaq Tru64 UNIX with Compq C++ Compiler (cxx)

• • 

  SGI IRIX with MIPSpro C++ Compiler (CC)

• • 

  HP-UX with HP C++ Compiler (aCC)

• • 

  Windows with Cygwin or coLinux platforms and GNU Compiler Collection (g++ version 3.1 and higher)

RAM: 10 MB–1 GBClassification: 7.3External routines: ALPS [1], BLAS/LAPACK, HDF5Nature of problem: (See [2].) Quantum impurity models describe an atom or molecule embedded in a host material with which it can exchange electrons. They are basic to nanoscience as representations of quantum dots and molecular conductors and play an increasingly important role in the theory of “correlated electron” materials as auxiliary problems whose solution gives the “dynamical mean field” approximation to the self-energy and local correlation functions.Solution method: Quantum impurity models require a method of solution which provides access to both high and low energy scales and is effective for wide classes of physically realistic models. The continuous-time quantum Monte Carlo algorithms for which we present implementations here meet this challenge. Continuous-time quantum impurity methods are based on partition function expansions of quantum impurity models that are stochastically sampled to all orders using diagrammatic quantum Monte Carlo techniques. For a review of quantum impurity models and their applications and of continuous-time quantum Monte Carlo methods for impurity models we refer the reader to [2].Additional comments: Use of dmft requires citation of this paper. Use of any ALPS program requires citation of the ALPS [1] paper.Running time: 60 s–8 h per iteration.References:

• [1] 

  A. Albuquerque, F. Alet, P. Corboz, et al., J. Magn. Magn. Mater. 310 (2007) 1187.

• [2] 

  http://arxiv.org/abs/1012.4474, Rev. Mod. Phys., in press.